Standardowe zadanie
programowania liniowego
Gliwice
1
Standardowe zadanie programowania liniowego
Rozważamy proces, w którym zmiennymi są x1, x2, & , xn.
Proces poddany jest m ograniczeniom, zapisanymi w postaci
a11x1 + a12x2 + ...+ a1nxn = b1
a21x1 + a22x2 + ...+ a2nxn = b2
(1)
...
am1x1 + am2x2 + ...+ amnxn = bm
aij, bi  znane współczynniki
Gliwice
2
Standardowe zadanie programowania liniowego
Dopuszczamy jedynie nieujemne wartości xj, czyli:
xj e" 0, j =1,2, ...,n
(2)
Zakładamy również, że:
bi e" 0, i =1,2, ...,m
(3)
Z procesem jest związana funkcja celu Z:
Z = c1x1 + c2x2 + ...+ cnxn
(4)
cj, j = 1,2, & ,n  znane współczynniki
Gliwice
3
Standardowe zadanie programowania liniowego
Zagadnienie polega na maksymalizacji (minimalizacji) funkcji
celu Z (4), spełniającej ograniczenia (1), (2), (3).
Model matematyczny:
n
FC : Z =
"c xj MAX
j
j=1
m
ż#
"a xj = bi
ij
�#
j=1 (5)
�#
�#x e" 0,
O : j =1,2, ...,n
�#
j
�#b e" 0,
i =1,2, ...,m
i
�#
�#
�#
Gliwice
4
Standardowe zadanie programowania liniowego
Zapis w postaci macierzowej
FC : Z = cTx MAX
Ax = b
ż#
(6)
�#
O: x e" 0
�#
�#
b e" 0
�#
a11 a12 ... a1n c1 x1 b1
Ą# ń#Ą# ń#Ą# ń# Ą# ń#
ó#aa22 ... a2n Ą#ó#c Ą#ó#x Ą# ó#b Ą#
21 2 2
ó# Ą#ó# Ą#ó# Ą# ó# Ą#
A = c =2
x = b =
ó# ... ... ... ... Ą#ó#...Ą#ó#...Ą# ó#...Ą#
ó#aam2 ... amn Ą#ó#c Ą#ó#x Ą# ó#b Ą#
Ł# m1 Ś#Ł# n Ś#Ł# n Ś# Ł# n Ś#
Gliwice
5
Standardowe zadanie programowania liniowego
Przykład 1
Zakład zamierza rozpocząć produkcję dwóch wyrobów: W1 i W2.
Wśród środków produkcyjnych, które zostaną użyte w procesie
produkcji dwa są limitowane. Limity te wynoszą: dla środka
pierwszego S1 63 kilogramy, dla środka drugiego S2 64 kilogramy.
Aby wyprodukować jeden wyrób W1 potrzeba 9 kg środka S1 oraz
8 kg środka S2. Aby wyprodukować jeden wyrób W2 potrzeba 7 kg
środka S1 oraz 8 kg środka S2. Wyrób W1 będzie produkowany
jednocześnie na 3 maszynach, a wyrób W2 na
2 maszynach. Koszty przestrojenia maszyn zwrócą się po
wyprodukowaniu łącznie 6 sztuk wyrobów.
Wiedząc, że cena za wyrób W1 będzie wynosić 6 zł, a cena za
wyrób W2 5 zł określić wielkość produkcji, która zoptymalizuje
zysk ze sprzedaży.
Gliwice
6
Standardowe zadanie programowania liniowego
W1 W2
S1
S2
ilość
maszyn
cena
Gliwice
7
Standardowe zadanie programowania liniowego
Zmienne decyzyjne:
x1 
x2 
Gliwice
8
Standardowe zadanie programowania liniowego
Funkcja celu (FC):
Z x1, x2 =
( )
Ograniczenia (O):
1
2
3
Warunki brzegowe (WB):
x1 , x2
Gliwice
9
Standardowe zadanie programowania liniowego
Zadanie programowania liniowego
Z x1, x2 =
FC: ( )
O:
1
2
3
x1 , x2
WB:

