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