Dualność ogólniej

Jak zobaczymy w ustępie , czasami wygodnie będzie nam dysponowąć problemem dualnym do PPL w następującej postaci:

$$% latex2html id marker 3479 \left\{ \begin{array}{lrclr}... ...\in R)\\ & x_j & \geq & 0 & (j \in P) \end{array} \right.$$ (4.17)

W PPL postaci () tylko o części zmiennych $(x_j)$ zakładamy, że są nieujemne (dla $j \in P$), pozostałe zmienne nazywamy wolnymi, a zbiór indeksów zmiennych wolnych oznaczamy przez $W$^4.3

Definicja 4.2   Problemem dualnym do () nazywamy problem programowania liniowego następującej postaci:

$$% latex2html id marker 3500 \left\{ \begin{array}{lrcll}... ...y_i & \geq & 0 & \mbox{\em dla } i \in N \end{array} \right.$$ (4.18)

Problem () nazywamy wtedy problemem prymalnym (względem ()).

Przykład 4.3   Problemem dualnym do PPL

$$% latex2html id marker 3744 \begin{array}{lrcrcrcr} \mbox... ... 5x_2 & + & x_3 & = & 1\\ &&&&& x_2 & \geq & 0 \end{array}$$

jest PPL

$$% latex2html id marker 3745 \begin{array}{lrcrcrcr} \mbox... ...2 & + & y_3 & = & 2\\ &&&&& y_1,y_2 & \geq & 0 \end{array}$$

Rzeczywiście, w naszym przykładzie mamy $N=\{1,2\}$, $R=\{ 3\}$, $P=\{ 2\}$, $W=\{1,3\}$.$\Box$

Wyniki jakie otrzymamy dla problemów () i () są uogólnieniami twierdzeń ustępu w tym sensie, że jeśli w problemach () i () położymy $R=\emptyset$ i $W=\emptyset$ (a więc $P=1,...,n$), to poniższe twierdzenia i sprowadzają się do twierdzeń i .

Twierdzenie 4.8   Jeżeli $\bar{x}_1,...,\bar{x}_n$ i $\bar{y}_1,...,\bar{y}_m$ są rozwiązaniami dopuszczalnymi problemów, odpowiednio () i (), to zachodzi nierówność

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

Dowód twierdzenia niewiele różni się od dowodu twierdzenia .
Dla $j \in P$ mamy

$$c_j \leq \sum_{i=1}^m a_{ij}\bar{y}_i$$

co po wymnożeniu przez $\bar{x}_j$ (pamiętamy, że wtedy $\bar{x}_j \geq 0$) daje

$$c_j\bar{x}_j \leq (\sum_{i=1}^m a_{ij}y_i)\bar{x}_j$$

Z kolei dla $j\in W$

$$c_j = \sum_{i=1}^m a_{ij}\bar{y}_i$$

i wobec tego

$$c_j\bar{x}_j = (\sum_{i=1}^m a_{ij}\bar{y}_i)\bar{x}_j$$

Sumując te wzory po wszystkich $j=1,...,n$ otrzymamy

$$\sum_{j=1}^n c_j\bar{x}_j \leq \sum_{j=1}^n (\sum_{i=1}^m a_{ij}\bar{y}_i)\bar{x}_j$$

co po łatwych przekształceniach daje

$$\sum_{j=1}^n c_j\bar{x}_j \leq \sum_{j=1}^n (\sum_{i=1}^m a_{ij}\bar{y}_i)\bar{x}_j$$

Dla $i\in N$ mamy $\sum_{j=1}^na_{ij}\bar{x}_j \leq b_i$ oraz $\bar{y}_i \geq 0$, więc

$$(\sum_{j=1}^n a_{ij}\bar{x}_j)\bar{y}_i \leq b_i\bar{y}_i$$

Podobnie, dla $i\in R$

$$(\sum_{j=1}^n a_{ij}\bar{x}_j)\bar{y}_i = b_i\bar{y}_i$$

Znowu sumując po $i\in N \cup R = \{ 1,...,m\}$ otrzymamy ostatecznie

$$\sum_{i=1}^m (\sum_{j=1}^n a_{ij}\bar{x}_j)\bar{y}_i \leq \sum_{i=1}^mb_i\bar{y}_i$$

i dowód twierdzenia jest zakończony. Czytelnika który nie jest jeszcze znużony kolejnym wykorzystaniem metody sympleksowej którą poznał w rozdziale 3, zachęcamy do samodzielnego udowodnienia przedstawionej poniżej uogólnionej zasady dualności (lub do odszukania dowodu w literaturze (np. w [4]).

Twierdzenie 4.9   [Ogólna zasada dualności] Jeżeli problem prymalny () ma rozwiązanie optymalne, to także problem dualny () ma rozwiązanie optymalne i wartości funkcji celu obu tych rozwiązań są równe.

Uwaga. Łatwo zauważyć, że jeśli wymnożymy w obu problemach () i () funkcje celu oraz nierówności w pierwszych linijkach ograniczeń przez $-1$, to otrzymamy sytuację w której problem () jest problemem w którym maksymalizujemy funkcję celu i problemem do niego dualnym jest (). Stąd prawdziwy jest wniosek:

Wniosek 4.10   Jeśli () ma rozwiązanie optymalne, to także () ma rozwiązanie optymalne i wartości tych rozwiązań są identyczne.