Badania operacyjne
1
dr Piotr Pusz
BADANIA OPERACYJNE
Literatura:
1. „Badania operacyjne w przykładach i zadaniach”, red. Karol Kukuła, PWN, W-wa 1999.
2. „Badania operacyjne dla menadżerów”, Krawczyk, AE, Wrocław 1997
PRZYKŁAD DIETY
Zadanie.
Zapewniamy organizmowi dziennie nie mniej niż 3000 cal i 100 gramów białka. Przy czym:
1 kg chleba
= 2000 cal i 50 gram białka,
1 kg sera
= 4000 cal i 200 gram białka.
1 kg chleba kosztuje 5 zł.
1 kg sera kosztuje 18 zł.
Rozwiązanie.
1000 cal – 1 jednostka
25 g – 1 jednostka
Chleb Ser Zapotrzebowanie
kalorie (1000 cal)
białko (25 g)
2
2
4
8
3
4
cena 5
18
Niewiadome: x - ilość chleba
y - ilość sera
2x – zawartość kalorii w chlebie
4y – zawartość kalorii w serze
z – cena
→
+
=
→
≥
+
→
≥
+
≥
minimum
18y
5x
z
bialko
4
8y
2x
kalorie
3
y
4
x
2
0
y
,
x
1
1
y
x
Z
1
z
2
punkt optymalny
Badania operacyjne
2
Obszar decyzji dopuszczalnych – decyzje, które spełniają warunki zagadnienia.
=
=
=
=
≥
+
=
⇒
≥
+
2
1
y
2
1
x
4
3
y
0
x
4
y
8
x
2
4
2x
-
3
y
3
y
4
x
2
1. Wybieramy dowolny punkt na płaszczyźnie i sprawdzamy czy spełnia warunki zadania. Jeżeli nie
(np. punkty (0,0)), to obszar po drugiej stronie prostej spełnia to.
2. Wyznaczamy drugi obszar.
=
=
=
=
=
⇒
≥
+
≥
+
0
y
2
x
2
1
y
0
x
4
x
-
2
y
4
y
8
x
2
3
y
4
x
2
Wyznaczamy część wspólną 2 obszarów tzn. obszar decyzji dopuszczalnych, z których będziemy
wybierać decyzje optymalne.
Funkcja z = 5x + 18y obrazuje koszt zakupu chleba i sera.
Np. wybieramy, że na jedzenie możemy wydać 20 zł:
=
=
=
=
−
=
−
=
=
+
=
9
5
y
2
x
0
y
4
x
18
x
5
20
y
x
5
20
y
18
20
y
18
x
5
20
z
Prosta ta zawiera decyzje dopuszczalne, można je „opuszczać” równolegle w dół osi X, ale do
momentu gdy ma styczność z obszarem decyzji dopuszczalnych.
Optymalnym punktem będzie punkt przecięcia się tych 3 prostych.
optymalny
punkt
1
x
4
1
y
1
4y
4
y
8
x
2
3
y
4
x
2
←
=
=
⇒
=
⇒
=
+
=
+
Badania operacyjne
3
Dieta zatem będzie kosztować:
zl
5
,
9
z
4
1
18
1
5
z
=
×
+
×
=
Jeżeli prosta „z” pokryła by się z jedną z prostych to oznacza, że optymalnych rozwiązań było by
nieskończenie wiele. Dlatego wystarczy sprawdzić punkty wierzchołkowe obszaru. Wtedy funkcję
celu liczymy w 3 punktach i wybieramy optymalne.
( )
2,0
10
0
18
2
5
z
.
3
4
1
1,
5
,
9
4
1
18
1
5
z
.
2
4
3
0,
5
,
13
4
3
18
0
5
z
.
1
=
×
+
×
=
=
×
+
×
=
=
×
+
×
=
Badania operacyjne
4
ZAGADNIENIA DYNAMICZNE
1. Inwestycje
Zadanie 1.
Przedsiębiorca mając pieniądz na inwestycje może wykorzystać je na 3 linie produkcyjne (Francuską,
Szwedzką, Polską) lub może po części zainwestować w każdą. Posiadany kapitał 6 mln zł.
Nakłady w mln zł 1 2 3 4 5 6
F 6 12 12 12 19 20
S 5 8 11 14 17 18
Produkcja
w tonach
P 4 15 15 15 15 16
Inwestujemy tylko w 2 linie produkcyjne – szwedzką i polską.
6 mln zł.
5 mln zł.
4 mln zł.
S(0) + P(6) = 15
(0 + 16)
S(0) + P(5) = 15
S(0) + P(4) = 15
S(1) + P(5) = 20
(5 + 15)
S(1) + P(4) = 20
S(1) + P(3) = 20
S(2) + P(4) = 23
(8 + 15)
S(2) + P(3) = 23
S(2) + P(2) = 23
S(3) + P(3) = 26
(11 + 15)
S(3) + P(2) = 26
S(3) + P(1) = 15
S(4) + P(2) = 29
(14 + 15)
S(4) + P(1) = 18
S(4) + P(0) = 14
S(5) + P(1) = 21
(17 + 4)
S(5) + P(0) = 17
S(6) + P(0) = 18
(18 + 0)
3 mln zł.
2 mln zł.
1 mln zł.
S(0) + P(3) = 15
S(0) + P(2) = 15
S(0) + P(1) = 4
S(1) + P(2) = 20
S(1) + P(1) = 9
S(1) + P(0) = 5
S(2) + P(1) = 12
S(2) + P(0) = 8
S(3) + P(0) = 11
Nakłady 0 1 2 3 4 5 6
F
0 6 12 12 12 15 20
P + S 0 5 15 20 23 26 29
6 mln zł.
F(0) + PS(6) = 29
F(1) + PS(5) = 32
F(2) + PS(4) = 35
F(3) + PS(3) = 32
F(4) + PS(2) = 27
F(5) + PS(1) = 20
F(6) + PS(0) = 20
Badania operacyjne
5
Zadanie 2.
Firma przewozowa dostarcza towar ustalając trasy przejazdu ciężarówek dzieląc całą trasę na 5
etapów. W każdym z etapów wyznaczono po kilka miast, przez które przejeżdżać będą ciężarówki.
Problem polega na znalezieniu najkrótszej drogi.
Odległości:
1 – 2 → 100
4 – 7 → 200
1 – 3 → 80
4 – 8 → 250
2 – 4 → 150
5 – 7 → 200
2 – 5 → 80
5 – 8 → 180
2 – 6 → 120
6 – 7 → 150
3 – 4 → 150
6 – 8 → 110
3 – 5 → 130
7 – 9 → 120
3 – 6 → 190
8 – 9 → 130
Droga:
d(7,9) = 120
d(4,7,9) = 320 d(5,8,9) = 310 d(6,7,9) = 270
d(8,9) = 130
d(4,8,9) = 380 d(5,7,9) = 320 d(6,8,9) = 240
Najkrótsze:
d(4,9) = 320
d(5,9) = 310
d(6,9) = 240
Droga optymalna:
d(6,9) = 240
d(2,9) = d(2,4) + d(4,9) = 470
d(3,9) = d(3,4) + d(4,9) = 470
d(2,9) = d(2,5) + d(5,9) = 390
d(3,9) = d(3,5) + d(5,9) = 440
d(2,9) = d(2,6) + d(6,9) = 360
d(3,9) = d(3,6) + d(6,9) = 430
d(2,9) = d(2,6) + d(6,9) = 360
d(3,9) = d(3,6) + d(6,9) = 430
Droga optymalna:
d(2,9) = d(2,6) + d(6,9) = 360
d(1,9) = d(1,2) + d(2,9) = 460
d(1,9) = d(1,3) + d(3,9) = 510
Droga optymalna: d(1,9) = d(1,2) + d(2,9) = 460
Odpowiedź.
Najkrótsza droga: 1 → 2 → 6 → 7 → 9.
I etap
II etap
III etap
IV etap
V etap
1
3
4
5
6
7
8
9
2
Badania operacyjne
6
Zadanie domowe.
Pytanie: gdzie zainwestować w reklamę, aby wzrost sprzedaży był maksymalny? Mamy do
zainwestowania 7 mln zł.
Nakłady w mln zł
0 1 2 3 4 5 6 7
TV 0 100 150 200 250 300 350 400
GW 0 200 200 200 200 200 200 500
Przyrost sprzedaży
RMF 0 100 100 300 400 500 500 550
reklama
7 mln zł.
6 mln zł.
5 mln zł.
4 mln zł.
G(0) + R(7) = 550
G(0) + R(6) = 500
G(0) + R(5) = 500
G(0) + R(4) = 400
G(1) + R(6) = 700
G(1) + R(5) = 700
G(1) + R(4) = 600
G(1) + R(3) = 500
G(2) + R(5) = 700
G(2) + R(4) = 600
G(2) + R(3) = 500
G(2) + R(2) = 300
G(3) + R(4) = 600
G(3) + R(3) = 500
G(3) + R(2) = 300
G(3) + R(1) = 300
G(4) + R(3) = 500
G(4) + R(2) = 300
G(4) + R(1) = 300
G(4) + R(0) = 200
G(5) + R(2) = 300
G(5) + R(1) = 300
G(5) + R(0) = 200
G(6) + R(1) = 300
G(6) + R(0) = 200
G(7) + R(0) = 500
3 mln zł.
2 mln zł.
1 mln zł.
G(0) + R(3) = 300
G(0) + R(2) = 100
G(0) + R(1) = 100
G(1) + R(2) = 300
G(1) + R(1) = 300
G(1) + R(0) = 200
G(2) + R(1) = 300
G(2) + R(0) = 200
G(3) + R(0) = 200
Nakłady w mln zł
0 1 2 3 4 5 6 7
TV
0 100 150 200 250 300 350 400
Przyrost sprzedaży
GW +RMF 0 200 300 300 500 600 700 700
7 mln zł.
6 mln zł.
T(0) + GR(7) = 700
T(0) + GR(6) = 700
T(1) + GR(6) = 800
T(1) + GR(5) = 700
T(2) + GR(5) = 750
T(2) + GR(4) = 650
T(3) + GR(4) = 700
T(3) + GR(3) = 500
T(4) + GR(3) = 550
T(4) + GR(2) = 550
T(5) + GR(2) = 600
T(5) + GR(1) = 500
T(6) + GR(1) = 550
T(6) + GR(0) = 350
T(7) + GR(0) = 400
Badania operacyjne
7
GRY DECYZYJNE
1. GRA O SUMIE ZERO – tzn., że wygrana jednego gracza, automatycznie oznacza przegraną
drugiego.
B
A
B
1
B
2
… B
n
A
1
a
11
a
12
… a
1m
A
2
a
21
…
… … …
A
n
a
n1
… … a
nm
Przykład 1.
Czy przedsiębiorstwo A może uruchomić produkcję pewnego produktu w wysokości: 100.000;
200.000; 300.000? Konkurencyjne przedsiębiorstwo B może postąpić w ten sam sposób.
Strategie B
Strategie A
B
1
B
2
B
3
min
strata
A
100 A
1
20 -150 -250 -250
200 A
2
150
-80
-100
-100
300 A
3
250
100
40
40
max 250
100
40
Pytanie: Jaką decyzję powinno podjąć przedsiębiorstwo A aby ponieść jak najmniejszą stratę?
Strategia A
3
dla gracza A oznacza maksymalny zysk.
Wygrana gracza A oznacza stratę gracza B.
Odpowiedź.
Gracz A powinien wybrać strategię A
3
, zaś B – B
3
. Oznacza to, że A ma zapewniony minimalny zysk
40, zaś gracz B maksymalną stratę 40.
Punkt (40) oznacza PUNKT SIODŁOWY tzn. gra ma rozwiązanie w STRATEGIACH CZYSTYCH.
Przykład 2.
B
A
B
1
B
2
B
3
min
zysk
A
1
10
230
50
10
A
2
150 250 140 140
A
3
80 200 220 80
max strata 150 250 220
Wartość taj grupy V
∈
(140,150) tzn., że gra nie ma rozwiązania w strategiach czystych. Dlatego
wprowadzamy STRATEGIĘ MIESZANĄ.
Gracz A nadal będzie miał trzy strategie, ale z pewnymi prawdopodobieństwami (tak samo B).
1
q
q
q
;
q
,
q
,
q
B
,
B
,
B
1
p
p
p
;
p
,
p
,
p
A
,
A
,
A
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
=
+
+
=
+
+
Badania operacyjne
8
Próbujemy sprawdzić:
STRATEGIĘ DOMINOWANĄ tzn. strategia A
k
dominuje strategię A
i
, jeżeli każdy element z
wiersza A
k
jest większy bądź równy od odpowiadającego mu elementu w wierszu A
i
(A
k
≥
A
i
) np:
A
1
: 10 230 50 strategia A
1
nie opłaca się, gdyż: 10<150; 230<250; 50<140.
A
2
: 150 250 140
B
1
: 10 150 80 strategia B
2
jest nieopłacalna: 230>10; 250>150; 200>80.
B
2
: 230 250 200
Pozostały nam po dwie sensowne strategie (strategie zdominowane zostały wyrzucone).
B
A
q
1
B
1
q
3
B
3
p
2
A
2
150 140
p
3
A
3
80 220
Rozwiązujemy układy równań:
Wartość gry wynosi 145⅓. Oznacza to, że gracz A zwiększył swój zysk, a gracz B zmniejszył swoją
stratę.
3
1
145
15
7
80
15
8
150
V
15
7
q
15
8
q
8
q
15
)
q
1
(
8
q
7
q
1
q
10
/
q
80
q
70
q
1
q
q
220
q
80
q
140
q
150
1
q
q
q
220
q
80
V
q
140
q
150
V
B
3
1
1
1
1
1
3
3
1
1
3
3
1
3
1
3
1
3
1
B
3
1
B
=
×
+
×
=
=
=
=
−
=
−
=
÷
=
−
=
+
=
+
=
+
+
=
+
=
3
1
145
15
1
80
15
14
150
V
15
1
p
1
p
15
14
p
14
p
15
p
14
14
p
)
p
1
(
14
p
p
14
p
p
1
p
10
/
p
140
p
10
1
p
p
p
220
p
140
p
80
p
150
1
p
p
p
220
p
140
V
p
80
p
150
V
A
2
3
2
2
2
2
2
2
3
2
2
3
3
2
3
2
3
2
3
2
3
2
3
2
A
3
2
A
=
×
+
×
=
=
−
=
=
=
−
=
−
=
=
−
=
÷
=
=
+
+
=
+
=
+
+
=
+
=
Badania operacyjne
9
Inny sposób:
Dlatego, że punkt (0,0) nie spełnia nierówności.
Wyznaczamy punkt P.
=
+
=
+
1
y
220
x
140
1
y
80
x
150
−
≥
≥
←
+
≥
≥
≥
+
≥
+
=
=
=
+
≥
+
≥
+
÷
=
+
÷
≥
+
÷
≥
+
←
∈
=
+
≥
+
≥
+
0
,
140
1
,
220
1
0,
220
x
140
1
y
,0
150
1
,
80
1
0,
80
150x
-
1
y
e
najmniejsz
jak
y
x
0
y
,
0
x
1
y
220
x
140
1
y
80
x
150
y
,
x
:
y
podstawiam
1
220
140
1
80
150
V
|
1
p
p
V
|
V
p
220
p
140
V
|
V
p
80
p
150
V
przez
dzielimy
dlatego
)
150
,
140
(
V
1
p
p
V
p
220
p
140
V
p
80
p
150
V
p
V
p
V
1
V
p
V
p
V
p
V
p
V
p
V
p
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
1/80
1/220
1/150
1/140
Badania operacyjne
10
=
=
=
=
=
=
=
=
=
=
2180
1
,
2180
14
P
2180
1
21800
10
y
2180
14
21800
140
x
10
1
140
1
150
W
140
220
1
80
1
W
21800
220
140
80
150
W
y
x
Obliczamy wartość funkcji w trzech punktach:
15
1
p
p
1
p
15
14
2180
14
146
Vx
p
x
V
p
146
1
V
1
:
Zatem
140
1
y
x
;
0
,
140
1
minimum
146
1
y
x
;
2180
1
,
2180
14
80
1
y
x
;
80
1
,
0
3
2
3
2
2
=
⇒
−
=
=
×
=
=
⇒
=
=
=
+
←
=
+
=
+
Badania operacyjne
11
GRY Z NATURĄ
Przykład:
Rolnik posiadający glebę klasy III ma wybrać pod uprawę jeden z trzech rodzajów zboża. Plony tych
zbóż z 1ha w kwintalach w zależności od warunków klimatycznych zawiera tabela.
Zboże
I II
III
IV
A
1
żyto
24,5 18 18 16 16
A
2
pszenica 18 32 24 21 18 ← max
A
3
jęczmień 15 19 26 19 15
I.
KRYTERIUM WALDA (zasada maksimum)
1. Wyznaczamy najmniejszy zbiór zboża, w zależności od stanu natury.
2. Wybieramy z tego największy zysk (w naszym przypadku jest to pszenica)
II. KRYTERIUM
HURWICZA
}
}
5
,
20
15
2
1
26
2
1
A
max
25
18
2
1
32
2
1
A
25
,
20
16
2
1
5
,
24
2
1
A
2
1
dla
.
np
3
2
min
max
1
=
×
+
×
=
←
=
×
+
×
=
=
×
+
×
=
=
γ
III. KRYTERIUM
BAY’ESA
Kryterium to zakłada, że każdy stan natury jest tak samo prawdopodobny (proporcjonalność).
75
,
19
4
79
4
19
26
19
15
A
max
75
,
23
4
95
4
21
24
32
18
A
125
,
19
4
5
,
76
4
16
18
18
5
,
24
A
3
2
1
=
=
+
+
+
=
←
=
=
+
+
+
=
=
=
+
+
+
=
IV. KRYTERIUM
SAVAGE’A
Ustalamy straty w stosunku do najlepszego (ustalamy tabelę strat).
I II III IV
A
1
0
14 8 5
14
A
2
6,5 0 2 0
6,5
← min
A
3
9,5 13 0 2 13
Wyznaczamy maksymalne straty w stosunku do najlepszych przy danym stanie natury, a
następnie minimum tych maksimów.
Kryterium Savage’a spełnia postać minimalizacji oczekiwanych strat wynikłych z podjęcia
przez nas decyzji gorszej niż najlepsza możliwa dla danego stanu natury.
{ }
{ }
[ ]
0,1
;
a
min
)
1
(
a
max
.
ij
ij
∈
γ
γ
−
+
γ
Badania operacyjne
12
Zadania domowe.
1. Rolnik ma wybrać jeden z trzech możliwych terminów siewów w zależności od stanu
pogody.
Pogoda
Plony
A B C D
I
21 15 32 16
II
28 20 10 20
III
13 27 25 15
2. Poszukiwanie niesprawności odbiornika radiowego można rozpocząć od jednego z
czterech układów: A, B, C, D. W tablicy podano procent udanych prób uruchomienia
odbiorników w określonym czasie w zależności od kolejności szukania uszkodzeń oraz
miejsca występowania uszkodzenia.
Układy
Kolejność
A B C D
A
80 30 10 25
B
12 90 42 36
C
25 40 85 52
D
10 70 40 95
3. Gra z sumą zero.
Wskazówka: należy rozwinąć grę tzn. znaleźć wartość gry (na początku szukamy punktu
siodłowego, potem stosujemy strategię mieszaną).
B
A
B
1
B
2
B
3
A
1
2 4 6
A
2
3 1 4
A
3
2 3 3
Badania operacyjne
13
ROZWIĄZYWANIE ZAGADNIEŃ NIELINIOWYCH
Ekstremum funkcji:
f(x)
f’(x)=0 liczymy pochodną
x
0
szukamy ekstremum
1. badamy znak pochodnej
2. wyznaczamy II pochodną
f’’(x
0
)>0 → min
f’’(x
0
)<0 → max
6x
(x)
'
f'
0
x
0
)
x
(
'
f
x
3
)
x
(
'
f
x
)
x
(
f
2
3
=
=
⇔
=
=
=
Funkcje dwóch zmiennych.
)
x
,
x
(
f
2
1
pochodne cząstkowe:
2
1
x
f
;
x
f
δ
δ
δ
δ
Np.
zmienna
x
,
stala
x
5
0
x
6
x
6
0
x
f
zmienna
x
,
stala
x
0
7
x
6
x
4
x
f
x
5
x
7
x
x
6
x
3
x
2
)
x
,
x
(
f
2
1
1
2
2
1
2
2
1
1
2
1
2
1
2
2
2
1
2
1
−
−
+
−
+
−
=
δ
δ
−
−
+
−
+
=
δ
δ
+
−
+
−
=
Liczymy drugą pochodną:
6
x
f
x
x
f
6
x
x
f
4
x
f
2
2
2
1
2
2
2
1
2
2
1
2
−
=
δ
δ
δ
δ
δ
=
=
δ
δ
δ
=
δ
δ
+
X
0
max
+
X
0
min
Badania operacyjne
14
Pojawia się macierz dwóch pochodnych:
6
6
6
4
x
f
x
x
f
x
x
f
x
f
A
2
2
2
2
1
2
1
2
2
2
1
2
−
=
δ
δ
δ
δ
δ
δ
δ
δ
δ
δ
=
Wyznaczamy ekstremum (mamy tyle równań ile niewiadomych ):
=
δ
δ
=
δ
δ
0
x
f
0
x
f
2
1
Rozwiązując układ równań wyznaczamy punkt, w którym może być ekstremum (x’,y’).
Patrzymy na macierz:
1. warunkiem istnienia minimum jest:
0
x
f
^
0
A
det
2
1
2
>
δ
δ
>
tzn. macierz jest dodatnio określona.
2. warunkiem istnienia maksimum jest:
0
x
f
^
0
A
det
2
1
2
<
δ
δ
>
tzn. macierz jest określona ujemnie.
Liczenie ekstremum.
)
x
,...,
x
,
x
,
x
(
f
n
3
2
1
Warunkiem jest to, że zmienne powinny być nieujemne.
,
0
x
,...,
0
x
,
0
x
,
0
x
n
3
2
1
≥
≥
≥
≥
Zadanie.
Z elektrociepłowni energia przesyłana jest do dwóch używających ją zakładów produkcyjnych.
Funkcja kosztów przesyłania energii do tych zakładów w zależności od wielkości przesyłu dana jest
wzorem:
0
x
,
x
81
x
4
x
12
x
7
x
x
8
x
5
)
x
,
x
(
f
2
1
2
1
2
2
2
1
2
1
2
1
>
+
−
−
+
−
=
x
1
– energia przesłana do zakładu I
x
2
– energia przesłana do zakładu II
Rozdziel dzienną produkcję energii wynoszącą 16MWh pomiędzy te dwa zakłady tak, aby
zminimalizować koszty przesyłu energii.
16
x
x
2
1
=
+
Badania operacyjne
15
Rozwiązanie:
Wyznaczamy ekstremum warunkowe.
0
4
0
x
14
x
8
0
x
f
0
0
12
0
x
8
x
10
x
f
2
1
2
2
1
1
+
−
−
+
−
=
δ
δ
+
−
−
+
−
=
δ
δ
Pochodne przyrównujemy do 0.
ekstremum
być
możo
punkcie
tym
w
19
34
x
19
50
x
34
24
10
2
4
6
5
W
50
8
42
7
2
4
6
W
19
16
35
7
4
4
5
W
2
x
7
x
4
6
x
4
x
5
0
2
x
7
x
4
0
6
x
4
x
5
2
|
0
4
x
14
x
8
2
|
0
12
x
8
x
10
2
1
y
x
2
1
2
1
2
1
2
1
2
1
2
1
←
=
=
=
+
=
−
=
=
+
=
−
=
=
−
=
−
−
=
=
+
−
=
−
=
−
+
−
=
−
−
÷
=
−
+
−
÷
=
−
−
Liczymy II pochodne.
8
x
x
f
14
x
f
10
x
f
2
1
2
2
2
2
2
1
2
−
=
δ
δ
δ
=
δ
δ
=
δ
δ
Budujemy macierz drugich pochodnych.
min
mamy
punkcie
tym
w
tzn.
0
10
x
f
0
76
64
140
A
det
14
8
8
10
A
2
1
2
>
=
δ
δ
>
=
−
=
−
−
=
Badania operacyjne
16
Sprawdzamy czy spełnione jest ograniczenie:
16
19
94
19
34
19
50
x
x
2
1
<
=
+
=
+
tzn. nie spełnia ograniczenia i rozwiązanie takie jest niedobre.
Wprowadzamy MNOŻNIKI LAGRANGE’A (mnożników jest tyle ile ograniczeń)
∑
=
λ
+
=
λ
λ
n
1
i
e
równościow
ie
ograniczen
n
2
1
i
i
n
2
1
r
1
n
1
)
x
,...,
x
,
x
(
g
)
x
,...,
x
,
x
(
f
)
,...,
,
x
,...,
x
(
L
4
4 3
4
4 2
1
W naszym przypadku mamy:
)
16
x
x
(
81
x
4
x
12
x
7
x
x
8
x
5
)
,
x
,
x
(
L
2
1
2
1
2
2
2
1
2
1
2
1
−
+
λ
+
+
−
−
+
−
=
λ
Liczymy pochodną cząstkową:
=
=
−
=
=
−
=
−
=
+
+
−
−
=
−
=
+
−
−
−
=
−
=
+
−
=
+
÷
−
=
+
−
=
−
+
=
+
+
−
−
+
−
+
+
−
=
λ
=
−
+
=
λ
+
−
+
−
=
λ
+
−
−
−
+
=
δλ
δ
λ
+
−
+
−
=
δ
δ
λ
+
−
−
=
δ
δ
9
x
7
x
x
16
x
40
1
x
20
x
16
x
4
x
11
x
9
144
x
16
x
4
x
11
)
x
16
(
9
x
16
x
4
x
11
x
9
16
x
x
2
|
8
x
22
x
18
0
16
x
x
0
12
x
8
x
10
4
x
14
x
8
12
x
8
x
10
0
16
x
x
0
4
x
14
x
8
0
12
x
8
x
10
16
x
x
f
4
x
14
x
8
x
f
12
x
8
x
10
x
f
1
2
2
1
2
2
1
2
2
2
1
2
2
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1
2
1
1
0
40
0
10
14
8
8
0
0
1
1
1
14
8
1
8
10
A
det
0
76
64
140
14
8
8
10
A
det
0
10
a
0
a
0
3)
detA(3
0
2)
detA(2
:
minimum
istnialo
Aby
0
1
1
1
14
8
1
8
10
A
robić
nie
można
Tego
3
3
2
2
11
11
<
−
=
+
−
−
−
−
=
−
−
=
>
=
−
=
−
−
=
>
=
>
>
×
>
×
−
−
=
×
×
Badania operacyjne
17
MINIMALIZACJA
Minimalizować można:
1. czynniki produkcji (środki trwałe, materiały, siłę roboczą, kapitał,…)
2. proces produkcyjny opisany funkcją produkcji
3. wielkość sprzedaży wyrobów
C(x) – koszty produkcji
x
1
, x
2
,…,x
n
– czynniki produkcji
p
1
,p
2
,…,p
r
– ceny czynników produkcji
K
s
– koszty stałe
]
x
,...,
x
,
x
[
x
]
p
,...,
p
,
p
[
p
K
x
p
K
p
x
)
x
(
C
n
2
1
r
2
1
s
n
1
i
T
s
i
i
=
=
+
=
+
=
∑
=
Przychód firmy ze sprzedaży wyprodukowanych wyrobów:
∑
=
=
y
c
c
y
)
y
(
R
T
i
i
y
1
, y
2
,…, y
3
– ilość wyprodukowanych wyrobów
c
1
, c
2
,…, c
3
– ceny wyprodukowanych wyrobów
[
]
[
]
=
=
=
=
n
2
1
n
2
1
n
2
1
n
2
1
y
y
y
y
c
c
c
c
y
,...,
y
,
y
y
c
,...,
c
,
c
c
M
M
Zysk przedsiębiorstwa:
Z(x, y) = R(y) – C(x)
Zadanie.
Wyznacz optymalne nakłady czynników produkcji x
1
, x
2
do wytworzenia nadanej wielkości produkcji
y
0
=120 przy możliwie najniższych kosztach. Proces produkcji opisuje funkcja :
a koszty produkcji:
2
1
2
1
x
x
2
)
x
,
x
(
f
y
=
=
10
x
x
4
)
x
(
C
2
1
+
+
=
Badania operacyjne
18
Rozwiązanie:
)
x
x
2
120
(
10
x
x
4
L
x
x
2
120
)
x
,
g(x
;
120
x
x
2
2
1
2
1
2
1
2
1
2
1
−
λ
+
+
+
=
−
=
=
Szukamy minimum tej funkcji:
=
=
=
=
=
=
=
=
×
−
=
λ
=
−
=
λ
−
=
λ
−
−
=
δλ
δ
λ
−
=
δ
δ
>
λ
−
=
δ
δ
120
x
30
x
60
x
2
x
4
x
60
x
4
x
x
x
4
1
60
x
x
0
x
x
x
x
4
1
x
x
4
0
x
x
2
120
0
x
x
1
0
x
x
4
x
x
2
120
L
x
x
1
x
L
0
x
,
x
x
x
4
x
L
2
1
1
1
2
1
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
1
2
2
1
2
1
2
2
1
1
2
1
C(x) = 4•30+120+10=250 ← minimum kosztów produkcji
Maksymalizujemy produkcję (minimalne koszty już obliczyliśmy).
)
10
x
x
4
C
(
x
x
2
L
const
C
2
1
0
2
1
0
−
−
−
λ
+
=
=
Badania operacyjne
19
Metoda postępowania.
1. Funkcja kryterium zysku P=F(x)
2. Ograniczenie
równościowe
=
=
=
⇒
=
r
1
2
2
1
1
a
)
x
(
g
a
)
x
(
g
a
)
x
(
g
a
)
x
(
g
M
3. Tworzenie
Lagrange’a
4. Wyznaczamy warunki konieczne (liczymy pochodne cząstkowe po wszystkich zmiennych i
porównujemy do 0)
=
−
=
δλ
δ
=
δ
−
δ
λ
+
δ
δ
=
δ
δ
0
)
x
(
g
a
L
0
x
))
x
(
g
a
(
x
F
x
L
T
5. Warunki
wystarczające (dodatnio określona dla minimum i ujemnie określona dla maksimum)
δ
δ
x
L
2
Badania operacyjne
20
PROGRAMY PIERWOTNY I DUALNY
Zadanie.
Przedsiębiorstwo produkuje cztery wyroby W
1
, W
2
, W
3
, W
4
, dwa spośród wielu środków używanych
w procesie produkcji są limitowane. Limity te wynoszą: środek 1 – 90.000, środek 2 – 120.000
jednostek. Nakłady limitowanych środków na jednostkę produkcji podano w tabeli.
Jednostkowe nakłady
na produkcję wyrobu
Środek
Produkcji
W
1
W
2
W
3
W
4
I 1
2
1,5
6
II 2
2
1,5
4
Zysk osiągany
na jednostkę produkcji
4 6 3 12
Ustalić optymalne rozmiary produkcji poszczególnych wyrobów. Podać łączny zysk zrealizowany
przy optymalnym asortymencie produkcji.
PROGRAM PIERWOTNY
←
+
+
+
=
≤
+
+
+
≤
+
+
+
≥
funkcji
max tej
szukamy
x
12
x
3
x
6
x
4
)
x
,
x
,
x
,
x
(
F
120000
x
4
x
5
,
1
x
2
x
2
90000
x
6
x
5
,
1
x
2
x
0
x
,
x
,
x
,
x
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
i
– ilość produkowanych wyrobów W
i
PROGRAM DUALNY
Wprowadzamy zmienne dualne. Zasady konstrukcji:
1. W programie dualnym jest tyle zmiennych ile warunków ograniczających w programie
pierwotnym.
2. Współczynniki funkcji celu programu pierwotnego są wyrazami wolnymi układu nierówności
programu dualnego (i na odwrót).
3. Macierz współczynników układu nierówności w programie dualnym jest transpozycją macierzy
współczynników układu nierówności w programie pierwotnym.
4. Programem dualnym względem programu dualnego jest program pierwotny.
5. Jeżeli w programie pierwotnym funkcja celu jest maksymalizowana to w programie dualnym jest
minimalizowana (i na odwrót).
6. Konstruując program dualny należy zmienić kierunki nierówności na przeciwne w porównaniu z
programem pierwotnym.
7. a. W rozwiązaniach optymalnych obu programów, wartości funkcji celu są sobie równe.
b. Jeżeli j – ty warunek programu dualnego jest chociaż jednym optymalny rozwiązaniem tego
programu spełnionym z nierównością ostrą to odpowiadająca mu j – ta zmienna x
j
w dowolnym
optymalnym rozwiązaniu przyjmuje wartość 0.
Badania operacyjne
21
Rozwiązanie.
−
≥
−
≥
−
≥
−
≥
←
+
=
≥
+
≥
+
≥
+
≥
+
≥
2
y
3
6
y
y
2
y
y
3
y
2
y
4
y
y
000
.
120
y
000
.
90
)
y
,
y
(
G
12
y
4
y
6
3
y
5
,
1
y
5
,
1
6
y
2
y
2
4
y
2
y
0
y
,
y
1
2
1
2
1
2
1
2
2
1
2
1
2
1
2
1
2
1
2
1
2
1
funkcji
min tej
szukamy
Dane punkty są potencjalnymi rozwiązaniami dopuszczalnymi.
G(0,3) = 390.000
G(2,1) = 300.000 ← min
G(4,0) = 360.000
zysk
max
tys.
←
=
300
)
x
,
x
,
x
,
x
(
F
(
Max
4
3
2
1
Sprawdzamy w programie dualnym, która z nierówności spełniona jest ostro.
>
=
×
+
×
>
=
×
+
×
=
=
×
+
×
=
=
×
+
0)
równe
są
x
i
x
(zmienne
nierówność
ostra
4
4
3
12
16
1
4
2
6
3
5
,
4
1
5
,
1
2
5
,
1
6
6
1
2
2
2
4
1
2
2
2
y
3
6
y
y
2
y
y
3
y
2
1
y
4
2
y
1
2
1
2
1
2
−
≥
−
≥
−
≥
−
≥
1
(2,1)
(4,0)
(0,3)
1
y
2
y
1
2
y
3
6
y
y
2
y
y
3
y
2
1
y
4
2
y
1
2
1
2
1
2
−
≥
−
≥
−
≥
−
≥
Badania operacyjne
22
=
=
=
+
−
=
−
−
=
+
×
=
+
30000
x
30000
x
120000
x
2
x
2
180000
x
4
x
2
120000
x
2
x
2
90000
x
2
x
2
1
2
1
2
1
2
1
2
1
(-2)
|
Odpowiedź.
Trzeba wyprodukować 30.000 sztuk pierwszego i 30.000 sztuk drugiego wyrobu – osiągnięty zysk
będzie równy 300.000.
Pytanie.
Jak zwiększy się zysk przedsiębiorstwa jeśli zwiększymy jeden z limitów o 1.
Wniosek.
Optymalna wartość i – tej zmiennej dualnej yi informuje o tym jaki zmienny przyrost programu
pierwotnego przypadnie na wzrost wyrazu wolnego w i – tym warunku programu pierwotnego o
jednostkę.
2
)
30000
,
30000
(
F
)
30001
,
29999
(
F
30001
x
29999
x
240000
x
x
90001
x
2
x
120000
x
2
x
2
90001
x
2
x
2
1
2
1
2
1
2
1
2
1
=
−
=
=
=
+
−
=
−
−
÷
=
+
×
=
+
2
|
(-1)
|
1
o
limit
pierwszy
Zwiększamy
=
=
=
+
=
+
29999
x
30002
x
60001
x
x
90000
x
2
2
1
2
1
2
M
1
x
o1
limit
drugi
Zwiększamy
Badania operacyjne
23
WYBÓR PROCESU TECHNOLOGICZNEGO
Zadanie.
Tartak otrzymała zamówienie na wykonanie co najmniej 300 kompletów belek. Każdy komplet składa
się z 7 belek o długości 0,7 m. oraz 4 belek o długości 2,5 m. W jaki sposób powinno być
zrealizowane zamówienie, aby odpad powstały w procesie cięcia dłużnic o długości 5,2 m.? Był
minimalny. Ile wyniesie wielkość odpadu przy optymalnym cięciu?
m
5
,
2
1200
m
7
,
0
2100
×
×
Różne cięcia belki o dł. 5,2 m.
I II III
0,7
7 3 0
2,5
0 1 2
Odpad
0,3 0,6 0,2
x
1
– liczba cięć sposobem I
x
2
– liczba cięć sposobem II
x
3
– liczba cięć sposobem III
Budujemy program pierwotny:
←
+
+
=
≥
+
+
≥
+
+
≥
min
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
x
2
,
0
x
6
,
0
x
3
,
0
)
x
,
x
,
x
(
F
1200
x
2
x
x
0
2100
x
0
x
3
x
7
0
x
,
x
,
x
Budujemy program dualny:
←
+
=
≤
+
≤
+
≤
+
≥
max
2
1
2
1
2
1
2
1
2
1
2
1
y
1200
y
2100
)
y
,
y
(
G
2
,
0
y
2
y
0
6
,
0
y
y
3
3
,
0
y
0
y
7
0
y
,
y
1
,
0
y
3
y
6
,
0
y
70
3
y
2
2
1
1
≤
−
≤
≤
10
1
,
70
3
0
,
70
3
y
1
y
2
0,5
0,5
1
,
0
y
3
y
6
,
0
y
70
3
y
2
2
1
1
≤
−
≤
≤
10
1
,
70
3
0
,
70
3
10
1
,
0
Badania operacyjne
24
120
10
1
,
0
G
90
0
,
210
10
1
,
70
3
G
=
=
←
=
70
3
G
odpad
minimalny
Sprawdzamy w programie dualnym, która z nierówności spełniona jest ostro.
=
=
×
=
⇒
<
=
+
×
=
=
×
0,2
5
1
10
1
2
x
0,6
70
3
3
2
0
70
16
10
1
3
,
0
3
,
0
70
3
7
=
=
=
=
600
x
300
x
1200
x
2
2100
x
7
3
1
3
1
Odpowiedź.
Trzeba pociąć 300 razy sposobem I i 600 razy sposobem III. Odpad będzie równy 210m.