Badania operacyjne - kolokwium

Kolokwium z badań operacyjnych nr 2 – zestaw A
Imię i nazwisko: ……………………………………………………
Zadanie 1
Dane jest zadanie programowania wielokryterialnego:
f 1 ( x1 , x 2 ) = x1 + 3x 2 → max
f 2 ( x1 , x 2 ) = 3 x1 + x 2 → max
x1 + 2 x 2 ≤ 12
2 x1 + x 2 ≤ 12
x1 , x 2 ≥ 0
Znaleziono następujące optima cząstkowe: f 1 max (0,6) = 18 , f 2 max (6,0) = 18 .
A. Sformułuj odpowiednie zadanie programowania celowego jeżeli wiadomo, że wagi dla obu
kryteriów cząstkowych są równe.
B. Zastosuj odpowiednie podstawienie i sformułuj zadanie pomocnicze.
C. Rozwiązanie zadania pomocniczego ma postać: x1 = 4 , x 2 = 4 , y1 = 0 , y 2 = 0 , z1 = 2 , z2 = 2 .
Podaj interpretację wartości zmiennych pomocniczych.
Zadanie 2
Dane jest zadanie programowania całkowitoliczbowego:
5 x1 + 4 x 2 + 3x 3 → max
2 x1 + 3 x 2 + 2 x 3 ≤ 7
4 x1 + 3 x 2 + 3 x3 ≤ 8
x1 , x 2 , x3 ≥ 0,
x1 , x 2 , x 3 ∈ Z
Otrzymano następujące rozwiązanie dla jednego z podzbiorów:
cj
5
4
3
0
cB
xB
xj
x1
x2
x3
x4
4
x2
0
1
1/3
2/3
5
x1
1
0
1
-1/2
A. Zdefiniuj odpowiedni podział.
0
x5
-1/3
1/2
B. Wyznacz nowe rozwiązania dla obu podzbiorów, lub wykaż że nie istnieją:
bi
2
1/2
Zadanie 3
Dzienny popyt na napój owocowy w pewnym barze (w litrach) zależy od pogody i opisany jest
funkcją gęstości:
0,01; x ∈ 0;100

f (x ) = 
0; x ∉ 0;100

