Wstęp teoretyczny:

Metoda simplex pozwala na wyliczenie maksymalnej wartości funkcji liniowej przy zachowaniu pewnych ograniczeń co do wartości zmiennych i przy założeniu że wszystkie współczynniki są dodatnie a ograniczenia równościowe. W przypadku braku ograniczeń równościowych należy problem sprowadzić do takiej postaci poprzez wprowadzenie dodatkowych zmiennych .

Algorytm simplex znajduje zastosowanie wszędzie tam gdzie występuje problem zmaksymalizowania wydajności procesu przy ograniczonych zasobach.

Treść Programu:
function x=simplex(A,b,nb,zm_bazowe,zm_nbazowe)

%WYWO£ANIE

%simplex(A,b,nb,zm_bazowe,zm_nbazowe)

%A-macierz wspó³czynnikow

%b-liczba zmiennych bazowych

%nb-liczba zmiennych niebazowych

%zm_bazowe-wektor zmiennych bazowych

%zm_nbazowy-wektor zmiennych niebazowych

%ETYKIETY

%1-999 - zminne x

%1000-1999 - zmienne y

%2000-2999 - zmienne z

%zestawy danych

%simplex([0 0 0 0; 4 -1 -3 -2; 5 -2 4 -1; 0 3 2 1],2,3,[2001 2002 ],[1 2 3 ])

%simplex([0 0 0 0 0; 1 -1 -2 0 -2; 3 0 -3 -2 -1; 0 2 1 -3 4],2,4,[2001 2002],[1 2 3 4])

%simplex([0 0 0 0 0; 21 -3 -3 -1 0; 20 -2 -4 0 -1; 0 7 11 0 0],2,4,[2001 2002],[1 2 1001 1002])

%simplex([0 0 0 0 0; 2 -2 1 1 0; 5 -1 -1 0 -1; 0 1 -1 0 0],2,4,[2001 2002],[1 2 1001 1002])

wymiaryA=size(A); %okreœlenie wymiarów macierzy

dlugoscA=wymiaryA(2);

wysokoscA=wymiaryA(1);

for i=2:1:wysokoscA-1 %utworzenie pomocniczej funkcji celu

A(1,:)=A(1,:)+A(i,:);

end

A(1,:)=-A(1,:);

display('Po utworzeniu pomocniczej funkcji celu:')

A

zm_nbazowe

zm_bazowe

%>>wyznaczanie pomocniczej funkcji celu<<

exit=0; % jak exit jest równy 1 to koniec programu

while exit==0 %powtarzaj procedure a¿ do funkcja celu nie bêdzie maksymalna

if czymaksymalna(A,b,nb)==1

display('Funkcja jest maksymalna')

exit=1;

else

display('Wyznaczanie pomocniczej funkcji celu:')

%krok 1

elem_centralny=znajdz_elem_centralny(A);

%zapamiêtanie wiersza i kolumny orginalnej

wie_org=A(elem_centralny(1),:)

kol_org=A(:,elem_centralny(2))

display('Po kroku 1:')

A

zm_nbazowe

zm_bazowe

% zamiana etykiet

pom = zm_bazowe(1,elem_centralny(1)-1);

zm_bazowe(1,elem_centralny(1)-1) = zm_nbazowe(1,elem_centralny(2)-1);

zm_nbazowe(1,elem_centralny(2)-1) = pom;

%krok 2

A(elem_centralny(1),:)=A(elem_centralny(1),:)/(-elem_centralny(3));

display('Po kroku 2:')

A

zm_nbazowe

zm_bazowe

%krok 3

for i=1:1:wysokoscA

if i~=elem_centralny(1)

A(i,:)=A(i,:)+A(elem_centralny(1),:)*kol_org(i);

end

end

display('Po kroku 3:')

A

zm_nbazowe

zm_bazowe

%krok 4

A(:,elem_centralny(2))=kol_org/elem_centralny(3);

display('Po kroku 4:')

A

zm_nbazowe

zm_bazowe

%krok 5

A(elem_centralny(1),elem_centralny(2))=1/elem_centralny(3);

display('Po kroku 5:')

A

zm_nbazowe

zm_bazowe

end

end

%sortowanie

for i=1:1:nb

for i = 1:1:nb-1

if zm_nbazowe(i)>zm_nbazowe (i+1)

