BADANIA OPERACYJNE Badania operacyjne Badania operacyjne są sztuką dawania złych odpowiedzi na te praktyczne pytania, na które inne metody dają odpowiedzi jeszcze gorsze. T. Sayty 2 Standardowe zadanie programowania liniowego Standardowe zadanie programowania liniowego Rozważamy proces, w którym zmiennymi są x1, x2, ..., xn. Proces poddany jest m ograniczeniom, zapisanymi w postaci: a11x1 + a12x2 +...+ a1nxn = b1 a21x1 + a22x2 +...+ a2nxn = b2 (1) ... am1x1 + am2x2 + ...+ amnxn = bm aij, bi znane współczynniki 4 Standardowe zadanie programowania liniowego Dopuszczamy jedynie nieujemne wartości xj, czyli: xj e" 0, j = 1,2,...,n (2) Zakładamy również, że: bi e" 0, i =1,2,...,m (3) Z procesem jest związana funkcja Z: Z = c1x1 + c2x2 +...+ cnxn (4) cj, j = 1, 2, ...,n znane współczynniki 5 Standardowe zadanie programowania liniowego Zagadnienie polega na maksymalizacji (minimalizacji) funkcji Z (wzór (4)) spełniającej ograniczenia (1), (2), (3). Zapis: n FC : Z = "c xj MAX j j=1 m ńł �ł"a xj = bi ij j=1 (5) �ł �ł �łx e" 0, O : j =1,2,...,n �ł j �ł �ł bi e" 0, i = 1,2,...,m �ł �ł ół 6 Standardowe zadanie programowania liniowego Zapis w postaci macierzowej: FC : Z = cTx MAX Ax = b ńł (6) �ł O: x e" 0 �ł �ł b e" 0 ół a11 a12 & a1n c1 x1 b1 �łłł �ł łł �ł łł �ł łł �łaa22 & a2n śł �łx śł �łb śł �łc śł 21 2 2 2 �łśł �ł śł �ł śł �ł śł A = c = x = b = & & & �ł śł
�łśł �ł śł �ł śł �łaam2 & amn śł �łx śł �łb śł �łc śł �ł m1 �ł �ł n �ł �ł m �ł �ł n �ł 7 Standardowe zadanie programowania liniowego Bardzo powszechną w zagadnieniach praktycznych odmianą ograniczeń są ograniczenia w postaci nierówności. To też są zagadnienia programowania liniowego ale nie w postaci standardowej. 8 Standardowe zadanie programowania liniowego Przykład 1. Zakład zamierza rozpocząć produkcję wyrobów W1 i W2. Wśród środków produkcyjnych, które zostaną użyte w produkcji dwa są limitowane. Limity te wynoszą: dla środka S1 63 jednostki, a dla środka S2 64 jednostki. Aby wyprodukować jednostkę wyrobu W1 potrzeba 9 jednostek środka S1 i 8 jednostek środka S2. Aby wyprodukować jednostkę wyrobu W2 potrzeba 7 jednostek S1 i 8 jednostek S2. Wyroby W1 i W2 są niezbędne do produkcji urządzenia U. Jedno urządzenie U wymaga 3 jednostek wyrobu W1 i 2 jednostek wyrobu W2. Produkcja będzie opłacalna, jeżeli zakład sprzeda wyroby W1 i W2 potrzebne do wytworzenia co najmniej 6 jednostek urządzenia U. Wiedząc, że cena wyrobu W1 będzie wynosić 6, a cena wyrobu W2 5 określ wielkość produkcji maksymalizującej zysk ze sprzedaży. 9 Standardowe zadanie programowania liniowego W1 W2
S1 9 7 63
S2 8 8 64 U 32 6 cena 65 10 Standardowe zadanie programowania liniowego Zmienne decyzyjne: x1 wielkość produkcji wyrobu W1 x2 wielkość produkcji wyrobu W2 11 Standardowe zadanie programowania liniowego Funkcja celu: Z(x1, x2) = 6x1 + 5x2 MAX Ograniczenia: 9x1 + 7x2 d" 63
8x1 + 8x2 d" 64
3x1 + 2x2 e" 6
Warunki brzegowe: x1 e" 0, x2 e" 0 12 Standardowe zadanie programowania liniowego Zadanie programowania liniowego: FC: Z(x1, x2) = 6x1 + 5x2 MAX O: 9x1 + 7x2 d" 63
x1 + x2 d" 8
3x1 + 2x2 e" 6
x1 e" 0, x2 e" 0 WB: Ograniczenia w postaci nierówności. To nie jest standardowe zadanie programowania liniowego 13 METODA GEOMETRYCZNA Metoda geometryczna Zadanie programowania liniowego z dwoma zmiennymi decyzyjnymi można rozwiązać metodą geometryczną (szczegóły na laboratorium). Na podstawie tej metody otrzymujemy zbiór punktów, a następnie sprawdzamy, w którym z nich wartość funkcji celu jest największa (lub najmniejsza). 15 Metoda geometryczna Rozwiązanie dla zadania z Przykładu 1.: A(2,0) Z(2,0) = 6�" 2 + 5�"0 = 12 B(7,0) Z(7,0) = 6�"7 + 5�"0 = 42 C(3.5,4.5) Z(3.5, 4.5) = 6�"3.5 + 5�" 4.5 = 43.5 MAX D(0,8) Z(0,8) = 6�"0 + 5�"8 = 40 E(0,3) Z(0,3) = 6�"0 + 5�"3 = 15 Odpowiedz: Aby zysk był maksymalny, należy wyprodukować 3.5 jednostki W1 oraz 4.5 jednostki W2. 16 ZADANIE DUALNE Zadanie dualne Przykład 2. Zakład produkuje cztery wyroby W1, W2, W3 i W4. Wśród środków produkcyjnych, używanych w procesie wytwarzania wyrobów dwa są limitowane. Limity te, oraz ilości środków potrzebne do wytworzenia poszczególnych wyrobów zostały przedstawione w tabeli. Znając jednostkowe ceny wyrobów, określić taki plan produkcji aby zysk był maksymalny. 18 Zadanie dualne W1 W2 W3 W4 S1 1 3 1 1 600 S2 4 1 1 5 1200 cena 8 9 6 10 Zmienne decyzyjne: xi wielkość produkcji wyrobu Wi i = 1...4 19 Zadanie dualne Model matematyczny: FC: Z(x1, x2, x3, x4) = 8x1 + 9x2 + 6x3 +10x4 MAX O: x1 + 3x2 + x3 + x4 d" 600 4x1 + x2 + x3 + 5x4 d"1200 WB: x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0 20 Zadanie dualne Zadanie pierwotne: FC: Z = cTx MAX Ax d" b O: x e" 0 WB: Zadanie dualne:
FC: Z = bTy MIN ATy e" c O: WB: y e" 0 21 Zadanie dualne Model matematyczny zadania dualnego: FC:
Z(y1, y2) = 600y1 +1200y2 MIN O: y1 + 4y2 e" 8 3y1 + y2 e" 9 y1 + y2 e" 6 y1 + 5y2 e" 10 WB: y1 e" 0, y2 e" 0 22 Zadanie dualne Interpretacja zadania dualnego Konkurent postanawia wykupić zapasy środków produkcji od producenta, i chce zminimalizować koszty materiałów (ma kupić 600 jednostek S1 i 1200 jednostek S2). Zmienne decyzyjne w zadaniu dualnym: y1 cena jednostki środka produkcji S1 y2 cena jednostki środka produkcji S2
Z(y1, y2) = 600y1 +1200y2 MIN 23 Zadanie dualne Interpretacja zadania dualnego c. d. Wyprodukowanie wyrobów wiąże się z kosztem środków S1 i S2. Konkurent, aby zachęcić producenta do sprzedaży materiałów musi mu zapłacić co najmniej tyle, ile producent uzyskałby ze sprzedaży wyrobów, które produkuje. y1 + 4y2 e" 8 3y1 + y2 e" 9 y1 + y2 e" 6 y1 + 5y2 e"10 24 Zadanie dualne Twierdzenie o dualności Zadanie pierwotne ma rozwiązanie wtedy i tylko wtedy, gdy zadanie dualne ma rozwiązanie, oraz:
Z(MAX) = Z(MIN) wnioski: 1. Rozwiązując jedno z zadań, automatycznie rozwiązujemy też drugie. 2. Twierdzenie ma duże znaczenie praktyczne, ponieważ czasami łatwiej jest rozwiązać zadanie dualne (mniej zmiennych). 25 Zadanie dualne Na podstawie metody geometrycznej:
Z(A) = 10800 A(0,9)
B(3/ 2,9 / 2) Z(B) = 6300
C(5,1) Z(C) = 4200 MIN
D(10,0) Z(D) = 6000 Aby koszt materiałów był najmniejszy i wynosił 4200, konkurent musi zapłacić za jednostkę S1 5, a za jednostkę S2 1. 26 Zadanie dualne Na podstawie twierdzenia o dualności: Maksimum FC zadania pierwotnego jest równe minimum FC zadania dualnego. Zysk producenta wyniesie również 4200 Jakie jest rozwiązanie zadania pierwotnego? Twierdzenie o równowadze. 27 Zadanie dualne Twierdzenie o równowadze Jeżeli i ty warunek zadania pierwotnego (ZP) jest (chociaż w jednym) optymalnym rozwiązaniu spełniony z nierównością (ostro), to odpowiadająca mu i ta zmienna yi w (dowolnym) optymalnym rozwiązaniu zadania dualnego (ZD) przyjmuje wartość zero. Dla zmiennej xi>0 w rozwiązaniu optymalnym ZP odpowiadające jej i te ograniczenie w ZD jest ograniczeniem równościowym. Twierdzenie jest również słuszne w przeciwną stronę. 28 Zadanie dualne Rozwiązanie przykładu: y1 = 5 y2 =1 Sprawdzenie ograniczeń ZD: j =1: 5 + 4�"1 > 8 j = 2: 3�"5 +1 > 9 j = 3: 5 +1 = 6 j = 4: 5 + 5�"1 = 10 Nierówności ostre dla j = 1 i j = 2: Dla rozwiązania optymalnego ZP x1 = 0 i x2 = 0 29 Zadanie dualne y1 = 5 > 0 y2 =1 > 0 Ponieważ: Ograniczenia 1 i 2 w ZP są ograniczeniami równościowymi (przy czym x1 = 0, x2 = 0): x3 + x4 = 600 x3 + 5x4 = 1200 x3 = 450 x4 =150 30 Zadanie dualne Odpowiedz do zadania pierwotnego: Aby zysk był maksymalny, producent musi wyprodukować 450 jednostek W3 i 150 jednostek W4. Zysk wyniesie 4200. 31 Szczegółowe zasady formułowania zadania dualnego Szczegółowe zasady formułowania zadania dualnego Zadanie pierwotne Zadanie dualne maksymalizacja minimalizacja 33 Szczegółowe zasady formułowania zadania dualnego Zadanie pierwotne Zadanie dualne Ograniczenia Zmienne i - te: yi d" 0 e" i - te: yi e" 0 d" = i - te: yi dowolne 34 Szczegółowe zasady formułowania zadania dualnego Zadanie pierwotne Zadanie dualne Zmienne Ograniczenia xj e" 0 j - te: e" xj d" 0 j - te: d" = xj dowolne j - te: 35 Szczegółowe zasady formułowania zadania dualnego Przykład 3. Dla podanego zadania pierwotnego zapisać zadanie dualne. FC : Z(x) = 2x1 + 3x2 + x3 + x4 MAX O: x1 + 2x2 - 3x3 + x4 = 20 2x1 + x2 + 3x3 - x4 d" 50 3x1 - x2 + x3 + 2x4 e" 40 WB : x1 e" 0 x2 e" 0 x3 d" 0 x4 dowolne 36 Szczegółowe zasady formułowania zadania dualnego Zadanie dualne: