Informatyka MIMUW

Motywacja: certyfikat optymalności

Dla niektórych problemów znane są algorytmy, które wraz z rozwiązaniem generują tzw. certyfikat poprawności, czyli dodatkową informację z pomocą której możemy łatwo (tzn. algorytmem, który jest nie tylko wielomianowy, ale również istotnie prostszy od algorytmu generującego rozwiązanie) sprawdzić, czy
zwrócone rozwiązanie jest poprawne (lub optymalne w przypadku problemów optymalizacyjnych). Algorytmy te określane są mianem algorytmów certyfikujących. Oto kilka przykładów:

• Algorytm sprawdzający, czy dany graf jest dwudzielny może zwracać 2-kolorowanie takiego grafu lub cykl nieparzysty.
• Algorytm znajdowania maksymalnego przepływu wraz z przepływem może zwracać minimalny przekrój.
• Istnieje algorytm testujący planarność grafów, który zwraca rysunek na płaszczyźnie bez przecięć krawędzi lub podgraf homeomorficzny z $K_{3,3}$ lub $K_5$.

Algorytmy certyfikujące oprócz znaczenia teoretycznego (aby generować takie certyfikaty należy dobrze zrozumieć problem) mają dużą wartość praktyczną: pomyślmy choćby o testowaniu poprawności kodu.

Czy dla programowania liniowego istnieją certyfikaty poprawności? Rozważmy decyzyjną wersję problemu programowania liniowego: mając dany (minimalizacyjny) PL i liczbę $\delta$ rozstrzygnąć, czy istnieje dopuszczalny $\mathbf{x}$ taki, że $\mathbf{c}^T\mathbf{x} \le \delta$. Załóżmy dla uproszczenia, że nasz program jest ograniczony. Wraz z odpowiedzią TAK algorytm certyfikujący może zwrócić współrzędne $\mathbf{x}$ (można nawet pokazać, że te współrzędne można reprezentować w pamięci wielomianowej względem rozmiaru danych). A więc istnieje certyfikat pozytywny. Z punktu widzenia teorii złożoności, dowodzi to, że problem jest w klasie NP. W dodatku algorytm weryfikacji certyfikatu jest banalny: po prostu sprawdzamy odpowiednie nierówności. Czy możemy podać certyfikat negatywny, tzn. certyfikat poprawności dla odpowiedzi NIE? Gdyby ten certyfikat był również krótki, mielibyśmy dowód, że programowanie liniowe jest w klasie co-NP.

W tym rozdziale przedstawimy pojęcie dualności programowania liniowego, które dostarcza odpowiedzi na powyższe pytania. Jak zobaczymy w kolejnych wykładach, dualność programowania liniowego ma dużo więcej konsekwencji w matematyce i informatyce.

Poszukiwanie ograniczenia na wartość rozwiązania optymalnego

Rozważmy następujący PL w postaci standardowej:

Łatwo sprawdzić, że punkt $(x_1=2,x_2=0,x_3=4)$ jest rozwiązaniem dopuszczalnym o wartości funkcji celu $14$.

Zauważmy, że skoro $x_1,x_2,x_3\ge 0$, to $3x_1 \le 4x_1$, a także $-x_2 \le 2x_2$ oraz $2x_3 \le 3x_3$. Stąd, $3x_1 - x_2 + 2x_3 \le 4x_1 + 2x_2 + 3x_3 \le 20$. Dostaliśmy górne ograniczenie! W tym przypadku możemy zauważyć nawet więcej. Ponieważ $3 \le 1+\frac{1}{2}\cdot 4$, $-1 \le -1+\frac{1}{2}\cdot 2$ oraz $2 \le \frac{1}{2}+\frac{1}{2}\cdot 3$, więc
$$\begin{split} \nonumber 3x_1 - x_2 + 2x_3 \le&\; x_1 - x_2 + \frac{1}{2}x_3 \; + \\ &\; \frac{1}{2}\cdot (4x_1 + 2x_2 + 3x_3) \le 4+\frac{1}{2}\cdot 20 = 14. \end{split}$$

Udowodniliśmy (choć, trzeba przyznać, dość fartownie), że wartość funkcji celu nigdy nie przekracza $14$, a więc mamy certyfikat optymalności, w dodatku bardzo krotki (kilka nierówności) i prosty do sprawdzenia.
Możemy to rozumowanie uogólnić: można brać dowolne kombinacje liniowe nierówności t.ż.:

• współczynniki kombinacji liniowej są nieujemne (bo inaczej odwrócą się kierunki nierówności),
• dla dowolnego $i$, współczynnik funkcji celu przy $x_i$ jest ograniczony z góry przez odpowiednią kombinację liniową współczynników przy $x_i$ w nierównościach.

