Programowanie liniowe 
Programowanie liniowe 
zagadnienia dualne
zagadnienia dualne
Z ka\
dym zadaniem programowania liniowego w postaci klasycznej (zadanie
prymarne PL), mo\
na związać odpowiadające mu zadanie dualne
Rozpatrzmy, znany ju\
przykład zadania PL: w postaci klasycznej:
w postaci klasycznej: w postaci macierzowej:
w postaci klasycznej w postaci macierzowej:
cx max
2x1 + 3x2 max
Ax d" b
x e" 0
2x1 + 2x2 d"14
x1
îÅ‚ Å‚Å‚
x1 + 2x2 d" 8
c = [2 3] x =
ïÅ‚x śł
ðÅ‚ 2 ûÅ‚
4x1 d"16
2 2
îÅ‚ Å‚Å‚
14
îÅ‚ Å‚Å‚
ïÅ‚2 2śł
A =
x1, x2 e" 0
ïÅ‚ śł
ïÅ‚ śł
b = 8
ïÅ‚ śł
ïÅ‚ śł
ðÅ‚4 0ûÅ‚
ïÅ‚
ðÅ‚16śł
ûÅ‚
y1, y2, y3
ceny wykorzystywanych surowców S1, S2, i S3
Oznaczmy przez :
i potraktujmy je jako zmienne decyzyjne
Mo\
emy zatem zbudować nowy model matematyczny, którego rozwiązanie pozwoli
określić, jakie powinny być wartości tych zmiennych aby zminimalizować
wartości posiadanych środków.
Zało\
eniem oczywistym jest, \
e wartość surowców wykorzystanych do
wytworzenia jednej jednostki produktu P1 i produktu P2 sÄ… nie mniejsze od zysku
osiągniętego z wytworzenia jednostki produktów (odpowiednio P1 i P2 )
Ogólna wartość posiadanych surowców:
P1 P2 ZASOBY
S1 2 2 14 14y1 + 8y2 +16y3
S2 1 2 8 Wartość surowców potrzebna do wytworzenia:
S3 4 0 16
2y1 + y2 + 4y3
ZYSK 2 3 produktu P1
2y1 + 2y2
produktu P2
Zadanie minimalizacji wartości zastosowanych surowców do produkcji
wyrobów P1 i P2 przy ograniczeniach na wartości tych surowców zapiszemy
następująco:
14y1 + 8y2 +16y3 min
2y1 + y2 + 4y3 e" 2
2y1 + 2y2 e" 3
y1, y2, y3 e" 0
Zadanie to mo\
na zapisać w postaci macierzowej:
Określając wektor zmiennych decyzyjnych jako y = [y1, y2, y3] otrzymamy:
yb min
yA e" c
y e" 0
jest to zadnienie dualne do uprzednio przedstawionego zadania prymarnego
zadnienie dualne zadania prymarnego
Zadania prymarne i dualne programowania liniowego charakteryzujÄ… siÄ™
następującymi własnościami:
1. Ka\
demu warunkowi ograniczającemu jednego z problemów odpowiada
zmienna decyzyjna drugiego Zmienna tÄ™ nazywamy zmiennÄ… komplementarnÄ…
zmiennÄ… komplementarnÄ…
do danego warunku ograniczajÄ…cego
Zadania prymarne i dualne programowania liniowego charakteryzujÄ… siÄ™
następującymi własnościami:
1. Ka\
demu warunkowi ograniczającemu jednego z problemów odpowiada
zmienna decyzyjna drugiego Zmienna tÄ™ nazywamy zmiennÄ… komplementarnÄ…
zmiennÄ… komplementarnÄ…
do danego warunku ograniczajÄ…cego
W zadaniu dualnym zmiennymi komplementarnymi do pierwszego, drugiego i
trzeciego warunku ograniczajÄ…cego zadania prymarnego sÄ…, odpowiednio, zmienne
natomiast w zadaniu prymarnym zmiennymi komplementarnymi do
y1, y2, y3
pierwszego i drugiego warunku ograniczajÄ…cego zadaniu dualnego sÄ…, odpowiednio,
x1 i x2
zmienne
Zadania prymarne i dualne programowania liniowego charakteryzujÄ… siÄ™
następującymi własnościami:
1. Ka\
demu warunkowi ograniczającemu jednego z problemów odpowiada
zmienna decyzyjna drugiego Zmienna tÄ™ nazywamy zmiennÄ… komplementarnÄ…
zmiennÄ… komplementarnÄ…
do danego warunku ograniczajÄ…cego
2. Ka\
dej nieujemnej zmiennej decyzyjnej jednego z problemów odpowiada
warunek ograniczajÄ…cy drugiego.
Warunek ten nazywamy warunkiem komplementarnym do danej zmiennej
warunkiem komplementarnym
decyzyjnej
Zadania prymarne i dualne programowania liniowego charakteryzujÄ… siÄ™
następującymi własnościami:
1. Ka\
demu warunkowi ograniczającemu jednego z problemów odpowiada
zmienna decyzyjna drugiego Zmienna tÄ™ nazywamy zmiennÄ… komplementarnÄ…
zmiennÄ… komplementarnÄ…
do danego warunku ograniczajÄ…cego
2. Ka\
dej nieujemnej zmiennej decyzyjnej jednego z problemów odpowiada
warunek ograniczajÄ…cy drugiego.
Warunek ten nazywamy warunkiem komplementarnym do danej zmiennej
warunkiem komplementarnym
decyzyjnej
W rozpatrywanym zadaniu prymarnym zmiennym x i x odpowiadajÄ… komplementarne
1 2
y1, y2, y3
warunki ograniczajÄ…ce: pierwszy i drugi zadania dualnego, natomiast zmiennym
w zadaniu dualnym odpowiadajÄ… komplementarne warunki ograniczajÄ…ce: pierwszy, drugi i
trzeci zadania prymarnego
Zadania prymarne i dualne programowania liniowego charakteryzujÄ… siÄ™
następującymi własnościami:
1. Ka\
demu warunkowi ograniczającemu jednego z problemów odpowiada
zmienna decyzyjna drugiego Zmienna tÄ™ nazywamy zmiennÄ… komplementarnÄ…
zmiennÄ… komplementarnÄ…
do danego warunku ograniczajÄ…cego
2. Ka\
dej nieujemnej zmiennej decyzyjnej jednego z problemów odpowiada
warunek ograniczajÄ…cy drugiego.
Warunek ten nazywamy warunkiem komplementarnym do danej zmiennej
warunkiem komplementarnym
decyzyjnej
3. Wektor współczynników przy funkcji celu w jednym zadaniu staje się
wektorem wyrazów wolnych w drugim, i odwrotnie, wektor wyrazów
wolnych w jednym zadaniu jest wektorem współczynników przy funkcji
celu w drugi.
4. Kierunki optymalizacji dla zadań dualnych są przeciwne.
O ile zadanie prymarne jest zadaniem maksymalizacji, to w odpowiadajÄ…cym mu
zadaniu dualnym funkcje celu minimalizujemy.
5. Zwroty nierówności w warunkach ograniczających zadania prymarnego są
przeciwne do zwrotów nierówności warunków ograniczających zadaniu
dualnego.
Podstawowe twierdzenia o dualności
Podstawowe twierdzenia o dualności
TWIERDZENIE 1
Je\
eli x i y sÄ… dowolnymi rozwiÄ…zaniami dopuszczalnymi, odpowiednio,
zadania prymarnego i dualnego, to wartości funkcji celu w tych zadaniach
spełniają zale\
ność:
cx d" yb
TWIERDZENIE 2 ( o komplementarności)
Je\
eli x i y sÄ… rozwiÄ…zaniami optymalnymi, odpowiednio, zadania prymarnego
i dualnego, to zachodzÄ… zwiÄ…zki:
y ( b  Ax ) = 0 zwiÄ…zek (1)
x (yA - c ) = 0 zwiÄ…zek (2)
TWIERDZENIE 3
Dla rozwiązań optymalnych x i y odpowiednio, zadania prymarnego i
dualnego zachodzi zwiÄ…zek:
c x = y b
Przykład zastosowania twierdzenia o komplementarności
twierdzenia o komplementarności
rozpiszmy zwiÄ…zek (1)
ëÅ‚ 14 2 2 öÅ‚ ëÅ‚ 14 - 2x1 - 2x2 öÅ‚
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚÷Å‚
ìÅ‚
ïÅ‚ śł ïÅ‚1 2śł Å" îÅ‚x1 Å‚Å‚÷Å‚ = ìÅ‚ ïÅ‚ śł÷Å‚
y ( b  Ax ) = [y1, y2, y3] 8 -
ìÅ‚
ïÅ‚x śł÷Å‚ ìÅ‚ ïÅ‚ 8 - x1 - 2x2 śł÷Å‚ =
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ 2 ûÅ‚
ìÅ‚ ÷Å‚ ìÅ‚
ïÅ‚ ïÅ‚ śłłł
16 - 4x1 ûÅ‚
ðÅ‚16śł ïÅ‚ 0ûÅ‚ ðÅ‚
ûÅ‚ ðÅ‚4 śł
íÅ‚ Å‚Å‚ íÅ‚
= y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
rozpiszmy zwiÄ…zek (2)
ëÅ‚ 2 2 öÅ‚
îÅ‚ Å‚Å‚
ìÅ‚
öÅ‚
ïÅ‚1 2śł - îÅ‚2Å‚Å‚÷Å‚ îÅ‚ x1 Å‚Å‚ = ëÅ‚ îÅ‚2y1 + y2 + 4y3 - 2Å‚Å‚÷Å‚ îÅ‚ x1 Å‚Å‚ =
ìÅ‚
(yA - c ) x = [y1, y2, y3]Å"
ìÅ‚
ïÅ‚3śł÷Å‚Å" ïÅ‚x śł ïÅ‚ śł÷Å‚Å" ïÅ‚x śł
ìÅ‚
ïÅ‚ śł
2y1 + 2y2 - 3
ðÅ‚ ûÅ‚ ðÅ‚ 2 ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ 2 ûÅ‚
ìÅ‚ ÷Å‚
íÅ‚ Å‚Å‚
ïÅ‚ śł
ðÅ‚4 0ûÅ‚
íÅ‚ Å‚Å‚
= (2y1 + y2 + 4y3 - 2)x1 + (2y1 + 2y2 - 3)x2 = 0
ze zwiÄ…zku (1)
y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
ze zwiÄ…zku (1)
y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
1 składnik 2 składnik 3 składnik
ze zwiÄ…zku (1)
y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
1 składnik + 2 składnik + 3 składnik
suma tych składników ma dać wartość zero
ze zwiÄ…zku (1)
y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
1 składnik + 2 składnik + 3 składnik
suma tych składników ma dać wartość zero
Wynika stÄ…d, \
e ka\
dy składnik tej sumy musi być równy zeru.
ze zwiÄ…zku (1)
y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
1 składnik + 2 składnik + 3 składnik
suma tych składników ma dać wartość zero
Wynika stÄ…d, \
e ka\
dy składnik tej sumy musi być równy zeru.
bo gdyby choć jeden z tych składników był dodatni, to
przynajmniej jeden musiałby przyjąć wartość ujemną a to
nie jest mo\
liwe

