SPRAWOZDANIE Z LABORATORIUM Techniki Optymalizacji
Skład grupy: Krzysztof Zielonka Jacek Guzowski

Ćwiczenie II Zadanie programowania liniowego dla ograniczeń mniejszościowych i większościowych DWUFAZOWA METODA SIMPLEKS	Ocena:

1. Wstęp teoretyczny

Celem ćwiczenia było zapoznanie się z zagadnieniem rozwiązywania układów programowania liniowego metodą dwufazową simpleks. Istota tej metody polega na badaniu rozwiązań bazowych, po wcześniejszym wyznaczeniu pomocniczej funkcji celu i przejścia do pierwszej tablicy simpleksowej która spełniać będzie warunek dopuszczalności. Mając rozwiązanie bazowe sprawdzamy, czy jest ono optymalne, czy nie. Jeśli dane rozwiązanie bazowe nie jest optymalne badamy następne rozwiązanie bazowe lepsze lub przynajmniej nie gorsze od poprzedniego, aż do momentu znalezienia rozwiązania optymalnego.

Metoda dwufazowego simpleksu pozwala na wyliczenie takiego wektora zmiennych

decyzyjnych x, należącego do zbioru rozwiązań dopuszczalnych X, dla którego funkcja celu osiąga maksimum (minimum)

Przy ograniczeniach:

1. 
   Zadania testowe

   1. Zadanie PL ograniczone, , jedno rozwiązanie optymalne

• Funkcja celu:

max x₀= 3x₁ + 2x₂

• Postać ograniczeń:

• Wykres ograniczeń:

Rysunek 1: Wykres wykonano w programie Graph

• Algorytm postępowania w celu wyznaczenia rozwiązania optymalnego dwufazową metodą simpleks:

  • Wprowadzenie zmiennych bazowych x₃, x₄, x₅ do nierówności ograniczających:

(KROK1) – Utworzenie pierwszej tablicy simpleksowej. W kolumnie wyrazów wolnych występuje wyraz ujemny, a więc nie ma rozwiązania dopuszczalnego. Potrzebne jest wskazanie pomocniczej funkcji celu, dzięki której wyznaczy się drugą tablicę simpleksową, która być może będzie miała rozwiązanie dopuszczalne dla metody simpleks(„Wskoczy” na jeden z wierzchołków obszaru wskazanego przez ograniczenia).

Wyznaczenie pomocniczej funkcji celu polega na określeniu wiersza w którym występuje ujemny wyraz wolny. Następnie wybiera się zmienną wchodzącą do bazy poprzez wybranie mniejszego współczynnika występującego w wierszu funkcji pomocniczej. Indeks wybranej kolumny wskazuje nam zmienną wchodzącą do bazy. Zmienną wychodzącą z bazy określa wiersz w którym iloraz wyrazu wolnego i wyrazu z kolumny zmiennej wchodzącej, daje najmniejszą wartość.

Tabela 1: Pierwsza tablica simpleksowa

	x0	-x1↑	-x2
x0	0	-3	-2
x3	3000	2	1
x4	2000	0	1
←x5	-9000	-10	-5

(KROK2) – Generowanie nowej tablicy simpleksowej przy pomocy metody eliminacji Gaussa, przy określonym punkcie centralnym.

Tabela 2: Druga tablica simpleksowa

	x0	-x5	-x2↑
x0	2700	-3/10	-1/2
x3	1200	1/5	0
x4	2000	0	1
←x1	900	-1/10	1/2

(KROK3) – W nowej tablicy simpleksowej spełniony jest warunek na istnienie rozwiązania dopuszczalnego.

Jeżeli w pierwszym wierszu tabeli występuje jeden współczynnik mniejszy od zera, to możemy polepszyć rozwiązanie. W przypadku wystąpienia więcej niż jednego współczynnika mniejszego od zera, wybieramy najmniejszy. Indeks kolumny j wskazuje nam x_j wchodzące do bazy. W naszym przypadku x₂.

(KROK4) - Wybieramy zmienną wychodzącą z bazy. Dzielimy wyraz wolny przez tylko dodatnie współczynniki w kolumnie x₂ (2000/1, 900/0,5). Mniejszy stosunek wskazuje nam punkt centralny, czyli dla kolumny x₂ jest to 1/2. Indeks wiersza wskazuje nam wyraz wychodzący z bazy. W naszym przypadku x_1.

