Technika optymalizacji
Optymalne rozwiÄ…zanie zadania programowania liniowego PL metodÄ…
II Zadanie programowania liniowego PL
simpleks
max f (x)= cT x
Twierdzenie 4.5
Twierdzenie 4.5
przy ograniczeniach:
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
jest rozwiązaniem optymalnym zadania PL, jeśli są spełnione dwa warunki:
A1x d" b1
A2 x e" b2
x e"0
(i) Warunek prymalnej dopuszczalności:
dim x=[n*1], dim c=[n*1]
yio e"0 dla i "{1,..., m}
Macierze A1, A2 odpowiadają za współczynniki w m1 i m2 ograniczeniach
(ii) Warunek optymalności
dim A1 =[m 1 * n], dim A2 =[m 2 * n]
Wektory b1, b2 odpowiadają za prawe strony ograniczeń y0 j e" 0 dla "j " RN
dim b1=[m1*1], dim b2=[m2*1]
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Pomocnicza funkcja celu
Zadanie programowania liniowego dla ograniczeń mniejszościowych i
Uproszczona wersja I fazy metoda dwufazowej simpleks  uzyskanie
większościowych
bazowego rozwiÄ…zania dopuszczalnego
Metoda dwóch faz
" Jeśli wektor b w początkowej tablicy simpleksowej ma przynajmniej jedną ujemną
współrzędną, to tablica przedstawia niedopuszczalne rozwiązanie bazowe.
I faza - nale\
y znalez
ć pierwsze rozwiązanie bazowe dopuszczalne
" PoczÄ…tkowÄ… niedopuszczalnÄ… tablicÄ™ simpleksowÄ… mo\
na przekształcić wykorzystując
poprzez rozwiÄ…zanie zadania pomocniczego
algorytm simpleks.
" Cel  uzyskanie nieujemnych wartości zmiennych pomocniczych.
II faza - maksymalizacja funkcji celu x0 dla następnego rozwiązania
" Nale\
y znalez
ć najmniejszą wartość
r Ò! min{yi0, yi0 < 0 dla i = 1,2,...,m }
bazowego dopuszczalnego wg algorytmu simpleks.
i
" Wybrany wiersz s będzie stanowił pomocniczą funkcję celu , którą nale\
y zmaksymalizować.
Algorytm simpleks (prymalny)  I faza Krok 1  nie ma mo\
liwości stworzenia
" Kolejne kroki metody simpleks powinny być prowadzone do uzyskania dopuszczalnej tablicy
pierwszego rozwiÄ…zania bazowego dopuszczalnego
simpleks, tzn. takiej dla której spełniony jest warunek prymalnej dopuszczalności:
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania
bazowego dopuszczalnego. Nale\
y sprawdzić dopuszczalność
yi0 e" 0 dla i =1,2,...,m
rozwiÄ…zania: czy Tak - idz
do Kroku 2, Nie  STOP.
yi 0 e" 0 dla i = 1,..., m
" Koniec I fazy
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Pomocnicza funkcja celu
Uproszczona wersja I fazy metoda dwufazowej simpleks cd.
Krok 3. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy
x ,
taką zmienną dla której
Br
yr0 Å„Å‚ yio yi0 üÅ‚
= minòÅ‚ : i = 1,..., m, > 0żł
Krok 1. (start- wybór pomocniczej funkcji celu). Rozpoczynamy algorytm od
yrk i ół yik yik þÅ‚
ys0 < 0
znalezienia wiersza s , dla którego oraz s = min{yi0 : yi0 < 0, i = 1,2,...,m}
i
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
yi0 e" 0 dla i =1,2,...,m
Jeśli brak takiego s ( ) to tablica odpowiada dopuszczalnemu
ys0 < 0 i ysk < 0
rozwiÄ…zaniu bazowemu  nale\
y przejść do II fazy. Taki przypadek zawsze istnieje, poniewa\

