Zagadnienia

8. Teoria dualności

8.1. Teoria dualności.

Definicja 8.1

Rozważmy zadanie PL zwane pierwotnym P.

Maxx0=c1x1T+c2x2T+c3x3T+b0,

gdzie x1Rn1,x2Rn2,x3Rn3,x=x1,x2,x3Rn1+n2+n3

A1,1A1,2A1,3xT=b1T

|A2,1A2,2A2,3|xTb2T

A3,1A3,2A3,3xTb2T

x1Rn1,x20,x30.

wtedy zadaniem dualnym D nazywamy zadanie:

Miny0=c1y1T+c2y2T+c3y3T+b0,

gdzie y1Rt1,y2Rt2,y3Rt3,y=y1,y2,y3Rt1+t2+t3

A1,1TA2,1TA3,1TyT=c1T

|A1,2TA2,2TA3,2T|yTc2T

A1,3TA2,3TA3,3TyTc2T

y1Rt1,y20,y30.

Reguły przechodzenia od zadania pierwotnego do dualnego przedstawia tabela:

Jeżeli P ma n zmiennych to D jest opisane przez n nierówności (równań). Jeżeli P jest opisane t nierównościami to D ma t zmiennych.

PierwotneDualneminmaxmaxmini-ta nierówność zgodna z typemi-ta zmienna 0j-ta nierówność niezgodna z typemj-ta zmienna 0k-ta nierówność jest równaniemk-ta zmienna nieograniczonai-ta zmienna 0i-ta nierówność zgodna z typemj-ta zmienna 0j-ta nierówność niezgodna z typemk-ta zmienna nieograniczonak-ta nierówność jest równaniem

gdzie:

dla zadań typu MaxaTxb - nierówność jest zgodna z typemaTxb - nierówność jest niezgodna z typemdla zadań typu MinaTxb - nierówność jest zgodna z typemaTxb - nierówność jest niezgodna z typem

Przykładami par zadań wzajemnie dualnych są:

P: maxcxT    D: minbyT

AxTbT      ATyTcT

x0        y0

lub

P: maxcxT    D: minbyT

AxT=bT      ATyTcT

x0        yRt

Przykład 8.1

Jeżeli zadanie pierwotne P ma postać:

Maxx0=2x1+x2-x3

x1+x2-3

x1+3x2+x32

-x1+2x3=7

x2+x35

x10,x30

bT=-3275A=110131-102011c=2,1,-1

to zadanie dualne D ma postać:

Miny0=-3y1+2y2+7y3+5y4

y1+y2-y32 zgodna z typem gdyż x10

y1+3y2+y4=1 gdyż x2 nieograniczone

y2+2y3+y4-1 niezgodna z typem gdyż x30

y10 gdyż x1+x2-3 niezgodna z typem

y20 gdyż x1+3x2+x32 niezgodna z typem

y3R gdyż -x1+2x3=7

y40 gdyż x2+x35 zgodna z typem.

Twierdzenie 8.1

Zadanie dualne do dualnego jest równoważne zdaniu pierwotnemu.

Przykład 8.2

Rozważmy zadanie pierwotne P:

MaxcTx

Axb

x0

D  MinbTy

ATyc

y0

D' -Max(-b)Ty

-ATy-c

y0

D(D')   -Min-cTz

-ATTz-bTT

z0

P'  MaxcTz

Azb

z0

P'=P

Definicja 8.2

Zadania P1 i P2 nazywamy równoważnymi jeżeli można od jednego do drugiego przejść stosując następujące reguły:

1) Mnożenie nierówności (równania ) przez liczbę r0.

1') Mnożenie zmiennej przez liczbę r0.

2) Zastąpienie nierówności i=1naixib parą

i=1naixi+xn+1=bxn+10.

2a) Zastąpienie pary

i=1naixi+xn+1=bxn+10

nierównością i=1naixib.

3) Zastąpienie równania i=1naixi=b parą

i=1naixibi=1n-aixi-b.

3a) Zastąpienie pary

i=1naixibi=1n-aixi-b.

równaniem i=1naixi=b.