(KROK5) – Aktualne rozwiązanie bazowe dopuszczalne wygląda następująco:

= [x₃,x₄,x₁, -x₅, -x₂]^T=[1200, 2000, 900, 0, 0]^T

x₀=2700

(KROK4) – Iteracja 1: Metodą eliminacji Gaussa, wyznaczamy nową tablice simpleksową.

Tabela 3: Trzecia tablica simpleksowa

	x0	-x5↑	-x1
x0	3600	-2/5	1
x3	1200	1/5	0
←x4	200	1/5	-2
x2	1800	-1/5	2

KROK(5) – Aktualne rozwiązanie bazowe dopuszczalne wygląda następująco:

= [x₃, x₄, x₂, -x₅,- x₁]^T=[1200, 200, 1800, 0, 0]^T

x₀=3600

KROK(6) – W wierszu pierwszym występuje przynajmniej jeden współczynnik mniejszy od zera, a wiec możliwe jest polepszenie wyniku, wykonujemy ponownie (KROK2), (KROK3), (KROK4).

KROK(7) – Iteracja 2: Metodą eliminacji Gaussa, wyznaczamy trzecią tablice simpleksową.

Tabela 4: Czwarta tablica simpleksowa

	x0	-x4	-x1↑
x0	4000	2	-3
←x3	1000	-1	2
x5	1000	5	-10
x2	2000	1	1

KROK(8) – Aktualne rozwiązanie bazowe dopuszczalne wygląda następująco:

= [x₃, x₅, x₂, -x₄,- x₁]^T=[1000, 1000, 2000, 0, 0]^T

x₀=4000

KROK(9) – W wierszu pierwszym występuje przynajmniej jeden współczynnik mniejszy od zera, a wiec możliwe jest polepszenie wyniku, wykonujemy ponownie (KROK2), (KROK3), (KROK4).

KROK(10) – Iteracja 3: Metodą eliminacji Gaussa, wyznaczamy trzecią tablice simpleksową.

Tabela 5: Piąta tablica simpleksowa

	x0	-x4	-x3
x0	5500	1/2	3/2
x1	500	-1/2	1/2
x5	6000	0	5
x2	2000	-1	0

KROK(11) – W pierwszym wierszu tabeli nie ma już żadnego współczynnika ujemnego, a więc nie można polepszyć wyniku. Optymalne rozwiązanie wygląda następująco:

= [x₁, x₅, x₂, -x₄, -x₃]^T=[500, 6000, 2000, 0, 0]^T

=5500

• Treść uruchomionego skryptu

lb=zeros(3,1);

f=[-3,-2];

A=[2,1;0,1;-10,-5];

b=[3000;2000;-9000];

options = optimset('LargeScale', 'off', 'simplex', 'on');

[x, fval, exitflag, output, lambda] = linprog(f,A,b,[],[],lb,[],[],options)

• Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

Optimization terminated.

x = 500

2000

fval = -5500

exitflag = 1

output = iterations: 3

algorithm: 'medium scale: simplex'

cgiterations: []

message: 'Optimization terminated.'

constrviolation: 0

firstorderopt: 0

lambda = ineqlin: [3x1 double]

eqlin: [0x1 double]

upper: [2x1 double]

lower: [2x1 double]

1. Zadanie programowania liniowego nie ma rozwiązania. Zbiór pusty

• Funkcja celu:

max x₀= 6x₁ + 5x₂

• Postać ograniczeń:

• Wykres ograniczeń:

Rysunek 2: Wykres wykonano w programie Graph

• Rozwiązanie zadania za pomocą dwufazowej metody simpleks:

  • Wprowadzenie zmiennych bazowych x₃, x₄ do nierówności ograniczającej:

  • Postępujemy zgodnie z algorytmem podanym powyżej i wyznaczamy pierwszą tablicę simpleksową i poszukujemy pomocniczej funkcji celu:

Tabela 6: Pierwsza tablica simpleksowa

	x0	-x1↑	-x2
x0	0	6	-5
x3	-5	-1	-1
←x4	6	3	2

