064 065 2

64 Programowanie liniowe

1.6.1. Zadanie dualne i jego własności

Z każdym zadaniem programowania liniowego w postaci klasycznej, zwanym dalej zadaniem prymalnym, można związać odpowiadające mu zadanie dualne. Pokażemy na przykładzie, w jaki sposób tworzymy zadanie dualne.

Przykład 1.12

Oznaczając przez, .yj, y₂ i y, ceny wykorzystywanych środków i traktując je jako zmienne decyzyjne, należy zbudować model matematyczny zadania, którego rozwiązanie optymalne pozwoli określić, jakie powinny być wartości tych zmiennych, aby zminimalizować wartość posiadanych.zasobów tych środków, przy czym wartości środków potrzebnych na wytworzenie jednej jednostki produktu P| i produktu P₂ są nie mniejsze od zysku osiągniętego z wytworzenia jednostki, odpowiednio, produktu P, i produktu P₂.

i "-.Mi    «

!

■ ■

I « A

Korzystając z danych zapisanych w tablicy 1.1, obliczymy wartość zasobów posiadanych środków. Wynosi ona 14y, + 8y₂ + 16y_s. Wartość środków potrzebna do wytworzenia jednej jednostki produktu P, wynosi 2y, +y₂ + 4y₃, natomiast wartość środków potrzebna do wytworzenia jednej jednostki produktu P₂ jest równa 2>’| + 2y₂. Zadanie minimalizacji wartości posiadanych zasobów środków przy ograniczeniach na wartości tych środków wykorzystywanych do wytwarzania produktów Pi i P₂ zapisujemy następująco:

l.

14y, + 8y₂+ 16y_;, —» min,    . ’

2y, + y₂+4y₃>2,    ^L 2>’, +2y₂

y„ y₂, yj>0.

C.

Zadanie to można zapisać w postaci macierzowej. Określając wektor zmiennych decyzyjnych jako y = [y_b y₂, y₃] oraz wykorzystując przyjęte uprzednio oznaczenia, otrzymujemy:

(1.8)

yb —> min,

yA ^ c,

y^o-

r y mo-ż

A-Vb i. ir

Zadanie (l.8j jest zadaniem dualnym do zadania (l.7). Zmienne decyzyjne zadania dualnego nazwiemy cenami rozrachunkowymi, natomiast optymalne wartości zmiennych decyzyjnych, otrzymane w~wyniku rozwiązania zadania dualnego, nazywamy cenami dualnymi.

Zadania prymalne i dualne charakteryzują się interesującymi własnościami. Niektóre z nich przedstawimy poniżej.

Op-

2.K.;

1 y'₁'

.<? A

<5

f *5

W'

65

w

I y(b-Ax)=(),

l (yA-c)x = 0.    a -• r

i) "" . . -i i ^r‘

-t /    *    :: ^:

■?■ zv, i

«r.

Dualizm w programowaniu liniowym

1.    Każdemu warunkowi ograniczającemu Jednego z problemów odpowiada zmienna decyzyjna drugiego. Zmienną tę nazwiemy zmienną komplementarną do danego warunku ograniczającego. Tak więc w zadaniu dualnym "zmiennymi komplementarnymi do pierwszego, drugiego i trzeciego warunku ograniczającego zadania prymalnego są, odpowiednio, zmienne y_lr y₂, y₃, natomiast w zadaniu prymalnym zmiennymi komplementarnymi do pierwszego i drugiego warunku ograniczającego zadania dualnego są, odpowiednio, zmienne x, i x₂.

2.    Każdej nieujemncj zmiennej decyzyjnej jednego z problemów odpowiada warunek ograniczający drugiego. Warunek ten nazwiemy warunkiem komplementarnym do danej zmiennej decyzyjnej. W rozpatrywanym zadaniu prymalnym zmiennym x, i x₂ odpowiadają komplementarne warunki ograniczające: pierwszy i drugi zadania dualnego, natomiast zmiennym y,, y₂, y₃ w zadaniu dualnym odpowiadają komplementarne warunki ograniczające: pierwszy, drugi i trzeci zadania prymalnego.

3.    Wektor współczynników przy funkcji celu w jednym zadaniu staje się ( J wektorem wyrazów wolnych w drugim, i odwrotnie, wektor wyrazów

wolnych w jednym zadaniu jest wektorem współczynników przy funkcji celu w drugim z nich.    &    ^{r 1} IJ

4.    Kierunki optymalizacji dla zadań dualnych są przeciwne. O ile zadanie

prymalne jest zadaniem maksymalizacji, to w zadaniu dualnym funkcję celu minimalizujemy.    v\w\ m9- '

5.    Zwroty nierówności w warunkach ograniczających zadania prymalnego są

przeciwne do zwrotów nierówności warunków ograniczających zadania dualnego.    >    > Q} £ <

Sformułujemy teraz podstawowe twierdzenia o dualności.

Twierdzenie l.l

Jeżeli x i y są dowolnymi rozwiązaniami dopuszczalnymi, odpowiednio, zada- f nia prymalnego i dualnego, to wartości funkcji celu w tych zadaniach spełniają * .

zależność:

Jcx^yb.    ^{c :} </'

Twierdzenie 1.2 (o komplementarności)

Jeżeli x i y są rozwiązaniami optymalnymi odpowiednio zadania prymalnego i dualnego, to zachodzą związki:

ż"!    'i''''. -■ I )

(1.9)

(1-10)