pomoc1 = zm_nbazowe(i);

pomoc2 = A(:,i+1);

zm_nbazowe(i) = zm_nbazowe(i+1);

A(:,i+1) = A(:,i+2);

A(:,i+2) = pomoc2;

zm_nbazowe(i+1) = pomoc1;

end

end

end

display('Po sortowaniu:')

A

zm_nbazowe

zm_bazowe

%zamana funkcji celu

A(1,:) = A(wysokoscA, :);

A(1:wysokoscA-1,:)

display('Wyznaczenie funkcji celu:')

%>>jeszcze raz to samo ju¿ dla g³ównej funkcji celu<<

exit=0; % jak exit jest równy 1 to koniec programu

while exit==0 %powtarzaj procedure a¿ do funkcja celu nie bêdzie maksymalna

if czymaksymalna(A,b,nb)==1

display('Funkcja jest maksymalna')

exit=1;

else

%krok 1

elem_centralny=znajdz_elem_centralny(A);

%zapamiêtanie wiersza i kolumny orginalnej

wie_org=A(elem_centralny(1),:)

kol_org=A(:,elem_centralny(2))

display('Po kroku 1:')

A(1:wysokoscA-1,:)

zm_nbazowe

zm_bazowe

% miana etykiet

pom = zm_bazowe(1,elem_centralny(1)-1);

zm_bazowe(1,elem_centralny(1)-1) = zm_nbazowe(1,elem_centralny(2)-1);

zm_nbazowe(1,elem_centralny(2)-1) = pom;

%krok 2

A(elem_centralny(1),:)=A(elem_centralny(1),:)/(-elem_centralny(3));

display('Po kroku 2:')

A(1:wysokoscA-1,:)

zm_nbazowe

zm_bazowe

%krok 3

for i=1:1:wysokoscA

if i~=elem_centralny(1)

A(i,:)=A(i,:)+A(elem_centralny(1),:)*kol_org(i);

end

end

display('Po kroku 3:')

A(1:wysokoscA-1,:)

zm_nbazowe

zm_bazowe

%krok 4

A(:,elem_centralny(2))=kol_org/elem_centralny(3);

display('Po kroku 4:')

A(1:wysokoscA-1,:)

zm_nbazowe

zm_bazowe

%krok 5

A(elem_centralny(1),elem_centralny(2))=1/elem_centralny(3);

display('Po kroku 1:')

A(1:wysokoscA-1,:)

zm_nbazowe

zm_bazowe

display(['Funkcja celu =', A(1,1)])

A(1:wysokoscA-1,:)

zm_bazowe

zm_nbazowe

end

end

display(['Funkcja celu =', num2str(A(1,1))])

display('Koñcowa tabela simplexsowa')

A(1:wysokoscA-1,:)

zm_bazowe

zm_nbazowe

end

------------------------------------------------------------------------

function x=czymaksymalna(A,b,nb)

licznik=0;

for i=1:1:nb-b

if A(1,i+1)>0

licznik=licznik+1;

end

if licznik==0

x=1;

else

x=0;

end

end

end

------------------------------------------------------------------------

function elem_centralny=znajdz_elem_centralny(A)

%elem_centralny(1)-nr wiersza

%elem_centralny(2)-nr kolumny

%elem_centralny(3)-wartosc elemmentu centralnego

wymiaryA=size(A);

dlugoscA=wymiaryA(2);

wysokoscA=wymiaryA(1);

x=zeros(1,3);

elem_centralny=zeros(1,3);

for i=1:1:dlugoscA

if A(1,i)==max(A(1,2:dlugoscA))

for j=1:1:wysokoscA

if A(j,i)==min(A(2:wysokoscA-1,i))

x=[j,i,A(j,i)];

if elem_centralny(1,3)>x(1,3)

elem_centralny=x;

end

end

end

end

end

if elem_centralny(1,3)>=0

display('element centralny jest dodatni lub zerowy')

end

end

Efekt wywołania funkcji simplex dla przykładu czwartego

simplex([0 0 0 0 0; 2 -2 1 1 0; 5 -1 -1 0 -1; 0 1 -1 0 0],2,4,[2001 2002],[1 2 1001 1002])

Po utworzeniu pomocniczej funkcji celu:

A =

-7 3 0 -1 1