4) Zastąpienie zmiennej nieograniczonej xi parą xi=xi+-xi-, gdzie xi+0xi-0.

5) Zastąpienie problemu x0=cxT+b0|xD problemem

x0=cfxT+b0|fxfD, gdzie f jest automorfizmem afinicznym.

Twierdzenie 8.2

Jeżeli zadania P1 i P2 są równoważne to dualne do nich zadania D1 i D2 też są równoważne.

Zakładamy, że zadania pierwotne są typu Max.

Ad 1). Niech w zadaniu P1 j- tą nierówność zgodną z typem mnożymy przez liczbę r0. Wtedy w zadaniu dualnym j- ta kolumna zostanie pomnożona przez tę samą liczbę r. Zastępując w zadaniu dualnym zmienną yj:=ryj otrzymamy ten sam rezultat. Ponadto znak j- tej nierówności zmienia się taj samo jak znak nierówności ryj0. W przypadku nierówności niezgodnej z typem lub równania rezultat jest analogiczny.

Ad 2). Niech w zadaniu P1 j- ta nierówność ma postać i=1naixib zaś w równoważnym zadaniu P2 będzie zastąpiona parą

i=1naixi+xn+1=bxn+10.

Wtedy w zadaniach dualnych: W zadaniu D1 zmienna yj0 zaś w zadaniu D2 zmienna yjR i dochodzi nowa nierówność, wyznaczona przez n+1- szą kolumnę zadania P2, jest nią yj0. Zatem otrzymujemy to samo zadanie.

Ad 3,4). Niech w zadaniu P1 j- ta równość ma postać i=1naixi=b zaś w zadaniu P2 j- ta równość została zastąpiona parą:

i=1naixibi=1n-aixi-b.

Wtedy w zadaniach dualnych: W zadaniu D1 zmienna yjR jest nieograniczona zaś w zadaniu D2 zmienna yj została zastąpiona parą yj+0,yj-0. Ponadto w zadaniu P2 dodatkowa nierówność ma współczynniki przeciwne do j- tej więc zadanie D2 można uzyskać z zadania D1 podstawiając yj=yj+-yj-0.

Ad 5). Ponieważ każdy automorfizm afiniczny jest złożeniem automorfizmu liniowego i przesunięcia, dowód rozbijemy na dwie części osobno dla automorfizmu liniowego i osobno dla przesunięcia. Przyjmijmy, że zadanie pierwotne ma postać P1=Maxx0=cxT+b0|AxTbT. wtedy zadanie dualne ma postać D1=Miny0=byT+b0|ATyT=cT,y0.

10 Niech f będzie automorfizmem liniowym zadanym macierzą B. Wtedy fxT=BxT i zadanie

P1=Maxx0=cfxT+b0|AfxTbT=Maxx0=cBxT+b0|ABxTbT.

Zatem zadanie dualne ma postać

D2=Miny0=byT+b0|BTATyT=BTcT,y0.

Zadanie D2 powstało z zadania D1 przez operacje elementarne na wierszach ( równaniach ).

20 Niech fx=x+d dla pewnego dRn. Wtedy

P1=Maxx0=cfxT+b0|AfxTbT=
Maxx0=cxT+cdT+b0|AxT+AdTbT=Maxx0=cxT+cdT+b0|AxTbT-AdT.

Zatem zadanie dualne ma postać

D2=Miny0=b-dATyT+cdT+b0|ATyT=cT,y0.

Zadania D1 i D2 są równoważne ponieważ w obszarze dopuszczalnym ATyT=cT co po przemnożeniu przez d daje dATyT=dcT=cdT.

Twierdzenie 8.3 (Słabe twierdzenie o dualności)

Jeżeli p jest punktem dopuszczalnym zadania pierwotnego P: Maxx0=cxT|AxTbT,x0 zaś q jest punktem dopuszczalnym zadania dualnego D: Miny0=byT|ATyTcT,y0 to

x0p=cTpbTq=y0q

Ponadto jeżeli cpT=bqT to p jest punktem optymalnym P, zaś q jest punktem optymalnym D.

Niech p i q będą punktami dopuszczalnymi zadań P i Q odpowiednio. Wówczas:

