Programowanie liniowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 + \cdots + a_n x_n \geqslant \alpha
a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leqslant \alpha
a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = \alpha

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

f = \alpha + c_1 x_1 + c_2 x_2 + \cdots + c_n x_n

Zmienne xi 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[edytuj | edytuj kod]

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

a_1 x_1 + a_2 x_2 + \cdots 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{align}
a_{11} x_1 + a_{12} x_2 + \cdots a_{1n} x_n &\leqslant b_1\\
a_{21} x_1 + a_{22} x_2 + \cdots a_{2n} x_n &\leqslant b_2\\
\dots\\
a_{m1} x_1 + a_{m2} x_2 + \cdots a_{mn} x_n &\leqslant b_m
\end{align}\;

x_1,x_2,\ldots,x_n\geqslant0\;

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


\begin{align}
 \sum_{j=1}^{n}a_{ij}x_j&\leqslant b_i&\quad\textrm{dla}\quad i&=1,\ldots,m\\
 x_j &\geqslant 0&\quad\textrm{dla}\quad j&=1,\ldots,n.
\end{align}

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{align}
   \mathbf{A}\mathbf{x}\leqslant \mathbf{b},\\
   \mathbf{x}\geqslant\Theta,
\end{align}

gdzie:


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

Sprowadzanie do postaci standardowej[edytuj | edytuj kod]

Ż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 zamiane znaków przy współczynnikach. Jeśli mamy warunek:

a_1 x_1 + a_2 x_2 + \cdots a_n x_n = \alpha

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

a_1 x_1 + a_2 x_2 + \cdots a_n x_n \geqslant \alpha
a_1 x_1 + a_2 x_2 + \cdots a_n x_n \leqslant \alpha

Czyli:

a_1 x_1 + a_2 x_2 + \cdots a_n x_n \geqslant \alpha
-a_1 x_1 + -a_2 x_2 - \cdots 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^\prime i x_i^{\prime\prime} i zamieniamy wszystkie wystąpienia tej zmiennej na x_i^\prime - x_i^{\prime\prime}. Na obie nowe zmienne możemy już nałożyć ograniczenie, że są one nieujemne.

Postać równościowa[edytuj | edytuj kod]

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 + \cdots 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 + \cdots a_n x_n = \alpha + s
a_1 x_1 + a_2 x_2 + \cdots 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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]