II Zadanie programowania liniowego PL dla ograniczeÅ„ wiÄ™kszoÅ›ciowych min x0 = cT x przy ograniczeniach: A x e" b x e" 0 dim x=[n*1], dim c=[n*1] Macierz A odpowiada za współczynniki w m ograniczeniach dim A=[m x n] Wektor wyrazów wolnych b odpowiada za prawÄ… stronÄ™ ograniczeÅ„ dim b =[m*1] Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Postać kanoniczna II zadania PL T min x0 = c x, A x e" b, x e" 0, T max - x0 = -c x, - A x + I xs = -b, s x , xs e" 0, Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Optymalne rozwiÄ…zanie II zadania PL metodÄ… dualnÄ… simpleks Twierdzenie: Twierdzenie: RozwiÄ…zanie bazowe dopuszczalne ukÅ‚adu równaÅ„ Ax=b jest rozwiÄ…zaniem optymalnym II zadania PL, jeÅ›li sÄ… speÅ‚nione warunki: (i) Warunek dualnej dopuszczalnoÅ›ci: yoj e"0 dla j " RN (ii) Warunek dualnej optymalnoÅ›ci yi0 e" 0 dla i "{1,..., m} Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Algorytm dualny simpleks Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszej tablicy dualnie dopuszczalnej. Nale\y sprawdzić dualnÄ… dopuszczalność yoj e" 0 dla j "RN rozwiÄ…zania: czy Tak - idz do Kroku 2, Nie koniec. yi0 e" 0 Krok 2. (test optymalnoÅ›ci). Czy dla ka\dego ? i = 1,..., m " Tak - to aktualne rozwiÄ…zanie jest optymalne. " Nie - idz do Kroku 3. Krok 3. (Wybór zmiennej usuwanej z bazy). Wybierz jako zmiennÄ… usuwanÄ… z y < 0 . bazy takÄ… zmiennÄ… x dla której r 0 B r xB TypowÄ… reguÅ‚Ä… jest wybór zmiennej dla której: r y = {y , y < 0, i = 1,..., m} r 0 io i 0 min j" R N Id\ do Kroku 4. Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Algorytm dualny simpleks c.d. Krok 4. (wybór zmiennej wprowadzanej do bazy). Wybierz jako zmiennÄ… wchodzÄ…cÄ… do bazy takÄ… zmiennÄ… dla której x k y0 j y0k = max( , yrj < 0). yrk yrj JeÅ›li wiele zmiennych speÅ‚nia ten warunek, wybierz arbitralnie jednÄ… z nich. Id\ do Kroku 5. Krok 5. (eliminacja). Dokonaj dualnÄ… iteracjÄ™ simpleksowÄ… metodÄ… eliminacji xB Gauss a poprzez wprowadzenie do bazy oraz usuniÄ™cie x r k Idz do Kroku 2. Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka PrzykÅ‚ad II zadania programowania liniowego dualna metoda simpleks min x0 =1x1 +1x2 x"X +1x1 + 2x2 e" 8 Å„Å‚ üÅ‚ ôÅ‚x X = : òÅ‚ 2x1 + 1x2 e" 6, x e" 0ôÅ‚ żł ôÅ‚ ôÅ‚ +1x1 + 1x2 e" 5 ół þÅ‚ tablica poczÄ…tkowa tablica poÅ›rednia tablica optymalna -x1 -x3 -x4 -x3 -x1 -x2 -x0 0 1 1 -x0 -4 ½ ½ -X0 -14/3 1/3 1/3 X3 -8 -1 -2 X2 4 ½ -1/2 X2 10/3 1/3 -2/3 X4 -6 -2 -1 x4 -2 -3/2 -1/2 X1 4/3 -2/3 1/3 X5 -5 -1 -1 X5 -1 -1/2 -1/2 X5 -1/3 -1/3 -1/3 tablica dualnie dopuszczalna tablica jeszcze nie optymalna y20 < 0 yi0 e" 0 dla "i = 1,..., m yoj e" 0 dla j "RN Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka PrzykÅ‚ad II zadania programowania liniowego dualna metoda simpleks cd. tablica optymalna I tablica optymalna II -x5 -x4 -x5 -x3 -x0 -5 1 0 -X0 -5 1 0 X2 4 -2 1 X2 3 1 -1 X1 2 -2 1 x1 1 1 -1 X4 1 -3 1 X3 1 -3 1 1 '" RozwiÄ…zanie optymalne I 1 1 1 x = [x1 , x1, x3, x1 , x5] = [2, 3, 0, 1, 0] 2 4 wierzchoÅ‚ek: '" 2 x0 = 5 '" RozwiÄ…zanie optymalne II 2 2 2 2 2 x = [x1 , x2 , x3 , x4 , x5 ] = [1, 1, 1, 0, 0] wierzchoÅ‚ek: Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka III Zadanie programowania liniowego PL max f (x)= cT x przy ograniczeniach: A1x d" b1 A2 x e" b2 x e"0 dim x=[n*1], dim c=[n*1] Macierze A1, A2 odpowiadajÄ… za współczynniki w m1 i m2 ograniczeniach dim A1 =[m 1 * n], dim A2 =[m 2 * n] Wektory b1, b2 odpowiadajÄ… za prawe strony ograniczeÅ„ dim b1=[m1*1], dim b2=[m2*1] Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Optymalne rozwiÄ…zanie zadania programowania liniowego PL metodÄ… simpleks Twierdzenie 4.5 Twierdzenie 4.5 RozwiÄ…zanie bazowe dopuszczalne ukÅ‚adu równaÅ„ Ax=b jest rozwiÄ…zaniem optymalnym zadania PL, jeÅ›li sÄ… speÅ‚nione dwa warunki: (i) Warunek prymalnej dopuszczalnoÅ›ci: yio e" 0 dla i "{1,..., m} (ii) Warunek optymalnoÅ›ci y0 j e" 0 dla "j " RN Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Zadanie programowania liniowego dla ograniczeÅ„ mniejszoÅ›ciowych i wiÄ™kszoÅ›ciowych Metoda dwóch faz I faza - nale\y znalezć pierwsze rozwiÄ…zanie bazowe dopuszczalne poprzez rozwiÄ…zanie zadania pomocniczego II faza - maksymalizacja funkcji celu x0 dla nastÄ™pnego rozwiÄ…zania bazowego dopuszczalnego wg algorytmu simpleks. Algorytm simpleks (prymalny) I faza Krok 1 nie ma mo\liwoÅ›ci stworzenia pierwszego rozwiÄ…zania bazowego dopuszczalnego Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania bazowego dopuszczalnego. Nale\y sprawdzić dopuszczalność rozwiÄ…zania: czy Tak - idz do Kroku 2, Nie STOP. yi0 e" 0 dla i = 1,..., m Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka I faza metody PL Nieznane pierwsze rozwiÄ…zanie bazowe dopuszczalne I.1 - technika zadania pomocniczego I.2 - technika pomocniczej funkcji celu Ad. I.1 RozwiÄ…zanie zadania pomocniczego PL z funkcjÄ… celu w postaci funkcji liniowej z0 îÅ‚ Å‚Å‚ A1 It A = ïÅ‚ śł 0 ðÅ‚A2 ûÅ‚ Gdzie It jest macierzÄ… jednostkowÄ… rzÄ™du t. A1xN + Itxt = b1 A2xN = b2 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka I faza metody PL cd. Wprowadzamy wektor zmiennych pomocniczych dim xÄ… xÄ… = m- t A1xN + Itxt = b1 A2xN + Im-txÄ… = b2 RozwiÄ…zanie bazowe dopuszczalne ukÅ‚adu równaÅ„: xt = b1, xÄ… = b2, xN = 0 Nale\y znalezć inne rozwiÄ…zanie bazowe dopuszczalne, w którym xÄ… =0 lub stwierdzić, \e takie rozwiÄ…zanie nie istnieje. Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka I faza metody zadanie pomocnicze PL - 1x , max z0 = Ä… x - c x - c x = 0, 0 N N t t xN , xt , xÄ… e" 0 A1xN + It xt = b1, I x = b , A2xN + m - t Ä… 2 Zmienna x0 zawsze pozostaje zmiennÄ… bazowÄ…. RozwiÄ…zaniem poczÄ…tkowym zadania PL I fazy jest xt = b1 - A1xN , xÄ… = b2 - A2xN , z0 = 1(b2 - A2xN ), x0 = ctb1 + (cN - ctA1)xN Oraz xN = 0 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Ad.I.2 Pomocnicza funkcja celu Uproszczona wersja I fazy metoda dwufazowej simpleks uzyskanie bazowego rozwiÄ…zania dopuszczalnego " JeÅ›li wektor b w poczÄ…tkowej tablicy simpleksowej ma przynajmniej jednÄ… ujemnÄ… współrzÄ™dnÄ…, to tablica przedstawia niedopuszczalne rozwiÄ…zanie bazowe. " PoczÄ…tkowÄ… niedopuszczalnÄ… tablicÄ™ simpleksowÄ… mo\na przeksztaÅ‚cić wykorzystujÄ…c algorytm simpleks. " Cel uzyskanie nieujemnych wartoÅ›ci zmiennych pomocniczych. " Nale\y znalezć najmniejszÄ… wartość r Ò! min{yi0, yi0 < 0 dla i =1,2,...,m } i " Wybrany wiersz s bÄ™dzie stanowiÅ‚ pomocniczÄ… funkcjÄ™ celu , którÄ… nale\y zmaksymalizować. " Kolejne kroki metody simpleks powinny być prowadzone do uzyskania dopuszczalnej tablicy simpleks, tzn. takiej dla której speÅ‚niony jest warunek prymalnej dopuszczalnoÅ›ci: yi0 e" 0 dla i =1,2,...,m " Koniec I fazy Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Ad.I.2 Pomocnicza funkcja celu Uproszczona wersja I fazy metoda dwufazowej simpleks cd. Krok 1. (start- wybór pomocniczej funkcji celu). Rozpoczynamy algorytm od ys0 < 0 s = min{yi0 : yi0 < 0, i = 1,2,..., m} znalezienia wiersza s , dla którego oraz i yi0 e" 0 dla i =1,2,...,m JeÅ›li brak takiego s ( ) to tablica odpowiada dopuszczalnemu rozwiÄ…zaniu bazowemu nale\y przejść do II fazy. Krok 2. (Wybór zmiennej wchodzÄ…cej do bazy). Wybierz jako zmiennÄ… wchodzÄ…cÄ… xk " RN ysk < 0 do bazy takÄ… zmiennÄ… dla której TypowÄ… reguÅ‚Ä… jest wybór zmiennej , dla której: x , k " R k N y = {y : y < 0} 0 k sk sk min j " R N xk JeÅ›li jest brak takiej zmiennej ( ) to jest brak ysk e" 0 dla k " RN rozwiÄ…zania dopuszczalnego. Jest to problem sprzeczny. Id\ do Kroku 3. Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka 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żł yrk i ół yik yik þÅ‚ JeÅ›li wiele zmiennych speÅ‚nia ten warunek, wybierz arbitralnie jednÄ… z nich. ys0 < 0 i ysk < 0 Taki przypadek zawsze istnieje, poniewa\ Id\ do Kroku 5. x , i `" R , Krok 4. (eliminacja Gauss a). Wyznacz oraz wzglÄ™dem zmiennych x Bi N k x , j " RN - {k} xB oraz zmiennej zgodnie z wyprowadzonymi wzorami. j r x = 0, j " RN -{k} i xBr = 0 Podstaw j aby otrzymać pierwsze rozwiÄ…zanie bazowe dopuszczalne. Idz do Kroku 1. Krok ten czasami nazywa siÄ™ wymianÄ… zmiennej bazowej ( piwotyzacjÄ…). Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka PrzykÅ‚ad III zadania programowania liniowego metoda dwufazowa simpleks max x0 = 1x1 +6x2 + 2x1 + 1x2 e" 2 Å„Å‚ üÅ‚ x"X ôÅ‚x X = : ,x e" 0ôÅ‚ òÅ‚ - 1x1 + 1x2 d" 3 żł ôÅ‚ ôÅ‚ + 1x1 + 1x2 d" 6 ół þÅ‚ I faza II faza cz.1 II faza cz.2 -x5 -x2 -x5 -x4 -x1 -x2 x0 6 1 -5 x0 28,5 3,5 2,5 x0 0 -1 -6 x3 10 2 1 x3 -2 -2 -1 X3 5,5 1,5 -0,5 x4 3 -1 1 x4 9 1 2 X2 4,5 0,5 0,5 x5 6 1 1 x1 6 1 1 X1 1,5 0,5 -0,5 Brak rozwiÄ…zania I rozwiÄ…zanie bazowe II rozwiÄ…zanie bazowe dopuszczalnego dopuszczalne dopuszczalne- rozwiÄ…zanie optymalne 6 îÅ‚ Å‚Å‚ xB = x0 B1 = 6 1,5 ïÅ‚0śł, îÅ‚ Å‚Å‚ 1 xB = x0 B2 = 28,5 ðÅ‚ ûÅ‚ ïÅ‚4,5śł, 1 ðÅ‚ ûÅ‚ T '" '" '" '" '" '" '" îÅ‚ Å‚Å‚ T 1 RozwiÄ…zanie optymalne: x0 = 28,5 x = x2 x3 x4 x5 śł == [1,5 4,5 5,5 0 0] ïÅ‚x ðÅ‚ ûÅ‚ Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Przypadki szczególne zbiór rozwiÄ…zaÅ„ dopuszczalnych jest zbiorem pustym - brak rozwiÄ…zania X = Ć W metodzie dwufazowej simpleks algorytm w I fazie obliczeÅ„ nie potrafi stworzyć pierwszego rozwiÄ…zania bazowego dopuszczalnego z powodu braku rozwiÄ…zaÅ„ dopuszczalnych. PrzykÅ‚ad: 1 max x0 = x1 - x2 - x3 x"X 2 -x1 -x2 -x3 1 Å„Å‚ üÅ‚ - x1 + 2x2 + x3 d" 2 ôÅ‚ ôÅ‚ -x1 -x4 -x3 2 ôÅ‚ ôÅ‚ x0 0 -1/2 1 1 1 ôÅ‚x x0 x x x x X = : - x1 + 2x2 - x3 e" 3, x e" 0ôÅ‚ òÅ‚ żł 2 x4 2 -1/2 2 1 ôÅ‚ ôÅ‚ x2 x x x x x2 - x3 d" 2 ôÅ‚ ôÅ‚ x5 -3 1/2 -2 1 x5 -1 0 1 2 ôÅ‚ ôÅ‚ ół þÅ‚ x6 x x x x x6 2 0 1 -1 Nie jest speÅ‚niony warunek dopuszczalnoÅ›ci drugiej tablicy simpleks i jednoczeÅ›nie druga tablica wskazuje, \e jest brak rozwiÄ…zaÅ„ dopuszczalnych. x2 = -x4 - 2x3 -1 x1, x2, x3, x4 e" 0 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Teoria dualnoÅ›ci dla zadania programowania liniowego PL max x0 = cT x min v0 = vT b A x d" b AT v e" c x e"0 v e"0 Twierdzenie 7.1 : JeÅ›li wektor x jest rozwiÄ…zaniem dopuszczalnym dla zadania prymalnego i 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 celu w zadaniu prymalnym. vTb e" cT x Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Teoria dualnoÅ›ci dla zadania PL cd. Twierdzenie 7.2 '" '" Dla pary rozwiÄ…zaÅ„ optymalnych zadania prymalnego i dualnego PL x i v zachodzi warunek: '" '" cT x = bT v Twierdzenie 7.3 Niech (xr ,xs ) i ( vr , vs) bÄ™dÄ… odpowiednio rozwiÄ…zaniami dopuszczalnymi zadania 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 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Twierdzenie 7.4 JeÅ›li jedno z pary wzajemnie dualnych zadaÅ„ programowania liniowego ma rozwiÄ…zanie optymalne, to ma je równie\ zadanie dualne i obydwa zadania majÄ… identyczne wartoÅ›ci funkcji celu. Twierdzenie 7.5 JeÅ›li zadanie dualne jest nieograniczone, to zadanie prymalne jest sprzeczne. Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka PrzykÅ‚ad I zadanie prymalne zadanie dualne max x0 = 2x1 +1x2 min v0 = 5v1 + 0v2 + 21v3 v"V x"X x1 + x2 d" 5 Å„Å‚ üÅ‚ v1 Å„Å‚ - v2 + 6v3 e" 2 üÅ‚ ôÅ‚x ôÅ‚x X = : - x1 + x2 d" 0 , x e" 0ôÅ‚ V = : v1 + v2 + 2v3 e" 1ôÅ‚ òÅ‚ żł òÅ‚ żł ôÅ‚ ôÅ‚ ôÅ‚ ôÅ‚ 6x1 + 2x2 d" 21 v1,v2,v3 e" 0 ół þÅ‚ ół þÅ‚ Postać wektora rozwiÄ…zaÅ„: v = [vr ,vs]= [v1,v2,v3 v4,v5] x = [xr , xs]= [x1, x2 x3, x4, x5] T xT v = 0 Ò! [xr , xs] [vs ,vr ]= 0 PrzykÅ‚ad II System ciÄ™cia dÅ‚u\yc max x0 = 2x1 + 1x2 x" X min v0 = 0.3v1 + 0.6v2 + 0.2v3 7x1 + 0x2 d" 0.3 7v1 + 3 v2 + 0v3 e" 2100 Å„Å‚ üÅ‚ ôÅ‚x X = : 3x1 +1x2 d" 0.6 , x e" 0ôÅ‚ òÅ‚ żł 0v1 + 1v2 + 2v3 e"1200 ôÅ‚ ôÅ‚ 0x1 + 2x2 d" 0.2 ół þÅ‚ v1,v2,v3 e" 0 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka Teoria dualnoÅ›ci dla zadania PL cd. I. RozwiÄ…zanie zadania dualnego metodÄ… simpleks 1x1 +1x2 d" 5 Å„Å‚ üÅ‚ Zadanie dualne: max x0 = 2x1 +1x2 x"X ôÅ‚x X = : - x1 + x2 d" 0 , x e" 0ôÅ‚ òÅ‚ żł ôÅ‚ ôÅ‚ 6x1 + 2x2 d" 21 ół þÅ‚ x5 x2 x1 x2 x5 x3 x0 7 1/3 -1/3 x0 0 -2 -1 x0 31/4 1/4 1/2 x3 3/2 -1/6 2/3 x3 5 1 1 x2 9/4 -1/4 3/2 x4 7/2 1/6 4/3 x4 0 -1 1 x4 1/2 1/2 -2 x5 21 6 2 x1 7/2 1/6 1/3 x1 11/4 1/4 -1/2 RozwiÄ…zanie optymalne: '" '" 11 9 1 îÅ‚ x = [x1, x2,Ä™! x3, x4, x5] a) Zadanie dualne x = , ,Ä™! 0, ,0Å‚Å‚ ïÅ‚ śł 4 4 2 ðÅ‚ ûÅ‚ '" b) Zadanie prymalne '" v = [v4,v5,Ä™! v1, v2 , v3] 1 1 îÅ‚ Å‚Å‚ v = 0, 0,Ä™! , 0, ïÅ‚ 2 4śł ðÅ‚ ûÅ‚ '" '" 31 Wartość optymalna funkcji celu: x0 = v0 = 4 Teoria i metody optymalizacji WydziaÅ‚ Elektroniki studia II st. Dr in\. Ewa Szlachcic kier. Automatyka i Robotyka