1 Treść dzisiejszego wykładu l Postać standardowa zadania PL. l Zmienne dodatkowe w zadaniu PL. l Metoda simpleks –wymagania metody simpleks, –tablica simpleksowa. l Alternatywne rozwiązania optymalne.

2 Wykorzystanie zasobów - Par, Inc. l dla rozwiązania optymalnego: –7/10 * 540 + 1 * 252 = 630 godzin cięcia i farbowania –1/2 * 540 + 5/6 * 252 = 480 godzin szycia –1 * 540 + 2/3 * 252 = 708 godzin wykańczania –1/10 * 540 + 1/4 * 252 = 117 godzin pakowania l pozostało niewykorzystanych: –120 godzin (600 - 480) szycia, –18 godzin (135 - 117) pakowania.

3 Postać standardowa - Par, Inc. 10x 1 + 9x 2 + 0s 1 + 0s 2 + 0s 3 + 0s 4  max p.w. 7/10x 1 + 1x 2 + 1s 1 = 630 1/2x 1 + 5/6x 2 + 1s 2 = 600 1x 1 + 2/3x 2 + 1s 3 = 708 1/10x 1 + 1/4x 2 + 1s 4 = 135 x 1, x 2, s 1, s 2, s 3, s 4 

4 Zmienne dodatkowe - Par, Inc.

5 Postać standardowa - reguły l Typ optymalizacji pozostaje ten sam. l W funkcji celu wprowadza się zmienne dodatkowe ze współczynnikami równymi 0. l Zmienne dodatkowe wprowadza się w ograniczeniach: –typu  s i (zmienna nadmiaru), –typu  s i (zmienna niedoboru), –typu =: nie wprowadza się zmiennej dodatkowej.

6 HighTech - zadanie PL x 1 - liczba wyprodukowanych sztuk Deskpro, x 2 - liczba wyprodukowanych sztuk Portable 50x 1 + 40x 2  max p.w. 3x 1 + 5x 2  150czas montażu 1x 2  20monitory komputera Portable 8x 1 + 5x 2  300przestrzeń magazynowa x 1, x 2  0

7 HighTech - postać standardowa 50x 1 + 40x 2 + 0s 1 + 0s 2 + 0s 3  max p.w. 3x 1 + 5x 2 + 1s 1 =  150 1x 2 + 1s 2 =  20 8x 1 + 5x 2 + 1s 3 =  300 x 1, x 2, s 1, s 2, s 3  0

8 Rozwiązanie bazowe l Dla x 2 = 0 i s 1 = 0: 3x 1 = 150x 1 = 50 1s 2 = 20  s 2 = 20 8x 1 + 1s 3 = 300s 3 = -100 l n- liczba zmiennych, l m- liczba warunków, gdzie n > m. l Aby wyznaczyć rozwiązanie bazowe, połóż za (n - m) zmiennych zero i rozwiąż układ m równań liniowych z m zmiennymi. l Zmienne bazowe- zmienne, za które nie kładziemy zera, np. x 1, s 2, s 3. l Zmienne niebazowe - (n - m) zmiennych, za które kładziemy zero, np. x 2, s 1.

9 Bazowe rozwiązanie dopuszczalne (BRD) l BRD - rozwiązanie bazowe, które spełnia dodatkowo warunki nieujemności. l Dla x 1 = 0 i x 2 = 0: 1s 1 = 150s 1 = 150 1s 2 = 20  s 2 = 20 1s 3 = 300s 3 = 300 l Wszystkie BRD odpowiadają wierzchołkom zbioru rozwiązań dopuszczalnych! l Metoda simpleks jest iteracyjną procedurą przechodzenia od jednego BRD do drugiego, do momentu znalezienia rozwiązania optymalnego.

10 Idea metody simpleks l punkt startowy: pierwsze BRD, l metoda simpleks generuje w każdej iteracji jedno BRD układu równań, które nie jest gorsze od poprzedniego BRD, l gdy wartość funkcji celu nie może być już w ten sposób poprawiona, to znaczy, że wyznaczone BRD jest rozwiązaniem optymalnym.

11 Przygotowanie ZPL do metody simpleks l Sformułuj problem decyzyjny w postaci zadania optymalizacji liniowej. l Zbuduj postać standardową zadania poprzez dodanie zmiennych niedoboru lub odjęcie zmiennych nadmiaru. l Zbuduj postać tabelaryczną zadania.

12 Wymagania metody simpleks l zadanie programowania liniowego, l punkt startowy - pierwsze BRD, l liczba zmiennych większa od liczby ograniczeń, wszystkie zmienne decyzyjne nieujemne, tj. x  0, l zadanie w postaci standardowej, tj. Ax = b, prawe strony nieujemne, tj. b  0.

13 HighTech - pierwsza tablica simpleksowa

14 Wskaźnik optymalności l Wskaźnik optymalności dla j-tej zmiennej:  j = c j - z j = c j - c B T h j, gdzie h j jest j-tą kolumną tablicy simpleksowej. – zmiana netto wartości funkcji celu, w sytuacji, gdy jednostka j-tej zmiennej wystąpi w rozwiązaniu, –  1 = 50  gdy zmienna x 1 przyjmie wartość 1 w rozwiązaniu, to wartość funkcji celu wzrośnie o 50.

15 Kryterium wejścia l Bazując na współczynnikach optymalności, wybierz zmienną, która po wejściu do bazy spowoduje największą jednostkową poprawę wartości funkcji celu. W przypadku remisu wybierz zmienną leżącą najbliżej lewej strony tabeli simpleksowej. l MAX: wchodzi zmienna o największym (dodatnim) współczynniku optymalności. l MIN: wchodzi zmienna o najmniejszym (ujemnym) współczynniku optymalności.

16 Kryterium wyjścia l Załóżmy, że zmienna wchodząca do bazy odpowiada j-tej kolumnie macierzy A. Dla każdego rzędu i oblicz iloraz b i /a ij dla każdego a ij większego od zera. Z bazy usuwana jest zmienna, której odpowiada najmniejszy iloraz. W przypadku remisu usuwa się zmienną leżącą najwyżej w tablicy simpleksowej. l Sposób wyboru zmiennej wychodzącej nie zależy od typu optymalizacji.

17 Element centralny

18 Kolejna tablica simpleksowa l Operacje elementarne: –mnożenie dowolnego wiersza przez niezerową liczbę, –odejmowanie lub dodawanie jednego wiersza do innego mnożonego przez liczbę.

19 HighTech - druga tablica simpleksowa l Operacje elementarne: –w’ 3 = 1/8*w 3 ; w’ 1 = w 1 - 3*w’ 3. l Rozwiązanie bazowe: –x B = [75/2 0 75/2 20 0] T

20 HighTech - trzecia tablica simpleksowa l Operacje elementarne: –w’ 1 = 8/25*w 1 ; w’ 2 = w 2 - w’ 1 ; w’ 3 = w 3 - 8/5*w’ 1. l Rozwiązanie bazowe: –x B = [30 12 0 8 0] T

21 Warunek STOP l MAX: Rozwiązanie optymalne problemu PL zostało osiągnięte, gdy wszystkie współczynniki optymalności mają wartości zero lub są ujemne. W takiej sytuacji rozwiązaniem optymalnym jest bieżące bazowe rozwiązanie dopuszczalne. l MIN: Rozwiązanie optymalne problemu PL zostało osiągnięte, gdy wszystkie współczynniki optymalności mają wartości zero lub są dodatnie. W takiej sytuacji rozwiązaniem optymalnym jest bieżące bazowe rozwiązanie dopuszczalne.