-Brak rozwiązania dopuszczalnego (występuje ujemny współczynnik w kolumnie wyrazów wolnych).

-Metodą eliminacji Gaussa wyznaczamy nową tablicę simpleksową

Tabela 7: Druga tablica simpleksowa

	x0	-x4	-x2↑
x0	12	2	-1
x3	-3	0,33	-0,33
←x1	2	0,33	0,67

Rozwiązanie bazowe dopuszczalne:

x*=[ x₃, x₁,-x₄ ,-x₂ ]^T = [-3;2;0;0]^T

- W kolumnie wyrazów wolnych występuje wyraz ujemny. Ponownie wybrano pomocniczą funkcję celu i wyznaczono zmienne wchodzącą do bazy i wychodzącą z bazy.

Tabela 8: Trzecia tablica simpleksowa

	x0	-x4	-x3
x0	15	2,5	1,5
x2	-2	0,5	0,5
x1	3	0,5	1,5

-Niespełniony warunek dopuszczalności trzeciej tablicy simpleksowej. W kolumnie wyrazów wolnych nadal występuje wartość ujemna.

Brak rozwiązań dopuszczalnych, a więc zbiór rozwiązań optymalnych jest pusty.

• Treść skryptu użytego w programie Matlab

lb=zeros(3,1);

f=[-6,-5];

A=[-1,-1;3,2];

b=[-5,6];

options = optimset('LargeScale', 'off', 'simplex', 'on');

[x, fval, exitflag, output, laubda] = linprog(f,A,b,[],[],lb,[],[],options)

• Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

Exiting: The constraints are overly stringent; no feasible starting point found.

x =

0

3

fval =

-15

exitflag =

-2

output =

iterations: 0

algorithm: 'medium scale: simplex'

cgiterations: []

message: [1x80 char]

constrviolation: 2

firstorderopt: 6

laubda =

ineqlin: [2x1 double]

eqlin: [0x1 double]

upper: [2x1 double]

lower: [2x1 double]

1. Zadanie PL nieograniczone,

• Funkcja celu:

max x₀= x₁ - x₂

• Postać ograniczeń:

• Wykres ograniczeń:

Rysunek 3: Wykres wykonano w programie Graph

• Rozwiązanie zadania za pomocą dwufazowej metody simpleks:

  • Wprowadzenie zmiennych bazowych x₃, x₄ do nierówności ograniczającej:

• Postępujemy zgodnie z algorytmem podanym powyżej wyznaczamy pierwszą tablicę simpleksową i poszukujemy pomocniczej funkcji celu:

Tabela 9: Pierwsza tablica simpleksowa

	x0	x1↑	x2
x0	0	1	-1
x3	1	-1	1
←x4	-3	-2	-1

-W kolumnie wyrazów wolnych występuje współczynnik ujemny => brak rozwiązania dopuszczalnego. Wyznaczono pomocniczą funkcję celu, po to ażeby wyznaczyć nową tablicę simpleksową.

Tabela 10: Druga tablica simpleksowa

	x0	-x4	-x2
x0	1,5	-0,5	1,5
x3	2,5	-0,5	1,5
x1	1,5	-0,5	0,5

– Aktualne rozwiązanie bazowe dopuszczalne wygląda następująco:

= [x₃, x₁, -x₄,- x₂]^T=[2,5 ; 1,5 ; 0, 0]^T

x₀=1,5

- Kryterium dopuszczalności rozwiązania optymalnego nie jest spełnione, wartość y₀₁ = -0,5 <0.

- Polepszenie bazowego rozwiązania dopuszczalnego nie jest również możliwe, gdyż nie jest spełniony warunek dodatniości y_ik.

-Druga tablica simpleksowa wskazuje na brak rozwiązania optymalnego, poprzez ujemne wartości y_ik, dla i=1,2 oraz k=1y_ik=-0.5<0.

• Treść skryptu użytego w programie Matlab

lb=zeros(3,1);

f=[-1,1];

A=[-1,1;-2,-1];

b=[1;-3];

options = optimset('LargeScale', 'off', 'simplex', 'on');

[x, fval, exitflag, output, laubda] =linprog(f,A,b,[],[],lb,[],[],options)

• Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

Exiting: The problem is unbounded; the constraints are not restrictive enough.

x =

1.0e+015 *

