Programowanie liniowe

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

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

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

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

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

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

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

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

${\displaystyle x_{1}\geqslant 2,}$

${\displaystyle x_{1}\leqslant 1.}$

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

Zmaksymalizuj ${\displaystyle f=x_{1}}$ przy warunku

${\displaystyle 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ć minimalizowana. Występują tylko warunki postaci:

${\displaystyle 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:

${\displaystyle x_{i}\geqslant 0.}$

Można więc zapisać:

${\displaystyle {\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:

${\displaystyle {\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:

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

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

przy ograniczeniach

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

gdzie:

${\displaystyle {\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 maksymalizacji na minimalizacje oraz warunków mniejsze-równe na większe-równe, dokonuje się przez zamianę znaków przy współczynnikach. Jeśli mamy warunek:

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

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

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

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

czyli:

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

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

Jeśli na zmienną ${\displaystyle x_{i}}$ nie ma ograniczenia, że musi przyjmować tylko wartości dodatnie, wprowadzamy 2 nowe zmienne ${\displaystyle x_{i}'}$ i ${\displaystyle x_{i}''}$ i zamieniamy wszystkie wystąpienia tej zmiennej na ${\displaystyle 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:

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

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

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

${\displaystyle 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:

${\displaystyle 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.

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

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

${\displaystyle 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 ${\displaystyle 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

Przypisy

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)].