dostawców posiada jednorodny towar odpowiednio w ilościach 
jednostek. Całą masę towarową należy przetransportować do 
odbiorców, których zapotrzebowanie odpowiednio wynosi 
jednostek. Znana jest macierz
Katedra Algorytmów i Modelowania Systemów
Wydział Elektroniki, Telekomunikacji i Informatyki
Politechniki Gdańskiej
BADANIA OPERACYJNE
Część IC Zastosowania programowania liniowego
Materiały pomocnicze do wykładu z przedmiotu "Badania operacyjne"
Opracował: dr Tadeusz Ratajczak
Gdańsk, 2005
Literatura:
1. Jacek Błażewicz, Wojciech Celary, Roman Słowiński, Jan Węglarz: Badania operacyjne dla informatyków. WNT, Warszawa 1983.
2. Saul I. Gass: Programowanie liniowe - Zastosowania. PWN, Warszawa 1976.
3. Stanisław Krawczyk: Programowanie matematyczne. PWE, Warszawa 1980.
4. Zbigniew Jędrzejczyk, Karol Kukuła, Jerzy Skrzypek, Anna Walkosz: Badania operacyjne w przykładach i zadaniach. PWN, Warszawa 1997.
1. Zagadnienie transportowe
dostawców posiada jednorodny towar odpowiednio w ilościach
jednostek. Całą masę towarową należy przetransportować do
odbiorców, których zapotrzebowanie odpowiednio wynosi
jednostek. Znana jest macierz
,
której element 
oznacza koszt transportu jednostki towaru od i-tego dostawcy do j-tego odbiorcy. Należy wyznaczyć taką macierz
,
gdzie 
oznacza liczbę jednostek towaru, którą należy przetransportować od i-tego dostawcy do j-tego odbiorcy, aby sumaryczny koszt transportu był najmniejszy.
Gdy 
zagadnienie nazywamy zagadnieniem transportowym zamkniętym. W przypadku, gdy 
problem nazywamy zagadnieniem transportowym otwartym. Zagadnienie transportowe otwarte sprowadzamy do zamkniętego w następujący sposób.
Jeśli 
< 
, to wprowadzamy fikcyjnego dostawcę 
przyjmując 
oraz 
.
Jeśli 
> 
, to wprowadzamy fikcyjnego odbiorcę 
przyjmując 
oraz 
.
Zad. 1.1. Trzech dostawców 
posiada jednorodny towar w ilości 
, 
, 
jednostek. Całą masę towarową należy przetransportować do pięciu odbiorców 
, których zapotrzebowanie odpowiednio wynosi 
, 
, 
, 
, 
. Koszty transportu jednostki towaru od poszczególnych dostawców do poszczególnych odbiorców są zestawione w poniższej macierzy
Wyznaczyć minimalny koszt transportu.
Zad. 1.2. Dwie bazy PKS: 
, 
wysyłają autobusy na cztery dworce: 
, 
, 
, 
położone na terenie miasta. Przejazdy między bazami i dworcami są traktowane jako puste przebiegi. Zaproponować rozdział autobusów pomiędzy dworce minimalizujący puste przebiegi.
W poniższej tablicy podano odległości pomiędzy bazami a dworcami, licznę autobusów, jakimi bazy dysponują oraz zapotrzebowanie dworców.
|
Dworce |
|
|||
Bazy |
|
|
|
|
Liczba autobusów |
|
15 |
12 |
10 |
17 |
100 |
|
5 |
18 |
24 |
7 |
150 |
Zapotrzebowanie |
40 |
65 |
45 |
60 |
|
2. Problemy przydziału
2.1. Problem przydziału I
wyrobów (czynności) można wykonywać na 
miejscach produkcji (stanowiskach pracy, maszynach). Zakładamy, że każdy rodzaj wyrobu może być wykonany na każdym miejscu produkcji. Znane są ograniczenia na moce produkcyjne poszczególnych miejsc produkcji 
(np. maksymalny dopuszczalny czas pracy) oraz plan wykonania poszczególnych wyrobów 
. Ponadto dana jest macierz
,
której element 
oznacza koszt (czas) i-tego miejsca produkcji przy wykonywaniu jednostki j-tego wyrobu (wydajność i-tego miejsca produkcji przy wykonywaniu j-tego wyrobu).
Należy zaproponować optymalny przydział zadań produkcyjnych do poszczególnych miejsc produkcji z punktu widzenia jednego z poniższych kryteriów:
minimalizacja kosztów (czasu wykonania) zadań planowych,
maksymalizacja ilości wykonanych wyrobów.
2.2. Problem przydziału II (zagadnienie doboru)
Niech danych będzie 
stanowisk i 
kandydatów na te stanowiska. Każdy kandydat może być zatrudniony tylko na jednym stanowisku a każde stanowisko może być zajęte tylko przez jednego kandydata. Przydzielenie kandydata 
na stanowisko 
związane jest z kosztem 
. Należy znaleźć takie przyporządkowanie poszczególnych kandydatów do poszczególnych stanowisk, aby łączny koszt był najmniejszy.
Zad. 2.1. W pewnej instytucji 4 sekretarkom należy przydzielić 4 różne prace biurowe. Znane są czasy (w minutach) zajmujące sekretarkom wykonanie poszczególnych rodzajów prac:
Kandydatki |
|
|
|
|
|
210 |
450 |
390 |
330 |
|
270 |
390 |
450 |
330 |
|
270 |
510 |
390 |
390 |
|
330 |
450 |
330 |
450 |
Określić przydział prac sekretarkom minimalizujący łączny czas wykonania wszystkich prac. Zakładamy, że każda sekretarka będzie wykonywała tylko jedną pracę, oraz że każda praca będzie wykonywana przez jedną sekretarkę.
Algorytm węgierski
Krok 1. Wykorzystując dwie operacje:
od każdego wiersza macierzy 
odejmujemy minimalny element tego wiersza,
od każdej kolumny macierzy 
odejmujemy minimalny element tej kolumny
przekształcić macierz kosztów 
tak, aby w każdym wierszu i w każdej kolumnie występowało co najmniej jedno zero.
Krok 2. W przekształconej macierzy należy skreślić wiersze i kolumny zawierające zera najmniejszą liczbą linii. Jeżeli liczba linii niezbędnych do pokrycia zer macierzy jest równa 
, to otrzymaliśmy rozwiązanie optymalne i przechodzimy do kroku 4. W przeciwnym przypadku przechodzimy do kroku 3.
Krok 3. W przypadku, gdy liczba linii skreśleń jest mniejsza od 
w macierzy 
należy znaleźć najmniejszy nie skreślony element i ten element:
odjąć od elementów nie skreślonych,
dodać do elementów podwójnie skreślonych.
(elementy skreślone jedną linią pozostawiamy bez zmian). Następnie powracamy do kroku 2.
Krok 4. Konstruujemy macierz rozwiązania 
biorąc pod uwagę, że
jedynki w macierzy 
mogą znaleźć się tylko na tych pozycjach, na których występują zera w macierzy 
,
w każdym wierszu macierzy 
powinna wystąpić dokładnie jedna jedynka,
w każdej kolumnie macierzy 
powinna wystąpić dokładnie jedna jedynka.
Trzeba pamiętać, że
Metoda węgierska w opisanej postaci ma zastosowanie wyłącznie do rozwiązywania problemów minimalizacji.
Metoda węgierska w opisanej postaci zakłada, że macierz 
jest macierzą kwadratową, tzn. liczba kandydatów jest równa liczbie stanowisk.
W praktyce może się zdarzyć, że pewne przydziały są niedopuszczalne, tzn. trzeba założyć, że pewne 
muszą być równe zeru.
Zad. 2.2. Pewna instytucja zamierza zatrudnić trzech tłumaczy celem przetłumaczenia tekstów zapisanych w językach: angielskim, niemieckim i włoskim. W konkursie na te stanowiska wzięło udział czterech kandydatów. W poniższej tabeli podane są czasy potrzebne poszczególnym kandydatom na przetłumaczenie odpowiednich tekstów.
|
Czas [w godzinach] potrzebny na przetłumaczenie tekstu |
|||
Tekst w języku: |
Kandydat 1 |
Kandydat 2 |
Kandydat 3 |
Kandydat 4 |
angielskim |
5 |
2 |
10 |
12 |
niemieckim |
10 |
8 |
2 |
5 |
włoskim |
15 |
1 |
5 |
5 |
Wybrać trzechn kandydatów do tłumaczenia tekstów w taki sposób, aby sumaryczny czas tłumaczenia był najmniejszy. Zakładamy, że każdy z trzech tekstów będzie tłumaczony tylko przez jednego tłumacza oraz że każdy tłumacz może pracować tylko nad jednym tekstem.
3. GRY MACIERZOWE
3.1. Podstawowe definicje
Podstawowym zagadnieniem teorii gier (sformułowanym przez Johna von Neumanna) jest badanie następującego problemu: Jeśli n graczy rozgrywa zadaną grę , to jak musi grać i-ty gracz , aby uzyskać najpomyślniejszy wynik ?
Zakładamy, że na końcu rozgrywki każdy gracz otrzymuje pewną ilość pieniędzy . Ilość może być liczbą dodatnią (oznacza wówczas wygraną gracza ), ujemną (oznacza wówczas przegraną gracza ) lub równe zero (oznacza wówczas wynik remisowy). W najbardziej znanych grach, jak na przykład poker, dla wszystkich rozgrywek zachodzi
.
Takie gry nazywamy grami o sumie zero. W grach o sumie zero gracze nie tworzą ani nie rozbierają puli bankowej. Przykładem gry o sumie niezerowej mógłby być poker, w którym pewien procent puli stanowi wynagrodzenie dla właściciela lokalu.
Gra macierzowa
Gra macierzowa jest grą dwuosobową, zdefiniowaną przez macierz
o elementach rzeczywistych, zwaną macierzą wypłat. W najprostszym przypadku (w przypadku wyboru przez graczy strategii czystych) zasady gry są następujące.
Najpierw gracz 
wybiera numer wiersza i macierzy wypłat, a następnie gracz 
wybiera numer kolumny j. Element 
oznacza sumę, którą gracz 
płaci graczowi 
na zakończenie rozgrywki. Dopuszczamy oczywiście, że elementy 
mogą być ujemne i wówczas oznaczają, że 
płaci graczowi 
kwotę -
.
Dyskusja na temat wyboru strategii czystych przez graczy
Zgodnie ze sformułowanym we wstępie podstawowym zagadnieniem teorii gier, jedynym celem graczy jest maksymalizacja ich wygranych. Jeśli nie będziemy uwzględniali pomyłek graczy w trakcie rozgrywki, to przyjmiemy za naturalny następujący wybór strategii przez graczy 
i 
. Jeśli gracz 
wybierze wiersz i, to wygra co najmniej 
Ponieważ gracz 
wybiera numer wiersza, więc może wybrać takie i, które maksymalizuje jego wygraną: 
Stosując powyższą strategię gracz 
może wygrać co najmniej
Jeśli gracz wybierze strategię j, to w najgorszym przypadku może przegrać Ale gracz 
może wybrać taką strategię j, która minimalizuje jego przegraną: 
Stosując taką strategię, gracz 
może nie dopuścić, aby gracz 
wygrał więcej niż
w grach macierzowych mówimy, że gracz 
jest graczem maksymalizującym (wygraną) a gracz 
graczem minimalizującym (przegraną). Można wykazać, że zawsze zachodzi nierówność
.
Zad. 3.1. Wyznaczyć optymalne strategie czyste graczy dla gry macierzowej o następującej macierzy wypłat
3.2. Strategie mieszane
Przez strategię mieszaną gracza 
rozumiemy wektor
,
taki, że .
Przez strategię mieszaną gracza 
rozumiemy wektor
taki, że .
Elementy oraz można interpretować jako częstości z jakimi gracz 
wybiera i-ty wiersz a gracz 
j-tą kolumnę w serii rozgrywek gry macierzowej.
Wielkość wygranej gracza 
określa funkcja wypłaty (nadzieja matematyczna)
.
Rozwiązaniem gry macierzowej nazywamy parę strategii mieszanych
, ,
i taką liczbę rzeczywistą v, że
dla wszystkich strategii czystych j=1,2,...,n ,
dla wszystkich strategii czystych i=1,2,...,m .
Strategie nazywamy strategiami optymalnymi a v wartością gry.
Zasadnicze twierdzenie gier macierzowych
Dla każdej gry macierzowej istnieją i są sobie równe. Innymi słowy każda gra macierzowa ma rozwiązanie.
Uwaga. Za pomocą modelu programowania liniowego można wyznaczyć rozwiązanie gry macierzowej.
Zad. 3.2. Znaleźć rozwiązanie gry macierzowej o następującej macierzy wypłat
.
Zad. 3.3. Znaleźć rozwiązanie gry macierzowej o następującej macierzy wypłat
.
Zad. 3.4. Znaleźć rozwiązanie gry macierzowej o następującej macierzy wypłat
.
3.3. Gry z naturą
Gry z naturą są grami dwuosobowymi o sumie zero, w których przeciwnik (natura) nie podejmuje decyzji w trakcie gry.
Przykład 3.1. Rolnik ma wybrać jeden z trzech możliwych terminów t1, t2, t3 zasiewu zbóż. Wielkość plonów z hektara zależy od terminu zasiewu i stanu pogody. Zostały one zestawione w poniższej tabeli (w której wyróżniono 4 stany pogody S1, S2, S3, S4).
Terminy |
Stany pogody |
|||
zasiewów |
S1 |
S2 |
S3 |
S4 |
t1 |
21 |
15 |
32 |
16 |
t2 |
28 |
20 |
10 |
20 |
t3 |
13 |
27 |
25 |
15 |
Należy wspomóc rolnika w podjęciu decyzji o wyborze terminu zasiewu zbóż.
Wyboru można dokonać w oparciu o jedno z poniższych kryteriów.
Kryterium Walda
Zakładamy, że zajdą warunki najbardziej niekorzystne dla podejmującego decyzję. Dlatego optymalna decyzja i jest wybierana według reguły minmax. Odnośnie przykładu 1:
Następnie wybieramy
.
Ostatecznie wybieramy termin pierwszy (t1) gwarantując sobie wydajność z hektara co najmniej 15 kwintali.
Kryterium Hurwicza
Określa się arbitralnie współczynnik ostrożności a następnie wybiera się strategię i, dla której największa jest wartość
Przyjmując w przykładzie 1 kolejno mamy:
Następnie wybieramy
.
Ostatecznie wybieramy termin pierwszy (t1) spodziewając się osiągnięcia wydajności 18.4 kwintali z hektara..
Kryterium Bayesa
Zakładamy, że wszystkie stany z natury są jednakowo prawdopodobne. Zatem najlepszą strategią jest ta strategia i, która daje największą średnią arytmetyczną wygranych, tzn.
.
Dla przykładu 1 mamy
Następnie wybieramy
.
Ostatecznie wybieramy termin pierwszy (t1) oczekując wydajności 21.0 kwintali z hektara.
Zad. 3.5. Trzy typy hamulców 
,
,
podawano próbom w czterech rodzajach warunków drogowych 
,
,
,
. Procent zadowalających prób podano w poniższej tabeli
|
Rodzaj warunków drogowych |
|||
Rodzaj hamulców |
|
|
|
|
|
85 |
77 |
85 |
74 |
|
88 |
70 |
90 |
78 |
|
81 |
65 |
92 |
80 |
Wybrać do produkcji jeden z trzech rodzajów hamulców
przyjmując, że w trakcie eksploatacji będą występowały warunki zbliżone do najbardziej niekorzystnych,
przyjmując, że w trakcie eksploatacji wystąpienie każdego rodzaju warunków drogowych jest jednakowo prawdopodobne.
Skomentować podane rozwiązania.
13
