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.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
Zało\
enia:
X `" 0
1. Zbiór X rozwiązań dopuszczalnych
2. 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
Å„Å‚ üÅ‚
max x0 = 2x1 +1x2 X = ôÅ‚x : - x1 + x2 d" 0 , x e" 0ôÅ‚
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
Przykład:
x5 x2
x5 x3
x1 x2
x0 7 1/3 -1/3 x0 31/4 1/4 1/2
x0 0 -2 -1
x2 9/4 -1/4 3/2
x3 5 1 1
x3 3/2 -1/6 2/3
x4 1/2 1/2 -2
x4 0 -1 1
x4 7/2 1/6 4/3
x1 11/4 1/4 -1/2
x5 21 6 2
x1 7/2 1/6 1/3
'"
11 9 1
x = [x1, x2, x3, x4.x5 ]T = [ , , 0, , 0]T
RozwiÄ…zanie bazowe optymalne:
4 4 4
31
Wartość optymalna funkcji celu:
x0 =
4
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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
- x1 - x2 d" 2
x0 0 -1 -1
x1 - x2 e" -1
x3 2 -1 1
x1, x2 e" 0 x4 1 -1 1
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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}
dla której:
0 0 0 0
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.
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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
ół þÅ‚
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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:
yi0 e" 0 dla i = 1,..., m oraz y0 j e" 0 dla j = 1,..., n
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
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
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
x4 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
'"
2 7
x = ( , )T
Bazowe rozwiÄ…zanie optymalne:
3 3
'" '"
2 1
Å„Å‚x
X = " R2 : x = x+ ( , )T t, t e" 0üÅ‚
òÅ‚ żł
Zbiór rozwiązań optymalnych jest półprostą:
3 3
ół þÅ‚
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
V. Zadanie programowania liniowego  zbiór rozwiązań dopuszczalnych
X = Ć
jest zbiorem pustym - brak rozwiÄ…zania
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.
Przykład:
x1 + x2 d" 4 b1 + 4
Å„Å‚ üÅ‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
max x0 = x1 + 4x2 X = : b = =
òÅ‚x x1 - x2 d" - 2, x e" 0żł
ïÅ‚b śł ïÅ‚- 2śł
x"X
ół þÅ‚
ðÅ‚ 2 ûÅ‚ ðÅ‚ ûÅ‚
x1 x2
x0 0 -1 -4
x3 4 1 1
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
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic