2999072766

2.4.1. Postać bazowa

Aby zastosowań metodę simpleks, należy zadanie programowania liniowego zadanego w formie klasycznej przedstawić w formie standardowej (kanonicznej). Jak już wiemy, zbiór warunków ograniczających należy przedstawić w formie równań przez dodanie do każdej nierówności zmiennej bilansującej (formuła [2.7]). Nowych zmiennych w zadaniu będzie zatem tyle, ile jest warunków ograniczających. Ponieważ w naszym przykładzie występują dwie zmienne decyzyjne X/ i X2 oraz mamy trzy warunki ograniczające, więc dodamy trzy zmienne bilansujące. Kanoniczna postać naszego zadania przedstawia się następująco:

f(.x„X2,	jc3 , jc4 , jc5 ) = 2x, +3;t2 —> max	[2.24]
2xx + 2x-	Tt- ll H +	[2.25]
xx + 2x2	+ x4 — 8	[2.26]
4jc,	+ xs = 16	[2.27]
xt,x2,x3,	,x4,*5 >0	[2.28]

Dodane do lewych stron nierówności [2.25]-[2.27] zmienne bilansujące x₃, x₄ i X5 określają różnicę lewych i prawych stron nierówności. Możemy zatem zapisać, że zmienne bilansujące przyjmują wartości:

x₃ = 14-2x,-2x₂>0    [2.29]

x₄ = S-_Xl-2x₂>0    [2.30]

x₅ = 16-4jc, >0    [2.31]

Każdy warunek ograniczający [2.25]-[2.27] przyporządkowany jest określonemu surowcowi Sj, S2 i S₃. Wartości x₃, x₄, x₅, zapisane formułami [2.29]-[2.31], określają, jakie ilości surowców Sj, S2 i Sj pozostaną niewykorzystane w przypadku realizacji planu produkcji (x/, *2).

W rozpatrywanym przez nas zadaniu współczynniki funkcji celu [2.24] tworzą wektor współczynników funkcji celu c, współczynniki warunków ograniczających [2.25]-[2.27] wchodzą w skład macierzy współczynników A, prawe strony warunków ograniczających tworzą wektor warunków ograniczających b, zaś zmienne występujące w zadaniu przedstawimy jako wektor zmiennych x.

Wektorowy zapis ogólny kanonicznej postaci zdania PL został przedstawiony formułami [2.11]-[2.13]. W rozpatrywanym zadaniu występuje pięć zmiennych (dwie decyzyjne i trzy bilansujące) oraz trzy warunki ograniczające, tak więc składowe wektorów i elementy macierzy są następujące:

'2	2	1	0	0'		14'
1	2	0	1	0	» b =	8
4	0	0	0	1		^16

[2.32]

x₅

Macierz A utworzona jest ze współczynników podanych w zestawie nierówności [2.25]-[2.27], jej kolumny odpowiadają poszczególnym zmiennym, a wiersze poszczególnym warunkom ograniczającym. Ostatnie trzy kolumny macierzy utworzone

16