Liniowe modele decyzyjne
Model decyzyjny (1)
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 specjalnego
surowca. 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 (2)
1. Lista zmiennych decyzyjnych:
x1 - dzienna produkcja wyrobu A [szt.]
x2 - dzienna produkcja wyrobu B [szt.]
2. Funkcja celu: (wartość produkcji w cenach zbytu)
F(x) = F(x1,x2,) = 3x1 + 4x2 max [$]
3. Ograniczenia: (warunki określające zbiór planów dopuszczalnych)
(maszyny) x1 + 2x2 d" 500 [min]
(surowiec) x1 + x2 d" 350 [kg]
(min. poziom zysku) 2x1 + x2 e" 600 [$]
4. Warunki brzegowe: (warunki dotyczące zmiennych decyzyjnych)
x1 e" 0 [szt.] x1, x2 " C
x2 e" 0 [szt.]
1
Postać ogólna modelu decyzyjnego (1)
1. Lista n zmiennych decyzyjnych:
x1  zmienna decyzyjna nr 1 [j.m.]
x2  zmienna decyzyjna nr 2 [j.m.]
.
.
.
xn  zmienna decyzyjna nr n [j.m.]
2. Funkcja celu:
F(x) = F(x1,x2,& , xn) = c1x1 + c2x2 + & + cnxn max (lub min) [j.m.]
Postać ogólna modelu decyzyjnego (2)
3. Ograniczenia:
(ograniczenie nr 1) a11x1 + a12x2 + & + a1nxn d" b1 [j.m.]
. .
. .
. .
(ograniczenie nr k) ak1x1 + ak2x2 + & + aknxn = bk [j.m.]
. .
. .
. .
(ograniczenie nr m) am1x1 + am2x2 + & + amnxn e" bm [j.m.]
4. Warunki brzegowe:
x1 e" 0 x2 e" 0 & xn e" 0
Ilustracja graficzna zbioru decyzji dopuszczalnych
x2
600
min. zysk
400
surowiec
200
maszyny
x
200 400 600 x1
2
Poszukiwanie rozwiązania optymalnego
" metoda graficzna (2 zmienne decyzyjne)
" metoda simpleks (dowolna liczba zmiennych decyzyjnych)
Metoda graficzna
x2
300
G(150,200)
w: f = 1150
w: f = 1050
200
rozwiązanie
w: f = 900
optymalne
C A = (300,0)
100
B = (350,0)
C = (250,100)
A B
100 200 300 x1
Rozwiązanie optymalne
1. Formalny zapis decyzji optymalnej:
x1opt = 250 x2opt = 100 F(x1opt; x2opt) = 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
3
Klasyczna metoda simpleks (informacje ogólne, idea) (1)
1. Postać modelu:
F(x) = F(x1,x2,) = 3x1 + 4x2 max
x1 + 2x2 d" 500 (maszyny)
x1 + x2 d" 350 (surowiec)
2x1 + x2 e" 600 (min. poziom zysku)
x1 e" 0 x2 e" 0
2. Postać kanoniczna modelu:
3x1 + 4x2 + 0s1 + 0s2 + 0s3  Mt3 max
x1 + 2x2 + s1 = 500 (maszyny)
x1 + x2 + s2 = 350 (surowiec)
2x1 + x2 - s3 + t3 = 600 (min. poziom zysku)
x1 e" 0 x2 e" 0 s1 e" 0 s2 e" 0 s3 e" 0 t3 e" 0
Klasyczna metoda simpleks (informacje ogólne, idea) (2)
3. Interpretacja zmiennych swobodnych:
s1  niewykorzystany fundusz czasu pracy maszyn (limit 500 minut)
(ang. slack  luz)
s2  niewykorzystany zasób surowca (limit 350 kg)
(ang. slack  luz)
s3  przekroczenie minimalnej kwoty zysku (\
ądane minimum 600 $)
(ang. surplus  nadwy\
ka)
t3  zmienna sztuczna  zmienna pomocnicza, nie ma interpretacji
ekonomicznej
(ang. artificial  sztuczny)
Klasyczna metoda simpleks (program WinSTORM) (3)
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
Klasyczna metoda simpleks (program WinSTORM) (4)
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
Klasyczna metoda simpleks (program WinSTORM) (5)
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
Rozwiązanie (1)
Zmienna
Rozwiązanie Min. cj cj Max. cj Status
decyzyjna
x1 250  " 3 4 B
x2 100 3 4 " B
Wartość funkcji celu 1150
Zmienna Wycena
Ograniczenie Min. RHS RHS Max. RHS
swobodna dualna
Maszyny 50 450 500 " 0
Surowiec 0 300 350 366,67 5
Min. zysk 0 550 600 700 -1
5
Rozwiązanie  wycena dualna (2)
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).
yj  wycena dualna
Je\
eli w j-tym ograniczeniu zadania programowania liniowego wyraz wolny bj
wzrośnie (spadnie) o jednostkę, to optymalna wartość funkcji celu f(xopt)
wzrośnie o yj jednostek, tj. do poziomu f(xopt) + yj.
Rozwiązanie  analiza wra\
liwości (3)
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 RHSi
Rozwiązanie  analiza wra\
liwości (4)
Konsekwencje zmian jednego wybranego współczynnika cj w ramach
przedziału dopuszczalnych zmian:
rozwiązanie optymalne zadania nie ulegnie zmianie
zmieni się optymalna wartość funkcji celu
zmieni się wycena dualna
6
Rozwiązanie  analiza wra\
liwości (5)
c2 = 10 " (3,")
Zmienna
Rozwiązanie Min. cj cj Max. cj Status
decyzyjna
x1 250  " 3 10 B
x2 100 3 10 " B
Wartość funkcji celu 1750
Zmienna Wycena
Ograniczenie Min. RHS RHS Max. RHS
swobodna dualna
Maszyny 50 450 500 " 0
Surowiec 0 300 350 366,67 17
Min. zysk 0 550 600 700 -7
Rozwiązanie  analiza wra\
liwości (6)
c1 = 5 " ( ",4)
Zmienna
Rozwiązanie Min. cj cj Max. cj Status
decyzyjna
x1 350 4 5 " B
x2 0  " 4 5 B
Wartość funkcji celu 1750
Zmienna Wycena
Ograniczenie Min. RHS RHS Max. RHS
swobodna dualna
Maszyny 150 350 500 " 0
Surowiec 0 300 350 500 5
Min. zysk 100  " 600 700 0
Rozwiązanie  analiza wra\
liwości (7)
Konsekwencje zmian jednego wybranego wyrazu wolnego ograniczeń RHSj
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
7
Rozwiązanie  analiza wra\
liwości (8)
RHS3 = 650 "(550,700)
Zmienna
Rozwiązanie Min. cj cj Max. cj Status
decyzyjna
x1 300  " 3 4 B
x2 50 3 4 " B
Wartość funkcji celu 1100
Zmienna Wycena
Ograniczenie Min. RHS RHS Max. RHS
swobodna dualna
Maszyny 100 400 500 " 0
Surowiec 0 325 350 383,33 5
Min. zysk 0 550 650 700 -1
Rozwiązanie  analiza wra\
liwości (9)
RHS1 = 300 "(450, ")
Zmienna
Rozwiązanie Min. cj cj Max. cj Status
decyzyjna
x1 300 2 3 " B
x2 0  " 4 6 LB
Wartość funkcji celu 900
Zmienna Wycena
Ograniczenie Min. RHS RHS Max. RHS
swobodna dualna
Maszyny 0 300 300 300 3
Surowiec 50 350 350 " 0
Min. Zysk 0 600 600 600 0
Warianty rozwiązań zadania PL (1)
x2
zadanie sprzeczne
X = "
"
"
"
x1
8
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
Warianty rozwiązań zadania PL (4)
x2
niejednoznaczne optymalne
rozwiązanie zadania PL
X
G
x1
9
Problem decyzyjny  przykład
Podstawowy asortyment produkcji pewnego zakładu stanowią trzy
produkty: A, B i C. Ze struktury otrzymanych zamówień wynika, \
e wyrobu B
nale\
y wyprodukować przynajmniej dwa razy tyle co wyrobu A. Wiadomo
równie\
, \
e jednostkowy koszt wytworzenia wyrobu A wynosi 30 zł, wyrobu B
50 zł zaś wyrobu C 60 zł. A
ączny koszt wytworzenia wyrobów nie powinien
okazać się wy\
szy ni\
100 000 zł.
Spośród u\
ywanych w produkcji surowców dwa: S1 i S2 mają
kluczowe znaczenie dla procesu technologicznego. W związku z tym nale\
y
wziąć w ich przypadku pod uwagę limity zapasów, które wynoszą
odpowiednio: 150 ton i 150 hl. Na wyprodukowanie jednej sztuki wyrobu A
potrzeba 3 kg surowca S1 oraz 3 litry surowca S2. Wytworzenie jednej sztuki
wyrobu B wymaga 2 kg S1 i 1 litra S2. Z kolei wytworzenie jednej sztuki
wyrobu C wymaga 1 kg S1 i 3 litrów S2. Zakładamy, \
e cała produkcja
znajdzie nabywców. Zbudować zadanie optymalizacyjne ustalające wielkość
produkcji maksymalizującą wysokość osiąganego zysku je\
eli jednostkowy
zysk osiągany przy produkcji wyrobu A wynosi 80 zł, przy produkcji B 90 zł, a
przy produkcji C 85 zł.
10