Badania operacyjne - Laboratorium SD sem. II r.a. 2002/03 |
|
Temat: Zadania Optymalizacyjne |
|
Wykonał: Labuda Dawid |
|
Data wykonania ćwiczenia: 25.04.2003 |
Ocena: |
Data oddania sprawozdania: 10.05.2003 |
|
Zadanie 1
dana jest funkcja celu
f(x)=x1+ax2
x1 ≥ 1
x2 ≥ 2
7/9x1+ x2 ≤ 10
1/2x1- x2 ≤ 1
wyznaczyć wartości zmiennych stanu (x1, x2) dla których funkcja celu osiąga minimum.
a)rozwiązanie za pomocą funkcji
W moim przypadku a=7, wiec funkcja celu ma następującą postać:
f(x)=x1+7x2
Ponieważ funkcja linprog przyjmuje tylko nierówności, w których występują tylko znaki mniejszości dwie pierwsze nierówności należy przemnożyć przez -1, a więc otrzymujemy następujący układ nierówności:
x1 ≤ 1
x2 ≤ 2
7/9x1+ x2 ≤ 10
1/2x1- x2 ≤ 1
Z funkcji celu tworzymy następującą macierz:
f=[1 7]
Z wartości stojących przy zmiennych tworzymy następna macierz:
A=[-1 0
0 -1
7/9 1
1/2 -1]
Z wyrazów wolnych tworzymy trzecią macierz:
b= [-1 -2 10 1]
Następnie wykorzystujemy funkcje linprog jako jej argumenty wstawiamy podane macierze:
x=linprog (f,A,b)
Otrzymujemy następujący wynik:
x =
1.0000
2.0000
b) Przez wybór najlepszego rozwiązania
Metoda ta polega na rozwiązywaniu wszystkich możliwych par nierówności, a następnie sprawdzenie czy dane rozwiązanie spełnia wszystkie ograniczenia, po czym wybranie najlepszego rozwiązania z tych, które spełniają ograniczenia. Wyboru dokonujemy podstawiając wyniki do funkcji celu, a następnie wybieramy w zależności od tego czy szukamy minimum czy maksimum najmniejsze lub największe rozwiązanie.
Bierzemy pierwszą i drugą nierówność i z wartości stojących przy niewiadomych tworzymy następującą macierz A:
A=[-1 0
0 -1]
a z wyrazów wolnych następujący wektor b:
b=[1
-2]
Następnie tworzymy z nich w następujący sposób macierz Ab:
Ab=[A b]
Stosujemy skrypt gj (rozwiązuje on nierówność metodą iteracji Gausa-Jordana):
gj(Ab)
Otrzymany wynik:
1 0 1
0 1 2
Wpisujemy do tabeli.
Następnie powyższe operacje wykonujemy dla pozostałych par nierówności (1 3,1 4, 2 3,2 4,3 4).
Lp. |
Równania |
Rozwiązanie |
Spełnia nierówności? |
1 |
-x1≤-1 -x2≤-2 |
x1=1 x2=2 |
TAK |
2 |
-x1≤-1 7/9 x1+x2≤10 |
x1=1 x2=9,222 |
TAK |
3 |
-x1≤-1 7/9x1-x2≤1 |
x1=1 x2=-0,5 |
NIE |
4 |
-x2≤-2 7/9 x1+x2≤10 |
x1=10,2857 x2=2 |
NIE |
5 |
-x2≤-2 1/2x1-x2≤1 |
x1=6 x2=2 |
TAK |
6 |
7/9x1+x2≤10 1/2x1-x2≤1 |
x1=8,6087 x2=3,3043 |
TAK |
f(x)=1+7*2 f(x)=15
f(x)=1+7*9.222 f(x)=19.444
f(x)=6+7*2 f(x)=20
f(x)=8,6087+7*3,3043 f(x)=31.7388
Z powyższej tabeli widać że minimum tej funkcji znajduje się w punkcie x1=1 x2=2, bo dla funkcji celu f(x)=x1+7x2 funkcja osiąga najmniejszą wartość dla tego rozwiązania.
c)Metoda SIMPLEX
Do tej metody trzeba odpowiednio przygotować funkcje celu, oraz ograniczenia, ponieważ żeby algorytm działał ograniczenia musza być w postaci równań a nie nierówności, dokonuje się tego poprzez wprowadzenie dodatkowych zmiennych. Poza tym wyrazy wolne muszą być nie ujemne. W przypadku gdy dodatkowa zmienna jest ujemna wprowadza się jeszcze jedną zmienna, jednak wymaga to wprowadzenia sztucznej bazy.
Dla naszych ograniczeń wygląda to następująco:
x1 ≤ 1 od x1 należy odjąć dodatkowa zmienna by x1 było równe jedynce, a więc:
x1-x3=1
x2 ≤ 2 podobnie postępujemy dla drugiego ograniczenia, a więc:
x2-x4=2
7/9x1+ x2 ≤ 10
1/2x1- x2 ≤ 1 dwóch ostatnich ograniczeń należy dodać dodatkowe zmienne otrzymujemy wiec:
7/9x1+x2+x5=10
1/2x2-x2+x6=1
Ponieważ dodatkowe zmienne dla dwóch pierwszych ograniczeń są ujemne należy dodać dodatkowe zmienne, w wyniku czego otrzymujemy:
x1-x3+x7=1
x2-x4+x8=2
7/9x1+x2+x5=10
1/2x2-x2+x6=1
Jednak musimy teraz utworzyć bazę zastępczą wykonujemy to wyznaczając x7 i x8 z dwóch pierwszych równań i dodając je do siebie.
x7=1-x1+x3
x8=2-x2+x4
Nasza baza wygląda wtedy następująco:
T=3-x1-x2+ x3+x4
Tak przygotowane równania wpisujemy do tabeli:
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
bi/aij aij>0
|
1 |
1 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
=1/1 |
|
2 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
------ |
|
2 |
10 |
7/9 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
=2/0,7777 |
|
4 |
1 |
½ |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
------ |
|
f= |
0 |
1 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
------ |
|
T |
3 |
-1 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
------- |
Następnie należy wyszukać w bazie zastępczej element o największej wartości bezwzględnej, w naszym wypadku jest to -1. Następnie w kolumnie w której znajduje się ten element szukamy takiej wartości większej od zera ,takiej aby po podzieleniu wyrazu wolnego przez nią otrzymać możliwie najmniejszą wartość. Tak wybrany element jest naszym elementem głównym. Następnie tworzymy macierz A składającą się z kolumn tabeli od b do 8, a wiec:
A=[1 1 0 -1 0 0 0 1 0
2 0 1 0 -1 0 0 0 1
10 7/9 1 0 0 1 0 0 0
1 1/2 -1 0 0 0 1 0 0
0 1 7 0 0 0 0 0 0
3 -1 -1 1 1 0 0 0 0 ]
A następnie redukujemy ją względem elementu głównego za pomocą skrypty gj_1k podając jako argumenty naszą macierz i pozycje elementu głównego w postaci wektora:
A=gj_1k(A,[1;2])
Wynik zapisujemy do tabeli:
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
bi/aij aij>0
|
2 |
1 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
Usunięcie rozw.baz x7 |
0 |
|
|
2 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
|
1 |
=2/1 |
|
2 |
9.22 |
0 |
1 |
0.778 |
0 |
1 |
0 |
|
0 |
=9.22/1 |
|
4 |
0.5 |
0 |
-1 |
0.5 |
0 |
0 |
1 |
|
0 |
|
|
f= |
-1 |
0 |
7 |
1 |
0 |
0 |
0 |
|
0 |
|
|
T |
4 |
0 |
-1 |
0 |
0 |
0 |
0 |
|
0 |
|
Z tabeli usunęliśmy rozwiniecie bazy x7, gdyż nie jest ono nam już potrzebne.
W podobny sposób jak poprzednio wybieramy następny element główny w tym przypadku jest to element 2,3. Uruchamiamy skrypt ponownie z nowym elementem głównym:
A=gj_1k(A,[2;3])
Wynik zapisujemy do tabeli:
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
bi/aij aij>0
|
3 |
1 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
Usunięcie rozw.baz x7 |
Usunięcie rozw.baz x8 |
-------- |
|
2 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
|
|
=2/1 |
|
2 |
7.22 |
0 |
0 |
0.778 |
1 |
1 |
0 |
|
|
=9.22/1 |
|
4 |
2.5 |
0 |
0 |
0.5 |
-1 |
0 |
1 |
|
|
------- |
|
f= |
-15 |
0 |
0 |
1 |
7 |
0 |
0 |
|
|
------- |
|
T |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
------- |
Ponieważ wszystkie rozwinięcia już są nie potrzebne można usunąć bazę zastępczą i zacząć zerować funkcje celu:
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
bi/aij aij>0
|
3 |
1 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
Usunięcie rozw.baz x7 |
Usunięcie rozw.baz x8 |
--------- |
|
2 |
2 |
0 |
1 |
0 |
-1 |
0 |
0 |
|
|
-------- |
|
2 |
7.22 |
0 |
0 |
0.778 |
1 |
1 |
0 |
|
|
-------- |
|
4 |
2.5 |
0 |
0 |
0.5 |
-1 |
0 |
1 |
|
|
------- |
|
f= |
-15 |
0 |
0 |
1 |
7 |
0 |
0 |
|
|
-------- |
Jak widać kolumny zatytułowane 1 i 2 są kolumnami jedynkowymi, a więc możemy już odczytać rozwiązanie, którym są wartości b stojące w tym samym wierszu w którym zmienna ma wartość 1. W naszym przypadku jest to x1=1 i x2=2.
d) Wykres
Zadanie 2
Przedsiębiorstwo produkcyjne wytwarza 2 rodzaje produktów A i B, w ciągu godziny może
wyprodukować 14t wyrobu A lub 7t wyrobu B. Posiadany transport pozwala na przewiezienie w ciągu godziny do 7t produktu A lub do 12t produktu B. Urządzenia załadowcze pozwalają załadować nie więcej niż 8t dowolnego z produktów. Przedsiębiorstwo otrzymuje 5000 PLN/t produktu A i a*1000 PLN/t B. Jaką ilość produktów/h przedsiębiorstwo powinno produkować. Założyć że nie istnieje problem sprzedaży produkcji.
a)rozwiązanie za pomocą funkcji
x1/14 + x2/7≤1 - nierówność zapewniająca spełnienie warunku godzinnej produkcji
x1/7+x2/12≤1 - nierówność zapewniająca spełnienie warunku godzinnego transportu
x1+x2≤8 - nierówność spełniająca warunek załadunku
x1≥0 - nierówność zapewniająca niezerową produkcję produktu A -x1≤0 postać dla Matlaba
x2≥0 - nierówność zapewniająca niezerową produkcję produktu B -x2≤0 postać dla Matlaba
f(x)=5000x1+7000x2 - funkcja celu
Z funkcji celu tworzymy następującą macierz:
f=[-5000 -7000] - współczynniki są ujemne, gdyż chcemy znaleźć maksimum, a nie minimum
Z wartości stojących przy zmiennych tworzymy następna macierz:
A=[1/14 1/7
1/7 1/12
1 1
-1 0
0 -1]
Z wyrazów wolnych tworzymy trzecią macierz:
b= [1 1 8 0 0]
Następnie wykorzystujemy funkcje linprog jako jej argumenty wstawiamy podane macierze:
x=linprog (f,A,b)
Otrzymujemy następujący wynik:
x =
2.0000
6.0000
Odp. Firma w ciągu godziny powinna produkować dwie tony produktu A i 6 ton produktu B.
b) Przez wybór najlepszego rozwiązania
Postępujemy tak samo jak w b) zadania pierwszego
Lp. |
Równania |
Rozwiązanie |
Spełnia nierówności? |
1 |
x1/14+x2/7≤1 x1/7+x2/12≤1 |
x1=4,1176 x2=4,9412 |
NIE |
2 |
x1/14+x2/7≤1 x1+x2≤8 |
x1=2 x2=6 |
TAK |
3 |
x1/14+x2/7≤1 -x1≤0 |
x1=0 x2=7 |
TAK |
4 |
x1/14+x2/7≤1 -x2≤0 |
x1=14 x2=0 |
NIE |
5 |
x1/7+x2/12≤1 x1+x2≤8 |
x1=5,6 x2=2,4 |
TAK |
6 |
x1/7+x2/12≤1 -x1≤0 |
x1=0 x2=12 |
NIE |
7 |
x1/7+x2/12≤1 -x2≤0 |
x1=7 x2=0 |
TAK |
8 |
x1+x2≤8 -x1≤0 |
x1=0 x2=8 |
NIE |
9 |
x1+x2≤8 -x2≤0 |
x1=8 x2=0 |
NIE |
10 |
-x1≤0 -x2≤0 |
x1=0 x2=0 |
TAK |
f(x)=5000*2 +7000*6 f(x)=52000
f(x)=5000*0 +7000*7 f(x)=49000
f(x)=5000*5,6 +7000*2,4 f(x)=44800
f(x)=5000*7 +7000*0 f(x)=35000
f(x)=5000*0 +7000*0 f(x)=0
Jak widać najlepszym rozwiązaniem, jest wytwarzać na godzinę dwie tony produktu A i sześć ton produktu B, gdyż wtedy zysk jest największy.
c) Metoda SIMPLEX
Postępujemy podobnie jak w przykładzie pierwszym, z tym, że wartości funkcji celu wpisujemy z przeciwnym znakiem, a więc:
x1/14+x2/7+x3=1
x1/7+x2/12+x4=1
x1+x2+x5=8
-x1+x6=0
-x2+x7=0
-f(x)=-5000x1-7000x2
Nie musimy tutaj wprowadzać bazy zastępczej, gdyż dwa ostatnie warunki wystarczyło przemnożyć przez -1, jest to możliwe gdyż wyrazy wolne są zerowe.
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
bi/aij aij>0
|
1 |
1 |
1 |
1/14 |
1/7 |
1 |
0 |
0 |
0 |
0 |
=1/0.142 |
|
2 |
1 |
1/7 |
1/12 |
0 |
1 |
0 |
0 |
0 |
=1/0.083 |
|
2 |
8 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
=8/1 |
|
4 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
----- |
|
5 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
----- |
|
-f=- |
0 |
-5000 |
-7000 |
0 |
0 |
0 |
0 |
0 |
----- |
A=[1 1/14 1/7 1 0 0 0 0
1 1/7 1/12 0 1 0 0 0
8 1 1 0 0 1 0 0
0 -1 0 0 0 0 1 0
0 0 -1 0 0 0 0 1
0 -5000 -7000 0 0 0 0 0]
A=gj_1k(A,[1 3])
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
bi/aij aij>0
|
2 |
1 |
7 |
½ |
1 |
7 |
0 |
0 |
0 |
0 |
=7/0.5 |
|
2 |
5/12 |
17/168 |
0 |
-7/12 |
1 |
0 |
0 |
0 |
=0.416/0.1 |
|
3 |
1 |
½ |
0 |
-7 |
0 |
1 |
0 |
0 |
=1/0.5 |
|
4 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
----- |
|
5 |
7 |
½ |
0 |
7 |
0 |
0 |
0 |
1 |
7/0.5 |
|
-f=- |
49000 |
-1500 |
0 |
49000 |
0 |
0 |
0 |
0 |
----- |
A=gj_1k(A,[3 2])
krok |
Nr. Ograniczenia f. celu |
b |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
bi/aij aij>0
|
3 |
1 |
6 |
0 |
1 |
14 |
0 |
-1 |
0 |
0 |
|
|
2 |
3/14 |
0 |
0 |
5/6 |
1 |
-17/84 |
0 |
0 |
|
|
3 |
2 |
1 |
0 |
-14 |
0 |
2 |
0 |
0 |
|
|
4 |
2 |
0 |
0 |
-14 |
0 |
2 |
1 |
0 |
|
|
5 |
6 |
0 |
0 |
14 |
0 |
-1 |
0 |
1 |
|
|
-f=- |
52000 |
0 |
0 |
28000 |
0 |
3000 |
0 |
0 |
|
Otczytujemy rozwiązanie i wiemy już, że najlepszym rozwiązaniem jest 2 i 6.
d)Wykres
Wnioski:
Metoda SIMPLEX jest o wiele skuteczniejsza, niż rozwiązywanie kolejnych układów równań i sprawdzanie który z nich pasuje najlepiej. Jedyną jej wadą jest to, iż trzeba odpowiednio przerobić ograniczenia. Jednak wymaga ona o wiele mniejszej liczby iteracji. Na korzyść metody przez wybór przemawia jedynie to, że jest ona bardzo przejrzysta. Oczywiście najszybszym sposobem jest korzystanie ze skryptu takiego jak np. linprog, pozwala ona zaoszczędzić czas.
W instrukcji nr 4 znalazłem błąd przy bazie zastępczej jest T= x7 + x8 =-0.955x1 + 4x2 + x3 + 4x4,
a powinno być T= x7 + x8 =-0.955x1 + 4x2 + x3 + x4.
Wyszukiwarka
Podobne podstrony:
mazurkiewicz,badania operacyjne,Lista zadań z programowania liniowego i całkowitego
Badania operacyjne, bad ope02, Programowanie matematyczne
badania operacyjne, w3 Zagadnienia Dualne Programowania Liniowego
badania operacyjne w3-Zagadnienia Dualne Programowania Liniowego
Badania operacyjne - programowanie liniowe, lista3
Badania operacyjne programowanie liniowe lista3
Badania operacyjne – programowanie liniowe Zadania 1 Dariusz Chalimoniuk UPH
Projekt badania operacyjne- programowanie sieciowe, Badania operacyjne
Badania Operacyjne UW, wykład 3 produkcja-zapasy, Programowanie dynamiczne
badania operacyjne, bo program
opis formatu sprawozdania z BO, Badania operacyjne
Jadczak R - Badania operacyjne Wykład 3, programowanie całkowitoliczbowe
Metoda liniowa - szablon, Nauka, Studia, Notatki, Badania operacyjne
Jadczak R - Badania operacyjne Wykład 2, liniowe modele decyzyjne
Program wykładu, Studia - Materiały, Badania Operacyjne
Badania operacyjne liniowe
Badania operacyjne cwiczenia
więcej podobnych podstron