dmbo proposal

background image

Deterministyczne Modele

Badań Operacyjnych

Jesień 2011

Egzamin, I termin

26 stycznia 2012

gr. <

i

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.)

Zdefiniuj 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ł 7. 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

7

32

2

2

3

8

4

19

10

9

8

4

9

5

18

10

12

5

14

22

22

3

3

6

7

12

2

6

2

7

8

background image

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, że aby stworzyć dobra drużynę pewne założenia muszą 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ż 4 (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ż, że 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ć łączną zdolność punk-

towa „drużyny marzeń.”

(a)

(1p.)

Podaj zmienne decyzyjne problemu.

(b)

(1p.)

Zdefiniuj funkcję 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 sa 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

background image

(g)

(3 (bonus))

Jakie ograniczenia naloż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 

O‐A 

A‐P 

O‐A 

A‐P 

O‐A 

O‐P 

10 

O‐A 

Page 3

background image

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


Wyszukiwarka

Podobne podstrony:
dmbo proposal2
Amendend proposal com 93 225
A propos tekstu dra Jaśkowskiego list prof. Majewskiej, Zdrowie i ekologia, Szczepionki
proposals
Propos de littérature
hot proposal
Six Explanatory Propositions
Proposal Meg Cabot
wywiadŚrodowiskowycałej mojej grupy, !!izie!!!A propos 5, A propos 5
unit proposal
A propos wyników z interny., II rok, Interna
dmbo II termin
JM proposal
cohesion proposal pl
Proposicion, hiszpanski, gramatyka opisowa
A propos A1 Ćwiczenia CD pobieranie

więcej podobnych podstron