3582316817

PROGRAMOWANIE LINIOWE

Teoretyczne podstawy programowania liniowego

Znaleść maksimum (minimum) funkcji:

/(*l-^x2 ^Xx) = ^c\^x\ +    + - ^+Cx^X»    (2.1.1)

przy założeniu że zmienne xl ₍x2....., xn czynią zadość następującym warunkom:

'a_u*i+ -+«]**» Śhi

(2.1.2)

^a2l^xl ⁺-^+aU^Xx

a_KlXi + ... + ^axtK^Xx źhn

oraz

Xj >0„x₂ > 0,.....x_a >0    (2.1.3)

nazywamy modelem programowania liniowego, w skrócie modelem PL. Stosuje się także oznaczenie ZPL. Zadanie PL (2.1.1)-(2.1.3) wykorzystuje się do modelowania i optymalizacji wielu rzeczywistych problemów decyzyjnych.

Zadanie programowania liniowego jest określone jednoznacznie, gdy znane są wartości wszystkich parametrów występujących we wzorach (2.1.1) i (2.1.2), to znaczy liczby ci, aij oraz bj, dla i=l.....n, j=l.....m.

Ze strukturą modelu PL wiążą się pojęcia: zmienne decyzyjne - zmienne xl,x2.....xn,

decyzja (rozwiązanie) - wektor wartości zmiennych decyzyjnych (xl,x2,...,xn)^eRn,

funkcja celu - funkcja f dana wzorem (2.1.1),

współczynniki funkcji celu - parametry cl,c2,...,cn,

warunki ograniczające - nierówności występujące w układzie (2.1.2),

warunki nieujemności - nierówności (2.1.3) dotyczące znaku wartości zmiennych

decyzyjnych,

kryterium optymalności - wartość funkcji celu f podlegająca maksymalizacji albo minimalizacji, (max albo min).

Jeżeli z treści problemu wynika, że pewien warunek ograniczający ma postać równania: ailxl+...+ainxn=bi

wówczas w układzie (2.1.2) jest on reprezentowany przez parę nierówności: a_lix_l + ...+ a_trlx_n<b_l

-a_nxi~--ą„x„    <-b,

W celu uproszczenia zapisu wzorów (2.1.1), (2.1.2), (2.1.3) wprowadzamy notację macierzową:

	V			V			~^an	^ai2	...		TT
X =	X*		C =	^2		A =	021	^22	... a2n	b =	h
	3_	w rl		_v	wxl		3i	^2	• • • Omn_	mxn	-1 -C)^fc_1

Zgodnie z tymi oznaczeniami zadanie PL ma postać:

1