Programowanie liniowe

Schemat postępowania w badaniach operacyjnych

decydent

sytuacja decyzyjna

sytuacja decyzyjna
decyzje

decyzje dopuszczalne

niedopuszczalne

kryterium wyboru

zadanie decyzyjne

zadanie decyzyjne
zmienne decyzyjne

warunki ograniczające
zbiór rozwiązań dopuszczalnych
(ZRD)

funkcja celu (kryterium)

Model matematyczny

Model matematyczny

Rozwiązanie zadania

Rozwiązanie zadania

Analiza wrażliwości

Analiza wrażliwości

Sytuacja decyzyjna

Sytuacja decyzyjna

Interpretacja wyników

Interpretacja wyników

Przykład 1. Ustalanie struktury produkcji

Warsztat produkuje dwa wyroby A i B, do produkcji których potrzebne są stal (1 kg na wyrób A i 4
kg na wyrób B) oraz siła robocza (odpowiednio 2 rh i 3 rh). Warsztat dziennie może wykorzystać
14 kg stali, i 13 h pracy zatrudnionych pracowników. Ustalić plan produkcji maksymalizujący
łączny przychód ze sprzedaży, przy założeniu, że cena wyrobu A wynosi 1000 zł/szt, a wyrobu B
2000 zł/szt.

Tabela parametrów

Wyszczególnienie

Jedn.

Zapas

1

Zmienne

Model matematyczny

ZPL

- zadanie programowania liniowego

ZPL













=













=













=













=

x

A

b

c

f(x) = c

1

x

1

+ c

2

x

2

→ max

a

11

x

1

+ a

12

x

2

≤ b

1

a

21

x

1

+ a

22

x

2

≤ b

2

x

1

, x

2

≥ 0

Postać macierzowa ZPL

f(x) = c

T

x

→ max

A x

≤ b

x

≥ 0

x - wektor zmiennych
c - wektor współczynników funkcji celu (wag)
A - macierz współczynników (kombinacji równoważnej)
b - wektor wyrazów wolnych (prawa strona - RHS)

Rozwiązanie zadania – metoda geometryczna

2

8

7

6

5

4

3

2

1

0

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Interpretacja wyników

Analiza wrażliwości

Co się zmieni w rozwiązaniu, jeżeli
zmienimy cały wektor parametrów?

Jak może się zmieniać wybrany parametr,
przy niezmienionych pozostałych parametrach,
aby rozwiązanie optymalne pozostało stabilne.

Analiza

wrażliwości

Analiza

Analiza

wrażliwości

wrażliwości

Analiza

wektorowa

Analiza

parametryczna

3

Przykład: Co się stanie, jeżeli cena zarówno wyrobu A, jak i B wzrośnie o 1 tys. zł?

6

5

4

3

2

1

0

1 2 3 4 5 6

x

2

x

1

(2)

(1)

C

C

D

D

Przykład: W jakich granicach może zmieniać się cena wyrobu A, nie zmieniając rozwiązania
optymalnego?

6

5

4

3

2

1

0

1 2 3 4 5 6

x

2

x

1

(2)

(1)

C

C

D

D

4

c

1

= 1

Dopuszczalny spadek = 1/2 Dopuszczalny wzrost = 1/3

c

2

= 2

Dopuszczalny spadek = 1/2 Dopuszczalny wzrost = 2

Przykład W jakich granicach może zmieniać się zapas stali, by zachować stabilność rozwiązania?

6

5

4

3

2

1

0

1 2 3 4 5 6

x

2

x

1

(2)

(1)

C

C

D

D

6

5

4

3

2

1

0

1 2 3 4 5 6

x

2

x

1

(2)

(1)

C

C

D

D

5

b

1

= 1

Dopuszczalny spadek = 7 1/2 Dopuszczalny wzrost = 3 1/3

b

2

= 2

Dopuszczalny spadek = 2 1/2 Dopuszczalny wzrost = 15

Wrażliwość na zmiany wartości parametrów

Nie

Tak

Gradient

Rozwiązanie

ogólne

Rozwiązanie

szczegółowe

Badanie stabilności

Tak

Tak

Wartość funkcji celu

Tak

Nie

Współrzędne punktu
optymalnego

Tak

Nie

ZRD

b

b

c

c

Nie

Tak

Gradient

