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)= x₁ + 11x₂.

Z treści zadania wynikają następujące ograniczenia.

x₁>=1

x₂>=2

7/9x₁+x₂<=10

1/2x₁-x₂<=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.

-x₁<=-1

-x₂<=-2

7/9x₁+x₂<=10

1/2x₁-x₂<=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)= 5000x₁ + 11000x₂

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 x₁=1 i x₂=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 x₁=0 i x₂=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)=1x₁ + 11x₂

7/9x₁ + x₂ <= 10
1/2x1-x₂<=1
x₁>=1
x₂>=2

Ograniczenia przekształcamy do postaci ax=b dodając lub odejmując dodatkowe zmienne bazowe.

7/9x₁ + x₂ +x₃ = 10
1/2x₁ -x₂ + x₄ =1
x₁ - x₅=1
x₂ - x₆=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 x₁ = 1 i x₂=2

Z zadania 2 wynika:

F(x) = 5000 x₁ + 11000 x₂

x₁ >= 0

x₂ >= 0

1/14 x₁ + 1/7 x₂ <= 1

1/7 x₁ + 1/12 x₂ <= 1

x₁+x₂ <= 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 X₁ = 0 i X₂ = 7

• Wnioski:

1. Z użyciem funkcji linprog. - Szybka pod względem działania i prosta do zastosowania i przystosowania danych.

2. Analiza punktów przecięć ograniczeń - Szybsza od „linprog” równie łatwa pod względem obsługi, prosta algorytmicznie.

3. Simplex - Najszybsza, trudna algorytmicznie, w obsłudze i przystosowaniu danych.