Id\
do Kroku 5.
Krok 2. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną wchodzącą
xk " RN dla której
do bazy takÄ… zmiennÄ… ysk < 0
x , i `" R ,
Krok 4. (eliminacja Gauss a). Wyznacz oraz względem zmiennych
Typową regułą jest wybór zmiennej , dla której: x Bi N
x , k " R
k N k
x , j " RN - {k} oraz zmiennej xB zgodnie z wyprowadzonymi wzorami.
j
y = {y : y < 0} r
0 k sk sk
min
j " R
N
x = 0, j " RN -{k} i xBr = 0
Podstaw
j
xk ysk e" 0 dla k aby otrzymać pierwsze rozwiązanie bazowe dopuszczalne.
Jeśli jest brak takiej zmiennej ( " RN ) to jest brak
rozwiÄ…zania dopuszczalnego. Jest to problem sprzeczny.
Idz
do Kroku 1.
Id\
do Kroku 3.
Krok ten czasami nazywa siÄ™ wymianÄ… zmiennej bazowej ( piwotyzacjÄ…).
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
1
Technika optymalizacji
Przykład II zadania programowania liniowego Przypadki szczególne  zbiór rozwiązań dopuszczalnych jest zbiorem
metoda dwufazowa simpleks pustym - brak rozwiÄ…zania
max x0 = 1x1 +6x2 Å„Å‚ + 2x1 + 1x2 e" 2 üÅ‚ X = Ć
x"X
ôÅ‚x
X = : -1x1 + 1x2 d" 3 żł W metodzie dwufazowej simpleks algorytm w I fazie obliczeń nie potrafi stworzyć
,x e" 0ôÅ‚
òÅ‚
ôÅ‚ ôÅ‚
+ 1x1 + 1x2 d" 6
ół þÅ‚ pierwszego rozwiÄ…zania bazowego dopuszczalnego z powodu braku rozwiÄ…zaÅ„
dopuszczalnych.
I faza II faza cz.1 II faza cz.2
Przykład: 1
max x0 = x1 - x2 - x3
x"X
-x5 -x2 2
-x5 -x4
-x1 -x2
Å„Å‚ 1 üÅ‚ -x1 -x2 -x3
x0 6 1 -5 - x1 + 2x2 + x3 d" 2
x0 28,5 3,5 2,5 ôÅ‚ ôÅ‚
x0 0 -1 -6 -x1 -x4 -x3
2
ôÅ‚ ôÅ‚ -1/2 1 1
x0 0
ôÅ‚x 1
x3 -2 -2 -1 x3 10 2 1 X3 5,5 1,5 -0,5 x0 x x x x
X = : - x1 + 2x2 - x3 e" 3 , x e" 0ôÅ‚
òÅ‚ żł
2 x4 2
ôÅ‚ ôÅ‚ -1/2 2 1
x4 3 -1 1 x4 9 1 2 X2 4,5 0,5 0,5 x2 x x x x
x2 - x3 d" 2
ôÅ‚ ôÅ‚
x5 6 1 1 x5 -3 1/2 -2 1 -1 0 1 2
x5
x1 6 1 1 X1 1,5 0,5 -0,5 ôÅ‚ ôÅ‚
ół þÅ‚
x6 2 0 1 -1 x6 x x x x
Brak rozwiÄ…zania
I rozwiÄ…zanie bazowe II rozwiÄ…zanie bazowe
Nie jest spełniony warunek dopuszczalności drugiej tablicy simpleks i jednocześnie druga tablica
dopuszczalnego
dopuszczalne dopuszczalne- rozwiÄ…zanie
wskazuje, \
e jest brak rozwiązań dopuszczalnych.
optymalne
îÅ‚6Å‚Å‚
xB = x0 B1 = 6
1 ïÅ‚0śł, îÅ‚1,5Å‚Å‚
x5 = -1- x4 - 2x3
ðÅ‚ ûÅ‚ xB1 = x0 B2 = 28,5
ïÅ‚4,5śł,
ðÅ‚ ûÅ‚
T '" x1, x2, x3, x4, x5, x6 e" 0
'" '" '" '" '" '"
îÅ‚ Å‚Å‚
1 T
Rozwiązanie optymalne: x = x2 x3 x4 x5 śł == [1,5 4,5 5,5 0 0] x0 = 28,5
ïÅ‚x
ðÅ‚ ûÅ‚
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Postać kanoniczna II zadania PL
III Zadanie programowania liniowego PL
T
min x0 = c x,
min x0 = cT x
przy ograniczeniach:
A x e" b ,
x e" 0,
A x e" b
x e" 0
T
max - x0 = - c x,
dim x=[n*1], dim c=[n*1]
- A x + I xs = -b,
Macierz A odpowiada za współczynniki w m ograniczeniach
s
dim A=[m x n]
x , xs e" 0,
Wektor wyrazów wolnych b odpowiada za prawą stronę ograniczeń
dim b =[m*1]
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Teoria dualności dla zadania programowania liniowego PL
Optymalne rozwiÄ…zanie II zadania PL metodÄ… dualnÄ… simpleks
max x0 = cT x
min v0 = vT b
Twierdzenie:
Twierdzenie:
A x d" b
AT v e" c
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
x e"0 v e"0
jest rozwiązaniem optymalnym II zadania PL, jeśli są spełnione
warunki:
(i) Warunek dualnej dopuszczalności: Twierdzenie 7.1 :
Jeśli wektor x jest rozwiązaniem dopuszczalnym dla zadania prymalnego i
yoj e" 0 dla j " RN
wektor v jest rozwiązaniem dopuszczalnym dla zadania dualnego, to wartość
funkcji celu w zadaniu dualnym nie mo\
e być mniejsza od wartości funkcji
(ii) Warunek dualnej optymalności
celu w zadaniu prymalnym.
yi0 e"0 dla i "{1,...,m}
vTb e" cT x
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
2
Technika optymalizacji
Teoria dualności dla zadania PL cd.
Twierdzenie 7.2
Twierdzenie 7.4
'" '"
Dla pary rozwiązań optymalnych zadania prymalnego i dualnego PL
x i v
Jeśli jedno z pary wzajemnie dualnych zadań programowania liniowego ma
zachodzi warunek:
rozwiązanie optymalne, to ma je równie\
zadanie dualne i obydwa zadania majÄ…
'" '"
identyczne wartości funkcji celu.
cT x = bT v
Twierdzenie 7.5
Twierdzenie 7.3
Niech (xr ,xs ) i ( vr , vs) będą odpowiednio rozwiązaniami dopuszczalnymi zadania Jeśli zadanie dualne jest nieograniczone, to zadanie prymalne jest sprzeczne.
prymalnego i dualnego, przy czym xs i vs są wektorami zmiennych dopełniających
do postaci kanonicznej zadania w wektorach rozwiązań.
Wtedy (xr ,xs ) i ( vr , vs) będą odpowiednio rozwiązaniami optymalnymi pary zadań
prymalnego i dualnego, jeśli zachodzi warunek komplementarności zmiennych:
T T
xTv = 0
tzn. xr vs + xs vr = 0
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Teoria dualności dla zadania PL cd.
Przykład I zadanie prymalne
zadanie dualne
I. RozwiÄ…zanie zadania dualnego metodÄ… simpleks
min v0 = 5v1 + 0v2 + 21v3 max x0 = 2x1 +1x2
v"V x"X
Å„Å‚ x1 + x2 d" 5 üÅ‚
Å„Å‚ v1 - v2 + 6v3 e" 2üÅ‚ Zadanie dualne: max x0 = 2x1 +1x2 Å„Å‚ 1x1 +1x2 d" 5 üÅ‚
ôÅ‚x x"X ôÅ‚ ôÅ‚
ôÅ‚x
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚ X = : - x1 + x2 d" 0 , x e" 0żł
òÅ‚x
V = : v1 + v2 + 2v3 e" 1ôÅ‚ òÅ‚ żł
òÅ‚ żł
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ 6x1 + 2x2 d" 21
v1, v2 , v3 e" 0 6x1 + 2x2 d" 21 ół þÅ‚
ół þÅ‚
ół þÅ‚
Postać wektora rozwiązań:
x5 x2
x1 x2
v = [vr ,vs]= [v1,v2 ,v3 v4,v5] x = [xr , xs]= [x1, x2 x3, x4 , x5] x5 x3
x0 7 1/3 -1/3
x0 0 -2 -1 x0 31/4 1/4 1/2
T
x3 3/2 -1/6 2/3
x3 5 1 1
xT v = 0 Ò! [xr , xs] [vs , vr ]= 0 x2 9/4 -1/4 3/2
x4 7/2 1/6 4/3
x4 0 -1 1
x4 1/2 1/2 -2
Przykład II System cięcia dłu\
yc x5 21 6 2 x1 7/2 1/6 1/3
x1 11/4 1/4 -1/2
max x0 = 2100x1 +1200x2
x"X
min v0 = 0.3v1 + 0.6v2 + 0.2v3
RozwiÄ…zanie optymalne:
'"
'"
îÅ‚11 9 1
7v1 + 3 v2 + 0v3 e" 2100 Å„Å‚ 7x1 + 0x2 d" 0.3 üÅ‚
a) Zadanie dualne x = [x1, x2 ,Ä™! x3, x4, x5]
x = , ,Ä™! 0, ,0Å‚Å‚
ïÅ‚ śł
ôÅ‚x 4 4 2
ðÅ‚ ûÅ‚
'"
X = : 3x1 +1x2 d" 0.6 , x e" 0ôÅ‚
òÅ‚ żł
0v1 + 1v2 + 2v3 e" 1200 b) Zadanie prymalne
'"
v = [v4 ,v5,Ä™! v1, v2 , v3]
îÅ‚ 1 1 Å‚Å‚
ôÅ‚ ôÅ‚ v = 0, 0,Ä™! , 0,
0x1 + 2x2 d" 0.2 ïÅ‚
ół þÅ‚ 2 4śł
ðÅ‚ ûÅ‚
v1,v2,v3 e" 0
'" '"
31
Wartość optymalna funkcji celu:
x0 = v0 =
4
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
3