Rozwiązanie

ogólne

Rozwiązanie

szczegółowe

Badanie stabilności

Tak

Tak

Wartość funkcji celu

Tak

Nie

Współrzędne punktu
optymalnego

Tak

Nie

ZRD

b

b

c

c

Zadanie dualne

ZP

- zadanie prymalne

ZD

- zadanie dualne

ZP

ZD

f(x) = c

T

x

→

max

A x

≤

b

x

≥

0

g(y) = b

T

y

→

min

yA

T

≥

c

y

i

≥

0

y

i

≤

0

y

i

∈R

∑

=

≤

∀

n

j

i

j

ij

b

x

a

i

dla

1

:

∑

=

≥

∀

n

j

i

j

ij

b

x

a

i

dla

1

:

∑

=

=

∀

n

j

i

j

ij

b

x

a

i

dla

1

:

6

Typy rozwiązań ZPL

Rozwiązanie ZPL

Istnieje

rozwiązanie

optymalne

Brak

rozwiązania

optymalnego

Układ

sprzeczny

Niemożność wskazania

rozwiązania

optymalnego

Jedno

Wiele

x

2

x

1

f(x)-> max

x

2

x

1

(2)

(1)

f(x)-> max

x

2

x

1

∅

∈

ZRD

x

2

x

1

f(x)-> max

7

Rozwiązanie zadania w arkuszu Excel

A

B

x

2

3

c

1

2

8

(1)

1

4

14

1

(2)

2

3

13

1

A

B

x

0

0

c

1

2

8

(1)

1

4

14

14

(2)

2

3

13

13

4
3

Stan wyjściowy

Rozwiązanie końcowe

Microsoft Excel 8.0 Raport wyników

Komórka celu (Maks)

Komórka NazwaWartość początkow

Wartość końcowa

$D$4

c

0

8

Komórki decyzyjne

Komórka NazwaWartość początkow

Wartość końcowa

$B$3

x A

0

2

$C$3

x B

0

3

Warunki ograniczające

Komórka Nazwa Wartość komórki

formuła

Status

Luz

$D$5

(1)

14 $D$5<=$E$5 Wiążące

0

$D$6

(2)

13 $D$6<=$E$6 Wiążące

0

$B$3

x A

2 $B$3>=0

Nie wiążące

2

$C$3

x B

3 $C$3>=0

Nie wiążące

3

Microsoft Excel 8.0 Raport wrażliwości

Komórki decyzyjne

Wartość

Przyrost

Współczynnik Dopuszczalny Dopuszczalny

Komórka Nazwa

końcowa

krańcowy

funkcji celu

wzrost

spadek

$B$3

x A

2

0

1

0,3333333

0,5

$C$3

x B

3

0

2

2

0,5

Warunki ograniczające

Wartość

Cena

Prawa strona

Dopuszczalny Dopuszczalny

Komórka Nazwa

końcowa

dualna

w. o.

wzrost

spadek

$D$5

(1)

14

0,2

14

3,3333333

7,5

$D$6

(2)

13

0,4

13

15

2,5

8

Przykład 2. Zagadnienie diety

Stwierdzono, że należy spożywać co najmniej 60 g białka i co najmniej 120 g węglowodanów. Ser
zawiera (w 100 g) po 2 gramy białka i węglowodanów. Z kolei w chlebie założono, że jest 1 gram
białka i 3 gramy węglowodanów. Ustalić najtańszą możliwą dietę, zakładając, że ser kosztuje 30
zł/kg, a chleb 20 zł/kg.

Literatura

Literatura

1. M.Anholcer, H.Gaspars, A.Owczrkowski Przykłady i zadania z badań operacyjnych i
ekonometrii AE Poznań’2003 (skrypt nr 140)
2. E.Ignasiak (red.) Badania operacyjne PWE’2000
3. B.Guzik (red.) Ekonometria i badania operacyjne. Zagadnienia podstawowe, (skrypt AE
Poznań)
4. B.Guzik (red.) Ekonometria i badania operacyjne. Uzupełnienia z badań operacyjnych, (skrypt
AE Poznań)
5. K.Kukuła (red.) Badania operacyjne w przykładach i zadaniach, PWN
6. T.Trzaskalik Wprowadzenie do badań operacyjnych z komputerem, PWE 2003

9