Podręcznik: Wstęp do programowania liniowego

2. Modelowanie zależności

2.1. Wstęp do programowania liniowego

Programowanie liniowe (PL) to zadanie optymalizacji z ograniczeniami, w którym zależności między zmiennymi należącymi do zbioru liczb rzeczywistych, a parametrami są liniowe. Zadania optymalizacji są opisywane przez dwa rodzaje funkcji: funkcję celu i zbiór ograniczeń, zatem zadania PL są opisywane przez liniową funkcję celu i zbiór ograniczeń liniowych, w których występują zmienne rzeczywiste, ciągłe.

Formułowanie zadań w postaci PL ma bardzo duże znaczenie, ponieważ ciągłość i zależności liniowe gwarantują wypukłość zbiorów rozwiązań, a to z kolei pozwala na zastosowanie efektywnych algorytmów znajdowania optimum. W praktyce jednak mogłoby się wydawać, że rzeczywiste problemy bardzo rzadko są liniowe. Czy programowanie liniowe, poza teoretycznymi pozytywnymi właściwościami ma zatem znaczenie praktyczne? Otóż dwa główne argumenty stoją za tym, aby modelowaniu zależności liniowych poświęcić uwagę:

są liczne klasy zadań, dla których zależności między zmiennymi można ująć w sposób liniowy, również w sytuacjach, w których pozornie zdawałoby się, że nie wystarczą same funkcje liniowe i zmienne ciągłe;
są liczne algorytmy rozwiązywania nieliniowych, lub nieciągłych problemów optymalizacji, które w procesie poszukiwania optimum opierają się na wynikach modeli liniowych.

Celem kolejnych podrozdziałów jest przedstawienie najważniejszych technik modelowania liniowego, interesujących sformułowań przykładowych problemów oraz koncepcji dualności, nierozłącznie wiążącej się z programowaniem liniowym.

Na początek należy w sposób formalny przedstawić zapis zadań PL.

Postać kanoniczna zadania PL jest formułowana dla

$n$ zmiennych ciągłych

$x= (x_1,..., x_n) \in R^n$ jako problem minimalizacji funkcji celu:

$\min_x f(x) = c^T x$ przy ograniczeniach

$Ax \geq b, x\in R^n$ .

Często spotykamy też zapis zadań PL w postaci standardowej, w której dodatkowo wymaga się, aby wszystkie zmienne były nieujemne.

Postać standardowa zadania PL jest formułowana dla nieujemnych zmiennych ciągłych jako problem minimalizacji funkcji celu:

$\min_x f(x) = c^T x$ przy ograniczeniach

$Ax \geq b, x\geq 0$ .

Innym, czasami spotykanym sposobem zapisu zadań PL jest formułowanie problemu w postaci dopełnieniowej, w której do każdego ograniczenia jest wprowadzana jedna pomocnicza zmienna dopełniająca, która niejako reprezentuje zapas ograniczenia dla rozwiązania dopuszczalnego.

Postać dopełnieniowa zadania PL formułuje problem minimalizacji funkcji celu:

$\min_x f(x) = c^T x$ korzystając z nieujemnych zmiennych pomocniczych przy zapisie ograniczeń równościowych

$Ax-x^ \prime=b,\, x^ \prime\geq 0$ .

Czy jednak każdy problem PL można zapisać w równoważnej, np. standardowej postaci? Rozważmy kolejne sytuacje, w których nasze sformułowanie odbiegałoby od postaci standardowej:

problem jest zadaniem maksymalizacji, a nie minimalizacji; wystarczy wtedy zapisanie funkcji celu z przeciwnym znakiem: $\max_x c^Tx \Leftrightarrow -\min_x c^Tx$
ograniczenia są postaci równościowej (przypadek z odwrotnym skierowaniem ograniczeń jest trywialny); wystarczy wtedy zapisanie ograniczeń w postaci pary ograniczeń nierównościowych: $Ax=b \Leftrightarrow Ax \geq 0, Ax\leq 0$
zmienne należą do całej przestrzeni liczb rzeczywistych; wystarczy wtedy zastąpić każdą zmienną rzeczywistą różnicą między zmiennymi nieujemnymi, takimi że pierwsza reprezentuje wartość dodatnią zmiennej, a druga ewentualną wartość ujemną: $x\in R^n \Leftrightarrow x=x^+ - x^-,\; x^+\geq 0, x^-\geq 0$ .

Szczególnie ten trzeci sposób jest wart uwagi, gdyż zastępowanie zmiennej przez parę nieujemnych zmiennych to jedna z dwóch podstawowych technik stosowanych w modelowaniu zadań PL. Zanim jednak przejdziemy do tej części, rozwiążmy przykład ilustracyjny.

Zapisać poniższe zadanie LP w postaci standardowej i przedstawić dane dla tej postaci w formie macierzowej.

$\max x_1 +3x_2-4x_3+x_5$

$\begin{matrix} x_1 &+ x_2&&- x_4&&\geq 10\\ 7x_1 &&+ 3x_3&&+x_5&= 10\\ x_1 &&&&-x_5&\leq 0\\ &x_2&&+x_4&&\leq 15 \end{matrix} \\ x_1, x_2, x_3\geq 0,\; x_4 , x_5 \text{ swobodne}$

Rozwiązanie. Stosujemy techniki podane w punktach 1, 2 i 3 i zapisujemy zadanie w postaci:

$\min -x_1 -3x_2+4x_3-x^+_5+x^-_5$

$\begin{matrix} x_1 &x_2&&- x^+_4&+ x^-_4&&&\geq& 10\\ 7x_1 &&+ 3x_3&&&+x^+_5&-x^-_5&\geq& 10\\ -7x_1 &&- 3x_3&&&-x^+_5&+x^-_5&\geq& -10\\-x_1 &&&&&-x^+_5&+x^-_5&\geq& 0\\ &-x_2&&-x^+_4&+x^-_4&&&\geq& -15 \end{matrix} \\ x_1, x_2, x_3,x^+_4 , x^-_4,x^+_5 , x^-_5\geq 0$

Wtedy odpowiednie wektory i macierze zadania PL mają postać:

$c^T=[-1, -3, 4, 0, 0, -1, 1 ]$

$A= \left| \begin{matrix} 1 & 1&&-1&1\\ 7&&3&&&1&-1\\ -7&&-3&&&-1&1\\-1 &&&&&-1&1\\ &-1&&-1&1&& \end{matrix} \right|\; b= \left| \begin{matrix} 10\\ 10\\ -10\\ 0\\ -15\end{matrix} \right|$

Jak zmieni się zapis powyższego zadania LP w postaci standardowej, gdy przyjmiemy, że to zmienne

$x_1, x_2, x_3$ są zmiennymi swobodnymi, a

$x_4, x_5$ są nieujemne? Jak zmieni się postać odpowiednich wektorów i macierzy zadania PL?

W kolejnym podrozdziale skupimy się na dwóch podstawowych wariantach problemów nie posiadających standardowej liniowej postaci, które jednak można przekształcić w równoważny problem liniowy. Przedstawione metody modelowania zależności liniowych sprowadzają się do:

wprowadzenia do zadania dodatkowych zmiennych,
oraz wprowadzenia dodatkowych ograniczeń odnoszących się do nowych zmiennych.