Programowanie liniowe

Programowanie liniowe – klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:

$a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\geqslant \alpha ,$

$a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leqslant \alpha ,$

$a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}=\alpha .$

Mamy zmaksymalizować lub zminimalizować funkcję celu, również liniową:

$f=\alpha +c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}.$

Zmienne $x_{i}$ są liczbami rzeczywistymi.

Nie zawsze taki problem ma jakiekolwiek rozwiązanie, np.:

$x_{1}\geqslant 2,$

$x_{1}\leqslant 1.$

Być może też żadne rozwiązanie nie jest optymalne, ponieważ potrafimy uzyskać dowolnie dużą wartość funkcji celu, np.:

Zmaksymalizuj $f=x_{1}$ przy warunku

$x_{1}\geqslant 10.$

Programowanie liniowe znalazło szerokie zastosowanie w teorii decyzji, np. do optymalizacji planu produkcyjnego. Wiele problemów optymalizacyjnych znajduje rozwiązanie poprzez sprowadzenie ich do postaci problemu programowania liniowego.

Postać standardowa

Postać standardowa to taka, w której funkcja celu ma być maksymalizowana. Występują tylko warunki postaci:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha$

oraz na każdą zmienną nałożony jest warunek:

$x_{i}\geqslant 0.$

Można więc zapisać:

${\begin{array}{l}a_{11}x_{1}+a_{12}x_{2}+\ldots a_{1n}x_{n}\leqslant b_{1},\\a_{21}x_{1}+a_{22}x_{2}+\ldots a_{2n}x_{n}\leqslant b_{2},\\\ldots \\a_{m1}x_{1}+a_{m2}x_{2}+\ldots a_{mn}x_{n}\leqslant b_{m},\\[.7em]x_{1},x_{2},\dots ,x_{n}\geqslant 0,\end{array}}$

czyli ograniczenia w postaci standardowej można w sposób ogólny zapisać bardziej zwięźle:

${\begin{aligned}\sum _{j=1}^{n}a_{ij}x_{j}&\leqslant b_{i}&\quad {\textrm {dla}}\quad i&=1,\dots ,m,\\x_{j}&\geqslant 0&\quad {\textrm {dla}}\quad j&=1,\dots ,n.\end{aligned}}$

Jeszcze zwięźlej ujmuje się to zagadnienie w postaci macierzowej:

Zmaksymalizować funkcję celu $z(\mathbf {x} )$

$z(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x}$

przy ograniczeniach

${\begin{aligned}\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\\\mathbf {x} \geqslant \Theta ,\end{aligned}}$

gdzie:

${\begin{aligned}\mathbf {c} &=(c_{j})_{j=1,\dots ,n}\in \mathbb {R} ^{n},\\\mathbf {b} &=(b_{i})_{i=1,\dots ,m}\in \mathbb {R} ^{m},\\\mathbf {x} &=(x_{i})_{i=1,\dots ,n}\in \mathbb {R} ^{n},\\\Theta &=(0,\dots ,0)\in \mathbb {R} ^{n}\\\mathbf {A} &=(a_{ij})_{i=1,\dots ,m;j=1,\dots ,n}\in \mathbb {R} ^{m\times n}.\end{aligned}}$

Sprowadzanie do postaci standardowej

Żeby przekształcić problem do postaci standardowej, zamiany minimalizacji na maksymalizację oraz warunków mniejsze-równe na większe-równe, dokonuje się przez zamianę znaków przy współczynnikach. Jeśli mamy warunek:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha ,$

to jest on równoważny parze warunków:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,$

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha ,$

czyli:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,$

$-a_{1}x_{1}+-a_{2}x_{2}-\ldots a_{n}x_{n}\geqslant -\alpha .$

Jeśli na zmienną $x_{i}$ nie ma ograniczenia, że musi przyjmować tylko wartości dodatnie, wprowadzamy 2 nowe zmienne $x_{i}'$ i $x_{i}''$ i zamieniamy wszystkie wystąpienia tej zmiennej na $x_{i}'-x_{i}''.$ Na obie nowe zmienne możemy już nałożyć ograniczenie, że są one nieujemne.

Postać równościowa

Postać równościowa (kanoniczna) to taka, w której funkcja celu ma być zmaksymalizowana, wszystkie warunki są równościami, a na wszystkie zmienne nakłada się warunek, że są nieujemne.

Żeby pozbyć się nierówności:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,$

wprowadzamy nową zmienną $s,$ która może przyjmować tylko wartości nieujemne i przekształcamy równanie do postaci:

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}=\alpha +s,$

$a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}-s=\alpha$

i analogicznie dla mniejsze-równe, z odwróconym znakiem.

Zwykle chcemy przepisać te równania do postaci:

$x_{i}=\alpha _{i}+\sum _{j=1}^{n}c_{ij}x_{j}$

tak, że zmienne występujące po lewej stronie równań nie występują nigdzie indziej (ani po prawej stronie równań, ani w funkcji celu).

Z układem takim wiąże się rozwiązanie podstawowe – takie, w którym wszystkie zmienne oprócz lewostronnych mają przypisaną wartość zero, natomiast wszystkie lewostronne oraz funkcja celu mają wartość równą wartości odpowiednich stałych.

$f=2-x_{1}+x_{2},$

$x_{4}=5+2x_{2}-x_{3},$

$x_{5}=-2-x_{1}+{\frac {1}{2}}x_{3}.$

Rozwiązaniem podstawowym tego układu jest (0, 0, 0, 5, −2), i wartością funkcji celu jest 2.

Rozwiązanie podstawowe nie zawsze musi spełniać wszystkie warunki nieujemności (w tym przypadku niespełniony jest warunek na $x_{5}$). Przekształcenie równania, które zachowuje zbiór prawidłowych rozwiązań może zmieniać nam rozwiązanie podstawowe – taka jest zresztą idea podstawowego algorytmu programowania liniowego, algorytmu sympleksu.

Zobacz też

• metoda simpleks
• programowanie całkowitoliczbowe
• programowanie matematyczne
• programowanie nieliniowe

Linki zewnętrzne

• Skrypt dra Łukasza Kowalika z MIMUW
• Strona z przykładami programowania liniowego w środowisku Matlab autorstwa mgr inż. Anny Tomkowskiej. linprog.cba.pl. [zarchiwizowane z tego adresu (2011-08-09)].