Liniowe modele decyzyjne

Sytuacja decyzyjna - przykład

Mały zakład wytwarza dwa produkty A i B, których ceny zbytu 

wynosz

ą

 odpowiednio 3 $/szt. oraz  4 $/szt.

Nale

ż

y opracowa

ć

 dzienny plan produkcji zakładu tak, aby 

warto

ść

 produkcji liczona w cenach zbytu była mo

ż

liwie najwi

ę

ksza.

Produkcja jest limitowana głównie przez dwa czynniki: dost

ę

pny 

czas pracy maszyn i surowiec podstawowy.

Dzienny limit czasu pracy maszyn wynosi 500 minut. Sztuka 

wyrobu A wymaga 1 minuty czasu pracy maszyn, natomiast sztuka 
wyrobu B - 2 minut. Na wyprodukowanie sztuki wyrobu A zu

ż

ywa si

ę

 1 

kg surowca specjalnego. Równie

ż

 sztuka wyrobu B wymaga 1 kg tego 

surowca.

Umowy z producentem surowca podstawowego wskazuj

ą

, 

ż

e 

ka

ż

dego dnia zakład b

ę

dzie miał do dyspozycji 350 kg tego surowca 

(bezpieczny poziom).

Zakład jest zainteresowany takim programem dziennej 

produkcji, przy którym osi

ą

gał b

ę

dzie zysk minimum 600 $. Jednostkowy 

zysk ze sztuki wyrobu A wynosi 2 $/szt., a ze sztuki wyrobu B – 1 $/szt. 

Model decyzyjny

1. Lista zmiennych decyzyjnych:

x

1

- dzienna produkcja wyrobu A [szt.]

x

2

- dzienna produkcja wyrobu B [szt.]

2. Funkcja celu: (warto

ść

 produkcji w cenach zbytu)

F(x) = F(x

1

,x

2

,) = 3x

1

+ 4x

2

→

max

[$]

3. Ograniczenia: (warunki okre

ś

laj

ą

ce zbiór planów dopuszczalnych)

(maszyny)

x

1

+ 2x

2

≤

 500

[min]

(surowiec)

x

1

+   x

2

≤

 350

[kg]

(min. poziom zysku)     2x

1

+   x

2   

≥

600

[$]

4. Warunki brzegowe: (warunki dotycz

ą

ce zmiennych decyzyjnych)

x

1

≥

 0

[szt.]

x

1

, x

2

∈

C

x

2

≥

0

[szt.]

Posta

ć

 ogólna modelu decyzyjnego (1)

1. Lista n zmiennych decyzyjnych:

x

1

– zmienna decyzyjna nr 1

[j.m.]

x

2

– zmienna decyzyjna nr 2

[j.m.]

.

.

.
x

n

– zmienna decyzyjna nr n

[j.m.]

2. Funkcja celu:

F(x) = F(x

1

,x

2

,…, x

n

) = c

1

x

1

+ c

2

x

2

+ … + c

n

x

n

→

max (lub min)    

[j.m.]

Posta

ć

 ogólna modelu decyzyjnego (2)

3. Ograniczenia:

(ograniczenie nr 1)

a

11

x

1

+ a

12

x

2

+ … + a

1n

x

n

≤

 b

1

[j.m.]

. 

.

. 

.

. 

.

(ograniczenie nr k)

a

k1

x

1

+ a

k2

x

2

+ … + a

kn

x

n

= b

k

[j.m.]

. 

.

. 

.

. 

.

(ograniczenie nr m)

a

m1

x

1

+ a

m2

x

2

+ … + a

mn

x

n

≥

b

m

[j.m.]

4. Warunki brzegowe:

x

1

≥

 0     x

2

≥

 0     …     x

n

≥

 0

Ilustracja graficzna zbioru decyzji dopuszczalnych

x

1

x

2

200

400

600

200

400

600

maszyny

surowiec

min.  zysk

x

Rozwi

ą

zanie optymalne

1. Formalny zapis decyzji optymalnej:

x

1

opt

= 250

x

2

opt

= 100

F(x

1

opt

; x

2

opt

) = 1150

2. Najlepsza dzienna decyzja produkcyjna:

produkowa

ć

 250 szt. wyrobu A

produkowa

ć

 100 szt. wyrobu A

maksymalna warto

ść

 produkcji wyniesie 1150 $

fundusz czasu pracy maszyn (max. 500 minut) nie zostanie w pełni 
wykorzystany (codziennie wolne 50 minut)

zasób surowca (350 kg) b

ę

dzie wykorzystany w pełni

minimalny 

żą

dany poziom zysku został osi

ą

gni

ę

ty dokładnie na 

żą

danym poziomie

Poszukiwanie rozwi

ą

zania optymalnego

•

metoda graficzna (2 zmienne decyzyjne)

•

metoda simpleks (dowolna liczba zmiennych decyzyjnych)

Metoda graficzna

x

1

x

2

100

200

300

100

200

300

C

B

A

A = (300,0)
B = (350,0)
C = (250,100)

w: F = 1150

w: F = 1050

w: F = 900

G[150,200]

rozwi

ą

zanie 

optymalne

F

→

 max

Klasyczna metoda simpleks (informacje ogólne, idea) (1)

1. Posta

ć

 modelu:

F(x) = F(x

1

,x

2

,) = 3x

1

+ 4x

2

→

max

x

1

+ 2x

2

≤

 500

(maszyny)

x

1

+   x

2

≤

 350

(surowiec)

2x

1

+   x

2

≥

 600

(min. poziom zysku)

x

1

≥

 0 x

2

≥

 0

x

1

, x

2

∈

C

2. Posta

ć

 kanoniczna modelu:

3x

1

+ 4x

2

+ 0s

1

+ 0s

2

+ 0s

3

– Mt

3

→

max

x

1

+ 2x

2

+ s

1

= 500

(maszyny)

x

1

+   x

2

+ s

2

= 350

(surowiec)

2x

1

+   x

2

- s

3

+ t

3

= 600

(min. poziom zysku)

x

1

≥

 0

x

2

≥

 0    s

1

≥

 0    s

2

≥

 0    s

3

≥

 0    t

3

≥

 0

Klasyczna metoda simpleks (informacje ogólne, idea) (2)

3. Interpretacja zmiennych swobodnych:

s

1

– niewykorzystany fundusz czasu pracy maszyn (limit 500 minut)

(ang. slack – luz)

s

2

– niewykorzystany zasób surowca (limit 350 kg)

(ang. slack – luz)

s

3

– przekroczenie minimalnej kwoty zysku (

żą

dane minimum 600 $)

(ang. surplus – nadwy

ż

ka)

t

3

– zmienna sztuczna – zmienna pomocnicza, nie ma interpretacji

ekonomicznej
(ang. artificial – sztuczny)

Metoda simpleks (program WinSTORM) (1)

PROBLEM DATA IN EQUATION STYLE

Maximize

3 X1 + 4 X2

Subject to

MASZYNY   

1 X1 + 2 X2 <= 500

SUROWIEC  

1 X1 + 1 X2 <= 350

MIN. ZYSK 

2 X1 + 1 X2 >= 600

0 <= X1 <= Infinity 
0 <= X2 <= Infinity 

Metoda simpleks (program WinSTORM) (2)

OPTIMAL SOLUTION - DETAILED REPORT

Variable          

Value         Cost    

Red. cost 

Status

1   X1             

250.0000       3.0000       0.0000  

Basic

2   X2             

100.0000       4.0000       0.0000 

Basic

Objective Function Value = 1150

Slack Variables
3   MASZYNY

50.0000       0.0000       0.0000  

Basic

4   SUROWIEC

0.0000       0.0000      -5.0000  

Lower

5   MIN. ZYSK        0.0000       0.0000      -1.0000  

Lower

Constraint   Type  

RHS

Slack   

Shadow price

1  MASZYNY      <=    

500.0000

50.0000         0.0000

2  SUROWIEC    <=   

350.0000

0.0000         5.0000

3  MIN. ZYSK     >=     600.0000       

0.0000        -1.0000

Metoda simpleks (program WinSTORM) (3)

SENSITIVITY ANALYSIS OF COST COEFFICIENTS

Current  

Allowable    

Allowable

Variable

Coeff.     

Minimum 

Maximum

1    X1       

3.0000

- Infinity 

4.0000

2    X2    

4.0000       

3.0000    

Infinity 

SENSITIVITY ANALYSIS OF RIGHT-HAND SIDE VALUES

Current    

Allowable     Allowable

Constraint  

Type      

Value      

Minimum       Maximum

1  MASZYNY

<=          500.0000        450.0000        Infinity

2  SUROWIEC

<=          350.0000        300.0000        366.6667

3  MIN. ZYSK

>=          600.0000        550.0000        700.0000

Wycena dualna

Wyceny dualne pozwalaj

ą

 okre

ś

li

ć

 wielko

ść

 oraz kierunek zmian 

uzyskanej optymalnej warto

ś

ci funkcji celu na skutek zmiany warto

ś

ci 

prawych stron ogranicze

ń

 (wyrazów wolnych).

y

j

– wycena dualna

Je

ż

eli w j-tym ograniczeniu zadania programowania liniowego wyraz 

wolny b

j

wzro

ś

nie (spadnie) o jednostk

ę

, to optymalna warto

ść

 funkcji 

celu f(x

opt

) wzro

ś

nie o y

j

jednostek, tj. do poziomu  f(x

opt

) + y

j

.

Analiza wra

ż

liwo

ś

ci (1)

Czy, a je

ż

eli tak to na ile zmieni si

ę

 uzyskane rozwi

ą

zanie optymalne, 

je

ż

eli zmieni si

ę

 warto

ść

 jednego wybranego parametru 

rozwi

ą

zywanego zadania programowania liniowego?”

parametr w funkcji celu c

j

prawa strona ograniczenia b

j

Analiza wra

ż

liwo

ś

ci (2)

Konsekwencje zmian jednego wybranego współczynnika c

j

w ramach 

przedziału dopuszczalnych zmian:

rozwi

ą

zanie optymalne zadania nie ulegnie zmianie

zmieni si

ę

 optymalna warto

ść

 funkcji celu

zmieni si

ę

 wycena dualna

Analiza wra

ż

liwo

ś

ci (3)

Konsekwencje zmian jednego wybranego wyrazu wolnego 
ogranicze

ń

 b

j

w ramach przedziału dopuszczalnych zmian:

rozwi

ą

zanie optymalne zadania ulegnie zmianie, lecz tylko w 

zakresie zmiennych bazowych (status: basic)

zmieni si

ę

 optymalna warto

ść

 funkcji celu

wycena dualna pozostanie bez zmian

Warianty rozwi

ą

za

ń

 zadania PL (1)

x

1

x

2

X = 

∅

∅

∅

∅

zadanie sprzeczne

Warianty rozwi

ą

za

ń

 zadania PL (2)

x

1

x

2

brak sko

ń

czonego 

rozwi

ą

zanie zadania PL

G

X

Warianty rozwi

ą

za

ń

 zadania PL (3)

x

1

x

2

jednoznaczne optymalne 
rozwi

ą

zanie zadania PL

G

X

A

Warianty rozwi

ą

za

ń

 zadania PL (4)

x

1

x

2

niejednoznaczne optymalne 
rozwi

ą

zanie zadania PL

G

X