A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 1
ZAGADNIENIE DUALNE
Rozważmy zagadnienie liniowe (zagadnienie to nazywamy
prymalnym) o postaci kanonicznej:
max z = c1x1 + c2x2 + � � � + cnxn
a11x1 + a12x2 + � � � + a1nxn d" b1
a21x1 + a22x2 + � � � + a2nxn d" b2
. . .
. . .
. . .
am1x1 + am2x2 + � � � + amnxn d" bm
xj e" 0 (j = 1, 2, . . . , n)
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 2
Zagadnienie dualne definiuje si� nast� aco:
e epuj�
min w = b1y1 + b2y2 + � � � + bmym
a11y1 + a21y2 + � � � + am1ym e" c1
a12y1 + a22y2 + � � � + am2ym e" c2
. . .
. . .
. . .
a1ny1 + a2ny2 + � � � + amnym e" cn
yi e" 0 (i = 1, 2, . . . , m)
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 3
Budow� zagadnienia dualnego ilustruje tablica ??
e
Tab. 1: Budowa zagadnienia dualnego
max z
min w (x1 e" 0) (x2 e" 0) � � � (xn e" 0)
x1 x2 xn
(y1 e" 0) y1 a11 a12 � � � a1n d" b1
(y2 e" 0) y2 a21 a22 � � � a2n d" b2
. . . . . .
. . . . . .
. . . . . .
(ym e" 0) ym am1 am2 � � � amn d" bm
e" c1 e" c2 e" cn
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 4
Przykład 1. Zakład meblowy STYL produkuje stoły i fotele.
Wyprodukowany stół przynosi 160 zł. zysku a fotel 200 zł. Produkcja
stołów i foteli limitowana jest godzinami pracy, ilości� posiadanego
a
drewna i powierzchni� magazynowania. Zużycie tych zasobów oraz ich
a
dzienne limity s� nast� ace:
a epuj�
Zużycie zasobów
Zasoby Stół Fotel Limit dzienny(godz.)
Praca(godz.) 2 4 40
Drewno(m3) 18 18 216
Powierz.(m2) 24 12 240
Jaki powinien być dzienny plan produkcji maksymalizuj� zysk?
acy
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 5
Model prymalny:
max z = 160x1 + 200x2
2x1 + 4x2 d" 40
18x1 + 18x2 d" 216
24x1 + 12x2 d" 240
x1, x2 e" 0.
Model dualny
min w = 40y1 + 216y2 + 40y3
2y1 + 18y2 + 24y3 e" 160
4y1 + 18y2 + 12y3 e" 200
y1, y2, y3 e" 0.
Ekonomiczna interpretacja zagadnienia dualnego.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 6
Budowa zagadnienia dualnego dla dowolnej postaci zagadnienia
programowania liniowego - przykład.
max z = 2x1 + x2 min w = 2y1 + 3y2 + y3
x1 + x2 = 2 �! y1 - dowolna
2x1 - x2 e" 3 �! y2 d" 0
x1 - x2 d" 1 �! y3 e" 0
x1 e" 0 �! y1 + 2y2 + y3 e" 2
x2 - dowolna �! y1 - y2 - y3 = 1.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 7
Podstawowe zwi� edzy zagadnieniami pierwotnym i
azki pomi�
dualnym
Twierdzenie 1. Zagadnienie dualne do dualnego jest zagadnieniem
pierwotnym.
Twierdzenie 2. Wartość funkcji celu z dla dowolnego rozwi�
azania
dopuszczalnego zagadnienia pierwotnego jest nie wi�
eksza niż wartość
funkcji celu w dla dowolnego rozwi�
azania zagadnienia dualnego.
Z tego twierdzenia mamy dwa wnioski:
Wniosek 1. Jeśli (x1, x2, . . . , xn) i (y1, y2, . . . , ym) s� rozwi�
a azaniami
dopuszczalnymi odpowiednio zagadnienia pierwotnego i dualnego
takimi, że
z = c1x1 + c2x2 + . . . + cnxn = b1y1 + b2y2 + . . . + bmym = w, to s� to
a
rozwi�
azania optymalne tych zagadnień.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 8
Wniosek 2. Jeśli jedno z zagadnień (pierwotne lub dualne ) nie ma
skończonego rozwi�
azania optymalnego (funkcja celu jest
nieograniczona w zbiorze rozwi�
azań dopuszczalnych ), to drugie
zagadnienie nie ma rozwi�
azań dopuszczalnych (układ ograniczeń jest
sprzeczny).
Natomiast jeśli jedno z zagadnień nie ma rozwiazania dopuszczalnego
�
to jego zagadnienie dualne może albo nie mieć rozwiazania
�
dopuszczalnego albo nie mieć skończonego rozwiazania optymalnego.
�
Twierdzenie 3. Jeśli jedno z zagadnień (pierwotne lub dualne) ma
rozwi� a azania
azanie optymalne, to oba zagadnienia maj� rozwi�
optymalne i wartości funkcji celu tych zagadnień dla rozwi�
azań
optymalnych s� sobie równe.
a
Rozwiazujac metod� sympleks zagadnienia pierwotne z optymalnej
� � a
tablicy można odczytać rozwiazanie optymalne zagadnienia dualnego.
�
Rozważmy model liniowy dla firmy STYL. Optymaln� tablic�
a a
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 9
sympleksow� jest:
a
s1 s2 s3 x1 x2
1 1
200 x2 - 0 0 1 8
2 18
1
160 x1 -1 0 1 0 4
2 9
0 s3 6 -2 1 0 0 48
20
z 20 0 0 0 2240
3
Zmiennymi bazowymi rozwiazania optymalnego s� ZB = {x2, x1, s3}
� a
�ł łł
4 2 0
�ł śł
�ł śł. Macierz
natomiast baz� tego rozwiazania jest B =
a �
18 18 0
�ł �ł
12 24 1
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 10
�ł łł
1 1
- 0
2 18
�ł śł
1
�ł śł
odwrotna B-1 = znajduje si� w kolumnach
e
-1 0
�ł �ł
2 9
6 -2 1
s1, s2, s3 tablicy optymalnej. Rozwiazanie optymalne zagadnienia
�
dualnego (y1, y2, y3) można wyznaczyć korzystajac z macierzy B-1
�
nast� aco:
epuj�
�ł łł
1 1
- 0
2 18
�ł śł
20
1
�ł śł
(y1, y2, y3) = cBB-1 = (200, 160, 0) = (20, , 0).
-1 0
�ł �ł
2 9
3
6 -2 1
gdzie wektor cB zawiera współczynniki funkcji celu odpowiadajace
�
zmiennym bazowym. W tablicy optymalnej to rozwiazanie znajduje
�
si� w kolumnach s1, s2, s3 wiersza wskaz
ników optymalności.
e
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 11
Jeśli zagadnienie pierwotne jest w dowolnej postaci, to rozwiazanie
�
optymalne odczytujemy z optymalnej tablicy sympleksowej
nastepuj�
aco:
" Optymalna wartość zmiennej dualnej yi odpowiadaj�
acej
ograniczeniu  d" = współczynnik kolumny si wiersza wskaz
ników
optymalnośći.
" Optymalna wartość zmiennej dualnej yi odpowiadaj�
acej
ograniczeniu  e" = -(współczynnik kolumy ei wiersza wskaz
ników
optymalności).
" Optymalna wartość zmiennej dualnej yi odpowiadaj�
acej
ograniczeniu  = = (współczynnikowi kolumny ai wiersza
wskaz
ników optymalności)- M.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 12
Zmienna ei jest zmienn� któr� odejmujemy od lewej strony
a, a
ograniczenia postaci  e" , aby zamienić je na równanie, a zmienna ai
jest zmienn� sztuczn� w M- metodzie, któr� dodajemy do lewej
a a a
strony ograniczenia w postaci równania. Dla ilustracji rozważmy
zagadnienie:
max z = 3x1 + 2x2 + 5x5
x1 + 3x2 + 2x3 d" 15
2x2 - x3 e" 5
2x1 + x2 - 5x3 = 10
x1, x2, x3 e" 0.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 13
Dodajac odpowiednie zmienne mamy:
�
max z = 3x1 + 2x2 + 5x5 - Ma2 - Ma3
x1 + 3x2 + 2x3 + s1 = 15
2x2 - x3 - e2 + a2 = 5
2x1 + x2 - 5x3 + a3 = 10
x1, x2, x3, s1, a2, a3 e" 0.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 14
Optymalna tablica jest nast� �
epujaca:
x1 x2 x3 s1 e2 a2 a3
4 5 5 2 15
5 x3 0 0 1 - -
23 23 23 23 23
2 9 9 1 65
2 x2 0 1 0 - -
23 23 23 23 23
9 17 7 120
3 x1 1 0 0 -17
23 23 23 23 23
51 58 58 9 565
z 0 0 0 M - M +
23 23 23 23 23
Zagadnienie dualne ma postać:
min w = 15y1 + 5y2 + 10y3
y1 + 2y3 e" 3
3y1 + 2y2 + y3 e" 2
2y1 - y2 - 5y3 e" 5
y1 e" 0, y2 d" 0, y3 - dowolna.
A. Kasperski, M. Kulej Badania Operacyjne - programowanie liniowe 15
Odczytuj� rozwiazanie optymalne zagadnienia dualnego z
ac �
optymalnej tablicy sympleks mamy: ograniczenie pierwsze jest
51
nierównościa  d" to y1 = (współczynnik optymalności w kolumnie
�
23
s1), drugie ograniczenie jest nierównościa  e" to y2 = -58 (-
�
23
współczynnik optymalności w kolumnie e2), trzecie ograniczenie jest
9
równościa zatem y3 = (współczynnik optymalności w kolumnie a3
�
23
- M). Optymalna wartość rozwiazania dualnego wynosi
�
9 565
w = 1551 + 5(-58) + 1023 = i jest równa optymalnej wartości
23 23 23
funkcji celu zagadnienia pierwotnego.