ApTbT    ATqTcT

p0      q0

co możemy zapisać jako:

ApT-bTθ=00    ATqT-cTθ=00

p0      q0

Mnożąc na krzyż otrzymujemy;

qApT-bT0R     pATqT-cT0R

Wyliczamy

qApTqbT     pATqTpcT

Co daje

cpT=pcTpATqT=qApTqbT=bqT

Część druga

cpT=bqT to x z obszaru dopuszczalnego cxTbqT=cpTp optymalny i z drugiej strony identycznie byTcpT=bqTq optymalny

Wniosek 8.1

Jeżeli zadanie P jest nieograniczone to D jest sprzeczne.

Przypuśćmy że D nie jest sprzeczne istnieje q w obszarze dopuszczalnym zadania D

x dopuszczalnego cxTbqTP ograniczone

Wniosek 8.2

Jeżeli D jest nieograniczone to P sprzeczne.

Niestety zadania P i D mogą być naraz sprzeczne:

Przykład 8.3

P=maxx1+x2

-x1+x2-1

x1-x2-1

x1,x20

0-2

Dmin-y1-y2

-y1+y21

y1-y21

y1,y20

02

Lemat 8.1 (Lemat Farkas'a)

Spośród układów:

1) AxT=bTx0

2) yA0byT<0

dokładnie jeden ma rozwiązanie.

Przypuśćmy że 1) i 2) mają rozwiązania x0 i y0. Wtedy

x00 i y0Aθ więc y0Ax0T0. Ale y0Ax0T=y0bT<0. Sprzeczność.

Przypuśćmy że 1) nie ma rozwiązania. Stosujemy pierwszą fazę z dwufazowej metody sympleks.

Rozwiązujemy zadanie opisane tablicą 00110AIbT,

gdzie zapisane wierszami A=w1w2wt i bT=b1b2bt.

Końcowa tablica ma postać d1dnk1ktb0ADbT, gdzie
wiersz d1dn0 i b0<0. Ale wiersz ten jest kombinacją liniową wierszy macierzy A. Oznacza to, że istnieje ciąg y=y1,y2,,yt taki, że d1dn=i=1tyiwi oraz b0=i=1tyibi. Otrzymaliśmy rozwiązanie 2) yA0byT<0.

Podamy teraz pełną wersję twierdzenia 2.5.

Twierdzenie 8.4

Rozpatrujemy zadanie optymalizacji liniowej:

Maxx0=cx, gdzie xW i W jest opisane układem nierówności: w1xb1w2xb2wtxbt.

Niech pW będzie takim punktem, że wip=bi, dla i=1,2,,j oraz wix<bi, dla i>j. Wówczas:

p jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy dla pewnych liczb rzeczywistych r10,r20,,rj0 zachodzi c=i=1jriwi.

Niech B=w1w2wj będzie macierzą pochodzącą od pierwszych j nierówności. Wówczas p nie jest punktem optymalnym wtedy i tylko wtedy gdy kiedy istnieje wektor α taki, że p+αW i x0p+α>x0p. Ponieważ długość wektora α nie gra roli to tylko j pierwszych nierówności opisujących W ma znaczenie. Przekształćmy warunki:

w1p+αb1=w1pw2p+αb2=w2pwjp+αbj=wjp

cp+α>cp do:

BαT0 i cαT>0.

Przyjmując oznaczenia A=BT i y=-α otrzymujemy:

yA0cyT<0 czyli drugi układ z lematu Farkasa.

A zatem układ AxT=cTx0 nie ma rozwiązań. Oznacza to, że nie istnieje ciąg liczb nieujemnych r10,r20,,rj0 taki, że dla x=r1,r2,,rj xB=c czyli ci=1jriwi.

Twierdzenie 8.5 (Silne twierdzenie o dualności)

Jeżeli jedno z zadań P lub D ma rozwiązanie to drugie też ma rozwiązanie i wartość funkcji celu są równe.

Przyjmijmy, że zadanie pierwotne P:

Maxx0=cxT|AxTbT ma punkt optymalny p taki, że wip=bi, dla i=1,2,,j oraz wix<bi, dla i>j, gdzie A=w1w2wtRtn. Wówczas na mocy poprzedniego twierdzenia istnieje ciąg liczb nieujemnych r10,r20,,rj0 taki, że c=i=1jriwi.

Zadaniem dualnym jest D: Miny0=byT|ATyT=cT,y0.

Niech q=r1,r2,,rj,0,0,,0Rt. Wówczas q0

i qA=r1,r2,,rj,0,0,,0w1w2wt=i=1jriwi=c. Więc ATqT=cT, co oznacza, że q jest punktem dopuszczalnym zadania D.

Ale y0q=bqT=i=1tbiri=i=1jbiri=i=1jwipTri==i=1jriwipT=cpT=x0p.

Teraz ze słabego twierdzenia o dualności wynika optymalność punktu q.

Twierdzenie 8.6 (Twierdzenie o równowadze (Kuhn, Tucker))

Punkt dopuszczalny p zadania P (Maxx0=cxT|AxTbT,x0) jest punktem optymalnym wtedy i tylko wtedy gdy istnieje punkt dopuszczalny q zadania D

(Miny0=byT|ATyTcT,y0) taki, że:

1) qApT-bT=0

2) qA-cpT=0

Warunek 2) możemy równoważnie zapisać jako:

2a) pATqT-cT=0

Niech p będzie punktem optymalnym zadania P. Wówczas na mocy silnego twierdzenia o dualności (twierdzenia 8.5) istnieje rozwiązanie q optymalne dla zadania D. Podobnie jak w dowodzie słabego twierdzenia o dualności ( twierdzenie 8.3) uzyskujemy podwójną równość.

qbT=qApT=cpT.

Z pierwszej wyciągając q przed nawias otrzymujemy qApT-bT=0,

zaś z drugiej wyciągając pT przed nawias otrzymujemy qA-cpT=0.

Podkreślmy, jeżeli p jest punktem optymalnym zadania P a q jest punktem optymalnym zadania D to spełnione są warunki równowagi qApT-bT=0 i qA-cpT=0.

Przypuśćmy, że zachodzą warunki 1) i 2)

wtedy z  1) otrzymujemy qTAp=bTq

2) otrzymujemy cTp=qTAp. Zatem

bTq=cTp i na mocy słabego twierdzenia o dualności p i q optymalne.

Bezpośrednio z twierdzenia i dowodu otrzymujemy:

Wniosek 8.3

Jeżeli punkt p jest optymalny to zbiór punktów optymalnych zadania D jest równy zbiorowi punktów dopuszczalnych q zadania D spełniających warunki równowagi.

Uwaga 8.1

Niech p=p1,p2,,pn będzie punktem dopuszczalnym zadania P zaś q=q1,q2,,qt będzie punktem dopuszczalnym zadania D. Jeżeli punkty te spełniają warunki równowagi to:

1) Jeżeli qj0 to punkt p spełnia j - tą nierówność jako równanie.

2) Jeżeli punkt p spełnia j - tą nierówność na ”ostro” to qi=0.

3) Jeżeli pi0 to punkt q spełnia i - tą nierówność jako równanie.

4) Jeżeli punkt q spełnia i - tą nierówność na ”ostro” to pi=0.

Ad 1,2) Jeżeli qj>0 to j - tą nierówność zadania P jest zgodna z typem co daje qjwjpt-bj0. Zaś gdy qj< to j - tą nierówność zadania P jest niezgodna z typem co daje qjwjpT-bj0. (wj oznacza j-ty wiersz macierzy A).

Teraz qApt-bT=j=1tqjwjpT-bj=0 jest sumą liczb niedodatnich. Oznacza to, że każdy składnik musi być zerem czyli qj=0 lub wjpT=bj. Daje to warunki 1) i 2).

Punkty 3) i 4) można analogicznie wyprowadzić z drugiego warunku równowagi.

Przykład 8.4

P:   Maxx1+5x2-2x3

2x1+3x2-x35    =

3x1+5x2-2x3=7       =

x1+2x36         >y3=0

xi0

Sprawdzamy czy p=0,3,4 jest optymalny?

