Paweł Jakubik, nr indeksu: 214764				       10.10.2011

Laboratorium z Teorii i metod optymalizacji – projekt
Ćw. Programowanie liniowe

Zadanie 1: 
Znaleźć minimum funkcji f(a,b)=3a+b przy ograniczeniach:
2a+b ≥ -1
a+2b ≤ 8
znak a- dowolny, b – nieujemny

Rozwiązanie:
Musimy wstępnie podstawić pod a i b nowe zmienne. a=z1-z2, b=z3. Poszokujemy f(x)=-max f(x)

f(z1,z2,z3)=-3z1+3z2-z3

2z1-2z2+z3 ≥ -1 /*-1
z1-z2+2z3 ≤ 8

Dodajemy dodatkowe zmienne aby otrzymać równość

-2z1+2z2-z3+z4 = 1
z1-z2+2z3+z5 = 8

cb	b	A1	A2	A3	A4	A5
0	1	-2	2	-1	1	0
0	8	1	-1	2	0	1

1. Obliczenia wykonane w programie SIMPLEX:

  




  



I ostateczna tablica dająca wynik:


  



Zgodnie z zależnością min f(x)=-max f(x) otrzymujemy:

min f(a,b)=-4,33


	2. Kolejnym programem z którego będziemy korzystać przy badaniu minimum jest program S4.

Przechodzimy od razu do liczenia minimum funkcji:
 

  





  




  



Otrzymany wynik minimum funkcji:


  




	3. Ostatnim zadaniem jest dokonanie obliczeń za pomocą programu SIM_X. Otrzymujemy w wyniku tabele:


  




Otrzymujemy wynik bez znaku minus w obu przypadkach. Zarówno przy liczeniu bezpośrednio minimum lub w liczeniu maximum. Na podstawie poprzednich obliczeń należy uznać, że wynik przy liczeniu powinien być wzięty ze znakiem minus.
Zadanie 2:
Znaleźć minimum funkcji f(a,b)=4a+2b przy ograniczeniach

2a+b ≥ -2
a+2b ≤ 9
znak a- dowolny, b nieujemny

Rozwiązanie:
Na początku podstawiamy pod a=z1-z2 i pod b=z3. Otrzymujemy

f(z1,z2,z3)=4z1-4z2+2z3

2z1-2z2+z3 ≥ -2 /*-1
z1-z2+2z3 ≤ 9

-2z1+2z2-z3+z4 = 2
z1-z2+2z3+z5 = 9

Poszukujemy f(x)=-max f(x)
f(z1,z2,z3)=-4z1+4z2-2z2

cb	b	A1	A2	A3	A4	A5
0	2	-2	2	-1	1	0
0	9	1	-1	2	0	1

	1. Obliczenia za pomocą programu SIMPLEX:


  




  




Tak więc minimum funkcji, zgodnie z zależnością poprzez zależność min f(x)=-max f(x), f(a,b)=-4

	2. Obliczenia programem S4:


  




  




  



Oraz wynik:

  



Co zgadza się z poprzednim wynikiem

	3. Obliczenia programem SIM_X.


  



Tak jak w poprzednim przypadku wartość należy wziąć ze znakiem minus przy liczeniu minimum funkcji.
Wyniki:

L.p.	Pytanie	simplex	Sim-x	S4
1.	Czy program sam wprowadza zmienne uzupełniające?	N	N	T
2.	Czy program sam wprowadza zmienne sztuczne?	T	T	T
3.	Czy program sam wybiera bazę?	T	T	T
4.	Czy możliwy jest wybór max/min?	N	T	T
5.	Czy możliwe są ograniczenia nierównościowe?	N	N	T
6.	Czy prawe strony są przekształcane w dodatnie?	N	T	T
7.	Czy program czyta dane z pliku?	T	T	N
8.	Czy program zapisuje wyniki do pliku?	N	T	N
9.	Czy możliwy jest wybór nazwy pliku?	N	T	N
10.	Czy możliwa jest edycja danych na bieżąco?	N	T	T
11.	Czy po zakończeniu pracy następuje powrót do edycji danych?	N	T	T
12.	Czy program reaguje na wpisywanie błędnych znaków?	T	T	T
13.	Czy program pokazuje obraz zbioru dopuszczalnego?	N	T	T
14.	Czy pokazane są kolejne przejścia po wierzchołkach bazy (kolejne tablice simpleksów)?	T	T	N

Wnioski:

Programy do obliczania minimum funkcji metodą simplex pozwalają na szybkie dokonanie obliczeń zadanego zadania.

Podczas korzystania z programów liczących należy, przynajmniej za pierwszym razem, wykonać obliczenia nie tylko jednym programem. Pozwala to na uniknięcie otrzymania niepoprawnego,co do znaku, wyniku jak to jest w przypadku programu SIM-X. Program ten wylicza minimum jak i maksimum funkcji korzystając z tej samej metody. W przypadku minimum obliczenia są dokonywane za pomocą zależności min f(x)=-max f(x), gdzie max f(x) jest podane jako wynik w tablicach simplex.