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