z równania (1) y1(14 - 2x1 - 2x2)+ y2(8 - x1 - 2x2)+ y3(16 - 4x1)= 0
z równania (1)
otrzymamy zale\
ności:

y1(14 - 2x1 - 2x2 ) = 0
zale\
ność (1a)
y2(8 - x1 - 2x2 ) = 0
zale\
ność (1b)

zale\
ność (1c)
y3(16 - 4x1) = 0

Warunek (1a)
Je\
eli, to Oznacza to, \
e przy zadaniu prymarnym
14 - 2x1 - 2x2 = 0
y1 > 0
pierwszy warunek ograniczajÄ…cy, komplementarny do zmiennej ,
y1 > 0
musi być spełniony jako równanie.
Je\
eli (czyli w zadaniu prymarnym pierwszy warunek
14 - 2x1 - 2x2 > 0
ograniczający jest spełniony jako nierówność ostra) 
to zmienna komplementarna
y1 = 0
(2y1 + y2 + 4y3 - 2)x1 + (2y1 + 2y2 - 3)x2 = 0
z równania (2)
z równania (2)

=0
=0
otrzymamy zale\
ności:
(2y1 + y2 + 4y3 - 2)x1 = 0

zale\
ność (2a)
(2y1 + 2y2 - 3)x2 = 0
zale\
ność (2b)

