Korzyści

Z pewnością łatwiej jest rozwiązywać PPL w którym jest mniej równań - liczba zmiennych odgrywa tu mniejszą rolę. Jeśli więc mamy PPL o bardzo wielu (np. $m = 100$) równaniach i znacznie mniejszej liczbie (np $n = 5$) niewiadomych, to łatwiej będzie nam rozwiązywać, zamiast problemu oryginalnego, problem dualny, z $5$ równaniami i $100$ niewiadomymi ^4.1.
Powiedzmy, że rozwiązaliśmy prymalny PPL

$$\begin{array}{rrrr} \sum^{n}_{j=1}a_{ij}x_j & \leq & b_i ... ... \sum^{n}_{j=1}c_jx_j & \rightarrow & \mbox{max} \end{array}$$ (4.10)

Rozwiązaniem optymalnym () niech będzie $x^*_1,...,x^*_n$. Powiedzmy dalej, że $y^*_1,...,y^*_m$ jest rozwiązaniem optymalnym problemu dualnego

$$\begin{array}{rrrr} \sum^{m}_{i=1}a_{ij}y_i & \geq & c_j ... ... \sum^{m}_{i=1}b_iy_i & \rightarrow & \mbox{min} \end{array}$$ (4.11)

Przekonanie kogokolwiek wystarczającego światłego, na przykład naszego zleceniodawcy, że rozwiązania te są rzeczywiście rozwiązaniami optymalnymi swoich problemów (odpowiednio () i ()) jest bardzo proste: wystarczy sprawdzić, że $x^*_1,...,x^*_n$ oraz $y^*_1,...,y^*_m$ są rozwiązaniami dopuszczalnymi swoich problemów, czyli

$$\sum^{n}_{j=1}a_{ij}x_j \leq b_i \ \ (i=1,...,m)$$

oraz

$$\sum^{m}_{i=1}a_{ij}y_i \geq c_i \ \ (j=1,...,n)$$

oraz zachodzi wzór

$$\sum^n_{j=1} c_j x^*_j = \sum ^m_{i=1} b_i y_i^*$$ (4.12)

Twierdzenia i pozwolą nam nie tylko sprawdzić optymalność rozwiązań problemów prymalnego i dualnego kiedy już je mamy, ale także, w pewnych sytuacjach, łatwo znależć optymalne rozwiązanie problemu dualnego, gdy będzie dane rozwiązanie problemu prymalnego.

Twierdzenie 4.5   Niech $x^*_1,...,x^*_n$ będzie rozwiązaniem dopuszczalnym problemu (), zaś $y^*_1,...,y^*_m$ rozwiązaniem dopuszczalnym problemu dualnego (). $x_1^*,...,x_n^*$ oraz $y^*_1,...,y^*_m$ są - równocześnie - rozwiązaniami optymalnymi swoich problemów wtedy i tylko wtedy, gdy dla każdego $j=1,...,n$

$$\sum^m_{i=1}a_{ij}y^*_i = c_j \ \ \mbox{lub} \ \ x^*_j=0 \ \$$

oraz dla każdego $i=1,...,m$

$$\sum^n_{j=1}a_{ij}x^*_j = b_i \ \ \mbox{lub} \ \ y^*_i=0 \ \$$

Dowód. Niech $x^*_1,...,x^*_n$ będzie rozwiązaniem dopuszczalnym problemu prymalnego (), zaś $y^*_1,...,y^*_m$ rozwiązaniem dopuszczalnym problemu dualnego (). Podobnie jak w dowodzie twierdzenia

$$\sum_{j=1}^n c_jx^*_j \leq \sum_{j=1}^n \left( \sum_{i=1}^m... ..._{j=1}^n a_{ij}x^*_j \right) y^*_i \leq \sum_{i=1}^m b_iy^*_i$$

Zachodzenie równości

$$\sum^{n}_{j=1}c_jx^*_j = \sum^m_{i=1}b_iy^*_i$$

która, na mocy twierdzenia jest warunkiem koniecznym i wystarczającym optymalności rozwiązań $x^*_1,...,x^*_n$ i $y^*_1,...,y^*_n$ jest równoważne równościom

$$\sum_{j=1}^n c_jx^*_j = \sum_{j=1}^n \left( \sum_{i=1}^m a_... ...sum_{j=1}^n a_{ij}x^*_j \right) y^*_i = \sum_{i=1}^m b_iy^*_i$$

czyli, wobec $c_j \leq \sum^m_{i=1}a_{ij}y^*_i$ oraz $x^*_j \geq 0, (j=1,...,n)$

$$x^*_j = 0 \ \ \mbox{lub} \ \ c_j = \sum^m_{i=1}a_{ij}y^*_i \ \ (j=1,...,n)$$

oraz (wobec $\sum^n_{j=1}a_{ij}x^*_j \leq b_i \ y^*_i \geq 0 \mbox{ dla } \ i=1,...,m$)

$$y^*_i=0 \ \ \mbox{lub} \ \ \sum^n_{j=1}a_{ij}x^*_j = b_i \ (i=1,...,m). \hfill \rule{.1in}{.1in}$$

Z twierdzeń i wynika następne twierdzenie które nazwiemy twierdzeniem o odstępach komplementarnych.

Twierdzenie 4.6   Rozwiązanie dopuszczalne $x_1^*,...,x_n^*$ problemu () jest optymalne wtedy i tylko wtedy, jeżeli istnieje ciąg $m$ elementowy $y^*_1,...,y^*_m$ taki, że

1. jeśli $x^*_j >0$ to $\sum^m_{i=1}a_{ij}y^*_i = c_j$ (dla $j=1,...,n$),
2. jeśli $\sum^n_{j=1} a_{ij}x^*_j < b_i$ to $y^*_i=0$ (dla $i=1,...,m$),

przy czym:

$$\begin{array}{cccc} \sum^m_{i=1}a_{ij}y^*_i & \geq & c... ... (j=1,...,n) \\ y^*_i & \geq & 0 & (i=1,...,m).\end{array}$$ (4.13)

Dowód.

-

Jeśli PPL () ma rozwiązanie optymalne $x^*_1,...,x^*_n$, to na mocy twierdzenia istnieje rozwiązanie optymalne $y^*_1,...,y^*_m$ problemu dualnego. Tak więc $y^*_1,...,y^*_m$ spełniają () zaś $x^*_1,...,x^*_n$ spełniają warunki i na mocy twierdzenia .

-

Z drugiej strony, jeśli $y^*_1,...,y^*_m$ jest ciągiem spełniającym (), to stanowi on rozwiązanie dopuszczalne problemu dualnego . Z twierdzenia wynika, że jest to rozwiązanie optymalne.