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:
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.]
x2 e" 0 [szt.]
Postać ogólna modelu decyzyjnego (1)
1. Lista n zmiennych decyzyjnych:
x1  zmienna decyzyjna nr 1
x2  zmienna decyzyjna nr 2
.
.
.
xn  zmienna decyzyjna nr n
2. Funkcja celu:
F(x) = F(x1,x2,& , xn) = c1x1 + c2x2 + & + cnxn max (lub min)
Postać ogólna modelu decyzyjnego (2)
3. Ograniczenia:
(ograniczenie nr 1) a11x1 + a12x2 + & + c1nxn d" b1
. .
. .
. .
(ograniczenie nr k) ak1x1 + ak2x2 + & + cknxn = bk
. .
. .
. .
(ograniczenie nr m) am1x1 + am2x2 + & + cmnxn e" bm
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
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, a nawet występuje
nadwy\
ka 550 $
Poszukiwanie rozwiązania optymalnego
" metoda graficzna (2 zmienne decyzyjne)
" metoda simpleks (dowolna liczba zmiennych decyzyjnych)
Ilustracja graficzna zbioru decyzji dopuszczalnych
x2
300
G(150,200)
w: f = 1150
w: f = 1050
200
rozwiązanie
w: f = 900
optymalne
A = (300,0)
C
100
B = (250,100)
C = (350,0)
A
B
100 200 300
x1
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)
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).
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.
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 cj 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ń bj 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)
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
X
G
x1
Warianty rozwiązań zadania PL (4)
x2
niejednoznaczne optymalne
rozwiązanie zadania PL
X
G
x1