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.

Z łatwością można się przekonać, że po sprowadzeniu problemu () do postaci standardowej otrzymamy PPL którego problemem dualnym jest wyjściowy PPL (). Tak więc prawdziwy jest 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)

Następne twierdzenie bywa nazywane słabą zasadą dualności.

Twierdzenie 4.2   Niech () będzie problemem prymalnym a () problemem do niego dualnym. Jeżeli $\bar{x}_1,...,\bar{x}_n$ oraz $\bar{y}_1,...,\bar{y}_m$ są rozwiązaniami dopuszczalnymi, odpowiednio, problemów () i () to

$$\sum_{j=1}^n c_j\bar{x}_j \leq \sum_{i=1}^m b_i\bar{y}_i$$

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

$$\sum_{j=1}^n c_j\bar{x}_j \leq \sum_{j=1}^n \left( \sum_{i=... ...{ y}_i \leq \sum_{i=1}^m b_i\bar{y}_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$.

Oczywisty jest następujący wniosek z twierdzenia .

Wniosek 4.3   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.4 (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 optymalnym 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. Wzajemne zależności pomiędzy problemem prymalnym a dualnym wygodnie będzie mieć zapisane w poniższej tabeli.

Jeśli problem prymalny	to problem dualny
ma rozwiązanie optymalne	ma rozwiązanie optymalne o tej
skończone	samej wartości (twierdzenie )
jest nieograniczony	jest sprzeczny (wniosek )
jest sprzeczny	jest sprzeczny lub nieograniczony