Programowanie liniowe

Z Wikipedii

Programowanie liniowe to 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 \ge \alpha$

$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \le \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 x_i są liczbami rzeczywistymi.

Oczywiście nie zawsze taki problem ma jakiekolwiek rozwiązanie, np.:

$x_1 \ge 2$

$x_1 \le 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 \ge 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.

[edytuj] 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 + \cdots a_n x_n \le \alpha$

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

$x_i \ge 0.$

Można więc zapisać:

$\begin{align} a_{11} x_1 + a_{12} x_2 + \cdots a_{1n} x_n &\le b_1\\ a_{21} x_1 + a_{22} x_2 + \cdots a_{2n} x_n &\le b_2\\ \dots\\ a_{m1} x_1 + a_{m2} x_2 + \cdots a_{mn} x_n &\le b_m \end{align}\;$

$x_1,x_2,\ldots,x_n\geq0\;$

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&\leq b_i&\quad\textrm{dla}\quad i&=1,\ldots,m\\ x_j &\geq 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}\leq \mathbf{b},\\ \mathbf{x}\geq\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}$

[edytuj] 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 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 \ge \alpha$

$a_1 x_1 + a_2 x_2 + \cdots a_n x_n \le \alpha$

Czyli:

$a_1 x_1 + a_2 x_2 + \cdots a_n x_n \ge \alpha$

$-a_1 x_1 + -a_2 x_2 - \cdots a_n x_n \ge -\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.

[edytuj] 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 + \cdots a_n x_n \ge \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 + 2 x 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.

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Wykłady z programowania liniowego

Kategorie: Teoria decyzji • Algebra

We provide Linux to the World

Programowanie liniowe

Z Wikipedii

Spis treści

[edytuj] Postać standardowa

[edytuj] Sprowadzanie do postaci standardowej

[edytuj] Postać równościowa

[edytuj] Zobacz też

[edytuj] Linki zewnętrzne

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach