Problem dualny programowania liniowego

Definicja 4.1   Niech będzie dany PPL

$$\begin{array}{rcl} \sum_{j=1}^n a_{ij}x_j & \leq & b_i \ ... ...& = & \sum_{j=1}^n c_jx_j \rightarrow \mbox{max} \end{array}$$ (4.1)

PPL

$$\begin{array}{rcl} \sum_{i=1}^m a_{ij}y_j & \geq & c_j \ ... ...& = & \sum_{i=1}^m b_iy_i \rightarrow \mbox{min} \end{array}$$ (4.2)

nazywamy problemem dualnym problemu (). Problem () nazywamy problemem prymalnym. Równocześnie problem () nazywamy problemem dualnym problemu (prymalnego) ().

Z powyższej definicji wynika natychmiast następujący wniosek.

Wniosek 4.1   Problemem dualnym do problemu dualnego do PPL jest wyjściowy PPL.

Przykład 4.1   Problemem dualnym do

$$\begin{array}{rrrrl} 2x_1 & + x_2 & + 5x_3 & \leq & 2 \\ ... ...2x_1 & - x_2 & + 3x_3 & \rightarrow & \mbox{max} \end{array}$$ (4.3)

jest

$$\begin{array}{rrrrl} 2y_1 & + y_2 & + y_3 & \geq & 2 \\ ... ...2y_1 & + y_2 & + 3y_3 & \rightarrow & \mbox{min} \end{array}$$ (4.4)

Twierdzenie 4.1   Niech () będzie problemem prymalnym a () problemem do niego dualnym. Jeżeli $x_1,...,x_n$ oraz $y_1,...,y_m$ są rozwiązaniami dopuszczalnymi, odpowiednio, problemów () i () to

$$\sum_{j=1}^n c_jx_j \leq \sum_{i=1}^m b_iy_i$$

Dowód twierdzenia jest wyjątkowo prosty i mieści się w jednej linijce:

$$\sum_{j=1}^n c_jx_j \leq \sum_{j=1}^n \left( \sum_{i=1}^m a... ... \right) y_i \leq \sum_{i=1}^m b_iy_i \hfill \rule{.1in}{.1in}$$

Przykład 4.1 (c.d.)   $y_1=2, y_2=1, y_3=0$ jest rozwiązaniem dopuszczalnym () o wartości funkcji celu $w=5$. Stąd i z twierdzenia wynikają dwa wnioski:

1. problem () jest ograniczony,
2. wartość maksymalna funkcji celu jest co najwyżej równa $5$.

Zasada którą widzieliśmy w przykładzie działa także w ogólności.

Wniosek 4.2   Jeżeli problem prymalny jest nieograniczony, to problem do niego dualny jest sprzeczny.

Przykład 4.2   Może się zdarzyć, że oba problemy: prymalny i dualny są sprzeczne. Tak jest na przykład dla problemu prymalnego:

$$\begin{array}{rrrr} 2x_1 & -x_2 & \leq & 2\\ -2x_1 & + x... ... \hline 3x_1 & - x_2 & \rightarrow & \mbox{max} \end{array}$$

Z twierdzenia wynika, że gdyby udało nam się znaleźć takie rozwiązanie dopuszczalne $x_1,...,x_n,z$ problemu prymalnego () i $y_1,...,y_m,w$ problemu do niego dualnego (), że $z=w$, to każde z tych rozwiązań byłoby rozwiązaniem optymalnym swojego problemu. Powstaje pytanie: kiedy takie rozwiązania istnieją? Zaraz zobaczymy, że zawsze wtedy gdy problemy () i () są niesprzeczne. Mówi o tym twierdzenie sformułowane w ostatecznej formie przez D. Gale'a, H.W. Kuhna i A.W. Tuckera w 1951 roku.

Twierdzenie 4.2 (Zasada dualności.)   Jeżeli zagadnienie prymalne () ma rozwiązanie optymalne $(\bar{x}_1,...,\bar{x}_n)$ to problem dualny () ma także rozwiązanie optymalne $(\bar{y}_1,...,\bar{y}_m)$ i zachodzi równość

