lista 6.pdf

Badaniaoperacyjne-laboratorium,sem.letni2010/2011,lista6,PLC 1

Zadanie 1

Pewien amerykański bank chce rozszerzyć swoj¸a działalność na cz¸eść sta

nu, w którym jest aktualnie nieobecny. Rozpatrywany obszar składa si¸e z 20

regionów (patrz mapka).

Bank chce aby dla każdego obszaru był spełniony nast¸epuj¸acy warunek: albo

na tym obszarze znajduje si¸e oddział banku albo taki oddział znajduje si¸e na

obszarze bezpośrednio przyległym (uwaga: obszary 10 i 12 oraz 3 i 13 nie s¸a

przyległe). Gdzie należy wybudować oddziały banku alby ich liczba była naj

mniejsza?

Wskazówka: Należy zastosować zmienne 0 1, tj. X I = 1 jeżeli na Itym ob

szarze budujemy oddział i 0 w przeciwnym wypadku.

Zadanie 2

Samolottransportowymożezabraćpojednymładunkuzkażdegoz6typów.

Wagi, obj¸etości oraz zysk z przewozu podaje tabela:

Typ Waga Obj¸etość Zysk

1 5 1 400

2 8 9 750

3 3 6 600

4 2 5 550

5 1 7 400

6 4 8 900

Ładunek nie może ważyć wi¸ecej niż 21 i przekroczyć obj¸etości 20. Dodatko

we wymogi bezpieczeństwa powoduj¸a, że ładunek 1 nie może być przewożony

jednocześniezładunkiem 5 .Ponadto,jeżelizostaniezabranyładunek 4 tomusi

Badaniaoperacyjne-laboratorium,sem.letni2010/2011,lista6,PLC 2

być również zabrany ładunek 2 . Które typy ładunków należy zabrać aby zmak

symalizować zysk.?

Zadanie 3

Trenerzespołukoszykówkichcezestawićskładnamecz.Musidokonaćwybo

ru pi¸eciu spośródsiedmiu zawodników. Każdy zawodnik ma przypisane pozycje

na których może grać: O obrona, C centrum, A atak. Każdy gracz posiada

umiej¸etności w obronie, utrzymaniu piłki, rzutach i zbiórkach. Umiej¸etności te

s¸a oceniane w skali od 1 (słabo) do 3 (bardzo dobrze). Dane o zawodnikach

pokazane s¸a w poniższej tabeli:

zawodnik pozycja utrzymanie piłki rzuty zbiórki obrona

1 O

3 1 3

2 C

1 3 2

3 O,A 2

3 2 2

4 A,C 1

3 3 1

5 O,A 1

3 1 2

6 A,C 3

1 2 3

7 A,O 3

2 2 1

Zestawiony zespół musi spełniać nast¸epuj¸ace warunki: co najmniej 3 zawodni

ków musi potraﬁć grać w obronie, co najmniej 2 w ataku i co najmniej 1 w

centrum; średnie umiej¸etności drużyny w utrzymaniu piłki, rzutach i zbiórkach

musz¸a wynosić co najmniej 2; jeżeli gra zawodnik 3 to zawodnik 6 nie może

grać (ci gracze si¸e nie lubi¸a); jeżeli gra zawodnik 1 to musz¸a zagrać gracze 4 i

5 ; albo zawodnik 2 albo 3 musi zagrać. Zespół gra z trudnym rywalem dlatego

trener chce zmaksymalizować sumaryczn¸a umiej¸etność obronn¸a drużyny. Któ

rzy z zawodników powinni zagrać?

Zadanie 4

Pewna ﬁrma rozważa otwarcie hurtowni w czterech miastach: A , B , C i D .

Każda hurtownia może przyj¸ać 100 jednostek towaru w ci¸agu tygodnia. Tygo

dniowykosztobsługihurtowniwynosidlamiast A , B , C i D odpowienio:400$,

500$,300$,150$.Hurtownietemaj¸aobsługiwaćtrzyregiony,którychzapotrze

bowanietygodniowewynosiodpowiednio:80,70i40jednostek.Kosztywysłania

jednej jednostki towaru z hurtowni do regionu podane s¸a w poniższej tabeli:

region 1 region 2 region 3

A 20$ 40$ 50$

B 48$ 15$ 26$

C 26$ 35$ 18$

D 24$ 50$ 35$

Musz¸a być spełnione dodatkowe wymagania: jeżeli hurtownia zostanie otwarta

w mieście A to musi zostać otwarta hurtowania w mieście B ; można otworzyć

co najwyżej dwie hurtownie. Które hurtownie należy otworzyć aby zaspokoić

popyt regionów i zminimalizować ł¸aczny koszt tygodniowy?

Badaniaoperacyjne-laboratorium,sem.letni2010/2011,lista6,PLC 3

Zadanie 5 Zagadnienie komiwojażera(TSP)

a) Dla zagadnienia komiwojażera o 6 (lub więcej) węzłach i dowolnej macierzy

odległości (przyjmij,że odległości między miastami są liczbami całkowitymi z

przedziału [1,100]) zapisz model całkowitoliczbowy i rozwiąż go.

b) Porównaj to rozwiązanie z rozwiązaniem heurystki (2optymalnych tras) za

programowanej w STORMie.

Opcja: Distance Networks Module.

Wprowadzamy dane o macierzy odległości:

Number of nodes: 6 (lub więcej wierzchołków),

Distance matrix type (SYM/ASYM): ASYM,

i wpisujemy odległości między miastami w macierzy.

Po wpisaniu odległości wybieramy opcję: Traveling salesperson’s tour .

c)Następnierozwiążtozagadnieniemetodąpodanąnawykładzie,tj.rozwiązu

jącciągproblemówcałkowitoliczbowychzktórychkażdyproblemkonstruujemy

dodając do ograniczeń modelu całkowitoliczbowego problemu poprzedniego do

datkowe ograniczenia eliminujące możliwość powstania cykli (tyle dodatkowych

ograniczeń ile podcykli zawierało rozwiązanie optymalne problemu poprzednie

go. Podcykl eliminujemy dopisując ograniczenie, które jest nierównością ”‘ ”’

której lewa strona jest sumą zmiennych tworzących ten podcykl a prawa strona

jest liczbą zmiennych tego cyklu minus 1). Obliczenia kontynujemy do momen

tu otrzymania rozwiązanie nie zawierającego podcyklu. To rozwiązanie jest już

rozwiązniem optymalnym.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: