Deterministyczne Modele

Badań Operacyjnych

Jesień 2011

Egzamin, I termin

26 stycznia 2012

gr. ∝

Imię, nazwisko i numer indeksu:

Zadanie

1

2

3

Łącznie

Punkty do zdobycia

10

10

5

25

Punkty uzyskane

1. (Rycerz nieistniejący) Dzielny rycerz Agilulf wyrusza na ratunek wdowy Priscilli

i jej współtowarzyszek. Aby ratunek był możliwie najbardziej skuteczny musi czym

prędzej dostać się z posterunku (węzeł 1) do zamku, w którym więzione są niewiasty

(węzeł 10). Rysunek 1 przedstawia możliwe trasy przejścia.

(a)

(1p.)

Zdefiniuj zmienne decyzyjne.

(b)

(1p.)

Podaj funkcję celu rozważanego problemu.

(c)

(2p.)

Podaj warunki ograniczające zadania.

(d)

(3p.)

Podaj najkrótszą drogę do Priscilli.

(e)

(3p.)

W obszarze wyrażonym przez węzeł 9 grasuje stado niedźwiedzi. Przejście przez

ten obszar możliwe jest tylko przy wsparciu Gurdulu. Wizyta węzła 9 musi być

poprzedzona odwiedzeniem miejsca stacjonowania „giermka” wyrażonego przez

węzeł 4. Podaj proszę i krótko skomentuj nowy warunek programu uwzględ-

niający nowy postulat. Jaka jest nowa najkrótsza droga?

Rysunek 1: Możliwe drogi Agilulfa

1

4

10

2

12

3

10

7

20

10

9

5

5

6

17

9

5

12

10

4

8

22

22

3

10

14

12

2

16

4

8

17

2. (Dream Team) Trener Jacek chce wyselekcjonować 7 graczy do „drużyny marzeń.”

Ograniczył wybór do 10 graczy. Dla każdego gracza, Jacek zebrał i wyskalował odpo-

wiednio niektóre statystyki (1 najlepsze, 5 najgorsze) dotyczące graczy. Dodatkowo,

gracze mogą grać tylko na niektórych pozycjach. Pozycje, na których może grać każ-

dy z graczy oraz statystyki dotyczące asyst, punktów, obrony oraz zbiorek znajdują

się w tabelce poniżej.

Trener Jacek wie, ze aby stworzyć dobra drużynę pewne założenia musza być speł-

nione:

1. Przynajmniej dwóch graczy musi umieć grać na obronie, przynajmniej czterech

graczy musi umieć grać na ataku i przynajmniej dwóch graczy musi umieć grać

w pomocy

2. Maksymalny (czyli najgorszy) średni ranking dotyczący asyst, punktów, obro-

ny oraz zbiorek w drużynie 7 zawodników musi być lepszy niż 3 (pamiętaj 1

jest najlepszy, 5 jest najgorszy)

3. Jeśli gracz 4 i 6 grają razem, wtedy gracz 5 nie może być w drużynie. (Kwestie

dopasowania miedzy graczami)

4. Gracze 3 i 9 musza być wybrani razem, ponieważ, ze są najbardziej efektywni,

kiedy grają ze sobą (zatem albo obaj albo żaden nie powinien być wybrany)

5. Gracz 4 lub 3 (lub obaj) musza być wybrani, ponieważ są tymi, którzy przy-

ciągają fanów.

Przy tych ograniczeniach trener Jacek chce maksymalizować łączna zdolność punk-

towa „drużyny marzeń.”

(a)

(1p.)

Podaj zmienne decyzyjne problemu.

(b)

(1p.)

Zdefiniuj funkcje celu.

(c)

(3p.)

Zapisz ograniczenia 1, 2, 3, 4 i 5. Jakie jeszcze ograniczenia potrzebujesz?

(d)

(3p.)

Rozwiąż problem i podaj optymalne wartości zmiennych decyzyjnych i funkcji

celu.

(e)

(1p.)

Które ograniczenia 1-5 są wiążące a które nie?

(f)

(1p.)

Jeśli dodam dodatkowe ograniczenie, to czy optymalna wartość funkcji celu się

nie poprawi, czy nie pogorszy? (nie lepsza, czy nie gorsza zdolność punktowa).

Page 2

(g)

(3 (bonus))

Jakie ograniczenia nałożyłbyś/łabyś a jakie wyeliminował/ła, aby skorzystać z

własności unimodularności w tym problemie?

GRACZ  POZYCJA  ASYSTY  PUNKTY  ZBIÓRKI  OBRONA 

1 

O 

3 

4 

2 

1 

2 

P 

2 

1 

3 

4 

3 

O‐A 

4 

2 

2 

4 

4 

A‐P 

1 

3 

3 

1 

5 

O‐A 

5 

2 

1 

2 

6 

A‐P 

4 

1 

2 

3 

7 

O‐A 

3 

5 

3 

1 

8 

O‐P 

2 

3 

4 

1 

9 

A 

2 

2 

2 

5 

10 

O‐A 

3 

3 

1 

2 

Page 3

3.

(5p.)

(Najkrótsza droga) Rysunek 2 przedstawia graf, w którym łuki oznaczone są odle-

głością pomiędzy wierzchołkami. Znajdź najkrótszą drogę pomiędzy wierzchołkiem

A i H przy pomocy algorytmu Dijkstry: na grafie zaznacz kolejność rozwiązanych

wierzchołków.

Rysunek 2: Problem najkrótszej drogi

A

B

3

D

5

C

2

2

F

13

6

E

4

G

3

2

5

2

H

3

6

6

Page 4