5.0000

0

fval =

-5.0000e+015

exitflag =

-3

output =

iterations: 0

algorithm: 'medium scale: simplex'

cgiterations: []

message: [1x78 char]

constrviolation: 0

firstorderopt: 1

laubda =

ineqlin: [2x1 double]

eqlin: [0x1 double]

upper: [2x1 double]

lower: [2x1 double]

1. Zadanie PL,, wymiar n>2

(Źródło: Jacek Stadnicki, „Teoria i praktyka rozwiązywania zadań optymalizacji”)

Mając do dyspozycji trzy stopy aluminium o znanym składzie i cenie jednostkowej, wytworzymy stop wynikowy, zawierający przynajmniej 12% Si, do 1% Mg, co najmniej 2% Cu oraz 0,5% Mn. Koszt stopu wynikowego powinien być jak najmniejszy.

Stop	[%] Zawartość pierwiastka	Cena [PLN/kg]
	Si	Cu
I	20	1,3
II	12	1,1
III	7	4

x_i –ilość stopów, jakie mają zostać zużyte do wytworzenia stopu wynikowego

• Funkcja celu:

min x₀= 36x₁ + 32x₂ + 45x₃

-Funkcja celu wyraża koszt jednostki stopu wynikowego.

• Postać ograniczeń:

-Lewe strony ograniczeń wyrażają ilość stopów składowych, które należy zużyć w celu zapewnienia wymaganego składu stopu wynikowego, a prawe – wymagania co do składu stopu wynikowego.

• Rozwiązanie zadania za pomocą dwufazowej metody simpleks

  • Wprowadzenie zmiennych bazowych x₄, x₅, x₆ do nierówności ograniczającej

-Zadanie składa się z 3 ograniczeń większościowych, a więc zamieniając te nierówności na typ mniejszościowy, po to by móc skorzystać z metody simpleks, w kolumnie wyrazów wolnych znajdą się aż trzy wartości ujemne.

-Algorytm będzie musiał trzy razy przejść przez fazę wyznaczania pomocniczej funkcji celu, do momentu aż w kolumnie wyrazów wolnych nie będzie żadnej ujemnej wartości i rozwiązanie będzie rozwiązaniem dopuszczalnym.

Tabela 11: Pierwsza tablica simpleksowa

	x0	x1	x2↑	x3
x0	0	36	32	45
x4	-12	-20	-12	-7
x5	-2	-1,3	-1,1	-4
x6	1	0,8	1,3	0,25
←x7	-0,5	-0,2	-1,1	-0,5

Tabela 12: Druga tablica simpleksowa

	x0	x1	x7	x3↑
x0	-14,545	30,182	29,091	30,455
x4	-6,545	-17,818	-10,909	1,545
←x5	-1,5	-1,1	-1	-3,5
x6	0,409	0,564	1,182	-0,341
x2	0,455	0,182	-0,909	0,455

Tabela 13: Trzecia tablica simpleksowa

	x0	x1↑	x7	x5
x0	-27,597	20,61	20,39	8,701
←x4	-5,883	-17,332	-10,468	-0,442
x3	0,429	0,314	0,286	-0,286
x6	0,555	0,671	1,279	-0,097
x2	0,26	0,039	-1,039	0,13

-Po wyznaczeniu trzech kolejnych tablic simpleksowych dochodzimy do momentu kiedy mamy tylko jeden współczynnik ujemny w kolumnie wyrazów wolnych, więc kolejna tablica którą otrzymamy będzie decydująca, czy rozwiązanie jest dopuszczalne, czy nie.

Tabela 14: Czwarta tablica simpleksowa

	x0	x4	x7	x5
x0	-34,593	1,189	7,942	8,176
x1	0,339	-0,058	0,604	0,025
x3	0,322	0,018	0,096	-0,294
x6	0,328	0,039	0,874	-0,114
x2	0,247	0,002	-1,062	0,129

–Rozwiązanie jest rozwiązaniem dopuszczalnym, nie da się już go polepszyć, a więc jednocześnie jest rozwiązaniem optymalnym.

-Rozwiązanie optymalne:

= [x₁,x₃,x_6,x₂,x₄,x₇,x₅]^T=[0,339; 0,322; 0,328; 0,247, 0, 0 ,0]^T

