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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbbe4ac6403a2d7ca27435d510d77b98c45468b2)
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}\leqslant \alpha ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54091636723e810f87687f51a0ef8e6037d1042a)
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots +a_{n}x_{n}=\alpha .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30446685c0132d0e2657c431406757e36ca9c0af)
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f696a83531dd1bbffa824bb0b2acaa737aa43c4)
Zmienne
są liczbami rzeczywistymi.
Nie zawsze taki problem ma jakiekolwiek rozwiązanie, np.:
![{\displaystyle x_{1}\geqslant 2,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a227d0959acd09eea38d8ea2b37b5c447dde449)
![{\displaystyle x_{1}\leqslant 1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8289175e621f78b60c642ba2f7ae049d39a0dbf)
Być może też żadne rozwiązanie nie jest optymalne, ponieważ potrafimy uzyskać dowolnie dużą wartość funkcji celu, np.:
- Zmaksymalizuj
przy warunku ![{\displaystyle x_{1}\geqslant 10.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3b55e3de05f5de52b729035515403b788e10e79)
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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f2d72a9cb0c4516dd5c3ce555e829c080f7a948)
oraz na każdą zmienną nałożony jest warunek:
![{\displaystyle x_{i}\geqslant 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a06a6bf847af60be5ff5c5ffe59d5c9dc2aa8e6)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96fe919ff96dcba3927b03021ef9385ee90495c7)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94f955839321759b1f091ed94bfeff0eb00a47d2)
Jeszcze zwięźlej ujmuje się to zagadnienie w postaci macierzowej:
Zminimalizować funkcję celu
![{\displaystyle z(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf4e71476b574057b127761499e51fe5ce6b4569)
przy ograniczeniach
![{\displaystyle {\begin{aligned}\mathbf {A} \mathbf {x} \leqslant \mathbf {b} ,\\\mathbf {x} \geqslant \Theta ,\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3b886d4e7737b9d1ca8f6cad34847aea55be3b)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4509a50e34b6959ae020adee135a0c298ce45f94)
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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2c1a102f8d405655cbac56d22ef3c85d1cc0954)
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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bbc8d2f163b28ed4fdef8eb67b18fd07932f918)
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\leqslant \alpha ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7ef95eac8d91717ebe6b4dd504e622e2b65d61d)
czyli:
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}\geqslant \alpha ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bbc8d2f163b28ed4fdef8eb67b18fd07932f918)
![{\displaystyle -a_{1}x_{1}+-a_{2}x_{2}-\ldots a_{n}x_{n}\geqslant -\alpha .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3665eb3920eb489a685bbb10aa93e848b56be0d5)
Jeśli na zmienną
nie ma ograniczenia, że musi przyjmować tylko wartości dodatnie, wprowadzamy 2 nowe zmienne
i
i zamieniamy wszystkie wystąpienia tej zmiennej na
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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bbc8d2f163b28ed4fdef8eb67b18fd07932f918)
wprowadzamy nową zmienną
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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1566d2f8214817f38a385e240bfb874ec6b236ad)
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\ldots a_{n}x_{n}-s=\alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0ee1231ebc44cd0c2c4311c182cdba1bb1dad72)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f35e2f06074ba4dbb736ffa2f5faf41dc6ab47c)
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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffb2950a7b0d30b1fc26798e9a0ec6ddffece33a)
![{\displaystyle x_{4}=5+2x_{2}-x_{3},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35d37741b46c90da7489bc250eabd2023377acb6)
![{\displaystyle x_{5}=-2-x_{1}+{\frac {1}{2}}x_{3}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f556d618523cbad5f33c9638eca39946414fa00)
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
). 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ż
Przypisy
- ↑ programowanie liniowe, [w:] Encyklopedia PWN [dostęp 2022-10-06] .
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)].
Kontrola autorytatywna (convex optimization):
- LCCN: sh85082127
- GND: 4035816-1
- NDL: 00570683
- BnF: 119415380
- BNCF: 21955
- NKC: ph122356
- J9U: 987007555765405171
Encyklopedie internetowe:
- Britannica: topic/linear-programming-mathematics, topic/linear-programming-education