2 -2 1 1 0

5 -1 -1 0 -1

0 1 -1 0 0

zm_nbazowe =

1 2 1001 1002

zm_bazowe =

2001 2002

Wyznaczanie pomocniczej funkcji celu:

wie_org =

2 -2 1 1 0

kol_org =

3

-2

-1

1

Po kroku 1:

A =

-7 3 0 -1 1

2 -2 1 1 0

5 -1 -1 0 -1

0 1 -1 0 0

zm_nbazowe =

1 2 1001 1002

zm_bazowe =

2001 2002

Po kroku 2:

A =

-7 3 0 -1 1

1 -1 0.5 0.5 0

5 -1 -1 0 -1

0 1 -1 0 0

zm_nbazowe =

2001 2 1001 1002

zm_bazowe =

1 2002

Po kroku 3:

A =

-4 0 1.5 0.5 1

1 -1 0.5 0.5 0

4 0 -1.5 -0.5 -1

1 0 -0.5 0.5 0

zm_nbazowe =

2001 2 1001 1002

zm_bazowe =

1 2002

Po kroku 4:

A =

-4 -1.5 1.5 0.5 1

1 1 0.5 0.5 0

4 0.5 -1.5 -0.5 -1

1 -0.5 -0.5 0.5 0

zm_nbazowe =

2001 2 1001 1002

zm_bazowe =

1 2002

Po kroku 5:

A =

-4 -1.5 1.5 0.5 1

1 -0.5 0.5 0.5 0

4 0.5 -1.5 -0.5 -1

1 -0.5 -0.5 0.5 0

zm_nbazowe =

2001 2 1001 1002

zm_bazowe =

1 2002

Wyznaczanie pomocniczej funkcji celu:

wie_org =

4 0.5 -1.5 -0.5 -1

kol_org =

1.5

0.5

-1.5

-0.5

Po kroku 1:

A =

-4 -1.5 1.5 0.5 1

1 -0.5 0.5 0.5 0

4 0.5 -1.5 -0.5 -1

1 -0.5 -0.5 0.5 0

zm_nbazowe =

2001 2 1001 1002

zm_bazowe =

1 2002

Po kroku 2:

A =

-4 -1.5 1.5 0.5 1

1 -0.5 0.5 0.5 0

2.6667 0.33333 -1 -0.33333 -0.66667

1 -0.5 -0.5 0.5 0

zm_nbazowe =

2001 2002 1001 1002

zm_bazowe =

1 2

Po kroku 3:

A =

0 -1 0 0 0

2.3333 -0.33333 0 0.33333 -0.33333

2.6667 0.33333 -1 -0.33333 -0.66667

-0.33333 -0.66667 0 0.66667 0.33333

zm_nbazowe =

2001 2002 1001 1002

zm_bazowe =

1 2

Po kroku 4:

A =

0 -1 -1 0 0

2.3333 -0.33333 -0.33333 0.33333 -0.33333

2.6667 0.33333 1 -0.33333 -0.66667

-0.33333 -0.66667 0.33333 0.66667 0.33333

zm_nbazowe =

2001 2002 1001 1002

zm_bazowe =

1 2

Po kroku 5:

A =

0 -1 -1 0 0

2.3333 -0.33333 -0.33333 0.33333 -0.33333

2.6667 0.33333 -0.66667 -0.33333 -0.66667

-0.33333 -0.66667 0.33333 0.66667 0.33333

zm_nbazowe =

2001 2002 1001 1002

zm_bazowe =

1 2

Funkcja jest maksymalna

Po sortowaniu:

A =

0 0 0 -1 -1

2.3333 0.33333 -0.33333 -0.33333 -0.33333

2.6667 -0.33333 -0.66667 0.33333 -0.66667

-0.33333 0.66667 0.33333 -0.66667 0.33333

zm_nbazowe =

1001 1002 2001 2002

zm_bazowe =

1 2

ans =

-0.33333 0.66667 0.33333 -0.66667 0.33333

2.3333 0.33333 -0.33333 -0.33333 -0.33333

2.6667 -0.33333 -0.66667 0.33333 -0.66667

Wyznaczenie funkcji celu:

wie_org =

2.6667 -0.33333 -0.66667 0.33333 -0.66667

kol_org =

0.66667

0.33333

-0.33333

