Programowanie liniowe

Programowanie liniowe to dziedzina programowania matematycznego, w której warunki ograniczające oraz funkcja celu są liniowe. W matematycznej postaci, warunki ograniczające można zapisać jako:

$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n \geqslant \alpha$
$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n \leqslant \alpha$
$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = \alpha$

Celem jest zmaksymalizowanie lub zminimalizowanie funkcji celu, również w formie liniowej:

$f = \alpha + c_1 x_1 + c_2 x_2 + \ldots + c_n x_n.$

Zmienne $x_i$ mogą przyjmować wartości rzeczywiste. W niektórych przypadkach problem nie ma rozwiązania lub nie ma rozwiązania optymalnego.

Postać standardowa

W postaci standardowej funkcja celu jest minimalizowana, a ograniczenia mają postać:

$a_1 x_1 + a_2 x_2 + \ldots + a_n x_n \leqslant \alpha$
$x_i \geqslant 0$ dla każdej zmiennej $x_i$ .

Można to zapisać w formie macierzowej jako:

$z(\mathbf{x}) = \mathbf{c}^T \mathbf{x},$

przy ograniczeniach:

$\mathbf{A}\mathbf{x} \leqslant \mathbf{b}, \quad \mathbf{x} \geqslant \Theta.$

Sprowadzanie do postaci standardowej

Aby przekształcić problem do postaci standardowej, należy zamienić maksymalizację na minimalizację oraz nierówności na równości, co można osiągnąć poprzez dodanie zmiennych sztucznych.

Postać równościowa

Postać równościowa (kanoniczna) zakłada maksymalizację funkcji celu, wszystkie warunki są równościami, a zmienne muszą być nieujemne. W celu przekształcenia nierówności w równości, wprowadza się zmienne pomocnicze.

Rozwiązanie podstawowe polega na przypisaniu zmiennym wartości zero z wyjątkiem zmiennych lewostronnych, które przyjmują wartości odpowiadające stałym. Przykład:

$f = 2 – x_1 + x_2$
$x_4 = 5 + 2x_2 – x_3$
$x_5 = -2 – x_1 + \frac{1}{2} x_3$

Wartością funkcji celu w tym przypadku jest 2.

Rozwiązanie podstawowe nie zawsze spełnia wszystkie warunki nieujemności, co ilustruje algorytm sympleksu, który dąży do znalezienia optymalnego rozwiązania.

Najnowsze aktualności:

Programowanie liniowe