16

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ń:

oraz

Dla zadań z pierwszej pary (I) zachodzą następujące zależności

a) Jeśli istnieje rozwiązanie dopuszczalne

0

x , czyli istnieje

X

∈

0

x

, to istnieje

odpowiadające mu rozwiązanie dopuszczalne dla zadania dualnego

Y

∈

0

y

oraz

0

0

y

b

x

c

T

T

≤

(6.9)

b) Jeśli istnieje rozwiązanie optymalne

op

x zadania prymalnego, to istnieje rozwiązanie

optymalne zadania dualnego

op

y

oraz

op

T

op

T

y

b

x

c

=

(6.10)

Druga para zadań dualnych

Zadanie prymalne Zadanie dualne

x

-wektor zmiennych decyzyjnych

y

- wektor zmiennych decyzyjnych

















≥

≥

→

0

x

b

x

A

x

c

:

min

X

T

→

←

















≥

≤

→

0

y

c

y

A

y

b

T

T

Y :

max

(II)

Pierwsza para zadań dualnych

Zadanie prymalne Zadanie dualne

x

-wektor zmiennych decyzyjnych

y

- wektor zmiennych decyzyjnych

















≥

≤

→

0

x

b

x

A

x

c

:

max

X

T

→

←

















≥

≥

→

0

y

c

y

A

y

b

T

T

Y :

min

(I)

17

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

0

x , czyli istnieje

X

∈

0

x

, to istnieje

odpowiadające mu rozwiązanie dopuszczalne dla zadania dualnego

Y

∈

0

y

oraz

0

0

y

b

x

c

T

T

≥

(6.11)

b) Jeśli istnieje rozwiązanie optymalne

op

x zadania prymalnego, to istnieje rozwiązanie

optymalne zadania dualnego

op

y

oraz

op

T

op

T

y

b

x

c

=

(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.