BADANIA OPERACYJNE
Badania operacyjne
 Badania operacyjne są sztuką dawania złych odpowiedzi na
 Badania operacyjne są sztuką dawania złych odpowiedzi na
te praktyczne pytania, na które inne metody dają odpowiedzi
jeszcze gorsze.
T. Sayty
2
Standardowe zadanie
Standardowe zadanie
programowania liniowego
Standardowe zadanie programowania liniowego
Rozważamy proces, w którym zmiennymi są x1, x2, ..., xn.
Proces poddany j m ograniczeniom, zapisanymi w p
py jest g, p y postaci:
a11x1 + a12x2 +...+ a1nxn = b1
a21x1 + a22x2 +...+ a2nxn = b2
(1)
(1)
...
am1x1 + am2x2 +...+ amnxn = bm
m1 1 m2 2 mn n m
aij, bi  znane współczynniki
4
Standardowe zadanie programowania liniowego
Dopuszczamy jedynie nieujemne wartości xj, czyli:
x e" 0 j =1 2 n (2)
xj e" 0, j =1,2,...,n (2)
Zakładamy również, że:
y ,
bi e" 0, i =1,2,...,m (3)
Z procesem jest związana funkcja Z:
Z = c1x1 + c2x2 + ...+ cnxn (4)
cj, j = 1, 2, ...,n  znane współczynniki
5
Standardowe zadanie programowania liniowego
Zagadnienie polega na maksymalizacji (minimalizacji) funkcji
Z (wzór (4)) spełniającej ograniczenia (1), (2), (3).
Z (wzór (4)) spełniającej ograniczenia (1), (2), (3).
Zapis:
n
FC : Z =
"c xj MAX
j
j=1
m
ż#
"a xj = bi
�# ij
j=1
j=1
(5)
(5)
�#
�#
�#
�#x e" 0,
O : j = 1,2,...,n
�#
j
�#
�#
�#
bi e" 0, i =1,2,...,m
�#
�#
�#
�#
�#
6
Standardowe zadanie programowania liniowego
Zapis w postaci macierzowej:
T
FC Z MAX
FC : Z = cTx MAX
Ax = b
ż#
(6)
�#
�#
O: x e" 0
�#
�#
b e" 0
�#
�#
a11 a12 & a1n c1 x1 b1
Ą# ń# Ą# ń# Ą# ń# Ą# ń#
ó#Ą# ó# Ą# ó# Ą#
ó#aa22 & a2n Ą# ó#x Ą# ó#b Ą#
ó# Ą#
ó#c Ą#
21 2 2 2
ó# Ą# ó# Ą# ó# Ą# ó# Ą#
A = c = x = b =

ó# & & & Ą# ó# Ą# ó# Ą# ó# Ą#
ó#Ą# ó# Ą# ó# Ą#
ó#aam2 & amn Ą# ó#x Ą# ó#b Ą#
ó# Ą#
ó#c Ą#
Ł# m1 Ś# Ł# n Ś# Ł# n Ś# Ł# m Ś#
7
Standardowe zadanie programowania liniowego
Bardzo powszechną wzagadnieniach praktycznych odmianą
B d h d i i h kt h d i
ograniczeń są ograniczenia w postaci nierówności.
To też są zagadnienia programowania liniowego ale
To też są zagadnienia programowania liniowego ale
nie w postaci standardowej.
8
Standardowe zadanie programowania liniowego
Przykład 1.
Zakład zamierza rozpocząć p odu cję wyrobów W1 i W2. Wś ód
a ad a e a o poc ąć produkcję y obó W1 W2 śród
środków produkcyjnych, które zostaną użyte w produkcji dwa są
limitowane. Limity te wynoszą: dla środka S1 63 jednostki, a dla
ś dk dk b d k ć dk b
środka S2 64 jednostki. Aby wyprodukować jednostkę wyrobu W1
potrzeba 9 jednostek środka S1 i 8 jednostek środka S2. Aby
wyprodukować jednostkę wyrobu W potrzeba 7 jednostek S i 8
wyprodukować jednostkę wyrobu W2 potrzeba 7 jednostek S1 i 8
jednostek S2. Wyroby W1 i W2 są niezbędne do produkcji
urządzenia U. Jedno urzą y g jednostek wyrobu
ą ądzenie U wymaga 3 j y
W1 i 2 jednostek wyrobu W2. Produkcja będzie opłacalna, jeżeli
zakład sprzeda wyroby W1 i W2 potrzebne do wytworzenia co
najmniej 6 jednostek urządzenia U.
j i j 6 j d t k d i U
Wiedząc, że cena wyrobu W1 będzie wynosić 6, a cena wyrobu
W 5 określ wielkość produkcji maksymalizującej zysk ze
W2 5 określ wielkość produkcji maksymalizującej zysk ze
sprzedaży.
9
Standardowe zadanie programowania liniowego
W1 W2