0.66667

Po kroku 1:

ans =

-0.33333 0.66667 0.33333 -0.66667 0.33333

2.3333 0.33333 -0.33333 -0.33333 -0.33333

2.6667 -0.33333 -0.66667 0.33333 -0.66667

zm_nbazowe =

1001 1002 2001 2002

zm_bazowe =

1 2

Po kroku 2:

ans =

-0.33333 0.66667 0.33333 -0.66667 0.33333

2.3333 0.33333 -0.33333 -0.33333 -0.33333

8 -1 -2 1 -2

zm_nbazowe =

2 1002 2001 2002

zm_bazowe =

1 1001

Po kroku 3:

ans =

5 0 -1 0 -1

5 0 -1 0 -1

8 -1 -2 1 -2

zm_nbazowe =

2 1002 2001 2002

zm_bazowe =

1 1001

Po kroku 4:

ans =

5 -2 -1 0 -1

5 -1 -1 0 -1

8 1 -2 1 -2

zm_nbazowe =

2 1002 2001 2002

zm_bazowe =

1 1001

Po kroku 1:

ans =

5 -2 -1 0 -1

5 -1 -1 0 -1

8 -3 -2 1 -2

zm_nbazowe =

2 1002 2001 2002

zm_bazowe =

1 1001

Funkcja jest maksymalna

Funkcja celu =5

Końcowa tabela simplexsowa

ans =

5 -2 -1 0 -1

5 -1 -1 0 -1

8 -3 -2 1 -2

zm_bazowe =

1 1001

zm_nbazowe =

2 1002 2001 2002

>>

Wnioski:

Pomimo że metoda simplex wprowadza szereg udogodnień wyliczaniu wartości maksymalnej zadanej funkcji liniowej to jej realizacja jest nietrywialna, z powodu ciągłej potrzeby spełniania wielu niezbędnych dla prawidłowego funkcjonowania procedury warunków.

W pierwszej części metody wyliczona została pomocnicza funkcja celu, której znajomość jest niezbędna do uzyskania wartości maksymalnej funkcji podstawowej. Następnie tablice simpleksową poddano sortowaniu oraz zamieniono funkcje celu na właściwą, dopiero po tych zabiegach można było przystąpić do wyliczenia właściwej funkcji celu. Jednocześnie po każdorazowym wykonaniu cyklu kroków należało dokonać zamiany etykiet tablicy w celu możliwości prawidłowego odtworzenia wektora bazowego i niebazowego.

Po każdorazowym wykonaniu pięciu kroków metody simplex należało sprawdzić czy spełniony jest warunek stopu czyli czy funkcja celu osiągnęła wartość maksymalną. Możliwy był też przypadek że funkcja nie jest ograniczona co powoduje wzrost funkcji celu do nieskończoności.

Dwa pierwsze przykłady były zadaniami z ograniczeniami równościowymi co pozwalało na zdefiniowanie tablicy simpleksowej jedynie za pomocą zmiennych x i z. Dwa kolejne przykłady są są zadaniami z ograniczeniami większościowymi co wymagało zdefiniowania dodatkowych zmiennych y.

Dodatkowo w przykładzie drugim możliwe jest wyznaczenie dwóch wektorów niebazowych generujących taką samą maksymalną wartość funkcji celu. To który z możliwych wektorów zostanie wyznaczony zależy od metody poszukiwania elementu centralnego. Posiadanie więcej niż jednego wektora optymalnego pozwala np. na zdecydowanie który z dostępnych obecnie surowców jest mniej dostępny(droższy, trudny w przechowywaniu) i wybranie wektora który pozwala na zaoszczędzenie tego surowca.

Zastosowanie metody simplex do rozwiązywania złożonych problemów, gdzie konieczne jest przeprowadzenie wielu iteracji może prowadzić do powstania dużych błędów obliczeniowych, spowodowane jest to poprzez liczne operacje dzielenia wykonywane w trakcie działania procedury.

http://simplex.republika.pl/

Wydział Elektroniki Kierunek AIR	^Nazwa Kursu Metody Numeryczne
	^Temat ćwiczenia Metoda Simplex	^Grupa sr 13:15-15:00	^Ćw. nr 6	^Prowadzący dr inż. Bartosz Jabłoński
^Wykonali: Michał Szymański 163252

---