= -34,593

-Rozwiązanie można interpretować następująco:

Aby otrzymać stop wynikowy o żądanym składzie, który będzie najtańszy, trzeba zmieszać 0,339 kg stopu I, 0,247 kg stopu II i 0,322 kg stopu III, otrzymamy 0,908 kg stopu wynikowego, który będzie kosztował 34,6zł/kg

• Treść skryptu użytego w programie Maltab

lb=zeros(4,2);

f=[36,32,45];

A=[-20,-12,-7;-1.3,-1.1,-4;0.8,1.3,0.25;-0.2,-1.1,-0.5];

b=[-12,-2,1,-0.5];

options = optimset('LargeScale', 'off', 'simplex', 'on');

[x, fval, exitflag, output ,laubda] = linprog(f,A,b,[],[],lb,[],[],options)

• Wynik otrzymany po wykonaniu funkcji linprog w programie Matlab

Optimization terminated.

x =

0.3394

0.2465

0.3219

fval =

34.5931

exitflag =

1

output =

iterations: 0

algorithm: 'medium scale: simplex'

cgiterations: []

message: 'Optimization terminated.'

constrviolation: 0

firstorderopt: 0

laubda =

ineqlin: [4x1 double]

eqlin: [0x1 double]

upper: [3x1 double]

lower: [3x1 double]

1. Wnioski:

   1. , jedno optymalne rozwiązanie

Zadanie testowe, jest zadaniem dualnym PL ograniczonym z jednym optymalnym rozwiązaniem. Funkcję celu ograniczają 3 funkcje ograniczające. Część wspólna ograniczeń jest przedstawiona na wykresie kolorem szarym. Problem rozwiązano za pomocą dwufazowej metody simpleks, algorytm potrzebował 3 iteracji do otrzymania wartości optymalnej funkcji celu. Wartość optymalna to =5500, dla x₁=500, x₂=2000. Do podpunktu dołączono wynik działania programu Matlab, z użyciem funkcji linprog. Jak widać dla x=[500,2000] mamy fval=-5500(max f(x)=-min [-f(x)], a więc =5500), liczba iteracji to 3, exitflag=1 co oznacza, że algorytm znalazł jedno rozwiązanie optymalne, oraz algorithm: 'medium scale: simplex' mówi, że algorytm opierał się na metodzie simpleks.

1. Zadanie PL, , brak rozwiązań

W przypadku tego zadania, ograniczenia funkcji celu nie mają żadnej części wspólnej przez co zadanie nie ma rozwiązań. Po wyznaczeniu pomocniczej funkcji celu pierwszej tablicy simpleksowej, nowa otrzymana tablica również nie spełniała kryterium dopuszczalności przez to algorytm się zatrzymuje. Dołączony wydruk programu Matlab potwierdza, że zadanie nie ma rozwiązania.

1. Zadanie PL nieograniczone,

Zadanie testowe jest zadaniem PL nieograniczonym. Ograniczenia nie zatrzymują wzrostu wartości funkcji celu. Wynik zwrócony po wykonaniu funkcji linprog przez program Matlab dla tego przypadku, zwrócił informacje o nieograniczonym problemie (‘The problem is unbounded’) i nieskończonej liczbie rozwiązań. Warto zwrócić uwagę również na exitflag, którego wartość równa się -3, co potwierdza powyższą informacje o nieograniczonym zadaniu. Zadanie nie ma rozwiązania optymalnego.

1. Zadanie PL,, wymiar n>2

Funkcja celu ograniczona jest 4 funkcjami ograniczającymi, przy czym trzy z tych ograniczeń są większościowe, a jedno mniejszościowe. Wartość optymalną funkcji celu wynosi , interpretacja funkcji celu i ograniczeń jest podana w rozwiązaniu zadania. Dodatkowo został dołączony wydruk przebiegu algorytmu z programu Matlab.

Literatura:

-Andrzej Cegielski – „Programowanie Matematyczne”

- dr Ewa Szlachcic - Zadania testowe dla programowania liniowego

-Jacek Stadnicki – „Teoria i praktyka rozwiązywania zadań optymalizacji”

-Andrzej P. Wierzbicki, Andrzej Stachurski – „Podstawy optymalizacji”