S 9 7 63
S1 9 7 63

S 8 8 64
S2 8 8 64

U
U
3 2 6
3 2 6
cena
cena
6 5
6 5
10
Standardowe zadanie programowania liniowego
Zmienne decyzyjne:
x1  wielkość produkcji wyrobu W1
lk ść d k b
x2  wielkość produkcji wyrobu W2
11
Standardowe zadanie programowania liniowego
Funkcja celu:
Z(x x ) = 6x + 5x MAX
Z(x1, x2) = 6x1 + 5x2 MAX
Ograniczenia:
Ograniczenia:
9x1 + 7x2 d" 63

8x + 8x d" 64
8x1 + 8x2 d" 64

3x1 + 2x2 e" 6

Warunki brzegowe:
x1 e" 0, x2 e" 0
12
Standardowe zadanie programowania liniowego
Zadanie programowania liniowego:
FC: Z(x1, x2) = 6x1 + 5x2 MAX
O
O: 9x1 + 7x2 d" 63

x1 + x2 d" 8

3x + 2x e" 6
3x1 + 2x2 e" 6

x1 e" 0, x2 e" 0
WB:
Ograniczenia w postaci nierówności.
To nie jest standardowe zadanie programowania liniowego
To nie jest standardowe zadanie programowania liniowego
13
METODA
METODA
GEOMETRYCZNA
GEOMETRYCZNA
Metoda geometryczna
Zadanie programowania liniowego z dwoma zmiennymi
decyzyjnymi można rozwiązać metodą geometryczną
decyzyjnymi można rozwiązać metodą geometryczną
(szczegóły na laboratorium).
Na podstawie tej metody otrzymujemy zbiór punktów, a
następnie sprawdzamy w którym z nich wartość funkcji celu
następnie sprawdzamy, w którym z nich wartość funkcji celu
jest największa (lub najmniejsza).
15
Metoda geometryczna
Rozwiązanie dla zadania z Przykładu 1.:
A(2,0) Z(2,0) = 6�" 2 + 5�"0 =12
B(7,0) Z(7,0) = 6�"7 + 5�"0 = 42
C(3.5,4.5) Z(3.5, 4.5) = 6�"3.5 + 5�"4.5 = 43.5
MAX
D(0,8) Z(0,8) = 6�"0 + 5�"8 = 40
E(0,3) Z(0,3) 6 0 + 5 3 15
E(0,3) Z(0,3) = 6�"0 + 5�"3 =15
Odpowiedz
:
Aby zysk był maksymalny, należy wyprodukować
3.5 jednostki W1 oraz 4.5 jednostki W2.
16
ZADANIE DUALNE
Zadanie dualne
Przykład 2.
Zakład produkuje cztery wyroby W1, W2, W3 i W4. Wśród
Zakład produkuje cztery wyroby W1, W2, W3 i W4. Wśród
środków produkcyjnych, używanych w procesie wytwarzania
wyrobów dwa są limitowane. Limity te, oraz ilości środków
potrzebne do wytworzenia poszczególnych wyrobów zostały
b d i ól h bó ł
przedstawione w tabeli.
Znając jednostkowe ceny wyrobów, określić taki plan
Znając jednostkowe ceny wyrobów, określić taki plan
produkcji aby zysk był maksymalny.
18
Zadanie dualne
W1 W2 W3 W4
S1 1 3 1 1 600
S2 4 1 1 5 1200
cena 8 9 6 10
Zmienne decyzyjne:
xi  wielkość produkcji wyrobu Wi i = 1...4
19
Zadanie dualne
Model matematyczny:
FC:
Z(x x x x ) = 8x + 9x + 6x +10x MAX
Z(x1, x2, x3, x4) = 8x1 + 9x2 + 6x3 +10x4 MAX
O:
x1 + 3x2 + x3 + x4 d" 600
3 600
4x1 + x2 + x3 + 5x4 d"1200
WB:
x e" 0 x e" 0 x e" 0 x e" 0
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0
20
Zadanie dualne
Zadanie pierwotne:
T
FC
FC:
Z = cTx MAX
Ax d" b
O:
x e" 0
WB:
Zadanie dualne:

