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: Z = c x → MAX

ˆ

T

Z = b y → MIN

O: Ax ≤ b

T

A y ≥ c

WB: x ≥ 0

y ≥ 0

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

ˆ

Z

=

max

Z min

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

x i

y są odpowiednio rozwiązaniami optymalnymi PP i PD, to zachodzi związek: T

T

y (b-Ax) = 0

( T

x

A y-c) = 0

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 x w optymalnym rozwiązaniu j

PP przyjmuje wartość zero.

JeŜeli zmienna y jest większa od zera w j

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 i

y

wartość zero.

JeŜeli zmienna jest większa od zera w i

x

rozwiązaniu

optymalnym

PP,

to

odpowiadające jej i-te ograniczenie w PD

jest ograniczeniem równościowym.