Gliwice
10
Metoda geometryczna
Gliwice
11
Metoda geometryczna
x2
10
9
8
7
6
5
4
3
2
1
x1
1 2 3 4 5 6 7 8 9 10
Gliwice
12
Metoda geometryczna
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
Odpowiedz
:
Gliwice
13
Zadanie dualne
Gliwice
14
Zadanie dualne
Przykład 2
Zakład produkuje cztery wyroby (F1, F2, F3 i F4). 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 przedstawione
w tabeli.
Znając jednostkowe ceny wyrobów, określić taki plan produkcji,
aby zysk był maksymalny.
Gliwice
15
Zadanie dualne
F1 F2 F3 F4
S1
1311 600
S2
4 1 1 5 1200
cena 8 9 6 10
Zmienne decyzyjne:
xi  wielkość produkcji wyrobu Fi, i = 1& 4
Gliwice
16
Zadanie dualne
MODEL MATEMATYCZNY:
Funkcja celu (FC):
Z x1, x2, x3, x4 = 8x1 + 9x2 + 6x3 +10x4 MAX
()
Ograniczenia (O):
x1 + 3x2 + x3 + x4 d" 600
4x1 + x2 + x3 + 5x4 d"1200
Warunki brzegowe (WB):
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0
Gliwice
17
Zadanie dualne
Zadanie pierwotne (ZP):
FC: Z = cTx MAX
O: Ax d" b
WB: x e" 0
Zadanie dualne (ZD):
FC: � = bTy MIN
O: ATy e" c
WB: y e" 0
Gliwice
18
Zadanie dualne
MODEL MATEMATYCZNY ZADANIA DUALNEGO:
Funkcja celu (FC):
� y1, y2 =
()
Ograniczenia (O):
1
2
3
4
Warunki brzegowe (WB):
y1 , y2
Gliwice
19
Zadanie dualne
Interpretacja zadania dualnego
Zmienne decyzyjne w zadaniu dualnym:
y1 
y2 
� y1, y2 =
()
Gliwice
20
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 uzyskałby ze
sprzedaży wyrobów, które produkuje
Gliwice
21
Zadanie dualne
Twierdzenie o dualności
Zadanie pierwotne ma rozwiązanie wtedy i tylko wtedy, gdy
zadanie dualne ma rozwiązanie, oraz:
Z MAX = � MIN
( ) ( )
Gliwice
22
Zadanie dualne
Na podstawie metody geometrycznej:
A 0,9
( ) � A =10800
( )
B 3/ 2,9/ 2
() � B = 6300
( )
C 5,1 MIN
( ) � C = 4200
( )
D 10,0
() � D = 6000
( )
Aby koszt materiałów był najmniejszy i wynosił 4200 zł, konkurent
musi zapłacić za jednostkę S1 5 zł, a za jednostkę S2 1 zł.
Gliwice
23
Zadanie dualne
Na podstawie twierdzenia o dualności:
Maksimum FC zadania pierwotnego jest równe minimum FC
zadania dualnego.
Zysk producenta wyniesie również 4200 zł.
Jakie jest rozwiązanie zadania pierwotnego?
TWIERDZENIE O RÓWNOWADZE.
Gliwice
24
Zadanie dualne
Twierdzenie o równowadze
Jeżeli i-ty warunek zadania pierwotnego (ZP) jest (chociaż
w jednym) w optymalnym rozwiązaniu spełniony z nierównością
(w sposób ostry), to odpowiadająca mu i-ta zmienna yi
w (dowolnym) optymalnym rozwiązaniu zadania dualnego (ZD)
przyjmuje wartość zero.
Dla zmiennej xi>0 w rozwiązaniu optymalnym ZP odpowiadające
jej i-te ograniczenie w ZD jest ograniczeniem równościowym.
Twierdzenie o równowadze jest również słuszne
w przeciwną stronę
Gliwice
25
Zadanie dualne
Rozwiązanie przykładu:
y1 = 5, y2 =1
Sprawdzenie ograniczeń ZD:
j = 1:
j = 2:
j = 3:
j = 4:
Nierówności ostre dla
W rozwiązaniu optymalnym ZP
Gliwice
26
Zadanie dualne
y1 = 5 > 0, y2 = 1 > 0
Ponieważ:
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
Z x1, x2, x3, x4 = 8�"0 + 9�"0 + 6�" 450 +10�"150 = 4200
FC: ()
Gliwice
27
Zadanie dualne
Odpowiedz
do zadania pierwotnego:
Aby zysk był maksymalny, producent musi wyprodukować
450 jednostek F3 oraz 150 jednostek F4. Zysk wyniesie 4200.
Gliwice
28
Szczegółowe zasady
formułowania zadania dualnego
Gliwice
29
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
maksymalizacja minimalizacja
Gliwice
30
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
Ograniczenia: Zmienne:
i  te: e" yi d" 0
i  te: d" yi e" 0
yi dowolne
i  te: =
Gliwice
31
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne Zadanie dualne
Zmienne: Ograniczenia:
xj e" 0 j  te: e"
xj d" 0 j  te: d"
xj dowolne j  te: =
Gliwice
32
Szczegółowe zasady formułowania zadania dualnego
Przykład 3
Dla podanego zadania pierwotnego zapisać zadanie dualne.
Z x = 2x1 + 3x2 + x3 + x4 MAX
FC: ( )
O:
x1 + 2x2 - 3x3 + x4 = 20
2x1 + x2 + 3x3 - x4 d" 50
3x1 - x2 + x3 + 2x4 e" 40
x1 e" 0, x2 e" 0, x3 d" 0, x4 dowolne
WB:
Gliwice
33
Szczegółowe zasady formułowania zadania dualnego
Zadanie dualne:
FC: � y =
( )
O:
WB:
Gliwice
34