PWSZ Elbląg |
Data:. 27.II.2003r. |
Ocena |
Badania operacyjne Studia dzienne Wydział: IIS Rok: I Grupa ćwiczeń: III |
Kamil Wietrzyński |
|
- Rozwiązywanie zadań z wykorzystaniem funkcji linprog:
a=11
W moim przypadku funkcja celu wygląda następująco: F(x)= x1 + 11x2.
Z treści zadania wynikają następujące ograniczenia.
x1>=1
x2>=2
7/9x1+x2<=10
1/2x1-x2<=1
Matlab przyjmuje tylko ograniczenia mniejszościowe więc powyższe układy równań należy przekształcić w następujący sposób.
-x1<=-1
-x2<=-2
7/9x1+x2<=10
1/2x1-x2<=1
Następnie układy przedstawiamy w postaci trzech macierzy:
f=[ 1 8];
A=[-1 0;0 -1;7/9 1;1/2 -1];
b=[ -1 -2 10 1]';
I stosujemy funkcje “linprog”:
x = Linprog(f,A,b)
Rozwiązaniem zadania są następujące zmienne decyzyjne:
x =
1.0000
2.0000
Z treści zadania 2 wynikają następujące równania:
a=11
F(x)= 5000x1 + 11000x2
Ponieważ naszym celem jest obliczyć „max” należy pomnożyć funkcje celu * -1
f = [5000 11000]
A = [-1 0;0 -1;1/14 1/7;1/7 1/12;1 1]
b = [0 0 1 1 8]';
x = linprog(-f,A,b)
Przedsiębiorstwo powinno produkować 0 produktów A i 7 produktów B na godzinę aby dochód był maksymalny.
x =
0.0000
7.0000
- Punkty przecięcia ograniczeń
Lp. |
Równania |
Przecięcie w |
Spełnia Ograniczenie |
1 |
-x1<=-1 -x2<=-2 |
1 2 |
Tak |
2 |
-x1<=-1 7/9x1+x2<=10 |
1 9,2222 |
Tak |
3 |
-x1<=-1 1/2x1-x2<=1 |
1 -0,5 |
Nie |
4 |
-x2<=-2 7/9x1+x2<=10 |
10,286 2 |
Nie |
5 |
-x2<=-2 1/2x1-x2<=1 |
6 2 |
Tak |
6 |
7/9x1+x2<=10 1/2x1-x2<=1 |
8,6087 3,3043 |
Tak |
Najlepszym punktem jest x1=1 i x2=2 bo f(1,2)=1+22 jest wartością najmniejszą.
Lp. |
Równania |
Przecięcie w |
Spełnia Ograniczenie |
1 |
-x1 <= 0 -x2 <= 0 |
0 0 |
Tak |
2 |
-x1 <= 0 1/14 x1 + 1/7 x2 <= 1 |
0 7 |
Tak |
3 |
-x1 <= 0 1/7 x1 + 1/12 x2 <= 1 |
0 12 |
Nie |
4 |
-x1 <= 0 x1+x2 <= 8 |
0 8 |
Nie |
5 |
-x2 <= 0 1/14 x1 + 1/7 x2 <= 1 |
14 0 |
Nie |
6 |
-x2 <= 0 1/7 x1 + 1/12 x2 <= 1 |
7 0 |
Tak |
7 |
-x2 <= 0 x1+x2 <= 8 |
8 9 |
Nie |
8 |
1/14 x1 + 1/7 x2 <= 1 1/7 x1 + 1/12 x2 <= 1 |
4,1176 4,9412 |
Nie |
9 |
1/14 x1 + 1/7 x2 <= 1 x1+x2 <= 8 |
2 6 |
Tak |
10 |
1/7 x1 + 1/12 x2 <= 1 x1+x2 <= 8 |
5,6 2,4 |
Tak |
Najlepszym punktem jest x1=0 i x2=7 bo f(0,7)=5000*0+11000*7 jest wartością największą
- Simplex
Algorytm simplex operuje na ograniczeniach przedstawionych w formie jednej macierzy.
f(x)=1x1 + 11x2
7/9x1 + x2 <= 10
1/2x1-x2<=1
x1>=1
x2>=2
Ograniczenia przekształcamy do postaci ax=b dodając lub odejmując dodatkowe zmienne bazowe.
7/9x1 + x2 +x3 = 10
1/2x1 -x2 + x4 =1
x1 - x5=1
x2 - x6=2
Tworzymy macierz
7/9 1 1 0 0 0 10
1/2 -1 0 1 0 0 1
1 0 0 0 -1 0 1
0 1 0 0 0 -1 2
1 11 0 0 0 0 0 <- Funkcja Celu
Dodajemy jeszcze dwie zmienne w celu utworzenia sztucznej bazy
7/9 1 1 0 0 0 0 0 10
1/2 -1 0 1 0 0 0 0 1
1 0 0 0 -1 0 1 0 1
0 1 0 0 0 -1 0 1 2
1 11 0 0 0 0 0 0 0
Z równań sztucznej bazy tworzymy tymczasową funkcję celu = x7+x8
7/9 1 1 0 0 0 0 0 10
1/2 -1 0 1 0 0 0 0 1
1 0 0 0 1 0 1 0 1
0 1 0 0 0 -1 0 1 2
1 8 0 0 0 0 0 0 0
-1 -1 0 0 1 1 0 0 3
W tymczasowej funkcji celu znajdujemy najmniejszą wartość ujemną następnie wybieramy wartość o najmniejszym stosunku odpowiedniej wartości kolumny ostatniej do tej wartości.
7/9 1 1 0 0 0 0 0 10
1/2 -1 0 1 0 0 0 0 1
1 0 0 0 1 0 1 0 1
0 1 0 0 0 -1 0 1 2
1 8 0 0 0 0 0 0 0
-1 -1 0 0 1 1 0 0 3
Według wybranej wartości wykonujemy redukcje metodą Gaussa Jordana.
A=gj_1k(A,[3 1])
Po wykonaniu operacji otrzymujemy następującą macierz;
0 1 1 0 0.77778 0 -0.77778 0 9.2222
0 -1 0 1 0.5 0 -0.5 0 0.5
1 0 0 0 -1 0 1 0 1
0 1 0 0 0 -1 0 1 2
0 8 0 0 1 0 -1 0 -1
0 -1 0 0 0 1 1 0 4
Dalsze operacje na macierzy wykonujemy w taki sam sposób do wyzerowania tymczasowej funkcji celu. W naszym przypadku potrzeba wykonać jeszcze jedną interlacjie.
A=gj_1k(A,[4 2])
Po wykonaniu operacji otrzymujemy następującą macierz;
0 0 1 0 0.77778 1 -0.77778 -1 7.2222
0 0 0 1 0.5 -1 -0.5 1 2.5
1 0 0 0 -1 0 1 0 1
0 1 0 0 0 -1 0 1 2
0 0 0 0 1 8 -1 -8 -17
0 0 0 0 0 0 1 1 6
Tymczasową funkcję celu usuwamy po wyzerowaniu się zmiennych decyzyjnych.
0 0 1 0 0.77778 1 -0.77778 -1 7.2222
0 0 0 1 0.5 -1 -0.5 1 2.5
1 0 0 0 -1 0 1 0 1
0 1 0 0 0 -1 0 1 2
0 0 0 0 1 8 -1 -8 -17
Po wyzerowaniu tymczasowej funkcji celu dalszą interlacje wykonujemy do otrzymania wyników zmiennych. W naszym przypadku wynikiem są odpowiednio liczby x1 = 1 i x2=2
Z zadania 2 wynika:
F(x) = 5000 x1 + 11000 x2
x1 >= 0
x2 >= 0
1/14 x1 + 1/7 x2 <= 1
1/7 x1 + 1/12 x2 <= 1
x1+x2 <= 8
Podobnie jak w zadaniu 1 tworzymy macierz z tą różnicą, że w funkcji celu zmienne mnożymy * (-1) ze względu na to, że liczymy max:
1 0 -1 0 0 0 0 1 0 0
0 1 0 -1 0 0 0 0 1 0
1/14 1/7 0 0 1 0 0 0 0 1
1/7 1/12 0 0 0 1 0 0 0 1
1 1 0 0 0 0 1 0 0 8
-5000 -11000 0 0 0 0 0 0 0 0
-1 -1 1 1 0 0 0 0 0 0
Dalsze operacje na macierzy wykonujemy według tego samego algorytmu co w przykładzie 1 do otrzymania następującej macierzy:
1 0 -1 0 0 0 0 1 0 0
0 1 0.5 0 7 0 0 -0.5 0 7
0 0 0.5 1 7 0 0 -0.5 -1 7
0 0 0.10119 0 -0.58333 1 0 -0.10119 0 0.41667
0 0 0.5 0 -7 0 1 -0.5 0 1
0 0 500 0 77000 0 0 -500 0 77000
Z otrzymanej macierzy wynika, że X1 = 0 i X2 = 7
Wnioski:
Z użyciem funkcji linprog. - Szybka pod względem działania i prosta do zastosowania i przystosowania danych.
Analiza punktów przecięć ograniczeń - Szybsza od „linprog” równie łatwa pod względem obsługi, prosta algorytmicznie.
Simplex - Najszybsza, trudna algorytmicznie, w obsłudze i przystosowaniu danych.