Szukamy w tym celu punktu q=y1,y2,y3 spełniającego oba warunki równowagi a potem sprawdzimy czy któryś ze znalezionych punktów jest dualnie dopuszczalny. Aby sprawdzić pierwszy warunek podstawiamy punkt p do nierówności. Ponieważ trzecia nierówność spełniona jest na ostro to trzecia współrzędna punktu q musi być zerowa.

Ap-b=00>0

Budujemy zadanie dualne.

D:Min5y1+7y2+6y3

2y1+3y2+y31          cokolwiek

3y1+5y25            =

-y1-2y2+2y3-2         =

y10,y2R,y30

Aby punkt q spełniał drugi warunek równowagi to ponieważ punkt p ma drugą i trzecią współrzędną niezerową to punkt q musi spełniać drugą i trzecią nierówność zadania dualnego jak równość. Po opuszczeniu trzeciej, zerowej współrzędnej otrzymujemy:

3y1+5y2=5-y1-2y2=-2y1=0y2=1

Zatem q=0,1,0 lub nie istnieje.

Ponieważ q=0,1,0 jest dopuszczalny dla zadania dualnego, więc p jest optymalny.

Ponadto q jest optymalny dla D.

Zadania

Ćwiczenie 8.1

Rozważmy zagadnienie programowania liniowego:

Max x0=3x1-4x2+2x3-x4 , gdy

2x1+3x2-2x3-x44

x1-2x2+x3-2x4=-8

6x1-3x2-5x3+5x41

x10, x20, x3R, x40

a) Zbadaj, czy 0,3,-2,0 jest wierzchołkiem obszaru dopuszczalnego.

b) Opisz jedną z krawędzi przechodzi przez punkt 0,3,-2,0.

c) Napisz zadanie dualne.

d) Stosując warunki równowagi sprawdź czy 0,3,-2,0 jest punktem optymalnym?

e) Opisz wszystkie punkty optymalne zadania dualnego.

f) Zbadaj jaki wymiar ma zbiór punktów optymalnych zadania pierwotnego.

Ćwiczenie 8.2

Rozważmy zagadnienie programowania liniowego:

Max x0=x1-7x2-3x3+x4 , gdy

x1+x2+x3+x42

2x1-5x2-6x3+2x46

x1+2x2-3x3+x4=3

x10, x20, x30, x4R

a) Napisz zadanie dualne.

b) Sprawdź czy 1,0,0,2 jest wierzchołkiem obszaru dopuszczalnego.

c) Zbadaj ile krawędzi zawiera w sobie punkt 1,0,0,2.

d) Stosując warunki równowagi sprawdź czy 1,0,0,2 jest punktem optymalnym zadania.

e) Opisz wszystkie punkty optymalne zadania pierwotnego.

f) Opisz wszystkie punkty optymalne zadania dualnego.

Ćwiczenie 8.3

Rozważmy zagadnienie programowania liniowego:

Max x0=3x1-3x2-7x3+x4 , gdy

x1+3x2-4x3+5x410

-x1+2x2+3x3+3x4-5

2x1+3x2-6x3-2x4=10

x1R, x20, x30 , x40 .

a) Napisz zadanie dualne.

b) Stosując warunki równowagi sprawdź czy 2,0,-1,0 jest punktem optymalnym zadania.

c) Napisz taką funkcję celu by zbiorem punktów optymalnych była krawędź zawierająca punkt 2,0,-1,0.

Ćwiczenie 8.4

Rozważmy zagadnienie programowania liniowego:

Max x0=3x1-x2-6x3 , gdy

2x1+3x2-2x3+x46

-3x1+5x2+3x3-2x4=-9

-x1+6x2+4x3-3

x10, x20, x3R0x40

a) Napisz zadanie dualne.

b) Sprawdź czy 2,0,-1,0 jest wierzchołkiem obszaru dopuszczalnego.

c) Opisz dowolną krawędź zawierającą z punkt 2,0,-1,0.

d) Stosując warunki równowagi sprawdź czy 2,0,-1,0 jest punktem optymalnym zadania.

e) Znajdź oszacowanie z dołu na funkcję celu zadania dualnego.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.