PPL

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 zabrać co najwyżej 5 ton towarów, musi zachodzić nierówność:

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

Z kolei 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}{rrll} \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.
Problem programowania liniowego można sformułować także tak:

$$% latex2html id marker 245 \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 postacią standardową 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 minimalnych efektach. Taki "pesymistyczny" model zachowań może mieć na przykład następującą formę analityczną.

Przykład 2.2 (PPL w postaci niestandardowej.)   Niech będzie dany następujący problem:

zminimalizować: $x_1 - x_2 + x_3$

przy ograniczeniach: $\left\{ \begin{array}{rrrrr} 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}{rrrrrl} x_1 & - 2x_2 & + x_3 & \leq & 2\\ -x_1 & & +... ..._2 & - 2x_3 & \leq & -4\\ && x_i & \geq & 0 & (i=1,2,3) \end{array} \right.$

Zadanie polegające na maksymalizacji funkcji $f:X \rightarrow {\bf R}$ jest równoważne minimalizacji funkcji $g:X\rightarrow {\bf R}$ zdefiniowanej wzorem $g(x)=-f(x)$. Każdą nierówność postaci

$$\sum_{j=1}^n a_{ij}x_j \geq b_i$$

można zastąpić równoważną jej nierównością

$$\sum_{j=1}^n(-a_{ij})x_j \leq -b_i$$

zaś równość

$$\sum_{j=1}^na_{ij}x_j=b_i$$

dwiema nierównościami:

$$\sum_{j=1}^n a_{ij}x_j \leq b_i$$

oraz

$$\sum_{j=1}^n a_{ij}x_j \geq b_i$$

Tak więc mimo, że w definicji zdefiniowaliśmy PPL w postaci standardowej, równie dobrze można powiedzieć, że PPL polega na maksymalizacji lub minimalizacji funkcji liniowej w zbiorze który jest rozwiązaniem ukłdu nierówności i równań liniowych w ${\bf R}^n$.
Problemem układów nierówności i równań liniowych będziemy się zajmować w rozdziale .