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

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} ⩾ α,

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} ⩽ α,

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = α .

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

f = α + c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n} .

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

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

x_{1} ⩾ 2,

x_{1} ⩽ 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} ⩾ 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ć maksymalizowana. Występują tylko warunki postaci:

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} ⩽ α

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

x_{i} ⩾ 0 .

Można więc zapisać:

\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + \dots a_{1 n} x_{n} ⩽ b_{1}, \\ a_{21} x_{1} + a_{22} x_{2} + \dots a_{2 n} x_{n} ⩽ b_{2}, \\ \dots \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots a_{m n} x_{n} ⩽ b_{m}, \\ [. 7 e m] x_{1}, x_{2}, \dots, x_{n} ⩾ 0, \end{matrix}

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

\begin{matrix} \sum_{j = 1}^{n} a_{i j} x_{j} & ⩽ b_{i} & dla i & = 1, \dots, m, \\ x_{j} & ⩾ 0 & dla j & = 1, \dots, n . \end{matrix}

Jeszcze zwięźlej ujmuje się to zagadnienie w postaci macierzowej:

Zmaksymalizować funkcję celu $z (𝐱)$

z (𝐱) = 𝐜^{T} 𝐱

przy ograniczeniach

\begin{matrix} 𝐀 𝐱 ⩽ 𝐛, \\ 𝐱 ⩾ Θ, \end{matrix}

gdzie:

\begin{matrix} 𝐜 & = (c_{j})_{j = 1, \dots, n} \in ℝ^{n}, \\ 𝐛 & = (b_{i})_{i = 1, \dots, m} \in ℝ^{m}, \\ 𝐱 & = (x_{i})_{i = 1, \dots, n} \in ℝ^{n}, \\ Θ & = (0, \dots, 0) \in ℝ^{n} \\ 𝐀 & = (a_{i j})_{i = 1, \dots, m; j = 1, \dots, n} \in ℝ^{m \times n} . \end{matrix}

Sprowadzanie do postaci standardowej

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

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} = α,

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

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} ⩾ α,

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} ⩽ α,

czyli:

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} ⩾ α,

- a_{1} x_{1} + - a_{2} x_{2} - \dots a_{n} x_{n} ⩾ - α .

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

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} ⩾ α,

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} + \dots a_{n} x_{n} = α + s,

a_{1} x_{1} + a_{2} x_{2} + \dots a_{n} x_{n} - s = α

i analogicznie dla mniejsze-równe, z odwróconym znakiem.

Zwykle chcemy przepisać te równania do postaci:

x_{i} = α_{i} + \sum_{j = 1}^{n} c_{i j} 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.

Zobacz też

Przypisy

Szablon:Przypisy

Linki zewnętrzne

Szablon:Kontrola autorytatywna

↑ Szablon:Encyklopedia PWN

[epwn-1] Szablon:Encyklopedia PWN

[1]

Programowanie liniowe

Spis treści

Postać standardowa

Sprowadzanie do postaci standardowej

Postać równościowa

Zobacz też

Przypisy

Linki zewnętrzne

Menu nawigacyjne

Programowanie liniowe

Postać standardowa

Sprowadzanie do postaci standardowej

Postać równościowa

Zobacz też

Przypisy

Linki zewnętrzne

Menu nawigacyjne

Szukaj