Badania operacyjne - zastosowanie naukowych metod do rozwiązywania problemów zarządzania w celu wspomagania menedżerów w podejmowanie lepszych decyzji.
I. Obserwaja ⇒ II. Sformułowanie problemu ⇒ III. Konstrukcja modelu ⇒
IV. Rozwiązanie modelu ⇒ V. Analiza i implementacja rozwiązania
Przykład:
I. Firma produkuje dwa wyroby W1 i W2 z dwóch surowców S1 i S2. Firma chce zaplanować produkcj¸e tak aby osi¸agn¸ać jak najwi¸ekszy zysk.
II. Zgromadzono nast¸epuj¸ace dane:
– 1 sztuka W1 zużywa 2 kg S1 i 1 kg S2.
– 1 sztuka W2 zużywa 1 kg S1 i 1 kg S2.
– Zapas S1 wynosi 100 kg a zapas S2 wynosi 80 kg.
– Zysk z 1 sztuki W1 wynosi 3 zł a zysk z 1 sztuki W2 wynosi 2 zł.
– Popyt na W1 wynosi 40 szt. a popyt na W2 jest nieograniczony.
III. Definiujemy zmienne decyzyjne x1 - ilość produkowanych szt. W1, x2 - ilość produkowanych szt. W2. Model matematyczny ma nast¸apuj¸a postać:
max z = 3x1 + 2x2 [Maksymalizacja zysku]
2x1 + x2 ≤ 100
[Zużycie surowca S1]
x1 + x2 ≤ 80
[Zużycie surowca S2]
x1 ≤ 40
[Popyt na W1]
x1 ≥ 0
x2 ≥ 0
Chcemy wi¸ec znaleźć plan produkcji maksymalizuj¸acy zysk przy posiada-nych zasobach (ograniczeniach).
1
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
2
IV. Stosujemy pewien algorytm (poznany w dalszej cz¸eści wykładu) aby rozwi¸azać model. Otrzymujemy: x1 = 20, x2 = 60 czyli należy produkować 20
szt. wyrobu W1 i 60 szt. wyrobu W2.
Model matematyczny:
max(min)z = f (x1, . . . , xn) [Funkcja celu]
g1(x1, . . . , xn) ≤ (≥, =)b1
[Ograniczenie 1]
. . .
gm(x1, . . . , xn) ≤ (≥, =)bm
[Ograniczenie m]
Zmienne x1, . . . , xn nazywamy zmiennymi decyzyjnymi. Rozwi¸azanie spełniaj¸ace wszystkie ograniczenia nazywamy rozwi¸azaniem dopuszczalnym. Rozwi¸azanie dopuszczalne dla którego wartość funkcji celu jest najwi¸eksza (najmniejsza) nazywamy rozwi¸azaniem optymalnym.
Funkcj¸e postaci h(x1, . . . , xn) = a1x1+a2x2+· · ·+anxn nazywamy funkcj¸a liniow¸a.
Model w którym wszystkie funkcje f, g1, . . . , gm s¸a liniowe nazywamy modelem liniowym lub zadaniem programowania liniowego. Model liniowy ma wi¸ec postać: max(min)z = c1x1 + c2x2 + · · · + cnxn
[Funkcja celu]
a11x1 + a12x2 + · · · + a1nxn ≤ (≥, =)b1
[Ograniczenie 1]
. . .
am1x1 + am2x2 + · · · + amnxn ≤ (≥, =)bm [Ograniczenie m]
x1 ≥ 0, . . . , xr ≥ 0, r ≤ n
[Ograniczenia na znak]
Specjanymi, wyróżnionymi ograniczeniami liniowymi s¸a ograniczenia na znak postaci xi ≥ 0.
Przykłady modeli liniowych
1. Problem ustalania diety. Pan X chce zestawić deser z czterech dań: tortu, kremu czekoladowego, coli i ciastek. Każde danie zawiera pewn¸a ilość kalorii, czekolady, cukru i tłuszczu (w odpowiednich jednostkach). Ilości te podane s¸a w poniższej tabeli.
Kalorie
Czekolada
Cukier
Tłuszcz
Cena
Tort (1 porcja)
400
3
2
2
5 zł
Krem (1 porcja)
200
2
2
4
2 zł
Cola (1 butelka)
150
0
4
1
3 zł
Ciastko (1 szt.)
500
0
4
5
8 zł
Pan X musi zjeść posiłek zawieraj¸acy co najmniej: 500 kalorii, 6 jednostek czekolady, 10 dkg cukru i 8 dkg tłuszczu. Chce przy tym zminimalizować koszt posiłku.
Zmienne decyzyjne:
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
3
• x1 - ilość porcji tortu.
• x2 - ilość porcji kremu.
• x3 - ilość butelek coli.
• x4 - ilość sztuk ciastek.
Model:
min z = 5x1 + 2x2 + 3x3 + 8x4
[Minimalizacja kosztu]
400x1 + 200x2 + 150x3 + 500x4 ≥ 500 [Kalorie]
3x1 + 2x2 ≥ 6
[Czekolada]
2x1 + 2x2 + 4x3 + 4x4 ≥ 10
[Cukier]
2x1 + 4x2 + x3 + 5x4 ≥ 8
[Tłuszcz]
xi ≥ 0, i = 1, . . . , 4
[Ograniczenia na znak]
Po rozwi¸azaniu modelu otrzymujemy optymaln¸a diet¸e: 3 porcje kremu i 1 butelk¸e coli (x1 = 0, x2 = 3, x3 = 1, x4 = 0).
2. Model procesu produkcyjnego Korporacja Rylon wytwarza cztery rodzaje perfum: Brute, Chanelle, Super Brute i Super Chanelle. Proces produkcji wygl¸ada nast¸epuj¸aco:
Brute
Super Brute
sprzedaż
7$/jedn.
14$/jedn.
sprzedaż
Materiał
-3$/szt.
sprzedaż
Chanelle
Super Chanelle
sprzedaż
6$/jedn.
10$/jedn.
• z 1 szt. materiału wytwarzane s¸a w ci¸agu 1 godziny 3 jedn. Brute i 4
jedn. Chanelle.
• 1 jedn. Brute jest przetwarzana w ci¸agu 3 godzin w 1 jedn. Super Brute.
• 1 jedn. Chanelle jest przetwarzana w ci¸agu 2 godzin w 1 jedn. Super Chanelle.
• Można zakupić do 4000 szt. materiału i wykorzystać do 6000 h. pracy.
Należy opracowć plan produkcji maksymalizuj¸acy zysk.
Zmienne decyzyjne:
• x1 - liczba sprzedanych jedn. Brute.
• x2 - liczba sprzedanych jedn. Super Brute.
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
4
• x3 - liczba sprzedanych jedn. Chanelle.
• x4 - liczba sprzedanych jedn. Super Chanelle.
• x5 - liczba zakupionych szt. materiału.
Model:
max z = 7x1 + 14x2 + 6x3 + 10x4 − 3x5 [Maksymalizacja zysku]
x1 + x2 − 3x5 = 0
[Produkcja Brute i Super Brute]
x3 + x4 − 4x5 = 0
[Produkcja Chanelle i Super Chanelle]
x5 ≤ 4000
[Limit materiału]
3x2 + 2x4 + x5 ≤ 6000
[Limit pracy]
xi ≥ 0, i = 1, . . . , 5
[Ograniczenia na znak]
Po rozwi¸azaniu modelu otrzymujemy optymalny plan produkcji: 11 333.333
jedn. Brute, 666.667 jedn. Super Brute i 16 000 jedn. Chanelle (x1 =
11333.33, x2 = 666.667, x3 = 16000, x4 = 0, x5 = 4000). Zysk wynosi 172 666.667 $.
3. Model zapasów. Firma X produkuje pewien wyrób w ci¸agu 4 kwartałów.
Firma chce zminimalizować koszty i zaspokoić popyt. Odpowiednie dane przedstawione s¸a w poniższej tabeli:
KW I
KW II
KW III
KW IV
Popyt (szt.)
30
60
75
25
Zdolność produkcyjna (szt.)
60
60
60
60
Koszt wytworzenia ($/szt.)
55
50
50
55
Koszt magazynowania ($/szt.)
2
2
3
-
Na początku pierwszego i na końcu czwartego kwartału firma nie ma zapasów wyrobu.
Zmienne decyzyjne:
• xi - produkcja w i-tym kwartale, i = 1, . . . 4.
• mi - zapasy w i-tym kwartale, , i = 1, . . . 4.
30
60
70
25
m1
m2
m
x
3
1
x2
x3
x4
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
5
Model:
min z = 55x1 + 50x2 + 50x3 + 55x4 + 2m1 + 2m2 + 3m3 [Min. kosztu]
x1 − m1 = 30
[Bilans w I kw.]
m1 + x2 − m2 = 60
[Bilans w II kw.]
m2 + x3 − m3 = 75
[Bilans w III kw.]
m3 + x4 = 25
[Bilans w IV kw.]
xi ≤ 60, i = 1, . . . 4
[Zd. produkcyjne]
xi ≥ 0, mi ≥ 0, i = 1, . . . , 4
[Ograniczenia na znak]
Po rozwi¸azaniu modelu otrzymujemy: x1 = 45, x2 = 60, x3 = 60, x4 = 25, m1 = 15, m2 = 15, m3 = 0.
4. Model inwestycji finansowych. Korporacja Finco Ivestment chce zainwestować kwot¸e 100 000 $ w pi¸eć inwestycji A,B,C,D,E. Okres inwestycji trwa trzy lata. Odpowiednie przepływy finansowe podane s¸a w poniższej tabeli: 0
1
2
3
A
-1$
+0.5$
+1$
-
B
-
-1$
+0.5$
1$
C
-1$
+1.2$
-
-
D
-1$
-
-
+1.9$
E
-
-
-1$
+1.5$
Na przykład inwestycja A jest dostępna w chwili 0, w chwili 1 (tj. po roku) otrzymujemy 0.5$ a w chwili 2 (tj.po dwóch latach ) otrzymujemy 1$ za każdy zainwestowany 1$ w A. Korporacja trzyma niezainwestowane pienią-
dze w banku na 8% w skali roku. Ponadto nie chce inwestować w żadną inwestycję więcej niż 75 000 $. Jak zainwestować posiadaną gotówkę aby zmaksymalizować ilość gotówki na koniec trzeciego roku.
Zmienne decyzyjne:
• xA, xB, xC , xD, xE - kwoty ulokowane w odpowiednie inwestycje.
• y0, y1, y2 - kwoty pozostaj¸ace w banku w chwilach 0, 1 i 2.
Model:
max z = xB + 1.9xD + 1.5xE + 1.08y2 [Max. gotówki w chwili 3]
xA + xC + xD + y0 = 100000
[Bilans w chwili 0 ]
0.5xA + 1.2xC + 1.08y0 − xB − y1 = 0 [Bilans w chwili 1]
xA + 0.5xB + 1.08y1 − xE − y2 = 0
[Bilans w chwili 2]
xA, xB, xC, xD, xE ≤ 75000
[Limit inwestycji]
xA, . . . , xE, y0, y1, y2 ≥ 0
[Ograniczenia na znak]
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
6
Rozwi¸azanie: Należy inwestować w A - 60 000$, B - 30 000$, D - 40 000$
i E - 75 000$. W banku nie należy trzymać gotówki (y0 = y1 = y2 = 0).
Gotówka w chwili 3 tj. na koniec trzeciego roku wyniesie 218500$.
(Dodatkowe zagadnienia do wykonania na laboratorium:)
5. Wybór asortymentu produkcji - fabryka mebli. Fabryka mebli produkuje sofy, stoły i krzesła. Do ich produkcji potrzebne są między innymi trzy limitowane zasoby: drewno, obicie i praca (inne zasoby nie są limitowane).
Ilości zasobu na każdy produkt oraz ich tygodniowe limity podano w tabeli: Mebel
Drewno(
3
2
m
)
Obicie(m )
Praca(godz.)
Zysk(zł.)
Sofa
7
12
6
400
Stół
5
-
9
275
Produkcję planuje się
Krzesło
4
7
5
190
Limit tygodniowy
2250
1000
240
na okres jednego tygodnia a cała wyprodukowana partia musi być przecho-wana w magazynie o pojemności 650 mebli. Fabryka chce wiedzieć ile sztuk każdego typu mebli produkować aby zmaksymalizować zysk.
6. Optymalny plan produkcji przy minimalnych nakładach - połączenie firm SFF i SOFOR. Dwa przedsiębiorstwa SFF i SOFOR produkujace resory typu RS (dla pociągów) i typu RL (dla samochodów) postanowiły się po-
łączyć (dotąd konkurowały ze sobą). W obu przedsiębiorstwach robotnicy pracuj przez 20 dni w miesicu - w SFF 250 osób i w SOFOR 200 osób.
Przedsiębiorstwa te mają różną wydajność: w SFF produkuje się dziennie 1
resor RS lub 4 resory RL na osobę a w SOFOR jedna osoba może dziennie wyprodukować 2 resory RS lub 1 resor RL. W przedsiębiorstwie SFF robotnik otrzymuje 25 FR za godz. pracy przy resorach RS i 20 FR za godz. pracy przy resorach RL. W przedsiębiorstwie SOFOR stawki są inne: 35 FR za godz. pracy przy resorach RS i 30 FR za godzinę pracy przy resorach RL. W
obu przedsiębiorstwach robotnicy pracują przez 8 godz. dziennie. Polityka płacowa nie ulega zmianie po połączeniu się przedsiębiorstw. Celem połą-
czonych przedsiębiorstw jest produkcja 300 resorów RS i 500 resorów RL
dziennie. Opracować taki plan produkcji, przy którym zrealizowany zosta-nie cel połaczonych przedsiębiorstw przy minimalnych nakładach na płace robotników.
7. CASE - Ochrona środowiska. Rafineria wytwarza pewien produkt podsta-wowy, używajc dwóch surowców A i B. Wyrodukowanie 1 kg tego produktu wymaga 1 kg surowca A i 2 kg surowca B. Stosowany proces chemiczny daje w wyniku 1 kg produktu podstawowego, 1 kg odpadów płynnych 1 1
kg odpadów stałych. Odpady stałe oddawane są fabryce nawozów bezpłat-nie, w zamian za zabranie tych odpadów. Odpady płynne nie mają żadnej wartości rynkowej i rafineria dotychczas wylewała je bezpośrednio do rzeki.
Ostatni wprowadzono zarządzenia rządowe zabraniające wylewania odpadów płynnych do rzeki. W rafinerii stworzono zatem grupę roboczą, któ-
ra przedstawiła następujący zestaw różnych możliwości poradzenia sobie z płynnymi odpadami:
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
7
(a) Produkcja drugorzędnego produktu K powstałego poprzez dodanie 1 kg surowca A do 1 kg odpadów płynnych.
(b) Produkcja drugorzędnego produktu M powstałego poprzez dodanie 1 kg surowca B do 1 kg odpadów płynnych.
(c) Specjalne przetworzenie odpadów płynnych tak, że będą one spełniały pew-ne wymogi i będą mogły być wprowadzone do rzeki.
Kierownictwo rafinerii zdaje sobie sprawę, że produkty drugorzędne bę-
dą miały niską jakość i nie przyniosą wiele zysku. Wie również, że specjalne przetworzenie odpadów jest drogą operacją. Problem polega na tym, jak zmaksymalizować zysk, spełniając wymogi ochrony środowiska. Kierownictwo rafinerii chce wiedzieć, ile ma produkować produktu podstawowego, ile (i czy w ogóle) produktów K i M,
ile odpadów (jeśli w ogóle) ma poddać specjalnemu przetworze-
niu przed wylaniem do rzeki. W poprzednim miesiącu wyprodukowano 10000 kg produktu podstawowego (nie produkowano niczego innego). Księ-
gowość dostarczyła następujcych danych o kosztach zmiennych: surowiec A: 15000 zł.; surowiec B: 16000 zł.; siła robocza bezpośrednia: 5000 zł. Koszty bezpośrednie siły roboczej produktów drugorzędnych szacuje się na 0.2 zł.
dla 1 kg produktu K i 0.1 zł. dla jednego kg produktu M. Cena rynkowa 1 kg produktu podstawowego wynosi 5.7 zł. Produkty drugorzędne K i M
można sprzedać odpowiednio za 0.85 zł. za kg i 0.65 zł. za kg. Przetworzenie 1 kg odpadów płynnych kosztować będzie 0.25 zł. W najbliższym okresie rafineria będzie miała do dyspozycji maksymalnie 5000 kg surowca A i 7000
kg surowca B.
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
8
Metoda graficzna dla programowania liniowego. Metodę graficzn¸a można stosować w przypadku, gdy liczba zmiennych decyzyjnych jest nie wi¸eksza niż trzy. Zilustrujemy tę metodę dla dwóch zmiennych - wtedy zbiory rozwiązań dopuszczalnych i funkcję celu można przedstawić na płaszczyźnie.
1. Przykład 1. Rozwiąż problem:
x
100
2
80
max z = 3x1 + 2x2
2x1 + x2 ≤ 100
x1 + x2 ≤ 80
60
(20,60)
x1 ≤ 40
x1 ≥ 0
x2 ≥ 0
40
20
z=60
z=180
10
20
30
40
50
60
70
80
x1
z=0
Krok 1 Rysujemy na płaszczyznie zbiór ograniczeń.
Krok 2 Rysujemy funkcje celu np: dla z = 0 i przesuwamy j¸a równolegle do góry (w dół dla problemu minimalizacji) dopóki przecina ona zbiór dopuszczalnych rozwi¸azań. Maksymalnie przsuni¸eta funkcja celu wy-znacza optymalne rozwi¸azanie.
Optymalne rozwi¸azanie: x1 = 20, x2 = 60, z = 180. Jest to jedyne optymalne rozwi¸azanie!
2. Przykład 2. Rozwi¸azać problem:
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
9
x
100
2
max z = 2x1 + 2x2
(0,80)
2x1 + x2 ≤ 100
80
x1 + x2 ≤ 80
z=160
x1 ≤ 40
x1 ≥ 0
60
(20,60)
x2 ≥ 0
40
20
z=40
10
20
30
40
50
60
70
80
x1
z=0
Problem posiada nieskończenie wiele rozwi¸azań optymalnych na odcinku ł¸acz¸acym punkty (0,80) i (20,60).
3. Przykład 3. Rozwi¸azać problem:
x2
80
max z = 2x1 + 2x2
z=320
2x1 − x2 ≤ 40
60
x2 ≥ 20
x1 ≥ 0
x2 ≥ 0
40
20
z=40
10
20
30
40
x1
z=0
Problem nie posiada rozwi¸azania optymalnego. Funkcja celu może przyj-mować dowolnie duż¸a wartość.
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
10
4. Przykład 4. Rozwi¸azać problem:
x2
max z = 3x1 + 2x2
60x1 + 40x2 ≤ 240
x1 ≥ 30
60
x2 ≥ 20
40
20
10
20
30
40
50
60
x1
Zbiór ograniczeń jest sprzeczny . Nie ma rozwi¸azania dopuszczalnego (zbiór rozwiązań dopuszczalnych jest pusty) i tym samym optymalnego.
dr inż. Adam Kasperski, dr M. Kulej Badania Operacyjne Wykład 1
11
Obserwacje
1. Zbiór rozwiązań dopuszczalnych jest wypukły. Zbiór D nazywamy zbiorem wypukłym wtedy i tylko wtedy, gdy odcinek łączący dwa dowolne jego punkty x(1), x(2) ∈ D jest zawarty w D.
2. Wierzchołków w zbiorze rozwiązań dopuszczalnych jest tylko skończenie wiele. Punkt x ∈ D nazywamy wierzchołkiem zbioru D wtedy i tylko wtedy, gdy nie istnieją takie dwa punkty x(1), x(2) ∈ D, różne od x, że dla 0 < λ < 1 : x = λx(1) + (1 − λ)x(2). Inaczej punkt x nie leży wewnątrz odcinka łączącego dwa inne punkty zbioru D.
3. Możliwy jest dokładnie jeden z czterech przypadków:
• Istnieje dokładnie jedno rozwi¸azanie optymalne.
• Istnieje nieskończenie wiele rozwi¸azań optymalnych. W rozpatrywanym przykładzie jest to odcinek - w ogólnym przypadku zbiór rozwią-
zań optymalnych jest zbiorem wypukłym.
• Funkcja celu jest nieograniczona.
• Zbiór ograniczeń jest sprzeczny - nie ma rozwi¸azania dopuszczalnego.
4. Jeżeli istnieje rozwi¸azanie optymalne to istnieje ono w pewnym wierzchoł-
ku (nazywanym również punktem ekstremalnym) zbioru rozwiązań dopuszczalnych. Jeżeli kilka wierzchołków zbioru rozwiązań dopuszczalnych re-prezentuje rozwiązanie optymalne, to każdy punkt ich wypukłej kombi-nacji liniowej jest także rozwiązaniem optymalnym. Wypukłą kombina-cją liniową wierzchołków x1, x2, . . . , xk nazywamy każdy punkt x taki, że x = λ1x1 + λ2x2 + · · · + λkxk, gdzie λ1, . . . , λk ≥ 0 i λ1 + · · · + λk = 1.