Można to zapisać za pomocą programu liniowego:

Powyższy program będziemy nazywać programem dualnym do programu (P1). Ogólnie, dla programu (będziemy go nazywać programem prymalnym)

program dualny ma postać:

Zauważmy, że macierz współczynników ograniczeń programu (D2) jest transpozycją macierzy dla programu (P2) (porównaj też dla programów (P1) i (D1)). Daje to niezwykle prosty, mechaniczny sposób konstruowania programu dualnego. Mianowicie dla programu

$$\begin{array}{ll@{\hspace{15mm}}l} \textrm{zmaksymalizuj} & \mathbf{c}^T\mathbf{x} & \\ \textrm{z zachowaniem warunków} & \mathbf{A}\mathbf{x} \le \mathbf{b}&\\ & \mathbf{x} \ge \mathbf{0}& \end{array}$$

program dualny ma postać:

$$\begin{array}{ll@{\hspace{15mm}}l} \textrm{zminimalizuj} & \mathbf{b}^T\mathbf{y} & \\ \textrm{z zachowaniem warunków} & \mathbf{A}^T\mathbf{y} \ge \mathbf{c} \\ & \mathbf{y}\ge\mathbf{0} \end{array}$$

Dualność jest relacją symetryczną, tzn. mówimy także, że (P2) jest dualny do (D2). Innymi słowy, program dualny do programu dualnego to program prymalny.

Słaba dualność i komplementarne warunki swobody

Pozostańmy przy programach w postaci standardowej. Z konstrukcji programu dualnego wynika następujący fakt (dla porządku podamy jednak dowód).

Twierdzenie 1 [o słabej dualności]
Niech $\mathbf{x}$ i $\mathbf{y}$ będą dowolnymi rozwiązaniami dopuszczalnymi odpowiednio programów (P2) i (D2). Wówczas $\mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y}$.

Dowód
Ponieważ dla każdego $j=1,\ldots,n$, mamy $x_j\ge 0$ oraz $\sum_{i=1}^m a_{ij}y_i \ge c_j$, więc
$$(*)\quad\quad \quad\quad \quad\quad c_j x_j \le \left(\sum_{i=1}^m a_{ij}y_i\right) x_j \quad\quad \forall j=1,\ldots,n.$$
Podobnie, ponieważ dla każdego $i=1,\ldots,m$, mamy $y_i\ge 0$ oraz $\sum_{j=1}^n a_{ij}x_j \le b_i$, więc
$$(**)\quad\quad \quad\quad \quad\quad\left(\sum_{j=1}^n a_{ij}x_j\right) y_i \le b_i y_i \quad\quad \forall i=1,\ldots,m.$$
Stąd,
$$(***)\quad\quad \quad\quad \quad\quad\mathbf{c}^T\mathbf{x}=\sum_{j=1}^n c_jx_j\le \sum_{j=1}^n\left(\sum_{i=1}^m a_{ij}y_i\right) x_j=\sum_{i=1}^m\left(\sum_{j=1}^n a_{ij}x_j\right) y_i\le\sum_{i=1}^m b_i y_i = \mathbf{b}^T\mathbf{y}.$$ ♦

Zastanówmy się, kiedy rozwiązania optymalne programu prymalnego (P2) i dualnego (D2) spotykają się, czyli $\mathbf{c}^T\mathbf{x}=\mathbf{b}^T\mathbf{y}$. Z dowodu twierdzenia o słabej dualności widzimy, że jest tak wtedy i tylko wtedy gdy obie nierówności w (***) są równościami. Tak może się wydarzyć tylko wtedy, gdy gdy wszystkie nierówności w (*) i (**) są równościami. To dowodzi następującego twierdzenia:

Twierdzenie (o komplementarnych warunkach swobody)
Niech $\mathbf{x}$ i $\mathbf{y}$ będą rozwiązaniami dopuszczalnymi odpowiednio dla zadania prymalnego i dualnego w postaci standardowej. Rozwiązania $\mathbf{x}$ i $\mathbf{y}$ są oba optymalne wtedy i tylko wtedy gdy

• prymalne komplementarne warunki swobody: dla każdego $j=1,\ldots,n$ albo $x_j=0$ albo $\sum_{i=1}^m a_{ij}y_i=c_j$.
  (tzn. albo $x_j=0$ albo $j$-ta nierówność programu dualnego jest spełniona z równością.)
• dualne komplementarne warunki swobody dla każdego $i=1,\ldots,m$ albo $y_i=0$ albo $\sum_{j=1}^n a_{ij}x_j=b_i$.
  (tzn. albo $y_i=0$ albo $i$-ta nierówność programu prymalnego jest spełniona z równością.)

Programy dualne do ogólnych programów liniowych

Nawet gdy program nie jest w postaci standardowej możemy napisać program dualny, kierując się tą samą zasadą: poszukujemy jak najlepszego górnego ograniczenia na wartość funkcji celu. Zobaczmy np. co się dzieje, gdy program zawiera równość:

$$\label{eq:primal11} \begin{array}{ll} \textrm{zmaksymalizuj} & 3x_1 - x_2 + 2x_3 \\ \textrm{z zachowaniem warunków} & x_1 - x_2 + \frac{1}{2}x_3 \le 4 \\ & - 4x_1 - 2x_2 - 3x_3 = -20\\ & x_1,x_2,x_3\ge 0 \end{array}$$

Podobnie jak poprzednio, dodając pierwszy warunek pomnożony przez $y_1 = 1$ do drugiego warunku pomnożonego przez $y_2=-\frac{1}{2}$ dostajemy ograniczenie górne równe $14$. Zauważmy, że w kombinacji liniowej warunków, współczynniki dla nierówności muszą być nieujemne, natomiast dla równości mogą być dowolne (w tym przypadku wybraliśmy ujemny). Program dualny wygląda następująco:

$$\label{eq:dual11} \begin{array}{ll} \textrm{zminimalizuj} & 4y_1 + 20y_2 \\ \textrm{z zachowaniem warunków} & y_1 + 4y_2 \ge 3 \\ & -y_1 + 2y_2 \ge -1\\ & \frac{1}{2}y_1+3y_2\ge 2\\ & y_1\ge 0. \end{array}$$

A co by się stało, gdyby w programie prymalnym dodatkowo mogły się pojawiać zmienne bez warunku nieujemności? Rozważmy np.

$$\label{eq:primal112} \begin{array}{ll} \textrm{zmaksymalizuj} & 3x_1 - x_2 + 2x_3 \\ \textrm{z zachowaniem warunków} & x_1 - x_2 + \frac{1}{2}x_3 \le 4 \\ & 4x_1 + 2x_2 + 3x_3 = 20\\ & x_1,x_3\ge 0 \end{array}$$
Wówczas nie możemy już napisać, że $3x_1 - x_2 + 2x_3 \le 4x_1 + 2x_2 + 3x_3$, gdyż niekoniecznie $-x_2 \le 2x_2$. Jeśli jednak pomnożymy pierwszą nierówność przez 3 i dodamy do drugiej, dostaniemy:

$$\begin{split} \nonumber 3x_1 - x_2 + 2x_3 \le&\; 3 (x_1 - x_2 + \frac{1}{2}x_3) \; + \\ &\; 4x_1 + 2x_2 + 3x_3 \le 12+20 = 32, \end{split}$$
gdyż $3x_1 \le 7x_1$, $-x_2 = -x_2$ oraz $2x_3\le 3x_3$. Znalezienie najlepszej kombinacji liniowej warunków odpowiada programowi:

$$\label{eq:dual111} \begin{array}{ll} \textrm{zminimalizuj} & 4y_1 + 20y_2 \\ \textrm{z zachowaniem warunków} & y_1 + 4y_2 \ge 3 \\ & -y_1 + 2y_2 = -1\\ & \frac{1}{2}y_1+3y_2\ge 2\\ & y_1\ge 0. \end{array}$$

Ogólnie, program dualny konstruujemy zgodnie z poniższą zasadą:

Można łatwo sprawdzić, że program dualny zbudowany zgodnie z powyższymi wytycznymi również spełnia twierdzenie o słabej dualności (a także twierdzenie o silnej dualności, które udowodnimy w kolejnym punkcie).

Silna dualność

Twierdzenie o słabej dualności można również wyrazić w następujący sposób:

Wniosek
Jeśli $z$ jest wartością funkcji celu rozwiązania optymalnego prymalnego minimalizacyjnego PL, natomiast $w$ jest wartością funkcji celu rozwiązania optymalnego programu dualnego, to $z \ge w$.

Wynika stąd w szczególności, że gdy $z=w$, to rozwiązanie optymalne programu dualnego jest certyfikatem optymalności naszego rozwiązania programu prymalnego. Okazuje się, że tak jest zawsze!

Twierdzenie (o silnej dualności)
Jeśli $z$ jest wartością funkcji celu rozwiązania optymalnego prymalnego PL, natomiast $w$ jest wartością funkcji celu rozwiązania optymalnego programu dualnego, to $z = w$.

Dowód
Dla uproszczenia przeprowadzimy dowód dla przypadku programu w maksymalizacyjnej postaci standardowej (dowód dla ogólnej postaci jest analogiczny). Oto program prymalny:

oraz program dualny:

