6.4.Dualizm w programowaniu liniowym

Jedną z własności zadań programowania liniowego jest istnienie dla każdego z zadań PL

odpowiadającego mu zadania dualnego. Takie dwa zadania dualne tworzą tak zwaną parę

zadań dualnych.

Wyróżniliśmy dwa typy zadań PL: zadanie na maksymalizację (PL-1) oraz zadanie na minimalizację (PL-2) funkcji celu. Każde z nich posiada odpowiednie zadanie dualne. Mamy zatem dwie pary zadań:

Pierwsza para zadań dualnych

Zadanie prymalne Zadanie dualne x -wektor zmiennych decyzyjnych y - wektor zmiennych decyzyjnych

c Tx → max

b T y → min







A x ≤ b 

← → 

A T y ≥ c (I)



X : 



Y : 



x ≥ 0



y ≥ 0

oraz

Druga para zadań dualnych

Zadanie prymalne Zadanie dualne x -wektor zmiennych decyzyjnych y - wektor zmiennych decyzyjnych

c T x → min

b T y → max







A x ≥ b 

← → 

A T y ≤ c (II)



X : 



Y : 



x ≥ 0



y ≥ 0

Dla zadań z pierwszej pary (I) zachodzą następujące zależności a) Jeśli istnieje rozwiązanie dopuszczalne x , czyli istnieje x

, to istnieje

0 ∈ X

0

odpowiadające mu rozwiązanie dopuszczalne dla zadania dualnego y oraz

0 ∈ Y

c T x

≤ b T y

(6.9)

0

0

b) Jeśli istnieje rozwiązanie optymalne op

x zadania prymalnego, to istnieje rozwiązanie

optymalne zadania dualnego op

y

oraz

T

op

T

op

c x

= b y

(6.10)

16

c) Jeśli zadanie prymalne jest sprzeczne, to odpowiadające mu zadanie dualne jest sprzeczne lub ma rozwiązanie nieograniczone.

d) Jeśli zadanie prymalne ma rozwiązanie nieograniczone, to odpowiadające mu zadanie dualne ma rozwiązanie nieograniczone

Analogiczne zależności zachodzą dla zadań z drugiej pary zadań dualnych (II): a) Jeśli istnieje rozwiązanie dopuszczalne x , czyli istnieje x

, to istnieje

0 ∈ X

0

odpowiadające mu rozwiązanie dopuszczalne dla zadania dualnego y oraz

0 ∈ Y

c T x

≥ b T y

(6.11)

0

0

b) Jeśli istnieje rozwiązanie optymalne op

x zadania prymalnego, to istnieje rozwiązanie

optymalne zadania dualnego op

y

oraz

T

op

T

op

c x

= b y

(6.12)

c) Jeśli zadanie prymalne jest sprzeczne, to odpowiadające mu zadanie dualne jest sprzeczne.

d) Jeśli zadanie prymalne ma rozwiązanie nieograniczone, to odpowiadające mu zadanie dualne ma rozwiązanie nieograniczone lub jest sprzeczne.

Każda para zadań dualnych posiada swoją ekonomiczną interpretację, która wynika z zasady racjonalnego gospodarowania, zgodnie z którą możemy:

-poszukiwać maksymalnego stopnia realizacji celu przy określonych nakładach; bądź

- określać minimalne nakłady do realizacji określonego wyniku (stopnia realizacji celu).

Problem ten będzie omówiony w przykładzie D1.

Pokażemy także w przykładzie D2, że rozwiązanie jednego z zadań należących do pary zadań dualnych wystarcza, aby odczytać z końcowej tablicy simpleks rozwiązanie dla drugiego z tych zadań.

Zagadnienia dotyczące dualizmu w programowania liniowym są także opisane np. w pozycji

[5] s.70-80.

17