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: