Rozważmy zadanie zwane pierwotnym P.
,
gdzie
.
wtedy zadaniem dualnym D nazywamy zadanie:
,
gdzie
.
Reguły przechodzenia od zadania pierwotnego do dualnego przedstawia tabela:
Jeżeli ma
zmiennych to
jest opisane przez
nierówności
(równań). Jeżeli
jest opisane
nierównościami to
ma
zmiennych.
gdzie:
Przykładami par zadań wzajemnie dualnych są:
P: D:
lub
P: D:
Jeżeli zadanie pierwotne P ma postać:
to zadanie dualne D ma postać:
zgodna z typem gdyż
gdyż
nieograniczone
niezgodna z typem gdyż
gdyż
niezgodna z typem
gdyż
niezgodna z typem
gdyż
gdyż
zgodna z typem.
Zadanie dualne do dualnego jest równoważne zdaniu pierwotnemu.
Rozważmy zadanie pierwotne P:
D
D'
D(D')
P'
P'=P
Zadania i
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ę .
1') Mnożenie zmiennej przez liczbę .
2) Zastąpienie nierówności parą
.
2a) Zastąpienie pary
nierównością .
3) Zastąpienie równania parą
.
3a) Zastąpienie pary
.
równaniem .
4) Zastąpienie zmiennej nieograniczonej parą
, gdzie
.
5) Zastąpienie problemu problemem
, gdzie
jest automorfizmem afinicznym.
Jeżeli zadania i
są równoważne to dualne do nich zadania
i
też są równoważne.
Zakładamy, że zadania pierwotne są typu Max.
Ad 1). Niech w zadaniu
tą nierówność zgodną z typem mnożymy przez liczbę
. Wtedy w zadaniu dualnym
ta kolumna zostanie pomnożona przez tę samą liczbę
. Zastępując w zadaniu dualnym zmienną
otrzymamy ten sam rezultat. Ponadto znak
tej nierówności zmienia się taj samo jak znak nierówności
. W przypadku nierówności niezgodnej z typem lub równania rezultat jest analogiczny.
Ad 2). Niech w zadaniu
ta nierówność ma postać
zaś w równoważnym zadaniu
będzie zastąpiona parą
.
Wtedy w zadaniach dualnych: W zadaniu zmienna
zaś w zadaniu
zmienna
i dochodzi nowa nierówność, wyznaczona przez
szą kolumnę zadania
, jest nią
. Zatem otrzymujemy to samo zadanie.
Ad 3,4). Niech w zadaniu
ta równość ma postać
zaś w zadaniu
ta równość została zastąpiona parą:
.
Wtedy w zadaniach dualnych: W zadaniu zmienna
jest nieograniczona zaś w zadaniu
zmienna
została zastąpiona parą
. Ponadto w zadaniu
dodatkowa nierówność ma współczynniki przeciwne do
tej więc zadanie
można uzyskać z zadania
podstawiając
.
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ć . wtedy zadanie dualne ma postać
.
Niech
będzie automorfizmem liniowym zadanym macierzą
. Wtedy
i zadanie
![]() |
Zatem zadanie dualne ma postać
![]() |
Zadanie powstało z zadania
przez operacje elementarne na wierszach ( równaniach ).
Niech
dla pewnego
. Wtedy
![]() |
![]() |
Zatem zadanie dualne ma postać
![]() |
Zadania i
są równoważne ponieważ w obszarze dopuszczalnym
co po przemnożeniu przez
daje
.
Jeżeli jest punktem dopuszczalnym zadania pierwotnego P:
zaś
jest punktem dopuszczalnym zadania dualnego D:
to
Ponadto jeżeli to
jest punktem optymalnym
, zaś
jest punktem optymalnym
.
Niech i
będą punktami dopuszczalnymi zadań
i
odpowiednio. Wówczas:
co możemy zapisać jako:
Mnożąc na krzyż otrzymujemy;
Wyliczamy
Co daje
Część druga
to
z obszaru dopuszczalnego
optymalny i z drugiej
strony identycznie
optymalny
Jeżeli zadanie jest nieograniczone to
jest sprzeczne.
Przypuśćmy że nie jest sprzeczne
istnieje
w
obszarze dopuszczalnym zadania
dopuszczalnego
ograniczone
Jeżeli jest nieograniczone to
sprzeczne.
Niestety zadania i
mogą być naraz sprzeczne:
Spośród układów:
1)
2)
dokładnie jeden ma rozwiązanie.
Przypuśćmy że 1) i 2) mają rozwiązania i
. Wtedy
i
więc
. Ale
. Sprzeczność.
Przypuśćmy że 1) nie ma rozwiązania. Stosujemy pierwszą fazę z dwufazowej metody sympleks.
Rozwiązujemy zadanie opisane tablicą ,
gdzie zapisane wierszami i
.
Końcowa tablica ma postać , gdzie
wiersz i
. Ale wiersz ten jest kombinacją liniową wierszy macierzy
. Oznacza to, że istnieje ciąg
taki, że
oraz
. Otrzymaliśmy rozwiązanie 2)
.
Podamy teraz pełną wersję twierdzenia 2.5.
Rozpatrujemy zadanie optymalizacji liniowej:
, gdzie
i
jest opisane układem nierówności:
.
Niech będzie takim punktem, że
, dla
oraz
,
dla
. Wówczas:
jest punktem optymalnym tego zadania wtedy i tylko wtedy gdy
dla pewnych liczb rzeczywistych
zachodzi
.
Niech będzie macierzą pochodzącą od pierwszych
nierówności. Wówczas p nie jest punktem optymalnym wtedy i tylko wtedy gdy kiedy istnieje wektor
taki, że
i
. Ponieważ długość wektora
nie gra roli to tylko j pierwszych nierówności opisujących
ma znaczenie. Przekształćmy warunki:
do:
i
.
Przyjmując oznaczenia i
otrzymujemy:
czyli drugi układ z lematu Farkasa.
A zatem układ nie ma rozwiązań. Oznacza to, że nie istnieje ciąg liczb nieujemnych
taki, że dla
czyli
.
Jeżeli jedno z zadań lub
ma rozwiązanie to drugie też ma
rozwiązanie i wartość funkcji celu są równe.
Przyjmijmy, że zadanie pierwotne P:
ma punkt optymalny
taki, że
, dla
oraz
,
dla
, gdzie
.
Wówczas na mocy poprzedniego twierdzenia istnieje ciąg liczb nieujemnych
taki, że
.
Zadaniem dualnym jest D: .
Niech . Wówczas
i . Więc
, co oznacza, że
jest punktem dopuszczalnym zadania D.
Ale .
Teraz ze słabego twierdzenia o dualności wynika optymalność punktu .
Punkt dopuszczalny zadania
jest punktem optymalnym wtedy i tylko wtedy gdy
istnieje punkt dopuszczalny
zadania
taki, że:
1)
2)
Warunek 2) możemy równoważnie zapisać jako:
2a)
Niech będzie punktem optymalnym zadania
. Wówczas na mocy silnego twierdzenia o dualności (twierdzenia 8.5)
istnieje rozwiązanie
optymalne dla zadania
.
Podobnie jak w dowodzie słabego twierdzenia o dualności ( twierdzenie 8.3) uzyskujemy podwójną równość.
.
Z pierwszej wyciągając przed nawias otrzymujemy
,
zaś z drugiej wyciągając przed nawias otrzymujemy
.
Podkreślmy, jeżeli jest punktem optymalnym zadania
a
jest punktem optymalnym zadania
to spełnione są warunki równowagi
i
.
Przypuśćmy, że zachodzą warunki 1) i 2)
wtedy z 1) otrzymujemy
2) otrzymujemy . Zatem
i na mocy słabego twierdzenia o dualności
i
optymalne.
Bezpośrednio z twierdzenia i dowodu otrzymujemy:
Jeżeli punkt jest optymalny to zbiór punktów optymalnych zadania
jest równy zbiorowi punktów dopuszczalnych
zadania
spełniających warunki równowagi.
Niech będzie punktem dopuszczalnym zadania
zaś
będzie punktem dopuszczalnym zadania
. Jeżeli punkty te spełniają warunki równowagi to:
1) Jeżeli to punkt
spełnia
- tą nierówność jako równanie.
2) Jeżeli punkt spełnia
- tą nierówność na ”ostro” to
.
3) Jeżeli to punkt
spełnia
- tą nierówność jako równanie.
4) Jeżeli punkt spełnia
- tą nierówność na ”ostro” to
.
Ad 1,2) Jeżeli to
- tą nierówność zadania
jest zgodna z typem co daje
. Zaś gdy
to
- tą nierówność zadania
jest niezgodna z typem co daje
. (
oznacza j-ty wiersz macierzy
).
Teraz jest sumą liczb niedodatnich. Oznacza to, że każdy składnik musi być zerem czyli
lub
. Daje to warunki 1) i 2).
Punkty 3) i 4) można analogicznie wyprowadzić z drugiego warunku równowagi.
∎P:
Sprawdzamy czy jest optymalny?
Szukamy w tym celu punktu
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.
Budujemy zadanie dualne.
cokolwiek
=
=
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:
Zatem lub nie istnieje.
Ponieważ jest dopuszczalny dla zadania dualnego, więc
jest optymalny.
Ponadto jest optymalny dla
.
Rozważmy zagadnienie programowania liniowego:
Max , gdy
,
,
,
a) Zbadaj, czy jest wierzchołkiem obszaru
dopuszczalnego.
b) Opisz jedną z krawędzi przechodzi przez punkt .
c) Napisz zadanie dualne.
d) Stosując warunki równowagi sprawdź czy jest punktem optymalnym?
e) Opisz wszystkie punkty optymalne zadania dualnego.
f) Zbadaj jaki wymiar ma zbiór punktów optymalnych zadania pierwotnego.
Rozważmy zagadnienie programowania liniowego:
Max , gdy
,
,
,
a) Napisz zadanie dualne.
b) Sprawdź czy jest wierzchołkiem obszaru
dopuszczalnego.
c) Zbadaj ile krawędzi zawiera w sobie punkt
d) Stosując warunki równowagi sprawdź czy
jest punktem optymalnym zadania.
e) Opisz wszystkie punkty optymalne zadania pierwotnego.
f) Opisz wszystkie punkty optymalne zadania dualnego.
Rozważmy zagadnienie programowania liniowego:
Max , gdy
,
,
,
.
a) Napisz zadanie dualne.
b) Stosując warunki równowagi sprawdź czy jest punktem optymalnym zadania.
c) Napisz taką funkcję celu by zbiorem punktów optymalnych była
krawędź zawierająca punkt .
Rozważmy zagadnienie programowania liniowego:
Max , gdy
,
,
a) Napisz zadanie dualne.
b) Sprawdź czy jest wierzchołkiem
obszaru dopuszczalnego.
c) Opisz dowolną krawędź zawierającą z punkt
d) Stosując warunki równowagi sprawdź czy 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.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
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.