Zakładając, że cena wyprodukowania 1 litra napoju wynosi 2 zł, a sprzedawany jest po 1 zł z kubek
(0,2 l), ustal ile litrów napoju dziennie powinien produkować właściciel baru, żeby minimalizować
swoją oczekiwaną stratę. Napój jest produkowany ze świeżych owoców, więc w razie nadprodukcji
właściciel traci całość. Wskazówka: za stratę z tytułu niedoboru przyjmij koszt utraconych korzyści
(czyli zysk).
A. Wyznacz funkcję oczekiwanej straty:
B. Wyznacz optymalną wielkość produkcji i odpowiadająca jej stratę:
Zadanie 4
Wyznacz najkrótszą drogę z a do f w sieci zdefiniowanej tabelą:
Krawędź
Długość
ab
10
bd
10
be
10
ca
-4
cd
8
ce
10
df
18
ec
-10
fe
-14
Kolokwium z badań operacyjnych nr 2 – zestaw B
Imię i nazwisko: ……………………………………………………
Zadanie 1
Dane jest zadanie programowania wielokryterialnego:
f 1 ( x1 , x 2 ) = x1 + 3 x 2 → min
f 2 ( x1 , x 2 ) = 3x1 + x 2 → min
x1 + 2 x 2 ≥ 12
2 x1 + x 2 ≥ 12
x1 , x 2 ≥ 0
Znaleziono następujące optima cząstkowe: f1min (12,0) = 12 , f 2 min (0,12) = 12 .
A. Sformułuj odpowiednie zadanie programowania celowego jeżeli wiadomo, że wagi dla obu
kryteriów cząstkowych są równe.
B. Zastosuj odpowiednie podstawienie i sformułuj zadanie pomocnicze.
C. Rozwiązanie zadania pomocniczego ma postać: x1 = 4 , x 2 = 4 , y1 = 4 , y2 = 4 , z1 = 0 , z 2 = 0 .
Podaj interpretację wartości zmiennych pomocniczych.
Zadanie 2
Dane jest zadanie programowania całkowitoliczbowego:
5 x1 + 4 x 2 + 3x 3 → max
2 x1 + 3 x 2 + 2 x3 ≤ 7
4 x1 + 3 x 2 + 3 x3 ≤ 8
x1 , x 2 , x 3 ≥ 0
x1 , x 2 , x 3 ∈ Z
Otrzymano następujące rozwiązanie dla jednego z podzbiorów:
cj
5
4
3
0
cB
xB
xj
x1
x2
x3
x4
4
x2
0
1
5/3
0
5
x1
1
0
0
0
0
x4
0
0
-2
1
A. Zdefiniuj odpowiedni Kolokwium nr 2 z badań operacyjnych – zestaw A
Imię i nazwisko: ………………………………………………………… Grupa: ……………
Zadanie 1
Dane jest zadanie programowania kwadratowego:
(0) f ( x1 , x 2 ) = ( x1 − 5) 2 + ( x 2 − 5) 2 → min,
(1) x1 + x 2 ≤ 2,
(2) x1 , x 2 ≥ 0.
a) Utwórz zadanie dualne do danego.
b) Zapisz warunki KKT dla tego zadania.
c) Sprawdź, czy te warunki są spełnione w punkcie (1, 1).
d) Sprawdź, czy punkt (1, 1) jest punktem optimum.
Zadanie 2
Za pomocą algorytmu Newtona z regulowaną długością kroku wyznacz minimum funkcji:
2
f ( x1 , x 2 ) = 2 x12 + 4 x1 x 2 + 6 x 2 − 4 x1 + 8 x 2 → min
Za punkt startowy przyjmij (0, 0).
Zadanie 3
Dane jest zadanie programowania wielokryterialnego:
f 1 ( x1 , x 2 ) = x1 + 3x 2 → max
f 2 ( x1 , x 2 ) = 3 x1 + x 2 → max
x1 + 2 x 2 ≤ 12
2 x1 + x 2 ≤ 12
x1 , x 2 ≥ 0
Znaleziono następujące optima cząstkowe: f 1 max (0,6) = 18 , f 2 max (6,0) = 18 .
a) Sformułuj odpowiednie zadanie programowania celowego jeżeli wiadomo, że wagi dla obu
kryteriów cząstkowych są równe.
b) Zastosuj odpowiednie podstawienie i sformułuj zadanie pomocnicze.
c) Rozwiąż zadanie pomocnicze za pomocą dodatku Solver. Podaj interpretację wartości zmiennych
pomocniczych.
Zadanie 4
Wyznacz najkrótszą drogę ze źródła do ujścia w następującej sieci:
Łuk
( a, b)
(a, c)
( b, d)
(b, e)
(c, d)
(c, e)
(d, f) (e, c)
Waga
6
7
6
6
5
7
6
–7
Podaj kolejne wartości cech węzłów (w tabeli albo na grafie) oraz kolejne postacie kolejki.
(e, f)
6
BRUDNOPIS
Kolokwium nr 2 z badań operacyjnych – zestaw B
Imię i nazwisko: ………………………………………………………… Grupa: ……………
Zadanie 1
Dane jest zadanie programowania kwadratowego:
(0) f ( x1 , x 2 ) = ( x1 − 8) 2 + ( x 2 − 8) 2 → min,
(1) x1 + x 2 ≤ 8,
( 2 ) x1 , x 2 ≥ 0 .
a) Utwórz zadanie dualne do danego.
b) Zapisz warunki KKT dla tego zadania.
c) Sprawdź, czy te warunki są spełnione w punkcie (4, 4).
d) Sprawdź, czy punkt (4, 4) jest punktem optimum.
Zadanie 2
Za pomocą algorytmu Newtona z regulowaną długością kroku wyznacz minimum funkcji:
2
f ( x1 , x 2 ) = 3x12 + 6 x1 x 2 + 9 x 2 − 6 x1 + 12 x 2 → min
Za punkt startowy przyjmij (0, 0).
Zadanie 3
Dane jest zadanie programowania wielokryterialnego:
f 1 ( x1 , x 2 ) = x1 + 3 x 2 → min
f 2 ( x1 , x 2 ) = 3x1 + x 2 → min
x1 + 2 x 2 ≥ 12
2 x1 + x 2 ≥ 12
x1 , x 2 ≥ 0
Znaleziono następujące optima cząstkowe: f1min (12,0) = 12 , f 2 min (0,12) = 12 .
a) Sformułuj odpowiednie zadanie programowania celowego jeżeli wiadomo, że wagi dla obu
kryteriów cząstkowych są równe.
b) Zastosuj odpowiednie podstawienie i sformułuj zadanie pomocnicze.
c) Rozwiąż zadanie pomocnicze za pomocą dodatku Solver. Podaj interpretację wartości zmiennych
pomocniczych.
Zadanie 4
Wyznacz najkrótszą drogę ze źródła do ujścia w następującej sieci:
Łuk
( a, b)
(a, c)
( b, d)
(b, e)
(c, d)
(c, e)
(d, f) (e, c)
Waga
4
5
4
4
3
5
4
–5
Podaj kolejne wartości cech węzłów (w tabeli albo na grafie) oraz kolejne postacie kolejki.
(e, f)
4
BRUDNOPIS
Kolokwium nr 2 z badań operacyjnych – zestaw C
Imię i Kolokwium nr 2 z badań operacyjnych – zestaw G
Imię i nazwisko: WZÓR Grupa: WSZYSTKIE
Zadanie 1
Dane jest zadanie programowania nieliniowego:
2
(0) f ( x1 , x2 ) = x12 − 2 x1 x2 + 5 x 2 − 6 x1 − 10 x2 → min,
(1) x1 + 2 x2 ≤ 12,
(2) 2 x1 + x2 ≤ 12,
(3) x1 , x 2 ≥ 0;
a) Zapisz zadanie w postaci standardowej dla metody kierunków dopuszczalnych Zoutendijka.
ଶ
ଶ
ሺ0ሻ݂ሺ‫ݔ‬ଵ , ‫ݔ‬ଶ ሻ = ‫ݔ‬ଵ − 2‫ݔ‬ଵ ‫ݔ‬ଶ + 5‫ݔ‬ଶ − 6‫ݔ‬ଵ − 10‫ݔ‬ଶ → ݉݅݊
ሺ1ሻ‫ݔ‬ଵ + 2‫ݔ‬ଶ ≤ 12
ሺ2ሻ2‫ݔ‬ଵ + ‫ݔ‬ଶ ≤ 12
ሺ3ሻ − ‫ݔ‬ଵ ≤ 0
ሺ4ሻ − ‫ݔ‬ଶ ≤ 0
b) Aktualnym rozwiązaniem jest (0, 6). Podaj postać zadania, które pozwoli wyznaczyć kierunek
poprawy. Wyznacz kierunek poprawy.
Warunki wiążące: (1), (3).
∇݂ሺ‫ݔ‬ଵ , ‫ݔ‬ଶ ሻ = ሺ2‫ݔ‬ଵ − 2‫ݔ‬ଶ − 6, −2‫ݔ‬ଵ + 10‫ݔ‬ଶ − 10ሻ் , ∇݂ሺ0,6ሻ = ሺ−18,50ሻ்
Zadanie pomocnicze:
ሺ0ሻ݃ሺ݀ଵ , ݀ଶ ሻ = −18݀ଵ + 50݀ଶ → ݉݅݊
ሺ1ሻ2݀ଵ + 2݀ଶ ≤ 0
ሺ2ሻ − ݀ଵ ≤ 0
ሺ3ሻ − 1 ≤ ݀ଵ ≤ 1
ሺ4ሻ − 1 ≤ ݀ଶ ≤ 1
Rozwiązanie optymalne zadania pomocniczego: ݀ଵ = 1, ݀ଶ = −1, ݃ሺ1, −1ሻ = −68
c) Ustal długość kroku i wyznacz kolejne rozwiązanie.
Kolejne rozwiązanie: ‫ = ݔ‬ሺ0,6ሻ் + ߣሺ1, −1ሻ் = ሺߣ, 6 − ߣሻ் .
Warunki ograniczające:
ሺ1ሻߣ + 2ሺ6 − ߣሻ ≤ 12
ሺ2ሻ2ߣ + ሺ6 − ߣሻ ≤ 12
ሺ3ሻ − ߣ ≤ 0
ሺ4ሻ − ሺ6 − ߣሻ ≤ 0
Stąd ߣ ∈
݂ሺߣ, 6 − ߣሻ = 8ߣଶ − 68ߣ + 120, ‫݀ ݈ܽ݊ܽ݉ݕݐ݌݋‬ł‫݋݃ݑ‬ść ݇‫= ∗ߣ ݑ݇݋ݎ‬
‫ݐݏ‬ą݀ ݇‫݅ݓݖ݋ݎ ݆݈݁݊݁݋‬ą‫ = ݔ ݁݅݊ܽݖ‬൬
17 7 ்
, ൰
4 4
17
,
4
d) Sprawdź, czy otrzymane rozwiązanie jest optymalne (przyjmij ε = 0,1).
Warunki wiążące: brak.
17 7
∇݂ሺ‫ݔ‬ଵ , ‫ݔ‬ଶ ሻ = ሺ2‫ݔ‬ଵ − 2‫ݔ‬ଶ − 6, −2‫ݔ‬ଵ + 10‫ݔ‬ଶ − 10ሻ் , ∇݂ ൬ , ൰ = ሺ−1, −1ሻ்
4 4
Zadanie pomocnicze:
ሺ0ሻ݃ሺ݀ଵ , ݀ଶ ሻ = −݀ଵ − ݀ଶ → ݉݅݊
ሺ1ሻ − 1 ≤ ݀ଵ ≤ 1
ሺ2ሻ − 1 ≤ ݀ଶ ≤ 1
Rozwiązanie optymalne zadania pomocniczego:
݀ଵ = 1, ݀ଶ = 1, ݃ሺ1,1ሻ = −2, |−2| ߝ,
Rozwiązanie nie jest optymalne.
Zadanie 2
Dane jest zadanie programowania nieliniowego:
2
(0) f ( x1 , x2 ) = x12 − 2 x1 x2 + 5 x 2 − 6 x1 − 10 x2 → min,
(1) x1 + 2 x2 ≤ 12,
(2) 2 x1 + x2 ≤ 12,
(3) x1 , x 2 ≥ 0;
Rozwiąż je za pomocą dodatku Solver.
Odp: x1 = 5 x2 = 2 FC = -25 .
Zadanie 3
Dyrektor fabryki zastanawia się nad liczbą części zamiennych, jakie powinien zamówić przy kupnie
maszyny, aby oczekiwana strata była minimalna. Tabela przedstawia prawdopodobieństwo
wystąpienia awarii. Cena zakupu części zamiennej w momencie wystąpienia awarii wynosi 4000 zł, a
rabat udzielany w chwili zakupu części wraz z maszyną wynosi 50%.
Liczba awarii
Prawdopodobieństwo
0
0,12
1
0,14
2
0,17
3
0,22
4
0,19
5
0,16
a) Stosując wzór rekurencyjny ustal optymalną wielkość zakupu części wraz z maszyną.
Liczba awarii (xj)
F(xj)
0
0,12
1
0,26
2
0,43
3
0,65
‫ݏ‬ଵ = 4 − 50% ∙ 4 = 2, ‫ݏ‬ଶ = 4 − 2 = 2
݂ሺ0ሻ = 2ሺ0,14 ∙ 1 + 0,17 ∙ 2 + 0,22 ∙ 3 + 0,19 ∙ 4 + 0,16 ∙ 5ሻ = 5,40
݂ሺ1ሻ = ݂ሺ0ሻ − 2 + ሺ2 + 2ሻ‫ܨ‬ሺ0ሻ = 3,88
݂ሺ2ሻ = ݂ሺ1ሻ − 2 + ሺ2 + 2ሻ‫ܨ‬ሺ1ሻ = 2,92
݂ሺ3ሻ = ݂ሺ2ሻ − 2 + ሺ2 + 2ሻ‫ܨ‬ሺ2ሻ = 2,64
݂ሺ4ሻ = ݂ሺ3ሻ − 2 + ሺ2 + 2ሻ‫ܨ‬ሺ3ሻ = 3,24
‫݂ ,3 = ∗ ݖ‬ሺ‫ ∗ ݖ‬ሻ = 2,64
b) Przy jakim rabacie optymalny byłby zakup 4 części?
݇ଵ
≤ ‫ܨ‬ሺ4ሻ
݇ଶ
ሺ1 − ‫ݎ‬ሻ݇ଶ
0,65 ≤ 1 −
≤ 0,84,
݇ଶ
Stąd ‫ %48 ,%56

(…)

…
Firma zajmująca się analizą danych wykorzystuje w swojej pracy między innymi (wynajmowany)
superkomputer do wykonania bardziej skomplikowanych obliczeń. Czas pracy firmy wynosi 240
godzin miesięcznie. Wielkość miesięcznego zapotrzebowania na pracę superkomputera jest zmienną
losową o funkcji gęstości postaci:
1 / 240, gdy x ∈ [0, 240],
φ ( x) = 
gdy x ∉ [0, 240].
0,
Firma wynajmująca superkomputer…
... zobacz całą notatkę