Zagadnienia dualne

programowania

liniowego.

Dla

każdego

zadania

programowania

liniowego

nazywanego

zagadnieniem

pierwotnym

lub prymalnym

można

sformułować

odpowiadające

mu

zagadnienie dualne.

Zagadnienie prymalne i dualne tworzą

sprzężoną parę zagadnień dualnych

względem siebie.

Przy konstruowaniu zagadnień dualnych

obowiązują następujące zasady:

1. maksymalizacji

wartości

funkcji

celu

zagadnienia

prymalnego

(PP)

odpowiada

minimalizacja wartości funkcji celu zagadnienia
dualnego (PD)

2. prawe strony ograniczeń

występujących w

problemie pierwotnym są współczynnikami przy
zmiennych w funkcji celu problemu dualnego

3. współczynniki przy zmiennych w funkcji

celu PP tworzą prawe strony ograniczeń

PD

4. macierz

współczynników

PD

jest

transponowaną

macierzą

A

współczynników PP

5. warunkowi ograniczającemu w postaci

nierówności w PP odpowiada w PD

nieujemna zmienna decyzyjna (tzw.

zmienna dualna)

6. warunkowi ograniczającemu w postaci

równania w PP odpowiada zmienna

dualna nie określona co do znaku

(przyjmuje dowolne wartości rzeczywiste)

7. nieujemnej zmiennej decyzyjnej PP

odpowiada w PD warunek ograniczający

w postaci nierówności typu „nie mniejsze”

8. zmiennej decyzyjnej nie określonej co do

znaku w PP odpowiada w PD warunek

ograniczający w postaci równania

9. w PD jest tyle zmiennych ile nierówności

w ograniczeniach w PP

10. w PD jest tyle warunków ograniczających

ile zmiennych w PP

Do przestawienia PP i PD zastosujemy zapis

macierzowy.

PP ma postać:

PD ma postać:

T

FC:

c x

MAX

O: Ax

b

WB: x

0

Z

=

→

≤

≥

ˆ

T

T

b y

MIN

A y

c

y

0

Z

=

→

≥

≥

Między rozwiązaniami PP i PD zachodzą

ś

cisłe związki. Można bowiem udowodnić

następujące twierdzenie o dualności:

Problem pierwotny ma rozwiązanie wtedy i

tylko wtedy, gdy problem dualny ma

rozwiązanie oraz

max

min

ˆ

Z

Z

=

Z twierdzenia o dualności wynikają

następujące wnioski:

1. na podstawie rozwiązania jednego z

problemów (pierwotnego lub dualnego)

możemy otrzymać rozwiązanie drugiego

problemu

2. ma ono duże znaczenie praktyczne, bo

czasami łatwiej jest rozwiązać problem

dualny

Twierdzenie o komplementarności podaje

zależność między rozwiązaniami PP i PD:

Jeżeli i są odpowiednio rozwiązaniami

optymalnymi PP i PD, to zachodzi związek:

x

y

(

)

0

T

T

x

A y-c

=

(

)

0

T

y

b-Ax

=

Twierdzenie równowadze:

Jeżeli j-ty warunek PD jest w optymalnym

rozwiązaniu (chociaż jednym) spełniony z

ostrą nierównością, to odpowiadająca mu

j-ta zmienna

w optymalnym rozwiązaniu

PP przyjmuje wartość zero.

j

x

Jeżeli zmienna jest większa od zera w

rozwiązaniu optymalnym PD, to odpowiadające

jej j-te ograniczenie w PP jest ograniczeniem

równościowym.

Jeżeli i-ty warunek PP jest w optymalnym

rozwiązaniu (chociaż jednym) spełniony z ostrą

nierównością, to odpowiadająca mu i-ta zmienna

w optymalnym rozwiązaniu PD przyjmuje

wartość zero.

j

y

i

y

Jeżeli zmienna jest większa od zera w

rozwiązaniu

optymalnym

PP,

to

odpowiadające jej i-te ograniczenie w PD
jest ograniczeniem równościowym.

i

x