Zagadnienia

9.1 Dualna metoda sympleks.

9. Dualna metoda sympleks

9.1. Dualna metoda sympleks.

Badamy zadanie:

P M⁢a⁢x⁢⁢x0=cT⁢x

A⁢x=b

x≥0

⁢T⁢S=-cN0Ab

przypomnijmy definicję 5.1. T⁢S jest pierwotnie dopuszczalna (przedstawia wierzchołek obszaru dopuszczalnego) ⇔b≥0

T⁢S jest dualnie dopuszczalna (przedstawia wierzchołek zadania dualnego) ⇔c≤0⁢-cN≥0

T⁢S przedstawia wierzchołek optymalny jest pierwotnie i dualnie dopuszczalna.

Przykład 9.1

P M⁢i⁢n⁢⁢x0=2⁢x1+3⁢x2

x1+x2≥2

3⁢x1+2⁢x2≥7

2⁢x1+x2≥4

x1≥0, x2≥0

(typowy przykład zagadnienia diety)

x0x1x2x3x4x5w⁢w1-2-30000011-10020320-10702100-14

T⁢S⁢⁢⁢⁢⁢-2-30000-1-1100-2-3-2010-7-2-1001-4

jest dualnie dopuszczalna.

Rozpatrzmy teraz zadanie dualne:

D M⁢a⁢x⁢⁢y0=2⁢y1+7⁢y2+4⁢y3

y1+3⁢y2+2⁢y3≤2

y1+2⁢y2+y3≤3

y1≥0, y2≥0, y3≥0.

I równoważne mu:

D∗ M⁢i⁢n-y0=-2⁢y1-7⁢y2-4⁢y3

T⁢S∗⁢⁢⁢⁢274000132102121013

Jeżeli wykreślimy kolumny związane ze zmiennymi bazowymi to -T⁢ST=T⁢S∗

Prześledźmy metodę sympleks na tych dwóch tablicach równocześnie.

Dualne Pierwotne

274000132102121013⁢⁢⁢-2-30000-1-1100-2-3-2010-7-2-1001-4

010-20-41321020-1-1-111⁢⁢0-1-200411-100201-310-101-2010

-130-23-130-4⁢231312313023130-13-23153⁢⁢0-530-2304⁢231230-130730-131-130130130-23123

Otrzymaliśmy rozwiązania

q=0,23,0,0,53 dla zadania dualnego i p=73,0,13,0,23 dla zadania pierwotnego. Ale wartości funkcji celu są równe

-y0=-4⁢23

y0=4⁢23=x0

Algorytm dualnej metody sympleks

(dla Max):

Na starcie mamy TS dualnie dopuszczalną (tzn. -cN≥0)

T⁢S=-cNb0Ab gdzie elementy macierzy A oznaczamy:

ai,j,1≤i≤n, 1≤j≤t zaś kolumny b oznaczamy bi,1≤j≤t.

1∘ Test optymalności. Jeżeli b≥0 to stop (tablica przedstawia

wierzchołek optymalny)

2∘ Wybieramy wiersz główny i, taki, że bi<0

3∘ Test sprzeczności: jeżeli w i-tym wierszu

wszystkie wyrazy są ≥0 to stop (zadanie sprzeczne)

Ponieważ i-ty wiersz reprezentuje równanie

∑j=1nai,j⁢xj=bi, w którym

ai,j≥0⁢⁢xj≥0 oraz bi<0

4∘ Wybór elementu centralnego:

Liczymy minimum M⁢i⁢n⁢cjai,j⁢: 1≤j≤t,⁢ai,j<0.

Jako element centralny wybieramy dowolne ai,j na którym

osiągalne jest minimum.

5∘ Eliminacja Gaussa-Jordana

6∘ Wracamy do 1∘

Rzeczywiście 5∘ daje T⁢S dualnie dopuszczalną:

nad kreską otrzymujemy W0-djai,j⁢Wi,

gdzie W0=d1,d2,…,dn zatem w k-tej kolumnie otrzymujemy

dk-djai,j⋅ai⁢k

Jeżeli ai,k≥0 to djai⁢j⋅ai⁢k≤0 bo ai,j≤0 i dk-djai,j⋅ai,k≥0.

Jeżeli ai,k<0 to djai⁢k≥djai⁢j

djai,k≤djai,j więc

dk≥djai,j⋅ai,k

Porównanie metody sympleks prostej i dualnej

1) zadanie opisane T⁢S dualnie dopuszczalną może mieć rozwiązanie lub być sprzeczne, ale nie może być nieograniczone.

1') zadanie opisane T⁢S pierwotnie dopuszczalną może mieć rozwiązanie lub być nieograniczone ale nie może być sprzeczne (T⁢S opisuje wierzchołek dopuszczalny)

2) Dualna metoda sympleks daje rozwiązanie (algorytm się kończy) ponieważ ma tyle kroków ile prosta metoda sympleks na zadaniu dualnym.

3) Przy zadaniu Max

W dualnej metodzie sympleks wartość funkcji celu maleje, ( w pierwotnej rośnie).

Dualna metoda sympleks jest używana tylko jako narzędzie pomocnicze, ponieważ niedokończone obliczenia nie dają przybliżonego rozwiązania, a tylko oszacowanie funkcji celu.

Ćwiczenie 9.1

Opisz dualny algorytm metody sympleks na przykładzie zadania:

Min x0=5⁢x1+x2+11⁢x3 , gdy:

x1+2⁢x3≥5

x1+x2+3⁢x3≤6

6⁢x1+2⁢x2+15⁢x3≥40

x1≥0, x2≥0, x3≥0

Ćwiczenie 9.2

Opisz dualny algorytm metody sympleks na przykładzie zadania:

Min x0=2⁢x1+4⁢x2+7⁢x3 , gdy:

2⁢x1-5⁢x2-2⁢x3≥5

x1+3⁢x2+2⁢x3≤6

x1-5⁢x2+x3≥2

x1≥0, x2≥0, x3≥0.

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

Optymalizacja I