FC:
Z = bTy MIN
A y e" c
ATy e" c
O:
O:
WB:
y e" 0
21
Zadanie dualne
Model matematyczny zadania dualnego:
FC:
FC:

Z(y1, y2) = 600y1 +1200y2 MIN
O
O:
y1 + 4y2 e" 8
3y1 + y2 e" 9
y1 y2
y1 + y2 e" 6
y1 y2
y1 + 5y2 e"10
WB:
y e" 0 y e" 0
y1 e" 0, y2 e" 0
22
Zadanie dualne
Interpretacja zadania dualnego
Konkurent postanawia wykupić zapasy środków produkcji od
producenta, i chce zminimalizować koszty materiałów (ma
kupić 600 jednostek S i 1200 jednostek S )
kupić 600 jednostek S1 i 1200 jednostek S2).
Zmienne decyzyjne w zadaniu dualnym:
y1  cena jednostki środka produkcji S1
y2 j pj S2
y2  cena jednostki środka produkcji S2

Z( ) 600 +1200 MIN
Z(y1, y2) = 600y1 +1200y2 MIN
23
Zadanie dualne
Interpretacja zadania dualnego c. d.
Wyprodukowanie wyrobów wiąże się z kosztemśrodków S1 i
S2. Konkurent, aby zachęcić producenta do sprzedaży
materiałów musi mu zapłacić co najmniej tyle ile producent
materiałów musi mu zapłacić co najmniej tyle, ile producent
uzyskałby ze sprzedaży wyrobów, które produkuje.
y1 + 4y2 e" 8
3y1 + y2 e" 9
y1 + y2 e" 6
y1 + 5y2 e"10
+ 5 e"10
24
Zadanie dualne
Twierdzenie o dualności
Zadanie pierwotne ma rozwiązanie wtedy i tylko wtedy, gdy
zadanie dualne ma rozwiązanie, oraz:

Z(MAX) = Z(MIN)
wnioski:
1. Rozwiązując jedno z zadań, automatycznie
rozwiązujemy też drugie.
2. Twierdzenie ma duże znaczenie praktyczne,
py ,
ponieważ czasami łatwiej jest rozwiązać
zadanie dualne (mniej zmiennych).
25
Zadanie dualne
Na podstawie metody geometrycznej:

Z(A) = 10800
A(0,9)

B(3/ 2,9 / 2)
Z(B) = 6300


C(5,1)
Z(C) = 4200
MIN