Niech $\mathbf{x}^*$ będzie rozwiązaniem optymalnym programu prymalnego (P3). Ze słabej dualności, wystarczy pokazać rozwiązanie dopuszczalne $\mathbf{y}$ programu dualnego (D3) t.ż. $\mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}$. Uruchamiamy algorytm simplex (patrz poprzedni wykład) na programie (P3).
W pierwszej iteracji algorytm simplex buduje program

Rozważmy program z ostatniej iteracji algorytmu simplex.

Ponieważ program prymalny jest ograniczony, więc dla każdego $j\in N$, $c'_j \le 0$ oraz algorytm simplex zwraca rozwiązanie optymalne $\mathbf{x}^*$ takie, że
$$x^*_i = \left\{ \begin{array}{cl} 0 & \text{gdy \(i\in N\)} \\ b'_i & \text{gdy \(i\in B\).} \end{array} \right.$$

Określimy teraz pewne rozwiązanie programu dualnego (D3):
$$y_i := \left\{ \begin{array}{cl} -c'_{n+i} & \text{gdy \(n+i\in N\)} \\ 0 & \text{w p. p.} \end{array} \right.$$

Pokażemy teraz, że $\mathbf{y}$ jest dopuszczalny o wartości funkcji celu równej $\mathbf{c}^T\mathbf{x}^*$. Określamy $c'_j:=0$ dla $j\in B$. Wówczas pierwszy warunek programu (P3-stop) możemy zapisać jako $z = v + \sum_{j=1}^{n+m} c'_jx_j$.

Weźmy dowolne $(x_1,\ldots,x_n)\in \mathbb{R}^n$. Określmy $x_{n+i} = b_i - \sum_{i=1}^n a_{ij}x_j$ oraz $z=\sum_{i=1}^n a_{ij}x_j$. Wówczas $(z,x_1,\ldots,x_{n+m})$ jest rozwiązaniem dopuszczalnym programu (P3-start). Ponieważ program (P3-stop) jest równoważny (P3-start), tzn. powstaje z (P3-start) na drodze ciągu operacji elementarnych, więc $(z,x_1,\ldots,x_{n+m})$ jest również rozwiązaniem dopuszczalnym programu (P3-stop). Z faktu, iż w obu programach spełnione są warunki zawierające zmienną $z$ mamy, iż:
$$\begin{array}{rcl} \sum_{j=1}^n c_jx_j & = & v + \sum_{j=1}^{n+m} c'_jx_j \\ & = & v + \sum_{j=1}^{n} c'_jx_j + \sum_{i=1}^{m} c'_{n+i}x_{n+i} \\ & = & v + \sum_{j=1}^{n} c'_jx_j + \sum_{i=1}^{m} (-y_i)(b_i - \sum_{j=1}^n a_{ij}x_j). \end{array}$$
Po przegrupowaniu dostajemy, że dla dowolnego $(x_1,\ldots,x_n)\in \mathbb{R}^n$,
$$\sum_{j=1}^n c_jx_j = \left(v - \sum_{i=1}^{m} y_i b_i\right) + \sum_{j=1}^n \left(c'_j + \sum_{i=1}^m y_i a_{ij}\right) x_j.$$

Podstawiamy $(x_1,\ldots,x_n) = (0,\ldots,0)$ i mamy $v = \sum_{i=1}^{m} y_i b_i$. Ponieważ $\mathbf{c}^T\mathbf{x}^* = v$, więc $\mathbf{c}^T\mathbf{x}^* = \mathbf{b}^T \mathbf{y}$. Pozostaje pokazać dopuszczalność $\mathbf{y}$. W tym celu rozważmy dowolne $k\in\{1,\ldots, n\}$. Podstawiamy $x_j=[j=k]$ dla każdego $j=1,\ldots,n$. Otrzymujemy
$$c_k = \underbrace{(v - \sum_{i=1}^{m} y_i b_i)}_{=0} + \underbrace{\quad c'_k\quad}_{\le 0} + \sum_{i=1}^m y_i a_{ik},$$
co implikuje $\sum_{i=1}^m y_i a_{ik} \ge c_k$ dla każdego $k$, czyli $\mathbf{A}^T \mathbf{y} \ge \mathbf{c}$. Zauważmy, że ponieważ $c'_j\le 0$ dla każdego $j$, więc $\mathbf{y} \ge 0$. Pokazaliśmy zatem, że $\mathbf{y}$ jest rozwiązaniem dopuszczalnym programu (D3) o wartości funkcji celu $\mathbf{c}^T\mathbf{x}^*$, co kończy dowód. ♦

Z powyższego dowodu wynika, że algorytm simplex znajduje równocześnie rozwiązania optymalne programu prymalnego i dualnego. W niektórych sytuacjach możemy uzyskać skrócenie czasu działania algorytmu stosując tzw. dualny algorytm simplex, tzn. uruchamiać algorytm simplex dla programu dualnego.