Programowanie liniowe

Programowanie liniowe (optymalizacja liniowa) – klasa problemów programowania matematycznego, w której funkcja celu oraz wszystkie warunki ograniczające mają postać liniową^[1]. Celem optymalizacji jest znalezienie maksimum lub minimum funkcji celu. Programowanie liniowe znalazło szerokie zastosowanie w teorii decyzji, np. do optymalizacji planu produkcyjnego. Wiele problemów optymalizacyjnych znajduje rozwiązanie poprzez ich sprowadzenie do postaci problemu programowania liniowego.

Funkcja celu ma postać liniową:

${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=\alpha +c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}}$

gdzie ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ - zmienne, które są liczbami rzeczywistymi, ${\displaystyle c_{1},c_{2},\dots ,c_{n}}$ oraz ${\displaystyle \alpha }$ - stałe parametry określające funkcję.

Warunki ograniczające występują w postaci nierówności lub równości liniowych, tj.:

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

lub

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

lub

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

Celem optymalizacji jest znalezienie punktu ${\displaystyle [x_{1},x_{2},\dots ,x_{n}]}$ dla którego ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=max}$ lub ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})=min.}$

Nie zawsze problem ma jakiekolwiek rozwiązanie:

(1) gdy warunki ograniczające wzajemnie się wykluczają:

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

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

(2) gdy żadne rozwiązanie nie jest optymalne, ponieważ można uzyskać dowolnie dużą wartość funkcji celu, np. zadanie:

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

${\displaystyle x_{1}\geqslant 10.}$

Postać standardowa to taka, w której funkcja celu ma być maksymalizowana. 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:

Zmaksymalizować 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}}}$

Ż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:

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

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

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