dr hab. Zbigniew Świtalski, prof. UZ

Wydział Matematyki, Informatyki i Ekonometrii

Uniwersytet Zielonogórski

BADANIA OPERACYJNE 2

(przykładowe zadania egzaminacyjne)

1. Spółdzielnia mieszkaniowa zamierza zbudować osiedle mieszkaniowe. Przygotowano projekty trzech rodzajów budynków: 3-kondygnacyjny (B1), 4-kondygnacyjny (B2)
   i 7-kondygnacyjny (B3). W budynku typu B1 zaprojektowano 6 mieszkań typu M2,
   10 mieszkań M3 i 6 mieszkań M4. W budynku B2 znajduje się 6 mieszkań M2,
   8 mieszkań M3, 10 mieszkań M4 i 6 mieszkań M5, a w budynku B3 - 10 mieszkań M2, 15 mieszkań M3, 10 mieszkań M4 i 15 mieszkań M5. Mieszkanie M2 ma powierzchnię 36 m², M3 - 48 m², M4 - 60 m², M5 - 80 m². Koszt budowy 1 m²
   w budynku B1 wynosi 3 tys. zł, w budynku B2 - 2,5 tys. zł, a w budynku B3 -
   2 tys. zł. Należy wybudować co najmniej 300 mieszkań, przy czym co najmniej 30% wszystkich mieszkań ma być typu M3 oraz co najmniej 30% - typu M4. Ze względów architektonicznych liczba budynków typu B3 nie może przekraczać 20% liczby wszystkich budynków. Należy określić liczbę budynków poszczególnych rodzajów, które należy wybudować, tak aby łączny koszt budowy był minimalny.

1. Sformułuj przedstawiony problem jako zadanie programowania dyskretnego. Określ zmienne decyzyjne, zapisz ograniczenia w postaci algebraicznej
   i podaj postać funkcji celu.

2. Wskaż przynajmniej dwie metody, za pomocą których można byłoby rozwiązać podane zadanie.

3. Udowodnij, że plan optymalny musi uwzględniać budowę przynajmniej jednego budynku B1.

4. Udowodnij, że jeśli liczba mieszkań M4 w budynku B2 zmniejszy się do
   8 (przy niezmienionych pozostałych parametrach), to podane zadanie nie ma rozwiązania.

2. Urządzenia U1, U2, U3 i U4 wymagają naprawy. Każde z urządzeń może być naprawiane w jednym z zakładów Z1, Z2, Z3 i Z4, przy czym w jednym zakładzie może być naprawiane tylko jedno urządzenie. Koszty naprawy poszczególnych urządzeń w poszczególnych zakładach (w tys. zł) podane są w tabeli

	U1	U2	U3	U4
Z1	7	5	10	8
Z2	8	4	12	7
Z3	6	3	11	6
Z4	9	5	10	8

Chcemy oddać urządzenia do naprawy tak, aby łączne koszty wszystkich napraw były

minimalne.

1. Sformułuj przedstawiony problem jako zadanie programowania dyskretnego.

Określ zmienne decyzyjne, zapisz ograniczenia w postaci algebraicznej i podaj postać funkcji celu.

2. Wskaż przynajmniej dwie metody, za pomocą których można byłoby

rozwiązać podane zadanie.

3. Załóżmy, że nakładamy dodatkowe ograniczenia:

1. Łączne koszty naprawy urządzeń U1 i U2 nie mogą przekroczyć
   11 tys. zł

2. Urządzenie U3 może być naprawiane tylko w zakładzie Z1 lub Z2.

Zapisz te ograniczenia w postaci algebraicznej.

3. Podany graf przedstawia sieć transportową. Liczby przy łukach oznaczają

przepustowości poszczególnych odcinków sieci.

1. Wyznacz maksymalny przepływ przez tę sieć. Określ wartość tego przepływu. Przedstaw kolejne kroki algorytmu. Wskaż ścieżki nasycone i nienasycone.

2. Jak wpłynie na rozwiązanie tego zadania zmniejszenie przepustowości wszystkich łuków na ścieżce (1, 3, 6, 8) o jedną jednostkę ?

4

2 5

15 8 1 12

8 6 12

1 3 6 8

10 1 3 11

6

• 
  7

4. Dane jest przedsięwzięcie składające się z czynności A - L. Czasy trwania czynności

(w dniach) oraz czynności bezpośrednio poprzedzające daną czynność podane są w

tabeli:

Czynność	Czynn. bezp. poprz.	Czas	Czynność	Czynn. bezp. poprz.	Czas
A	----------	17	G	A,E	4
B	----------	12	H	A,E	4
C	----------	6	I	A,E,F	4
D	A	2	K	D,G	12
E	B	5	L	D,G,H,I	20
F	C	6

1. Narysuj graf tego przedsięwzięcia (w konwencji „czynności - łuki”).

2. Wyznacz najkrótszy czas trwania przedsięwzięcia.

3. Wyznacz ścieżki krytyczne oraz luzy dla zdarzeń i czynności.

4. Narysuj harmonogram Gantta.

5. Załóżmy, że czynności G,H,I jesteśmy w stanie przyspieszyć o 1 dzień. Jak wpłynie to na najkrótszy czas trwania przedsięwzięcia? Czy zmieni się wtedy zbiór ścieżek krytycznych?

5. Komiwojażer chce odwiedzić 4 miasta: M1, M2, M3 i M4, wyjeżdżając z miasta M1

i przejeżdżając przez każde miasto dokładnie raz. Macierz odległości między miastami jest nastepująca:

∞ 7 2 4

3 ∞ 3 6

9 1 ∞ 5

2 6 4 ∞

1. Stosując algorytm Little'a wyznacz najkrótszą drogę komiwojażera.

2. O ile wydłuży się najkrótsza droga, jeśli założymy, że miasto M4 powinno być odwiedzone bezpośrednio po mieście M3 oraz, że bezpośredni przejazd z M2 do M3 jest niemożliwy?

6. Kandydaci A,B,C,D chcą się dostać do szkół X,Y,Z. Limity dla szkół są następujące:

l(X) = 2, l(Y) = 1, l(Z) = 1. Preferencje kandydatów i szkół mają postać : A: YZX

B: ZXY, C: ZYX, D: YXZ, X: CDBA, Y: BCAD, Z: ADBC.

1. Stosując algorytm Gale'a-Shapleya znajdź optymalny przydział kandydatów

do szkół (korzystny dla kandydatów).

2. Czy przydział ten zmieni się, jeśli zastosujemy algorytm korzystny dla szkół?

3. Czy istnieją inne przydziały stabilne oprócz tych wyznaczonych w punktach a) i b) ?

4. Czy zwiększenie limitów w szkołach Y i Z wpłynie na zmianę rozwiązania w punkcie a) ?

2

---