CCF03252008000

f

i jęczmienia nie przekroczy posiadanego areału. Warunek (2.21) powoduje, że zużycie ziemniaków na paszę i na sprzedaż nie przekroczy ilości uzyskanej z uprawy. Podobny warunek (2.22) przyjmujemy dla jęczmienia. Warunek (2.23) gwarantuje, że zapotrzebowanie na robociznę nie przekroczy ilości robocizny, jaką rolnik dysponuje (własna plus najęta).

Warunek (2.25) sprawia, iż zadanie (2.19) —(2.25) nie jest zadaniem PL, lecz zadaniem programowania calkowitoliczbowego liniowego (PCL). Ze względu na to, że rozwiązanie zadania PCL jest znacznie trudniejsze niż zadania PL, często warunek ten się pomija. Jest to uproszczenie, które w danej sytuacji jest możliwe do przyjęcia. W wielu innych przypadkach jest to jednak niedopuszczalne.

2.3

Postacie zadań programowania liniowego

Formułowane w poprzednim paragrafie modele matematyczne były liniowymi zadaniami decyzyjnymi. Jeżeli w zadaniu decyzyjnym wszystkie relacje są liniowe oraz wszystkie zmienne są ciągle, to takie zadanie nazywamy zadaniem programowania liniowego (PL).

Ogólna postać zadania PL jest następująca:

n

Z ^ci^xi ~^ł max .) J=1	(min),	(2.26)
n i I ^au--j < ^hi	(i = 1,2, ...,m),	(2.27)
i
1 " I a,jXj > b,	(i = m + 1,...,/;),	(2.28)
^J'^=1
I t oijX) = 6,.	(i = P + 1.-.''J.	(2.29)
i-1
X] ^ 0 gdzie n, ^ n.	(/= 1.2.....«,),	(2.30)

Każdy wektor zmiennych decyzyjnych x = (x,, x,,..., x„) spełniający warunki ograniczające (2.27) —(2.30) nazywamy rozwiązaniem dopuszczalnym zadania PL. Rozwiązanie dopuszczalne, dla którego funkcja celu (2.26) osiąga maksimum (minimum), nazywamy rozwiązaniem optymalnym.

Parametrami w tym zadaniu są c_Jt b_t oraz a_:j (i 1,2,y = 1,2,...,»). Parametr C: nazywamy j-tą wagą funkcji celu, parametr b_t — i-tym wyrazem wolnym, a parametr a_;j- — współczynnikiem macierzy ograniczeń stojącym w i-tym wierszu i /-tej kolumnie.

Ważną rolę przy formułowaniu zadań PL, jak i ich rozwiązywaniu

odgrywają dwie postacie szczególne: tzw. postać standardowa i postać kanoniczna.

Zadaniem PL o postaci standardowej nazywamy zadanie, w którym wszystkie ograniczenia są nierównościami typu < dla zadań na maksimum bądź nierównościami typu > dla zadań na minimum oraz wszystkie zmienne muszą być nieujemne.    /-,._v ,,    /

Zadaniem PL (o postaci kanonicznej nazywamy zadanie, w którym wszystkie warunki ograniczające są równaniami oraz na wszystkie zmienne nałożone są warunki dotyczące ich nieujemności.

Zadaniami PL o postaci standardowej są więc zadania:

n    '•

Z Cj*j J= 1	-> max, ry 7	i"'	V	Z ^ci^xj -*^min> J-1	V '	r) //
II Z ^aU^xJ j= 1	< bf (i =	,2,		Z a„Xj > b, i= i	(i = 1,2,..	■,m),
X W o	(j =	,2,		Xj ź 0	U = 1,2,.	.,«)■ (2.3

Nierówność ^ dla zadania na maksimum oraz nierówność > dla zadania na minimum nazywamy nierównościami typowymi, a samo zadanie będziemy oznaczali: PL(max) lub PL(min).

Zadanie PL o postaci kanonicznej w zapisie macierzowym można przedstawić następująco:

cx -> max (min),

Ax = b,

(2.32)

x Js 0,

gdzie:

«n	o 12 •	• «J»
Oli	22	^2/i	— macierz współczynników
omi	2	^nin

b

wektor wyrazów wolnych,