w2cm, NAUKA, Badania operacyjne

A.Kasperski,M.KulejBadaniaOperacyjne-programowanieliniowe
1
ZAGADNIENIEDUALNE
Zkażdymzagadnieniemliniowymzwiązanejestinnezagadnienienazywanedual
nym.Podamyterazterazjakbudowaćzagadnieniedualne,interpretacjeizwiązki
jakie zachodzą między tymi zagadnieniami. Rozważmy zagadnienie liniowe (za
gadnienie to nazywamy prymalnym) o postaci kanonicznej:
max z = c
1
x
1
+ c
2
x
2
+ ··· + c
n
x
n
a
11
x
1
+
a
12
x
2
+ ··· +
a
1n
x
n
b
1
a
21
x
1
+
a
22
x
2
+ ··· +
a
2n
x
n
b
2
.
.
.
.
.
.
.
.
.
a
m1
x
1
+
a
m2
x
2
+ ··· + a
mn
x
n
b
m
x
j
0 (j = 1, 2, . . . , n)
Zagadnienie dualne definiuje się następująco:
min w = b
1
y
1
+ b
2
y
2
+ ··· + b
m
y
m
a
11
y
1
+
a
21
y
2
+ ··· +
a
m1
y
m
c
1
a
12
y
1
+
a
22
y
2
+ ··· +
a
m2
y
m
c
2
.
.
.
.
.
.
.
.
.
a
1n
y
1
+
a
2n
y
2
+ ··· +
a
mn
y
m
c
n
y
i
0 (i = 1, 2, . . . , m)
Budowę zagadnienia dualnego ilustruje tablica 1.1
Tab. 1.1: Budowa zagadniena dualnego
max z
min w
(x
1
0)
(x
2
0) ··· (x
n
0)
x
1
x
2
x
n
(y
1
0)
y
1
a
11
a
12
··· a
1n
b
1
(y
2
0)
y
2
a
21
a
22
··· a
2n
b
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(y
m
0)
y
m
a
m1
a
m2
··· a
mn
b
m
c
1
c
2
c
n
Przykład1.1.
ZakładmeblowySTYLprodukujestołyifotele.Wyprodukowany
stół przynosi 160 zł. zysku a fotel 200 zł. Produkcja stołów i foteli limitowana
jestgodzinamipracy,ilościąposiadanegodrewnaipowierzchniąmagazynowania.
Zużycietychzasobóworazichdziennelimitysąnastępujace:
A.Kasperski,M.KulejBadaniaOperacyjne-programowanieliniowe
2
Zużyciezasobów
Zasoby Stół Fotel Limitdzienny(godz.)
Praca(godz.) 2
4
40
Drewno(
m
3
) 18
18
216
Powierz.(
m
2
) 24
12
240
Jakipowinienbyćdziennyplanprodukcjimaksymalizującyzysk?
Modelprymalny:
max z = 160x
1
+ 200x
2
2x
1
+ 4x
2
40
18x
1
+ 18x
2
216
24x
1
+ 12x
2
240
x
1
, x
2
0.
Modeldualny
min w = 40y
1
+ 216y
2
+ 40y
3
2y
1
+ 18y
2
+ 24y
3
160
4y
1
+ 18y
2
+ 12y
3
200
y
1
, y
2
, y
3
0.
Ekonomiczna interpretacja zagadnienia dualnego.
Załóżmy, że w zakła
dzie STYL pojawia się przedsiębiorca, który chce nabyć wszystkie zasoby zakła
du, tj. 40 godz. pracy, 210 m
3
drewna i 240 m
2
powierzchi magazynowej. Musi
zatem ustalić cenę każdej jednostki zasobu, którą gotów byłby za nie zapłacić.
Niech y
1
, y
2
i y
3
będziecenąodpowiednioza:godz.pracy,metrsześciennydrew
na i metr kwadratowy powierzchni magazynowej. Pokażemy, że te ceny można
wyznaczyć rozwiązując zagadnieniadualne.Całkowity kosztzasobówwyniesie w
tych cenach 40y
1
+ 216y
2
+ 240y
3
a ponieważ przedsiębiorca chce minimalizować
koszty zakupu zasobów to chce wyznaczyć:
min w = 40y
1
+ 216y
2
+ 240y
3
.
Jakie ograniczenia musi uwzględnić przedsiębiorca określając ceny? Ceny musi
ustalić na takim poziomie aby firma STYL zechciała mu sprzedać swoje zaso
by. Na przykład za zasoby, które zakład zużywa do wyprodukowania stołu tj. 2
godz. pracy, 18m
3
drewna i 24m
2
powierzchni magazynowej powinien zapłacić
co najmniej 160 zł. gdyż zakład produkując ten stół osiągnie zysk 160 zł. Zatem
oferując 2y
1
+ 18y
2
+ 24y
3
za zasoby do produkcji stołu musi tak ustalić ceny
y
1
, y
2
, y
3
tak, aby
2y
1
+ 18y
2
+ 24y
3
160.
A.Kasperski,M.KulejBadaniaOperacyjne-programowanieliniowe
3
Analogiczne rozumowanie dla fotela daje ograniczenie:
4y
1
+ 18y
2
+ 12y
3
200.
Muszą też być dodane ograniczenia na nieujemność tych cen tj. y
1
, y
2
, y
3
0, co
razem daje model dualny.
Budowęzagadnieniadualnegodladowolnejpostacizagadnieniaprogramowa
nia liniowego podamy na przykładzie.
max z = 2x
1
+ x
2
min w = 2y
1
+ 3y
2
+ y
3
x
1
+ x
2
= 2 ! y
1
dowolna
2x
1
−x
2
3 ! y
2
0
x
1
−x
2
1 ! y
3
0
x
1
0 ! y
1
+ 2y
2
+ y
3
2
x
2
− dowolna ! y
1
−y
2
− y
3
= 1.
Zauważmy, że każdemu ograniczeniu w modelu pierwotnym odpowiada zmienna
dualna a każdemu warunkowi na zmienną odpowiada ograniczenie w zagadnie
niu dualnym. Ograniczeniu ”
” odpowiada warunek na nieujemność zmiennej
dualnej odpowiadającej temu ograniczeniu, ograniczeniu w postaci równości od
powiadazmiennadualnaodowolnymznakuaograniczeniu”
”ujemnazmienna
dualna. Warunkowi na nieujemność zmiennej w zagadnieniu pierwotnym odpo
wiada w zagadnieniu dualnym ograniczenie ”
” natomiast zmiennej dowolnej
odpowiada w zagadnieniu dualnym ograniczenie w postaci równości. Lewą stro
nę ograniczenia jtego w zagadnieniu dualnym otrzymujemy przemnażając (ska
larnie) jtą kolumnę macierzy ograniczeń zagadnienia pierwotnego przez wektor
zmiennych dualnych a prawą jest współczynnik stojący przy zmiennej x
j
(tj. c
j
)
w funkcji celu zagadnienia pierwotnego. Funkcją celu zagadnienia dualnego jest
iloczyn (skalarny) wektora prawych stron ograniczeń zagadnienia pierwotnego
przez wektor zmiennych dualnych. Jeśli funkcja celu zgadnieia pierwotnego jest
maksymalizowana, to w zagadnieniu dualnym mamy minimalizacje funkcji celu.
Podstawowe związkipomiędzyzagadnieniami pierwotnymidualnym
Twierdzenie 1.1.
Zagadnienie dualne do dualnego jest zagadnieniem pierwot
nym.
Twierdzenie 1.2.
Wartość funkcji celu
z
dla dowolnego rozwiązania dopusz
czalnegozagadnieniapierwotnegojestniewiększaniżwartoścfunkcjicelu
w
dla
dowolnegorozwiązaniazagadnieniadualnego.
Z tego twierdzenia mamy dwa wnioski:
Wniosek 1.1.
Jeśli
(x
1
, x
2
, . . . , x
n
)
i
(y
1
, y
2
, . . . , y
m
)
są rozwiązaniami dopusz
czalnymiodpowiedniozagadnieniapierwotnegoidualnegotakimi,że
z = c
1
x
1
+
c
2
x
2
+ . . . + c
n
x
n
= b
1
y
1
+ b
2
y
2
+ . . . + b
m
y
m
= w
,tosątorozwiązaniaoptymalne
tychzagadnień.
A.Kasperski,M.KulejBadaniaOperacyjne-programowanieliniowe
4
Wniosek1.2.
Jeślijednozzagadnień(pierwotnelubdualne)niemaskończone
gorozwiązaniaoptymalnego(funkcjacelujestnieograniczonawzbiorzerozwiązań
dopuszczalnych),todrugiezagadnienieniemarozwiązańdopuszczalnych(układ
ograniczeńjestsprzeczny).
Natomiast jeśli jedno z zagadnień nie ma rozwiązania dopuszczalnego to jego
zagadnieniedualnemożealboniemiećrozwiązaniadopuszczalnegoalboniemieć
skończonego rozwiązania optymalnego.
Twierdzenie1.3.
Jeślijednozzagadnień(pierwotnelubdualne)marozwiązanie
optymalne,toobazagadnieniamająrozwiązaniaoptymalneiwartościfunkcjicelu
tychzagadnieńdlarozwiązańoptymalnychsąsobierówne.
Rozwiązując metodą sympleks zagadnienia pierwotne z optymalnej tablicy
można odczytać rozwiązanie optymalne zagadnienia dualnego. Rozważmy mo
del liniowy dla firmy STYL. Optymalną tablicą sympleksową jest tablica 1.2:
Zmiennymi bazowymi rozwiązania optymalnego są ZB = {x
2
, x
1
, s
3
} natomiast
Tab. 1.2: Optymalna tablica sympleksowa
s
1
s
2
s
3
x
1
x
2
1
2
−
18
200 x
2
0 0 1
8
160 x
1
−
2
1
9
0 1 0
4
0 s
3
6 2 1 0 0
48
20
3
z 20
0 0 0 2240
2
3
2
3
1
2
−
18
4
2
0
0
4
5
4
5
−
2
1
9
18
18
0
.Macierzodwrotna B
−
1
=
0
bazątegorozwiązaniajest B =
12
24
1
6 −2
1
znajduje się w kolumnach s
1
, s
2
, s
3
tablicy optymalnej. Rozwiązanie optymalne
zagadnienia dualnego (y
1
, y
2
, y
3
) można wyznaczyć korzystając z macierzy B
−
1
następująco:
2
3
1
2
−
18
0
= (20,
20
4
5
(y
1
, y
2
, y
3
) = c
B
B
−
1
= (200, 160, 0)
−
2
1
9
0
3
, 0).
6 −2
1
gdziewektor c
B
zawierawspółczynnikifunkcjiceluodpowiadającezmiennymba
zowym. W tablicy optymalnej to rozwiązanie znajduje się w kolumnach s
1
, s
2
, s
3
wierszawskażnikówoptymalności.Jeślizagadnieniepierwotnejestwdowolnejpo
staci, to rozwiązanie optymalne odczytujemy z optymalnej tablicy sympleksowej
nastepująco:
• Optymalna wartość zmiennej dualnej y
i
odpowiadającej ograniczeniu ‘
’
równa się współczynnikowi kolumny s
i
wiersza wskażników optymalnośći.
A.Kasperski,M.KulejBadaniaOperacyjne-programowanieliniowe
5
• Optymalna wartość zmiennej dualnej y
i
odpowiadającej ograniczeniu ‘
’
równa się (współczynnik kolumy e
i
wiersza wskażników optymalności).
• Optymalna wartość zmiennej dualnej y
i
odpowiadającej ograniczeniu ‘=’
równasię(współczynnikowikolumny a
i
wierszawskażnikówoptymalności)
M.
Zmienna e
i
jestzmienną,którąodejmujemyodlewejstronyograniczeniapostaci
‘
’, aby zamienić je na równanie, a zmienna a
i
jest zmienną sztuczną w M
metodzie, którą dodajemy do lewej strony ograniczenia w postaci równania. Dla
ilustracji rozważmy następujące zagadnienie:
max z = 3x
1
+ 2x
2
+ 5x
5
x
1
+ 3x
2
+ 2x
3
15
2x
2
− x
3
5
2x
1
+ x
2
− 5x
3
= 10
x
1
, x
2
, x
3
0.
Dodając odpowiednie zmienne mamy:
max z = 3x
1
+ 2x
2
+ 5x
5
−Ma
2
−Ma
3
x
1
+ 3x
2
+ 2x
3
+ s
1
= 15
2x
2
−x
3
−e
2
+ a
2
= 5
2x
1
+ x
2
− 5x
3
+ a
3
= 10
x
1
, x
2
, x
3
, s
1
, a
2
, a
3
0.
Rozwiązując to zagadnienie Mmetodą otrzymujemy następującą optymalną ta
blicę 1.3:
Tab. 1.3: Mmetoda, ostatnia tablica
x
1
x
2
x
3
s
1
e
2
a
2
a
3
4
23
5
23
−
23
−
23
15
23
5
x
3
0
0
1
23
−
23
2
9
23
−
23
65
23
2
x
2
0
1
0
9
23
17
23
−
1
23
7
23
120
23
3
x
1
1
0
0
51
23
58
23
M −
5
23
9
23
565
23
z
0
0
0
M +

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

alter.htw.pl