BO2 - PRZYKL ZAD EGZ.doc

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 m2, M3 – 48 m2, M4 – 60 m2, M5 – 80 m2. Koszt budowy 1 m2
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.

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

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

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

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

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

            minimalne.

a)      Sformułuj przedstawiony problem  jako  zadanie  programowania  dyskretnego.

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

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

rozwiązać   podane   zadanie.

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

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

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

4                                                                 

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: