1 DMBO Dualność i gry
2 Problem pakowania plecaka – ilustracja dualnościZłodziej napada na magazyn z plecakiem. Plecak nie może być zbyt ciężki, bo złodziej go nie uniesie. W magazynie znajduje się dużo dobrze podzielnych towarów np. złoto, srebro, pył diamentowy. Złodziej chce zapełnić plecak najbardziej cennymi towarami. Jak zdecyduje co wziąć do plecaka?
3 Model Parametry: Zmienne decyzyjne: Funkcja celu: Ograniczenia:W – maksymalna waga plecaka N – ilość towarów w magazynie wi – waga dobra i vi – wartość dobra i Zmienne decyzyjne: xi – jak dużo towaru i włożyć do plecaka (udział całości tego co jest w magazynie) Funkcja celu: Maksymalizuj wartość towarów Ograniczenia: (a) Złodziej nie może wziąć więcej danego towaru niż jest w magazynie. Złodziej nie uniesie więcej niż plecak i siły pozwolą. Złodziej nie może ukraść ujemnej ilości towarów (jeśli jest złodziejem)
4 Model Problem można zatem sformułować jako ZPL: Max
5 Przykład problemu prymalnego: Problem złodziejaPodstawmy N=3, W=4, w=(2,3,4) i v=(5,20,3) złoto, diamenty i srebro. max p.w. Rozwiązanie problemu złodzieja: (x1,x2,x3)=(0.5, 1, 0) Wartość funkcji celu: 22.5
6 Analiza Tylko jeden towar (złoto) jest wybrany w części ułamkowej. Jest to ogólna zasada w problemach z pakowaniem plecaka z N towarami. Intuicja: Optymalne rozwiązanie w tym przykładzie jest jednoznaczne. Aby jednoznacznie wyznaczyć 3 niewiadome, potrzebujemy 3 równania liniowe. Czyli przynajmniej 3 nasze ograniczenia muszą być spełnione w postaci równości. Jedno ograniczenie to waga plecaka, ale pozostałe dwa dotyczą ilości towarów 0≤xi≤1. Zatem tylko jeden towar może być wybrany w postaci ułamkowej w optimum.
7 Syndyk wykupuje złodziejaPrzypuśćmy, że syndykat przestępczy chce wykupić skradzione towary od złodzieja. Proponują ceny y1 za złoto, y2 za diamenty, y3 za srebro oraz y4 za kilogram plecaka. Ale złodziej może użyć 2 kilogramy pojemności plecaka i całe swoje złoto, aby wygenerować zysk 5 jednostek, czyli 2y4+y1 powinno wynosić przynajmniej 5. Podobnie w przypadku pozostałych towarów. Syndykat chciałby zminimalizować całkowitą cenę, którą płaci złodziejowi y1+y2+y3+4y4 Ceny powinny być nieujemne, inaczej złodziej nie sprzeda towarów i plecaka.
8 Przykład problemu dualnego: Problem syndykaProblem syndyka można zatem przedstawić następująco: min p.w. Rozwiązanie problemu syndyka: (y1,y2,y3,y4)=(0,12.5,0,2.5) Optymalna wartość funkcji celu: 22.5
9 Problem złodzieja: Jest równoważny: Ponieważ np. Przekształcamy: To jest równoważny problemowi syndyka:
10 Rozwiązanie problemu złodzieja: (x1,x2,x3)=(0.5, 1, 0) Optymalna wartość funkcji celu: 22.5 Rozwiązanie problemu syndyka: (y1,y2,y3,y4)=(0,12.5,0,2.5) ceny dualne Optymalna wartość funkcji celu: 22.5 PROBLEM DUALNY: SYNDYKA Microsoft Excel 14.1 Sensitivity Report Worksheet: [Workbook3]Sheet5 Report Created: 11/1/2011 4:06:44 PM Variable Cells Final Reduced Objective Allowable Cell Name Value Cost Coefficient Increase Decrease $B$2 y1 0.5 1 1E+30 $B$3 y2 12.5 $B$4 y3 $B$5 y4 2.5 4 Constraints Shadow Constraint Price R.H. Side $F$7 min cena za złoto 5 3.5 $F$8 min cena za diamenty 20 $F$9 min cena za srebro 10 3 7
11 Rozwiązanie problemu złodzieja: (x1,x2,x3)=(0.5, 1, 0) Optymalna wartość funkcji celu: 22.5 Rozwiązanie problemu syndyka: (y1,y2,y3,y4)=(0,12.5,0,2.5) ceny dualne Optymalna wartość funkcji celu: 22.5 PROBLEM PRYMALNY: ZŁODZIEJA Microsoft Excel 14.1 Sensitivity Report Worksheet: [Workbook3]Sheet1 Report Created: 11/1/2011 1:53:00 PM Variable Cells Final Reduced Objective Allowable Cell Name Value Cost Coefficient Increase Decrease $B$2 x1 0.5 5 3.5 $B$3 x2 1 20 1E+30 12.5 $B$4 x3 -7 3 7 Constraints Shadow Constraint Price R.H. Side $F$6 waga plecaka 4 2.5 $F$7 ilość x1 $F$8 ilość x2 $F$9 ilość x3
12 Gry o sumie zerowej W grach o sumie zerowej wypłaty sumują się do zera w każdym stanie Diagram przesunięć
13 Gry o sumie zerowej Minimax = maximin = wartość gryGra może mieć wiele punktów siodłowych
14 Gry o sumie zerowej Albo nie mieć ich wcaleJaka jest wartość gry w takim przypadku? Jeśli gra nie ma punktu siodłowego, trzeba wprowadzić strategie mieszane
15 Gry o sumie zerowej Jeśli jest więcej niż dwie strategie dla jednego gracza i gra nie ma punktu siodłowego, nie wiadomo, które strategie będą częścią optymalnej strategii mieszanej Niech mieszana strategia Kolumny będzie (x,1-x) Wypłata Wiersza dla każdej jego strategii
16 Gry o sumie zerowej Kolumna będzie wybierała x, aby zmaksymalizować „górną kopertę” (upper envelope)
17 Gry o sumie zerowej Przekształcamy w problem programowania liniowego
18 Studium przypadku: Teoria gier i dualnośćW latach pięćdziesiątych, Davenport studiował zachowanie rybaków w małej wiosce na Jamajce.
19 Twenty-six fishing crews in sailing, dugout canoes fish this area [fishing grounds extend outward from shore about 22 miles] by setting fish pots, which are drawn and reset, weather and sea permitting, on three regular fishing days each week … The fishing grounds are divided into inside and outside banks. The inside banks lie from 5-15 miles offshore, while the outside banks all lie beyond … Because of special underwater contours and the location of one prominent headland, very strong currents set across the outside banks at frequent intervals … These currents are not related in any apparent way to weather and sea conditions of the local region. The inside banks are almost fully protected from the currents. [Davenport 1960]
20 Jamajka
21 Strategie 26 drewnianych kanoe. Kapitanowie tych kanoe mają do dyspozycji 3 strategie połowu: IN – ustawić wszystkie kosze w zatokach OUT – ustawić wszystkie kosze na wodach odsłoniętych IN-OUT – część koszy w zatokach część na zewnątrz
22 Zalety i wady połowu na otwartym morzuDopłynięcie do łowiska zabiera więcej czasu, więc można postawić mniej koszy Jak prąd jest aktywny, powoduje duże zagrożenie dla koszy ustawionych na otwartym morzu Znosi znaczniki Uszkadza kosze podczas przesuwania Zmiany temperatury wody mogą zabijać ryby wewnątrz koszy ZALETY Ryby na łowiskach zewnętrznych są dużo lepszej jakości Jeśli jest ich dosyć, mogą wyprzeć ryby z łowisk wewnętrznych zupełnie z rynku Rybołóstwo na łowiskach zewnętrznych wymaga dużo lepszych kanoe Zazwyczaj ci, którzy łowią na łowiskach wewnętrznych kupują używane kanoe od tych, którzy łowią na łowiskach zewnętrznych Posiadanie lepszych kanoe daje dużo prestiżu, ponieważ ich kapitanowie dominują w corocznych wyścigach kanoe
23 Dane Davenport zebrał dane dotyczące średnich dziennych zysków w zależności od strategii połowu oraz obecności/nieobecności prądu Rybacy\Prąd Płynie Nie płynie IN 17,3 11,5 OUT -4,4 20,6 IN-OUT 5,2 17,0
24 Strategia OUT
25 1 Gra o sumie zerowej?? Nie ma punktu siodłowegoStrategia mieszana – załóżmy, że „złośliwy” prąd „stosuje” strategię „Płynę” z prawdopodobieństwem p1, „Nie płynę” z prawdopodobieństwem p2 Strategia rybaków: IN z prawd. q1, OUT z prawd. q2, IN-OUT z prawd. Q3 Dla każdego p rybacy wybierają strategię (q) z maksymalną wypłatą A „złośliwy” prąd wybiera p tak, aby rybacy zarobili jak najmniej
26 Rozwiązanie graficzne problemu prąduSolution: p=0.31 Optymalna strategia mieszana prądu
27 Podobnie w przypadku odwrotnym:Dla każdej strategii rybaków q, prąd „wybiera” taką, dla której rybacy zarobią najmniej: Rybacy natomiast będą się starali tak wybrać q, aby zmaksymalizować swoją wypłatę
28 Maxmin i minimax funkcja celu Strategia prądu p 1-p minimalizuj 13.310.31 0.69 Oczekiwana wypłata ze strategii wewnętrznej <= zewnętrznej 12.79 in-out prawdopodobieństwa 1.00 = funkcja celu Strategia rybaków q1 q2 q3 maksymalizuj 13.31 0.67 0.00 0.33 Oczekiwana wypłata prądu gdy: płynę >= nie płynę prawdopodobieństwa 1.00 =
29 Raport wrażliwości minimaxMicrosoft Excel 14.1 Sensitivity Report Worksheet: [maximinnowe.xlsx]minimax Report Created: 11/16/ :19:08 PM Variable Cells Final Reduced Objective Allowable Cell Name Value Cost Coefficient Increase Decrease $B$3 minimalizuj funkcja celu 1 1E+30 $C$3 minimalizuj p 0.3125 11.8 5.8 $D$3 minimalizuj 1-p 0.6875 Constraints Shadow Constraint Price R.H. Side $B$6 wewnętrznej funkcja celu 12.1 0.7 $B$7 zewnętrznej funkcja celu 0.525 $B$8 in-out funkcja celu 0.3 $B$9 prawdopodobieństwa funkcja celu
30 Raport wrażliwości maximinMicrosoft Excel 14.1 Sensitivity Report Worksheet: [maximinnowe.xlsx]maximin Report Created: 11/16/ :20:13 PM Variable Cells Final Reduced Objective Allowable Cell Name Value Cost Coefficient Increase Decrease $B$3 maksymalizuj funkcja celu 1 1E+30 $C$3 maksymalizuj q1 0.7 12.1 $D$3 maksymalizuj q2 -0.525 0.525 $E$3 maksymalizuj q3 0.3 Constraints Shadow Constraint Price R.H. Side $B$6 płynę funkcja celu 5.8 11.8 $B$7 nie płynę funkcja celu $B$8 prawdopodobieństwa funkcja celu
31 Prognoza i obserwacja Gra o sumie zerowej ObserwacjaNikt nie ryzykuje zastawiania koszy na zewnętrznych łowiskach Optymalna strategia rybaków: 67% IN, 33% IN-OUT [Oczekiwana wypłata: 13.31] Optymalna strategia prądu: 31% PŁYNIE, 69% NIE PŁYNIE Nikt nie ryzykuje zastawiania koszy na zewnętrznych łowiskach Strategia rybaków: 69% IN, 31% IN-OUT [Oczekiwana wypłata: 13.38] Prąd: 25% PŁYNIE, 75% NIE PŁYNIE Konkluzja Davenporta: rybacy są dobrze przystosowani Odkrycie Davenporta przez parę lat nie zostało zakwestionowane aż do momentu …
32 Prąd nie jest złośliwy Kozelka 1969 oraz Read, Read 1970 zauważyli, żePrąd nie dostosowuje swojej „strategii” do działań rybaków Dlatego rybacy powinni zastosować zasadę oczekiwanych zysków Oczekiwane zyski rybaków IN: x x 11.5 = 12.95 OUT: x (-4.4) x 20.6 = 14.35 IN-OUT: x x 17.0 = 14.05 Czyli wszyscy rybacy powinni łowić na zewnętrznych łowiskach Może jednak nie są zbyt dobrze przystosowani Rybacy\Prąd Płynie (25%) Nie płynie (75%) IN 17,3 11,5 OUT -4,4 20,6 IN-OUT 5,2 17,0
33 Prąd może być jednak złośliwyPrąd nie rozumuje, ale łowienie na otwartym morzu jest bardzo ryzykowne. Nawet jeśli prąd płynie ŚREDNIO 25% czasu, to jednak może płynąć częściej w danym roku. Załóżmy, że w jednym roku prąd płynie 35% czasu. Oczekiwana wypłata: IN: x x 11.5 = 13.53 OUT: x (-4.4) x 11.5 = 11.85 IN-OUT: x x 17.0 = Poprzez potraktowanie prądu jak złośliwego gracza rybacy GWARANTUJĄ sobie wypłatę przynajmniej 13.31, niezależnie od tego, jak często płynie prąd Rybacy płacą $1.05 składki ubezpieczeniowej Rzeczywisty (25%) Złośliwy (31%) 35% Gra o sumie 0 Rzcezywista 13.291 OUT 14.35 12.85 11.85
34 Skojarzenia http://mathsite.math.berkeley.edu/smp/smp.html x HelenaGosia Irena rowsums Dawid 1 Edward Filip colsums kompatybliność 0.5 0.75 2 2.5 1.5 funkcja celu 4.5