Ogólny problem programowania liniowego

Nasze rozważania o programowaniu liniowym rozpocznijmy od przykładu.

Przykład 2.1   Właściciel ciężarówki może przewieźć z miejscowości A do B cukier, mąkę i chipsy. W ciężarówce mieści się towar o objętości co najwyżej 7000 litrów i wadze co najwyżej 5 ton. 1 kg cukru zajmuje objętość 1,5 litra, 1 kg mąki 2 litry, natomiast 1 kg chipsów zajmuje objętość 4 litrów. Zysk od przewozu poszczególnych towarów jest następujący:

-

za 100 kg cukru 8 zł,

-

za 100 kg mąki 10 zł,

-

za 100 kg chipsów 25 zł.

Ile cukru, mąki i chipsów powinien załadować właściciel ciężarówki aby zmaksymalizować swój zysk?
Matematyczny model tak postawionego zadania jest następujący:
Oznaczmy przez:

$x_1$ - ilość cukru,

$x_2$ - ilość mąki,

$x_3$ - ilość chipsów

(za każdym razem w setkach kilogramów).
Skoro ciężarówka może zabrac co najwyżej 5 ton towarów, musi zachodzić nierówność:

$$100 x_1 + 100 x_2 + 100 x_3 \leq 2000$$

Z koleji ograniczenie objętości wyraża się wzorem

$$150 x_1 + 200 x_2 + 400 x_3 \leq 7000$$

Zysk właściciela wynosi:

$$z = 8x_1 + 10 x_2 + + 25 x_3$$

$x_1, x_2$ i $x_3$ muszą być oczywiście nieujemne. Po uproszczeniach otrzymamy więc problem programowania matematycznego:

$f(x_1,x_2,x_3) = 8x_1+ 10 x_2 + 25 x_3 \rightarrow \mbox{max}$

w zbiorze $\left\{ \begin{array}{llll} x_1 & + x_2 & x_3 & \leq 50\\ 1,5x_1 & + 2x_2 & 4x_3 & \leq 70\\ & x_j \geq 0 & \mbox{dla } & j=1,2,3. \end{array} \right .$

Definicja 2.1   Problemem programowania liniowego, lub krótko: PPL, będziemy nazywać problem programowania matematycznego sformułowany następująco:
Niech $c_j$ dla oraz $a_{ij}$ dla $i=1,...,m, \ j=1,...,n$ będą liczbami rzeczywistymi.

znaleźć maksimum funkcji $f(x_1,...,x_n) = \sum^{n}_{j=1} c_{j}x_j$

przy ograniczeniach:

$\sum^{n}_{j=1} a_{ij}x_j\leq b_i \ \ \ (i=1,...,m)$

$x_j \geq 0 \ \ \ (j=1,..,n).$

Często wygodnie będzie nam pisać

$$\begin{array}{rrl} \sum^{n}_{j=1} a_{ij}x_j & \leq b_i & ... ...sum^{n}_{j=1} c_{j}x_j & \rightarrow \mbox{ max} \end{array}$$ (2.1)

$f(x_1,...,x_n) = \sum^{n}_{j=1} c_{j}x_j$ nazywamy funkcją celu, zaś nierówności ograniczeniami. Zmienne $x_1,...,x_n$ nazywamy zmiennymi decyzyjnymi. Zauważmy, że zarówno funkcja celu jak i lewe strony nierówności we wzorze są funkcjami liniowymi. Nasz problem programowania liniowego można sformułować więc tak:

$$% latex2html id marker 220 \left. \begin{array}{ll} \mb... ...{\bf b} \\ & {\bf x} \geq \Theta _n \end{array} \right\}$$ (2.2)

(gdzie ${\bf c}=[c_1,...,c_n], {\bf x} = (x_j)_{j=1,...,n} \in {\bf R^n}, \ \ \Theta_n = (0,...,0) \in {\bf R^n}$), ${\bf A}=(a_{ij})_{ i=1,...,m; j=1,...,n } \in {\bf R^{m\times n}}.$ Postać PPL przedstawioną w definicji czy też wzorami () lub () nazywamy standardową postacią PPL.
Uwaga:
W życiu codziennym buisnessmanow występują dwa rodzaje zachowań: albo maksymalizują oni swój zysk (model optymistyczny), albo minimalizują koszty (model pesymistyczny) - oczywiście przy założonych z góry efektach. Taki "pesymistyczny" model zachowań może mieć na przykład następującą formę analityczną.
Przykład PPL w postaci niestandardowej:

zminimalizować: $x_1 - x_2 + x_3$

przy ograniczeniach: $\left\{ \begin{array}{rrrr} x_1 & - 2x_2 & + x_3 & \leq 2\\ x_1 & & - x_3 & \geq 1\\ x_1 & + x_2 & + 2x_3 & = 4 \end{array} \right.$ $x_i \geq 0 \ \ (i=1,2,3)$

Zauważmy, że przy pomocy banalnych operacji arytmetycznych można powyższy problem sprowadzić do PPL w postaci standardowej:

zmaksymalizować: $-x_1 + x_2 - x_3$

przy ograniczeniach: $\left\{ \begin{array}{rrrrl} x_1 & - 2x_2 & + x_3 & \leq & 2\\ -x_1 & & + ... ... & - 2x_3 & \leq & -4\\ && x_i & \geq & 0 \ \ \ i=1,2,3 \end{array} \right.$