Programowanie liniowe - Polski Serwis Naukowy

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 \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.

Algorytm sympleksowy, inaczej metoda sympleks(ów) to stosowana w matematyce iteracyjna metoda rozwiązywania zadań programowania liniowego za pomocą kolejnego polepszania (optymalizacji) rozwiązania. Nazwa metody pochodzi od sympleksu, figury wypukłej będącej uogólnieniem trójkąta na więcej wymiarów.

Macierz – w matematyce układ liczb, symboli lub wyrażeń zapisanych w postaci prostokątnej tablicy. Choć słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową, to możliwe jest rozpatrywanie macierzy wielowskaźnikowych (zob. notacja wielowskaźnikowa). Macierze jednowskaźnikowe nazywa się często wektorami wierszowymi lub kolumnowymi, co wynika z zastosowań macierzy w algebrze liniowej. W informatyce macierze modeluje się zwykle za pomocą (najczęściej dwuwymiarowych) tablic.

Oczywiście 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

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

Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

Programowaniem całkowitoliczbowym nazywamy programowanie liniowe, w którym na zmienne decyzyjne (niektóre lub wszystkie) nałożono dodatkowe warunki, że muszą przyjmować wartości całkowite dodatnie, ponieważ rozwiązania z wartościami ułamkowymi nie miałyby sensu rzeczywistego (np. określenia 2/3 osoby lub ¾ samochodu).

$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

Ż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

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ż

programowanie nieliniowe,

programowanie matematyczne,

programowanie całkowitoliczbowe,

metoda simpleks.

Linki zewnętrzne

Skrypt dra Łukasza Kowalika z MIMUW

Strona z przykładami programowania liniowego w środowisku Matlab autorstwa Mgr inż. Anny Tomkowskiej