Programowanie liniowe - 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.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Twierdzenie 6.1
Niech będzie dany układ równań liniowych
Ax=B
gdzie jest macierzą mxn, dim x=m, (A)=m, n>m. Jeśli istnieje
rozwiązanie dopuszczalne układu równań tzn. takie, \
e x>=0 to
istnieje równie\
bazowe rozwiÄ…zanie dopuszczalne tzn. x=[xB,0]
Twierdzenie 6.2
RozwiÄ…zanie dopuszczalne x zadania programowania liniowego
jest punktem wierzchołkowym zbioru rozwiązań dopuszczalnych
XOL wtedy i tylko wtedy gdy odpowiada mu bazowe rozwiÄ…zanie
dopuszczalne tzn. x=[xB,0]
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
RozwiÄ…zania optymalne
Twierdzenie 6.3
Twierdzenie 6.3
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.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Przypadki szczególne cd.
II. Zadanie programowania liniowego  zadanie nieograniczone
Twierdzenie 6.4
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,
-x - x d" 2
1 2
- x + x d" 1
1 2
x , x e" 0
1 2
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
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.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
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 w:
R2
2
'"
2 14
R2
x = [ , ]T
" 2 rozwiÄ…zanie bazowe optymalne w:
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
ół þÅ‚
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
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.
Przykład:
Å„Å‚ -2x1 + x2 d" 1
üÅ‚
max x0 = -2x1 + 4x2
X =òÅ‚x: ,xe"0żł
x"X
-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
Zbiór rozwiÄ…zaÅ„ optymalnych jest półprostÄ…: Å„Å‚ üÅ‚
X = " R2 : x = x+[ , ]T t, t e" 0żł
òÅ‚x
3 3
ół þÅ‚
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
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.
Przykład:
max x0 = x1 + 4x2
x1 x2
x"X
b1 + 4
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x0 0 -1 -4
b = =
ïÅ‚b śł ïÅ‚- 2śł
x1 + x2 d" 4
Å„Å‚ üÅ‚
ðÅ‚ 2 ûÅ‚ ðÅ‚ ûÅ‚
x3 4 1 1
X =òÅ‚x: ,xe"0żł
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
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka