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 - dzienna produkcja wyrobu A [szt.]

1

x - dzienna produkcja wyrobu B [szt.]

2

2. Funkcja celu: (wartość produkcji w cenach zbytu) F( x) = F( x , x ,) = 3 x + 4 x 1

2

1

2

→

max

[$]

3. Ograniczenia: (warunki okreś lają ce zbiór planów dopuszczalnych) (maszyny)

x + 2 x

1

2 ≤ 500

[min]

(surowiec)

x + x

1

2 ≤ 350

[kg]

(min. poziom zysku) 2 x + x

1

2 ≥ 600

[$]

4. Warunki brzegowe: (warunki dotyczą ce zmiennych decyzyjnych) x

, x ∈ C

1 ≥ 0

[szt.]

x1 2

x2 ≥ 0

[szt.]

1

Postać ogólna modelu decyzyjnego (1)

1. Lista n zmiennych decyzyjnych:

x – zmienna decyzyjna nr 1

[j.m.]

1

x – zmienna decyzyjna nr 2

[j.m.]

2

...

x – zmienna decyzyjna nr n

[j.m.]

n

2. Funkcja celu:

F( x) = F( x , x ,…, x ) = c x + c x + … + c x 1

2

n

1 1

2 2

n n

→

max (lub min) [j.m.]

Postać ogólna modelu decyzyjnego (2)

3. Ograniczenia:

(ograniczenie nr 1)

a x + a x + … + a x

[j.m.]

11 1

12 2

1n n

≤ b1

.

.

.

.

.

.

(ograniczenie nr k)

a x + a x + … + a x

= b

[j.m.]

k1 1

k2 2

kn n

k

.

.

.

.

.

.

(ograniczenie nr m)

a

x + a

x + … + a

x

[j.m.]

m1 1

m2 2

mn n ≥ bm

4. Warunki brzegowe:

x1 ≥ 0 x2 ≥ 0 …

xn ≥ 0

Ilustracja graficzna zbioru decyzji dopuszczalnych

x2

600

min. zysk

400

surowiec

200

maszyny

x

200

400

600

x1

2

Rozwiązanie optymalne

1. Formalny zapis decyzji optymalnej:

x opt = 250

x opt = 100

F( x opt; x opt) = 1150

1

2

1

2

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, a nawet występuje nadwyŜka 550 $

Poszukiwanie rozwiązania optymalnego

•

metoda graficzna (2 zmienne decyzyjne)

•

metoda simpleks (dowolna liczba zmiennych decyzyjnych) Metoda graficzna

x2

F → max

300

G[150,200]

w: F = 1150

w: F = 1050

200

rozwiązanie

w: F = 900

optymalne

A = (300,0)

100

C

B = (350,0)

C = (250,100)

A

B

100

200

300

x1

3

Klasyczna metoda simpleks ( informacje ogólne, idea) (1) 1. Postać modelu:

F( x) = F( x , x ,) = 3 x + 4 x 1

2

1

2

→

max

x + 2 x

1

2 ≤ 500

(maszyny)

x + x

1

2 ≤ 350

(surowiec)

2 x + x

1

2 ≥ 600

(min. poziom zysku)

x

, x ∈ C

1 ≥ 0 x2 ≥ 0

x1 2

2. Postać kanoniczna modelu:

3 x + 4 x + 0 s + 0 s + 0 s – M t 1

2

→

max

1

2

3

3

x + 2 x + s

= 500

(maszyny)

1

2

1

x + x

+ s

= 350

(surowiec)

1

2

2

2 x + x

- s + t = 600

(min. poziom zysku)

1

2

3

3

x1 ≥ 0 x2 ≥ 0 s1 ≥ 0 s2 ≥ 0 s3 ≥ 0 t3 ≥ 0

Klasyczna metoda simpleks ( informacje ogólne, idea) (2) 3. Interpretacja zmiennych swobodnych:

s – niewykorzystany fundusz czasu pracy maszyn (limit 500 minut) 1

( ang. slack – luz)

s – niewykorzystany zasób surowca (limit 350 kg) 2

( ang. slack – luz)

s – przekroczenie minimalnej kwoty zysku (Ŝądane minimum 600 $) 3

( ang. surplus – nadwyŜ ka)

t – zmienna sztuczna – zmienna pomocnicza, nie ma interpretacji 3

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

4

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 – wycena dualna

j

JeŜeli w j-tym ograniczeniu zadania programowania liniowego wyraz wolny b wzrośnie (spadnie) o jednostkę, to optymalna wartość funkcji j

celu f(xopt) wzrośnie o y jednostek, tj. do poziomu f(xopt) + y .

j

j

5

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 cj

prawa strona ograniczenia bj

Analiza wraŜliwości (2)

Konsekwencje zmian jednego wybranego współczynnika c w ramach j

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 w ramach przedziału dopuszczalnych zmian: j

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

6

Warianty rozwiązań zadania PL (1)

x2

zadanie sprzeczne

X = ∅

x1

Warianty rozwiązań zadania PL (2)

x2

brak skończonego

G

rozwiązanie zadania PL

X

x1

Warianty rozwiązań zadania PL (3)

x2

jednoznaczne optymalne

rozwiązanie zadania PL

A

X

G

x1

7

Warianty rozwiązań zadania PL (4)

x2

niejednoznaczne optymalne

rozwiązanie zadania PL

X

G

x1

8