Podsumowanie
Ka\
de bazowe rozwiÄ…zanie dopuszczalne jest
punktem wierzchołkowym zbioru X.
Istnieje punkt wierzchołkowy zbioru X w którym
funkcja celu zadania PL przyjmuje maksimum
Ka\
demu punktowi wierzchołkowemu zbioru X
odpowiada m wektorów liniowo niezale\
nych z
danego zbioru n wektorów związanych z tym
punktem.
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
RozwiÄ…zania optymalne
Twierdzenie 6.1
Twierdzenie 6.1
Jeśli zadanie programowania liniowego PL posiada rozwiązanie optymalne i
Jeśli zadanie programowania liniowego PL posiada rozwiązanie optymalne i
wszystkie rozwiÄ…zania bazowe sÄ… niezdegenerowane to za pomocÄ… algorytmu
wszystkie rozwiÄ…zania bazowe sÄ… niezdegenerowane to za pomocÄ… algorytmu
simpleks uzyskuje siÄ™ rozwiÄ…zanie optymalne po co najwy\
ej
simpleks uzyskuje siÄ™ rozwiÄ…zanie optymalne po co najwy\
ej
n
ëÅ‚ öÅ‚
ìÅ‚
ìÅ‚m÷Å‚
÷Å‚
íÅ‚ Å‚Å‚
iteracjach.
iteracjach.
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
Zadanie programowania liniowego - przypadki szczególne
Zało\
enia:
algorytm simpleks startuje z bazowego dopuszczalnego rozwiÄ…zania oraz w
trakcie jego realizacji nie występuje degeneracja
I. Zadanie programowania liniowego PL posiada jedno rozwiÄ…zanie
x1 + x2 d" 5
Å„Å‚ üÅ‚
PrzykÅ‚ad: ôÅ‚x
max x0 = 2x1 +1x2
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
x1 x2 x5 x2 x5 x3
x0 0 -2 -1 x0 7 1/3 -1/3 x0 31/4 1/4 1/2
x3 5 1 1 x3 3/2 -1/6 2/3 x2 9/4 -1/4 3/2
x4 0 -1 1 x4 7/2 1/6 4/3 x4 1/2 1/2 -2
x5 21 6 2 x1 7/2 1/6 1/3 x1 11/4 1/4 -1/2
1
'"
11 9
x = [ , ]T
4 4
RozwiÄ…zanie bazowe optymalne:
31
x0 =
Wartość optymalna funkcji celu:
4
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
Przypadki szczególne cd.
II. Zadanie programowania liniowego - nieograniczone
Twierdzenie 6.2
Jeśli zadanie PL jest nieograniczone, to istnieją rozwiązania
y
bazowe dopuszczalne oraz wektor taki, \
e:
x
K
B
y0k < 0 i yik d" 0 dla i =1,..., m
Wówczas zbiór rozwiązań jest pusty.
Przykład:
min x0 = -x1 - x2,
- x1 - x2 d" 2
x1 - x2 e" -1
x1, x2 e" 0
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
Przypadki szczególne cd.
III. Zadanie programowania liniowego  posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze ograniczonym
Ten przypadek wystÄ…pi wtedy, gdy mo\
na znalez
ć tablicę simpleksową, której
odpowiada optymalne rozwiÄ…zanie bazowe, takie \
e:
yi0 e" 0 dla i = 1,...,m oraz y0 j e" 0 dla j = 1,..., n
i istnieje para
(i , j ), i "{1,..., m}, j "{1,...,n}
0 0 0 0
dla której:
y0 j0 = 0, yi 0 > 0 i yi j0 > 0
0 0
Dla przestrzeni o wymiarze n rozwiązanie optymalne jest kombinacją wypukłą
wierzchołków nale\
Ä…cych do zbioru optymalnego.
xi
'"
p p
'"
'"
x =
i i
" xi gdy " = 1 , i "[0,1], i = 1,..., p
i=1 i=1
!! Dla rozwiÄ…zania zdegenerowanego, przypadek ten mo\
e zaistnieć równie\

