badania operacyjne, Kamil Wietrzyński, Laboratorium polegało na rowiązaniu 2 zadań dwoma poznanymi metodami (za pomoocą funkcji „linprog” i algorytmu simplex)


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-x
2<=1
x
1>=1
x
2>=2

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

7/9x1 + x2 +x3 = 10
1/2x
1 -x2 + x4 =1
x
1 - x5=1
x
2 - 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

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

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

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



Wyszukiwarka

Podobne podstrony:
Referaty, EKSPERYMENT LABORATORYJNY P, Eksperyment laboratoryjny polega na tym, że badanie odbywa si
Ściągi na prawo rzymskie, RAMKI9, PRAWO W ZNACZENIU PRZEDMIOTOWYM I PODMIOTOWYM Termin „prawo&
BADANIA OPERACYJNE PYT NA EXAM
Metodologia 2, Analiza ? polega na podzieleniu przedmiotu badania na cz??ci sk?adowe i badaniu ka?de
badania operacyjne, pytania do pl odp, Odpowiedz na każde z pytań TAK lub NIE (tam, gdzie to koniecz
badania operacyjne, pytania do pl odp, Odpowiedz na każde z pytań TAK lub NIE (tam, gdzie to koniecz
Badania operacyjne laboratoria studia dzienne
sprawozdanie1, Cyfrowa obróbka sygnału polega na wykonywaniu operacji matematycznych na kolejnych pr
Badania Operacyjne II - zadania na kolokwium, Badnia Operacyjne II
Systemy Operacyjne - mini1, Funkcje systemu operacyjnego polegają na rozwiązywaniu konfliktów podcza
Godziny rozpoczęcia laboratoriów z Badań operacyjnych, Badania operacyjne
Badanie właściwości termicznych tworzyw sztucznych za pomocą metody Martensa polega na określeniu te
Badanie właściwości termicznych tworzyw sztucznych za pomocą metody Martensa polega na określeniu te
badania operacyjne pytaina na kolokwium1 ZMXZRAW5MSEI3FCIB7PZZJHXAXM276RGEDYJZFI
Badania operacyjne wyklad 2 id Nieznany
badania operacyjne 3 id 76767 Nieznany (2)
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Lab 1 Analiza wrazliwosci, Materiały AGH- zarządzanie finansami, badania operacyjne
Program zajęć ED, aaa, studia 22.10.2014, Materiały od Piotra cukrownika, materialy Kamil, Szkoła, L

więcej podobnych podstron