BADANIA OPERACYJNE I TEORIE
OPTYMALIZACJI
Liniowe modele optymalizacyjne
Częśd 2
Rozwiązanie algebraiczne i analiza wrażliwości
Klasyczna metoda simpleks (1)
W celu rozwiÄ…zania zadania programowania liniowego algebraicznie,
metodą simpleks, dowolną postać zadania należy sprowadzić do
postaci kanonicznej. Do takiego przekształcenia wykorzystujemy
zmienne swobodne, które oznaczamy symbolem si , gdzie i to numer
ograniczenia.
Klasyczna metoda simpleks (2)
1. Wyjściowa postad 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 x1, x2 C
2. Postad kanoniczna modelu:
3x1 + 4x2 + 0s1 + 0s2 + 0s3  Mt3 max
x1 + 2x2 + s1 = 500 (maszyny)
x1 + x2 + s2 = 350 (surowiec)
2x1 + x2 - s3 = 600 (min. poziom zysku)
x1 e" 0 x2 e" 0 s1 e" 0 s2 e" 0 s3 e" 0
Klasyczna metoda simpleks (2)
Następnie sprawdzamy, czy w macierzy współczynników warunków
ograniczających znajduje się macierz jednostkowa, jeżeli nie to
tworzymy ją za pomocą zmiennych sztucznych, które oznaczamy
symbolem ti , gdzie i to numer ograniczenia. W analizowanym
przykładzie macierz współczynników warunków jest postaci:
1 2 1 0 0
A 1 1 0 1 0
2 1 0 0 1
W macierzy A nie występuje macierz jednostkowa.
Klasyczna metoda simpleks (3)
Do modelu wprowadzamy zmiennÄ… sztucznÄ… w trzecim warunku
ograniczajÄ…cym :
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 (4)
Interpretacja zmiennych pomocniczych:
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 (4)
Po takim przekształceniu macierz współczynników warunków
ograniczajÄ…cych jest postaci :
1 2 1 0 0 0
A 1 1 0 1 0 0
2 1 0 0 -1 1
Macierz jednostkowa istnieje. Możemy przystąpić do rozwiązywania
algebraicznego, które otrzymamy za pomocą programu WinSTORM.
Klasyczna 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
Klasyczna 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
Klasyczna metoda simpleks
Program WinStorm (4)
Rozwiązanie jest optymalne jednoznacznie jeżeli w kolumnie
Red. Cost zero występuje tylko w tych wierszach, w których w
kolumnie Status występuje określenie Basic.
Rozwiązanie jest optymalne niejednoznacznie jeżeli w kolumnie
Red. Cost zero występuje w przynajmniej jednym wierszu, w którym w
kolumnie Status nie występuje określenie Basic.
Klasyczna 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
Klasyczna metoda simpleks
Wyceny dualne
Wyceny dualne ( shadow price) pozwalają określid wielkośd oraz kierunek
zmian uzyskanej optymalnej wartości funkcji celu na skutek zmiany wartości
prawych stron ograniczeo (wyrazów wolnych).
yi  wycena dualna , gdzie i to numer ograniczenia.
Jeżeli w i-tym ograniczeniu zadania programowania liniowego wyraz wolny
bi wzrośnie (spadnie) o jednostkę, to optymalna wartośd funkcji celu f(xopt)
wzrośnie o yj jednostek, tj. do poziomu f(xopt) + yi.
Analiza wrażliwości (1)
Co stanie się z uzyskanym rozwiązaniem optymalnym, jeżeli zmieni się
wartość jednego wybranego parametru rozwiązywanego zadania
programowania liniowego? :
" parametr w funkcji celu cj
" prawa strona ograniczenia bi
Analiza wrażliwości (2)
Jeżeli zmienimy wartośd jednego wybranego współczynnika cj , to
rozwiązanie może utracid optymalnośd. W tym przypadku celem analizy
wrażliwości jest określenie takiego przedziału
dopuszczalnych zmian wybranego współczynnika cj , aby rozwiązanie
pozostało optymalne. Zmianie będzie ulegała wartośd funkcji celu oraz
wartości wycen dualnych. W analizowanym przykładzie przedziały
dopuszczalnych zmian są następujące:
Dla c1 - ( - " ; 4,00 )
Dla c2 - ( 3,00 ; + " )
Jeżeli, któryś ze współczynników osiągnie kraniec przedziału np.
c1 = 4,00 lub c2 = 3,00 to rozwiązanie w dalszym ciągu będzie optymalne
ale niejednoznacznie.
Analiza wrażliwości (4)
Jeżeli zmienimy wartość jednego wybranego wyrazu wolnego bi, to
rozwiązanie ( struktura)może utracić dopuszczalność. W tym przypadku
celem analizy wrażliwości jest określenie takiego przedziału dopuszczalnych
zmian wybranego wyrazu wolnego bi, aby rozwiązanie pozostało
dopuszczalne. Zmianie będzie ulegała wartość funkcji celu, wartości
zmiennych , a wartości wycen dualnych pozostaną bez zmian. W
analizowanym przykładzie przedziały dopuszczalnych zmian są następujące:
Dla b1 - ( 450,00 ; + " )
Dla b2 - ( 300,00 ; 366,667)
Dla b3 - ( 550,00 ; 700,00)
Jeżeli, któryś ze współczynników osiągnie kraniec przedziału np.
b1 = 450,00 , b2 = 300,00 lub 366,667, b2 = 550,00 lub 700,00 to rozwiÄ…zanie
w dalszym ciągu będzie dopuszczalne ale zdegenerowane  wartość
przynajmniej jednej zmiennej bazowej będzie równa zero.