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 wskaznikó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 wskazników
optymalnośći.
" Optymalna wartość zmiennej dualnej yi odpowiadaj
acej
ograniczeniu e" = -(współczynnik kolumy ei wiersza wskazników
optymalności).
" Optymalna wartość zmiennej dualnej yi odpowiadaj
acej
ograniczeniu = = (współczynnikowi kolumny ai wiersza
wskaznikó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.
Wyszukiwarka
Podobne podstrony:
Lecture4 Med Women Monsters Filmlecture 2PP1 lecture 4Bezhanshivili Lattices and Topology (Lecture Presentation)wfhss conf20070503 lecture29 enFeynman Lectures on Physics Volume 1 ChapterSyntax lecture3Lecture POLAND Competitiv2008Telecommunication Systems and Networks 2011 2012 Lecture 6CJ Lecture 6lecture 14 Intro to lg morph LECTURE2014LECTURE Stuarts Part IILecture8 SlabTrackSyntax lecture12010 lecture 5 transl groupswięcej podobnych podstron