Obecnie wszystkie zmienne niebazowe mają dodatnie kryterium simpleks, a więc wartości funkcji celu nie da się już zmniejszyć.
Pozostawiając Czytelnikowi obliczenie elementów tablic pośrednich, poniżej (posługując się rachunkiem macierzowym) obliczono poszczególne elementy tablicy końcowej1.
yi y2
|
~y i" |
, więc B = |
2 3 |
, B1 =i |
'3 -3" |
|
Jl. |
1 3 |
3 |
-1 2_ |
elementy kolumn zmiennych sztucznych
B^b =
|
1 |
-1 |
h 3 |
1,5~| |
i | ||
|
““ |
1 |
2 |
1 3 |
0 |
0 | |
|
L 3 |
3 J | |||||
|
" 1 |
-f |
[301 |
'10' | |||
|
= |
1 |
2 |
20 |
— |
10 | |
|
. 3 |
3 J |
L3 | ||||
wartości zmiennych bazowych (rozwiązanie),
J elementy kolumn j zmiennych decyzyjnych y2, y2, y3,
|
'1000" _2400_ |
, więc clB~1 = [1000 2400] |
' 1 -1‘ 1 2 |
= [200 600] - |
|
_~7 7. |
elementy wiersza zi dla kolumn
Ji i s2,
elementy wiersza Zj dla kolumn
clB~lb = [1000 2400]
10000 + 8000 = 18 000 <— wartość funkcji celu.
Optymalne rozwiązanie programu dualnego jest zatem następujące:
Zauważmy jeszcze, że z ostatniej tablicy simpleksowej można odczytać także rozwiązanie optymalne programu dualnego. Mianowicie, optymalne wartości zmiennych decyzyjnych PD są równe wartościom bezwzględnym liczb występujących w wierszu zerowym (cy ~zj) ostatniej tablicy simpleksowej, odpowiadających zmiennym swobodnym PP (por. tabl. 42): j>j=|— 10| = 10,
10
T’
>>3 = 0. Analogicznie, wartości zmiennych decyzyjnych PP są
równe wartościom bezwzględnym liczb występujących w wierszu zerowym ostatniej tablicy simpleksowej PD, odpowiadających zmiennym swobodnym lego programu (por. tabl. 46: = |200| = 200, X2 = |600| = 600).
Pytania i problemy
1. Dany jest program liniowy:
x1+ x2+jc3 = 30, x1 + 2x2 + x3'^10,
2x2 + x3 ^ 20,
*i, x2, *3>0,
2x3 +x2 + 3x3-t max.
Sprowadzić powyższy program do postaci kanonicznej.
2. W powyższym PL wektor optymalnych zmiennych bazowych jest następujący:
x'
x3 .
*4
Podać rozwiązanie optymalne i wartość funkcji celu dla rozwiązania optymalnego.
3. Co to jest „wiersz zerowy” tablicy simpleksowej?
4. Omówić sposób zmiany bazy w kolejnych iteracjach algorytmu simpleks.
5. Który z poniższych wektorów (gdzie xlt x2 i x3 to zmienne dcyzyjne, xĄ i x5 to zmienne swobodne, a i s2 to zmienne sztuczne) nie jest wektorem optymalnym i dlaczego?
1.5. Analiza wrażliwości
Rozwiązanie programu liniowego jest dopiero początkiem analizy problemu. Podejmujący decyzje powinien także wiedzieć, jak wrażliwe jest uzyskane rozwiązanie optymalne na pewne zmiany w założeniach modelu lub zmiany czynników zewnętrznych (parametrów modelu). Odpowiedź na te pytania ułatwia analiza wrażliwości (ang. sensitivity analysis) rozwiązania optymalnego na zmiany niektórych parametrów modelu, a więc na przykład: a) współczynników funkcji celu (OFC - objective function coefficients), najczęściej cen - analiza wrażliwości pozwala w tym przypadku odpowiedzieć na pytanie, w jakich granicach mogą się zmieniać te parametry, aby dotychczasowe rozwiązanie pozostało optymalne;
clB~1A = [1000 2400]
1 0 0 1
1,5
-0,5
= [1000 2400 300]
53
Zauważmy, że ponieważ s2 = —yĄ, a s2 = —y}, współczynniki kolumn zmiennych swobodnych są wziętymi ze znakiem przeciwnym współczynikami kolumn odpowiadających im zmiennych sztucznych.