Deterministyczne Modele
Badań Operacyjnych Egzamin, II termin
Jesień 2011 14 lutego 2012
Imię, nazwisko i numer indeksu:
Zadanie 1 2 A
ącznie
Punkty do zdobycia 10 15 25
Punkty uzyskane
1. (Uczta na Wawelu) Książę Krak postanowił uczcić uratowanie Baltazara Gąbki
przez Smoka Wawelskiego i jego kompanów wyprawieniem wystawnej kolacji. Bar-
tolini Bartłomiej herbu Zielona Pietruszka otrzymał zadanie przygotowania odpo-
wiedniego menu dla każdego z gości: księcia Kraka, Smoka Wawelskiego i Baltazara
Gąbki. Nadworny kuchmistrz postanowił ograniczyć się jedynie do dwóch posiłków:
pieczonej jagnięciny i żabich udek. W ciągu godziny pracy Bartolini jest w stanie
przyrządzić 3 kg jagnięciny albo 1 kg żabich udek. Kolacja musi być przygotowana
według określonych zasad. Wiadomo, że:
1. Bartolini może poświęcić co najwyżej 10 godzin na przygotowanie uczty;
2. według dworskiej etykiety książę Krak musi zjeść łącznie co najmniej o 50%
więcej niż Baltazar Gąbka. Ponadto, nie może dojść do sytuacji, w której
prof. Gąbka zje więcej francuskich przysmaków niż książę;
3. Smok Wawelski nie może zjeść więcej każdego z posiłków niż pozostali goście
łącznie;
4. według diety nadwornego astrologa Onufrego Arkadiusza Paralaksy optymalna
dieta dla prof. Gąbki to łączna konsumpcja 2 kg uczty i odpowiednio 2.5 kg
w przypadku księcia Kraka. Jakiekolwiek odstępstwo, niezależnie czy w posta-
ci niedoboru czy nadmiaru, od optymalnego planu żywieniowego jest wysoce
niewskazane;
5. w celu uniknięcia kontrowersji i posądzenia przez lud o zbyt wystawne życie
księcia, łączna ilość żabich udek musi stanowić co najwyżej połowę spożywanej
jagnięciny.
Dla księcia Kraka najważniejsze są dwa cele: 1. nagrodzenie Smoka Wawelskiego
możliwie największą porcją jedzenia (dla smoka liczy się łączna ilość spożywanego
pokarmu, a nie proporcje); 2. konsumpcja Kraka i Gąbki powinna jak najmniej
odbiegać od optymalnej diety w jakąkolwiek ze stron. Cel 1. jest o 50% ważniejszy niż
cel 2. Zaproponuj optymalne menu dla każdego z gości mając na uwadze spełnienie
ograniczeń 1 5.
(1p.) (a) Zdefiniuj zmienne decyzyjne.
(4p.) (b) Podaj warunki ograniczające zadania w postaci ograniczeń liniowych.
(3p.) (c) Zdefiniuj funkcję celu rozważanego problemu w postaci funkcji liniowej.
(2p.) (d) Podaj optymalne menu dla każdego z bohaterów.
2. (Top secret) Wywiad MI6 dysponuje mapą tras dostaw pomiędzy punktami przesy-
łowymi przedstawioną na rysunku poniżej. Tabelka poniżej podaje przepustowość
każdej części trasy (w liczbie przesyłek), koszt przesłania jednej przesyłki oraz praw-
dopodobieństwo przechwycenia przesyłki przez wrogi wywiad.
Dla każdego z poniższych punktów podaj funkcję celu i ograniczenia oraz znajdz
za
pomocą programowania liniowego:
(4p.) (a) najtańszą drogę przesłania 1 przesyłki z punktu A do punktu B (wraz z min
kosztem).
(3p.) (b) najtańszą drogę przesłania 5 przesyłek z punktu A do punktu B (wraz z min
kosztem).
(3p.) (c) największą liczbę przesyłek, które mogą być przesłane z punktu A do B (mak-
symalny przepływ).
(5p.) (d) najmniej awaryjną ścieżkę od A do B: prawdopodobieństwa przechwycenia są
niezależne dla różnych łuków na trasie (wskazówka: przyjmij, że przesyłasz
jedną przesyłkę; iloczyn prawdopodobieństw to to samo co suma logarytmów
prawdopodobieństw; przyjmij -ln(1 - pi) jako koszt dla łuku i, pi oznacza
prawdopodobieństwo przechwycenia przesyłki na łuku i; po wyliczeniu opty-
malnej wartości funkcji celu f można przejść z powrotem na prawdopodobień-
stwo przejścia przesyłki bez przechwycenia za pomocą e-f ).
Page 2
Page 3
Page 4