pod innymi warunkami.
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
Przypadki szczególne cd.
III. Przykład gdy jest wiele rozwiązań optymalnych na zbiorze ograniczonym
Å„Å‚ - x1 + x2 d" 4
üÅ‚
max x0 = 4x1 + 2x2 X = : , x e" 0żł
òÅ‚x
2x1 + x2 d" 6
x"X
ół þÅ‚
x4 x2
x1 x2 x4 x3
x0 12 2 0
x0 0 -4 -2 x0 12 2 0
x3 4 -1 1 x3 7 0.5 1.5 x2 4.66 0.33 0.66
x4 6 2 1 x1 3 0.5 0.5 x1 0.66 0.33 0.5
1
'"
x = [3,0]T
" 1 rozwiÄ…zanie bazowe optymalne:
2
'"
2 14
x = [ , ]T
" 2 rozwiÄ…zanie bazowe optymalne:
3 3
Zadanie posiada dwa dopuszczalne bazowe rozwiązania optymalne. Odpowiadają one dwóm
wierzchołkom w zbiorze rozwiązań optymalnych.
Zbiór rozwiązań optymalnych
'"
2 14
Å„Å‚x
X = {x : x = x1 + (1- )x2,  "[0,1]}= : x = (3 + (1- )),(0 + (1- )),  "[0,1]üÅ‚
òÅ‚ żł
3 3
ół þÅ‚
2 7 14 14
Å„Å‚x
= : x = ( + ),( - )üÅ‚.
òÅ‚ żł
3 3 3 3
ół þÅ‚
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
Przypadki szczególne cd.
IV. Zadanie programowania liniowego  posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym
Ten przypadek wystÄ…pi wtedy, gdy mo\
na znalez
ć tablicę simpleksową,
której odpowiada optymalne rozwiązanie bazowe, takie \
e:
y e" 0 dlai = 1,..., m oraz y e" 0 dla j = 1,..., n
i0 0 j
dla której, \
e istnieje j0 takie, \
e i dla wszystkich  i zachodzi
y0 j0 = 0
yi0=0 (degeneracja) bÄ…dz

y0 j0 d" 0
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
IV. Zadanie programowania liniowego  posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym cd
Rozwiązanie optymalne zadania PL przyjmuje postać parametryczną:
Dla n=2 równanie parametryczne prostej,
Dla n=3 równanie parametryczne płaszczyzny itd.
max x0 = -2x1 + 4x2
Przykład:
x"X
Å„Å‚ -2x1 + x2 d" 1
üÅ‚
X =òÅ‚x: ,xe"0żł
-1x1 + 2x2 d" 4
ół þÅ‚
x1 x2
x 1 x3
x4 x3
x0 0 2 -4
x0 4 -6 4
x0 8 2 0
x3 1 -2 1
x2 1 -2 1
x2 2.33 0.66 -0,33
x4 4 -1 2
x4 2 3 -2
x1 0.66 0.33 -0,66
1
'"
2 7
x = ( , )T
Bazowe rozwiÄ…zanie optymalne:
3 3
1
'" '" '"
Å„Å‚ üÅ‚
2 1
X = " R2 : x = x + ( , )T t, t e" 0żł
Zbiór rozwiązań optymalnych jest półprostą:
òÅ‚x
3 3
ół þÅ‚
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA
V. Zadanie programowania liniowego  zbiór rozwiązań dopuszczalnych
jest zbiorem pustym - brak rozwiÄ…zania
X = Ć
W tej wersji metody prymalnej simpleks algorytm nie potrafi stworzyć pierwszego
rozwiązania bazowego dopuszczalnego z powodu wektora b, który posiada składowe
ujemne.
x1 x2
Przykład:
max x0 = x1 + 4x2
x"X
b1 + 4
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x0 0 -1 -4
b = =
ïÅ‚b śł ïÅ‚- 2śł
x1 + x2 d" 4
Å„Å‚ üÅ‚
ðÅ‚ 2 ûÅ‚ ðÅ‚ ûÅ‚
X =òÅ‚x: ,xe"0żł x3 4 1 1
x1 - x2 d" -2
ół þÅ‚ x4 -2 1 -1
Nie jest spełniony warunek dopuszczalności pierwszej tablicy simpleks
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania bazowego
dopuszczalnego. Nale\
y sprawdzić dopuszczalność
rozwiÄ…zania:
yi0 e" 0 dla i = 1,..., m
Technika optymalizacji Wydział Elektroniki PWr
Wykład 5
Dr in\
. Ewa Szlachcic EiT III r. subkier. EKA