$$\sum_{j=1}^n c_j\bar{x}_j = \sum_{i=1}^mb_i\bar{y}_i$$ (4.5)

Dowód. Przypuśćmy, że $(\bar{x}_1,...,\bar{x}_n)$ jest rozwiązaniem problemu prymalnego (). Zgodnie z twierdzeniem wystarczy wskazać takie rozwiązanie $(\bar{y}_1,...,\bar{y}_m)$ problemu dualnego (), żeby zachodziła równość ().
Przypuśćmy, że ostatnim słownikiem otrzymanym dla problemu () jest słownik w którym funkcja celu wyraża się wzorem

$$z = \bar{z} + \sum_{k=1}^{m+n}\bar{c}_kx_k$$ (4.6)

Pamiętamy, że we wzorze ()

-

$\bar{c}_k=0$ gdy $x_k$ jest zmienną niebazową ostatniego słownika

-

$\bar{c}_k \leq 0$ dla każdego $k=1,...,m+n$, bowiem zakładamy, że () ma rozwiązanie optymalne.

$\bar{z}$ jest oczywiście wartością maksymalną funkcji celu problemu () i, skoro $(\bar{x}_1,...,\bar{x}_n)$ jest rozwiązaniem optymalnym, zachodzi

$$\bar{z} = \sum_{j=1}^n c_j \bar{x}_j$$

Wykażemy, że szukanym rozwiązaniem optymalnym problemu dualnego jest

$$\bar{y}_1 = -\bar{c}_{n+1}, \bar{y}_2 = -\bar{c}_{n+2}, ..., \bar{y}_m = -\bar{c}_{n+m}$$

W tym celu przepiszemy wzór () po dokonaniu na nim następujących manipulacji:

-

zastępujemy $z$ przez $\sum_{j=1}^n c_jx_j$,

-

korzystając z faktu, że $\sum_{k=1}^{n+m}\bar{c}_kx_k = \sum_{j=1}^n \bar{c}_jx_j + \sum_{i=1}^m \bar{c}_{n+i}x_{n+i}$ ($x_{n+i}$ są zmiennymi sztucznymi), zastępujemy

$\bar{c}_{n+i}$ przez $-\bar{y}_i$ (inaczej mówiąc, definiujemy $\bar{y}_i:=-\bar{c}_{n+i}$)

$x_{n+i}$ przez $b_i - \sum_{j=1}^n a_{ij}x_j$.

Otrzymamy wtedy wzór

$$\sum_{j=1}^n c_jx_j = \bar{z} + \sum_{j=1}^n\bar{c}_jx_j - \sum_{i=1}^m \bar{y}_i(b_i-\sum_{j=1}^n a_{ij}x_j)$$

a stąd połatwych przekształceniach

$$\sum_{j=1}^n c_jx_j = (\bar{z} - \sum_{i=1}^m \bar{y}_ib_i) + \sum_{j=1}^n (\bar{c}_j + \sum_{i=1}^m \bar{y}_ia_{ij})x_j$$ (4.7)

Równość () jest równością wielomianów zmiennych $x_1,...,x_n$, stąd

$$c_j = \bar{c}_j + \sum_{i=1}^m a_{ij}\bar{y}_i \ \ \mbox{dla } \ j=1,...,n$$ (4.8)

oraz

$$\bar{z} = \sum_{i=1}^m \bar{y}_ib_i$$ (4.9)

Równość () oznacza, że zachodzi równość (). Ponieważ $\bar{c}_j \leq 0$ dla wszystkich $j$, równość () pociąga

$$\sum_{j=1}^n a_{ij}\bar{y}_i \geq c_j \ \ \ \mbox{dla }\ \ j=1,...,n$$

a więc $\bar{y}_1,...,\bar{y}_m$ jest rozwiązaniem dopuszczalnym problemu () i twierdzenie zostało wykazane.