CCF03252008002

1)    w zadaniu dualnym jest tyle zmiennych, ile nierówności w zadaniu pierwotnym (każdemu warunkowi ZP odpowiada jedna zmienna ZD),

2)    w zadaniu dualnym jest tyle warunków, ile zmiennych w zadaniu pierwotnym,

3)    wagi funkcji celu zadania pierwotnego są wyrazami wolnymi w zadaniu dualnym,

4)    wyrazy wolne zadania pierwotnego są wagami funkcji celu w zadaniu dualnym,

5)    macierz współczynników zadania dualnego jest transpozycją macierzy współczynników zadania pierwotnego,

6)    jeżeli zadanie pierwotne jest na maksimum, to dualne jest na minimum, i odwrotnie.

Zauważmy ponadto, że jeżeli zadanie pierwotne jest przedstawione w postaci standardowej, to zadanie dualne jest zapisywane także w tej postaci. Jeżeli natomiast zadanie pierwotne nie ma postaci standardowej, to podobnie jest z zadaniem dualnym (ZD odbiega na tyle od postaci standardowej, na ile odbiega od niej ZP).

W przypadku ogólnym stosujemy ponadto następujące, dodatkowe reguły tworzenia zadania dualnego:

1)    jeżeli w ZP i-ty warunek jest równością, to odpowiadająca mu zmienna y_; nie ma ograniczeń,

2)    jeżeli w ZP i-ty warunek jest nietypową nierównością, to w ZD zmienna y_t < 0,

3)    jeżeli w ZP na zmienną x, nie nałożono ograniczeń, to j-ty warunek ZD ^:'st równością,

4)    jeżeli w ZP zmienna Xj ^ 0, to w ZD j-ty warunek jest nietypową nierównością.

PRZYKŁAD 2.7

Mamy następujące zadanie pierwotne o postaci standardowej:

zmienne dualne:

y v

y₂.

(ZP)

*Lx j 4- 3x₂ 4- x₃ -> min, 4xj - 6x₂ + 5x₃ ^ 4, x_{ 4- 2x₂ 4- 4x₃ ^ 7,

W zadaniu dualnym będą oczywiście dwie zmienne y_u y₂ (co zaznaczono przy ZP), a samo zadanie dualne ma postać:

(ZD)

4y_i + ly₂ -* max, 4j>i + y₂ ^ 2,

— 6yi + 2_v₂ ^ 3,

5jZj 4- 4j<₂ ^ 1,

y„ y₂ > 0-

PRZYKŁAD 2.8

Należy utworzyć zadanie dualne do następującego zadania pierwotnego:

6x, + 8x₂ -> max 4xj + 6x₂ ^ 10,

; ■ 3xj + x₂ = 4,

(ZP

zmienne dualne:

Ti > 0,

y₂ — dowolne, y₃ ^ 0.

2x, + 2x₂ ^2,-

Xj — dowolne, x₂ ^ 0,

Zadanie dualne będzie miało trzy zmienne i dwa warunki ograniczające (poza warunkami znaku):

H'

10.v, + 4y₂ + 2y₃ W 4y_t + 3.v₂ + 2y₃ =' 6,?

V ; ÓVl + )'₂ + 2_)>3 -S '

>’i > 0, y₂ — dowolne, y₃

-*• min,

(ZD)

0.

2.4.2

Twierdzenia o dualności

Między rozwiązaniami zadania pierwotnego (2.34) i zadania dualnego (2.35) zachodzą zależności, które można sformułować w postaci następujących twierdzeń:

TWIERDZENIE 1 (o istnieniu)

Jeżeli ZP i ZD mają rozwiązania dopuszczalne, to obydwa mają rozwiązania optymalne. Jeżeli natomiast chociaż jedno z nich nie ma rozwiązania dopuszczalnego, to obydwa nie mają rozwiązań optymalnych.

TWIERDZENIE 2

Jeżeli x₁,x₂,...,x„ jest rozwiązaniem dopuszczalnym zadania pierwotnego (prymalnego), a y_l,y₂,-,y_m — rozwiązaniem dopuszczalnym zadania dualnego, to między wartościami funkcji celu zachodzi nierówność:

n    rn

X Cj^xj < I    (2.36)

i= i    "'=»

Dla rozwiązań dopuszczalnych wartość funkcji celu ZP nie może być większa od wartości funkcji celu ZD.

TWIERDZENIE 3 (o optymalności)

Jeżeli istnieją dwa takie rozwiązania dopuszczalne x₁₍x₂, ...,x„ (ZP) i yi>y₂>->Pm (^ZD)> ^że:

29