PRZYKA
AD AP-2
Dana jest tablica rozwiÄ…zania optymalnego
Wartości
50 100 80 0 0 M M
B BAZA Niewiadome niewiadomych
C
t1 t2
x1 x2 x3 S1 S2
bazowe bazowych
p6 p7
p1 p2 p5
p3 p4
80 0 0 1 -1 1 1 -1 10
p3
x3
50 1 1 0 1 -2 -1 2 20
p1
x1
0 -50 0 -30 -20 30 20 1800
" = z - cj
"
"
"
j j
-M -M
następującego zadania optymalizacyjnego:
Znalez
ć wartość najmniejszą funkcji f (x1, x2 , x3 ) = 50 x1 + 100 x2 + 80 x3 na zbiorze
rozwiązań układu nierówności:
x1 + x2 + 2x3 e" 40
Å„Å‚
ôÅ‚
x1+ x2 + x3 e" 30 .
òÅ‚
ôÅ‚
x1, x2, x3 e" 0
ół
Wiadomo, że bazę w startowej tablicy simpleks tworzyły wektory (p6 , p7 ).
a) Jakie wartości może przyjmować współczynnik c2 przy niewiadomej x2 , aby rozwiązanie
optymalne nie uległo zmianie?
b) Jakie wartości może przyjmować wartość ograniczenia b1 aby rozwiązanie optymalne było
w dalszym ciÄ…gu wyznaczane przez wektory (p3 , p1 )?
RozwiÄ…zanie:
Ad a) Załóżmy, że nowa wartość współczynnika przy niewiadomej x2 będzie równa
c2 = 100 + "c2 . Ponieważ w rozwiązaniu optymalnym niewiadoma x2 nie jest niewiadomą
bazowÄ…, to wystarczy aby "c2 e" "2 Ò! "c2 e" - 50 . StÄ…d wynika, że "c2 " < -50, + ") ,
czyli współczynnik c2 przy niewiadomej x2 może przyjmować wartości z przedziału
op op op
< 50, + ") i rozwiÄ…zanie optymalne x1 = 20 , x2 = 0 x3 = 10 nie ulegnie zmianie, nie
zmieni się także wartość funkcji celu.
Ad b) Załóżmy, że nowa wartość ograniczenia b1 będzie równa b1 = 40 + "b1 . Dopuszczalne
zmiany wartości b1 , przy których nie zmienia się baza wyznaczająca rozwiązanie optymalne
(ale zmieniać się mogą wartości zmiennych w rozwiązaniu bazowym) otrzymujemy
rozwiązując układ nierówności
B Å"b e" 0 .
Z tablicy rozwiązania optymalnego odczytujemy elementy macierzy B jako współrzędne
wektorów (p6 , p7 ), które tworzyły bazę w startowej tablicy simpleks, zatem
1
îÅ‚ -1 40 + "b1
Å‚Å‚ îÅ‚ Å‚Å‚
B = oraz b = .
ïÅ‚-1 2śł ïÅ‚ śł
30
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Rozwiązując układ nierówności
1Å" (40 + "b1) + (-1) Å" 30 e" 0
Å„Å‚
òÅ‚
ół(-1) Å" (40 + "b1) + 2 Å" 30 e" 0
Otrzymujemy, że "b1 " < -10, 20 > , a stąd b1 " < 30, 60 > . Rozwiązanie optymalne będzie
wówczas wyznaczone przez te same wektory (p3 , p1 ) i będzie ono następujące
op op op op op
x1 = 20 - "b1 , x2 = 0, x3 = 10 + "b1, S1 = 0, S2 = 0, t1 = 0, t2 = 0 . Funkcja celu dla
tego rozwiÄ…zania optymalnego ma wartość 1800 + 30 Å" "b1.