Warunek (2a)
Je\
eli, co oznacza \
e pierwszy warunek ograniczajÄ…cy w
2y1 + y2 + 4y3-2 > 0
zadaniu dualnym jest spełniony jako ostra nierówność), to zmienna
x1 = 0
komplementarna
Je\
eli to Oznacza to, \
e pierwszy
x1 > 0 2y1 + y2 + 4y3 - 2 = 0
warunek ograniczajÄ…cy w zadaniu dualnym, komplementarny do zmiennej
musi być spełniony jako równanie
Uogólnienie przedstawionych warunków
1. Je\
eli dowolna zmienna w rozwiÄ…zaniu optymalnym zadania prymarnego
lub dualnego jest dodatnia, to odpowiadajÄ…cy jej komplementarny
dodatnia
warunek ograniczający spełniony jest jako równanie
równanie
2. Je\
eli dowolny warunek ograniczajÄ…cy dla rozwiÄ…zania optymalnego zadania
prymarnego lub dualnego spełniony jest jako ostra nierówność, to
ostra nierówność
odpowiadajÄ…ca temu warunkowi zmienna komplementarna przyjmuje
wartość zero.
zero
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
x1 = 4, x2 = 2
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
x1, x2 e" 0
Poniewa\
zmienne
x1 = 4, x2 = 2
więc odpowiadające im warunki komplementarne
muszą być spełnione jako równania
2y1+ y2 + 4y3 = 2
2y1+2y2 = 3
Uogólnienie przedstawionych warunków
1. Je\
eli dowolna zmienna w rozwiÄ…zaniu optymalnym zadania prymarnego
lub dualnego jest dodatnia, to odpowiadajÄ…cy jej komplementarny
dodatnia
warunek ograniczający spełniony jest jako równanie
równanie
2. Je\
eli dowolny warunek ograniczajÄ…cy dla rozwiÄ…zania optymalnego zadania
prymarnego lub dualnego spełniony jest jako ostra nierówność, to
ostra nierówność
odpowiadajÄ…ca temu warunkowi zmienna komplementarna przyjmuje
wartość zero.
zero
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
x1, x2 e" 0
Poniewa\
zmienne
x1 = 4, x2 = 2
więc odpowiadające im warunki komplementarne
muszą być spełnione jako równania
2y1+ y2 + 4y3 = 2
2y1+2y2 = 3
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
Sprawdz
my teraz, które z warunków ograniczających zadania prymarnego są
spełnione jako nierówności ostre.
Uogólnienie przedstawionych warunków
1. Je\
eli dowolna zmienna w rozwiÄ…zaniu optymalnym zadania prymarnego
lub dualnego jest dodatnia, to odpowiadajÄ…cy jej komplementarny
dodatnia
warunek ograniczający spełniony jest jako równanie
równanie
2. Je\
eli dowolny warunek ograniczajÄ…cy dla rozwiÄ…zania optymalnego
zadania prymarnego lub dualnego spełniony jest jako ostra nierówność, to
ostra nierówność
odpowiadajÄ…ca temu warunkowi zmienna komplementarna przyjmuje
wartość zero.
zero
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
Sprawdz
my teraz, które z warunków ograniczających zadania prymarnego są
x1 = 4, x2 = 2
spełnione jako nierówności ostre. Podstawiając otrzymamy:
2x1 + 2x2 d"14 2Å" 4 + 2Å" 2 < 14
nierówność ostra
x1 + 2x2 d" 8 4 + 2Å" 2 = 8
4x1 d" 16 4Å" 4 =16
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
Poniewa\
pierwszy z warunków ograniczających w zadaniu prymarnym jest
spełniony jako nierówność ostra,
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
Poniewa\
pierwszy z warunków ograniczających w zadaniu prymarnym jest
spełniony jako nierówność ostra, więc odpowiadająca mu w zadaniu dualnym
zmienna komplementarna y1= 0
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
y1= 0
Podstawiając do układu równań wartość otrzymujemy
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
y1= 0
Podstawiając do układu równań wartość otrzymujemy
y2 + 4y3 = 2
2y2 = 3
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
2y1+ y2 + 4y3 = 2
x1 = 4, x2 = 2
2y1+2y2 = 3
Podstawiając do układu równań wartość otrzymujemy
y1e" 0
z tego układu wyliczamy dwie pozostałe składowe
y2 + 4y3 = 2
rozwiÄ…zania optymalnego zadania dualnego
2y2 = 3
y2 =1,5 ; y3 = 0,125
Przykład programowania liniowego  zagadnienia dualne
zagadnienie prymarne zagadnienie dualne
zagadnienie prymarne zagadnienie dualne
*
f (y1, y2, y3) =14y1 + 8y2 +16y3 min
f (x1, x2) = 2x1 + 3x2 max
2x1 + 2x2 d"14
2y1+ y2 + 4y3 e" 2
2y1+2y2 e" 3
x1 + 2x2 d" 8
4x1 d" 16
y1, y2, y3 e" 0
x1, x2 e" 0
x1 = 4, x2 = 2
y1= 0 y2 =1,5 ; y3 = 0,125
x3 = 2
Zauwa\
my, \
e dodatnie ceny dualne dla środków S2 i S3 pociągają za sobą
całkowite zu\
ycie tych zasobów przy realizacji plany maksymalizacji zysku,
natomiast niepełne zu\
ycie środka S1 w planie optymalnym powoduje to, \
e cena
dualna tego surowca jest równa zeru.
Dualna metoda simpleks  problem do przestudiowania w literaturze
Dualna metoda simpleks