D(10 0)
D(10,0)
Z(D) 6000
Z(D) = 6000
Aby koszt materiałów był najmniejszy i wynosił 4200, konkurent
musi zapłacić za jednostkę S1 5, a za jednostkę S2 1.
26
Zadanie dualne
Na podstawie twierdzenia o dualności:
M k i FC d i i t j t ó i i FC
Maksimum FC zadania pierwotnego jest równe minimum FC
zadania dualnego.
Zysk p y
y producenta wyniesie również 4200
Jakie jest rozwiązanie zadania pierwotnego?
Twierdzenie o równowadze.
27
Zadanie dualne
Twierdzenie o równowadze
Jeżeli i ty warunek zadania pierwotnego (ZP) jest (chociaż w
jednym) optymalnym rozwiązaniu spełniony z nierównością
( t ) t di d j i t i (d l )
(ostro), to odpowiadająca mu i ta zmienna yi w (dowolnym)
optymalnym rozwiązaniu zadania dualnego (ZD) przyjmuje
wartość zero.
a ość e o
Dla zmiennej xi>0 w rozwiązaniu optymalnym ZP
odpowiadające jej i te ograniczenie w ZD jest ograniczeniem
równościowym.
ó ś
Twierdzenie jest również słuszne w przeciwną stronę.
28
Zadanie dualne
Rozwiązanie przykładu:
y1 y2
y1 = 5 y2 =1
Sprawdzenie ograniczeń ZD:
j = 1: 5 + 4�"1 > 8
j = 2: 3�"5 +1 > 9
j = 3: 5 +1 = 6
3 5 1 6
j = 4: 5 + 5�"1 =10
Nierówności ostre dla j = 1 i j = 2:
Dla rozwiązania optymalnego ZP x1 = 0 i x2 = 0
29
Zadanie dualne
y1 = 5 > 0 y2 = 1 > 0
Ponieważ:
Oii 1 i 2 ZP ii i ó ś ii
Ograniczenia 1 i 2 w ZP są ograniczeniami równościowymi
(przy czym x1 =0, x2 =0):
x3 + x4 = 600
x3 + 5x4 =1200
x3 = 450 x4 =150
30
Zadanie dualne
Odpowiedz
do zadania pierwotnego:
Aby zysk był maksymalny producent musi wyprodukować 450
Aby zysk był maksymalny, producent musi wyprodukować 450
jednostek W3 i 150 jednostek W4. Zysk wyniesie 4200.
31
Szczegółowe zasady
formułowania zadania dualnego
formułowania zadania dualnego
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
maksymalizacja minimalizacja
maksymalizacja minimalizacja
33
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
Ograniczenia Zmienne
i te: y d" 0
i - te: yi d" 0
e"
e"
i - te: yi e" 0
d"
=
i - te: yi dowolne
34
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
Zmienne Ograniczenia
x e" 0 j te:
xj e" 0 j - te:
e"
e"
xj d" 0 j - te:
d"
=
xj dowolne j te:
j -
j
35
Szczegółowe zasady formułowania zadania dualnego
Przykład 3.
Dla podanego zadania pierwotnego zapisać zadanie dualne.
pg p g p
FC : Z(x) = 2x1 + 3x2 + x3 + x4 MAX
O: x1 + 2x2 - 3x3 + x4 = 20
2 + + 3 d" 50
2x1 + x2 + 3x3 - x4 d" 50
3x1 - x2 + x3 + 2x4 e" 40
WB : x1 e" 0 x2 e" 0 x3 d" 0 x4 dowolne
36
Szczegółowe zasady formułowania zadania dualnego
Zadanie dualne:

FC : Z(y) = 20y1 + 50y2 + 40y3 MIN
y1 + 2y2 + 3y3 e" 2
O:
2y + y y e" 3
2y1 + y2 - y3 e" 3
-3y1 + 3y2 + y3 d"1
y y + 2y 1
y1 - y2 + 2y3 =1
y1 y2 y3
y1 dowolne y2 e" 0 y3 d" 0
WB :
WB :
37
Na dzisiaj wystarczy
Na dzisiaj wystarczy...
38