Programowanie liniowe - metoda simplex

Grzegorz Hoppe

Robert Watras

Algorytm simplex jest algorytmem pozwalającym znaleźć maksimum linowej funkcji celu określonej równaniem

w obszarze ograniczonym liniowymi warunkami:

• podstawowymi:
  

• dodatkowymi
  

Algorytm ten polega na utworzeniu specyficznej macierzy simpleksowej i wykonywaniu na niej określonych operacji, które odpowiadają zmianom argumentów funkcji celu, aż do momentu otrzymania takiej wartości funkcji dla której nie jest już możliwa zmiana argumentów z zyskiem dla wartości.

.

W wykonaniu tego zadania posłużyliśmy się programem napisanym w matlabie, który wykonuje przekształceń macierzy simpleksowej. Przed utworzeniem macierzy simpleksowej doprowadziliśmy równanie funkcji celu i ograniczenia do postaci normalnej ZPL. W naszej macierzy simpleksowej pierwszy wiersz i pierwsza kolumna zawierają liczby będące indeksami przy zmiennych. Oto kod źródłowy programu:

function []=zpl()

a=[0 0 2 4

0 -2.5 1.5 1.5

1 1 -2 -2

3 1.5 -1.5 0.5]

k=3;

r=3;

% 7.Powtarzaj procedure dopóki mozliwe jest okreslenie elementu centralnego.

while (k<=size(a,2))&(r<=size(a,1))

% 1.Okresl element centralny dla kolejnej iteracji

while (k<=size(a,2))&(a(2,k)<=0)

k=k+1;

r=3;

if k<=size(a,2)

while (r<=size(a,1))&(a(r,k)>=0)

r=r+1;

end

end

end

if (k<=size(a,2))&(r<=size(a,1))

%k

%r

%a(r,k)

a1=a;

% 2.Wiersz r-ty podziel przez minus element centralny

for i=2:size(a,2)

a1(r,i)=a(r,i)/(-a(r,k));

end

% 3.Do kazdego i-tego z pozostałych wierszy dodaj wiersz centralny pomnozony przez aik.

for i=2:size(a,1)

if i~=r

for j=2:size(a,2)

a1(i,j)=a1(i,j)+a1(r,j)*a(i,k);

end

end

end

% 4.Oryginalna kolumne k-ta podziel przez element centralny ark

for i=2:size(a,1)

a1(i,k)=a(i,k)/a(r,k);

end

% 5. Element centralny ark zastap jego odwrotnoscia 1/ark

a1(r,k)=1/a(r,k);

% 6. Zamienia zmienne bazowe z niebazowymi

tmp=a1(r,1);

a1(r,1)=a1(1,k);

a1(1,k)=tmp;

a=a1

else

'koniec'

end

end

Zadanie 1.

Znaleźć
dla

przy ograniczeniach:

Po wykonaniu przekształceń algebraicznych otrzymujemy równoważną postać normalną ZPL:

Macierz simpleksowa wygląda wtedy następująco:

		x3
z	9.9	-2.6
x1	3.1	-1.1
x2	0.3	-0.3

Jak widać w macierzy współczynnik przy jedynej zmiennej niebazowej
jest ujemny, czyli nie można określić elementu centralnego. Wynika stąd, że
jest wartością maksymalną funkcji celu i jest ona osiągana dla

Zadanie 2.

Znaleźć
dla

przy ograniczeniach

Postać normalna ZPL:

Macierz simplex

		x2	x4
Z	-2.5	1.5	1.5
x1	1	(-2)	-2
x3	1.5	-1.5	-0.5

Elementem centralnym w tej macierzy jest element znajdujący się w kolumnie zmiennej niebazowej
(wartość przy tej zmiennej jest dodatnia) o wartości równej -2 (bierzemy ujemną wartość z rozpatrywanej kolumny. Przekształcenie macierzy simpleksowej wygląda wtedy następująco:

		x1	x4
Z	-1.75=-2.5+0.5*1.5	-0.75=1.5/(-2)	0=1.5+1.5*(-1)
x2	0.5=1/(-2)	-0.5=1/(-2)	-1=2/(-2)
x3	0.75=1.5+0.5*(-1.5)	0.75=-1.5/(-2)	1=-0.5+(-1)*(-1.5)

W otrzymanej macierzy nie ma już dodatnich wartości przy zmiennych niebazowych więc nie przekształcamy jej dalej. Odczytujemy wartość maksymalną funkcji celu
, która jest osiągana dla
.

Zadanie 3.

Znaleźć
dla

przy ograniczeniach:

Macierz simplex

		x1	x2	y1	y2
Z	0	7	11	0	0
z1	21	-3	3	-1	0
z2	20	-2	-4	0	-1
z'	-41	5	1	1	1

Po przekształceniu

		x1	z2	y1	y2
z	55	-5.5	-2.75	0	-2.75
z1	36	-4.5	-0.75	-1	-0.75
x2	5	-0.5	-0.25	0	-0.25
z'	-36	4.5	-0.25	1	0.75

Znalezione maksimum
dla

Zadanie 4.

Znaleźć
dla

przy ograniczeniach:

Macierz simplex

		z1	x2	y1	y2
Z	0	1	-1	0	0
z1	2	-2	1	1	0
z2	5	-1	-1	0	-1
z'	-7	3	0	-1	1

Po przekształceniu

		z1	x2	z2	y2
z	5	0	-2	-1	-1
x1	5	0	-1	-1	-1
y1	8	1	-3	-2	-2
z'	0	1	0	-1	0

Znalezione maksimum
dla

---