MO - laboratoria 3

SAVE OFFLINE

16 marzec 2013

Optymalizacja

Slajd 1

Optymalizacja

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 2

Funkcje dostępne w SciLab • linpro()

- funkcja do rozwiązywania zadań programowania liniowego

• quapro()

- funkcja do rozwiązywania zadań programowania liniowego kwadratowego

• karmarker()

- funkcja do rozwiązywania zadań programowania liniowego z wykorzystaniem algorytmu Karmarker’a

• optim()

- funkcja do rozwiązywania nieliniowych zadań optymalizacji

• leastsq()

- funkcja do rozwiązywania nieliniowych zagadnień metodą najmniejszych kwadratów

• lsqrsolve()

- funkcja do minimalizacji sumy kwadratów zagadnień nieliniowych z wykorzystaniem algorytmu Levenberg’a-Marquardt’a

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 3

Plan zajęć • programowanie liniowe i kwadratowe • programowanie liniowe: przykład wyboru asortymentu produkcji • zagadnienie transportowe z wykorzystaniem funkcji linpro() • nieliniowe zadanie optymalizacji z wykorzystaniem funkcji optim() • przykład zagadnienia odwrotnego w oparci o funkcje: leastsq() lub lsqrsolve()

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 4

Ćwiczenie 1

Znajdź minimum funkcji f(x1,x2,x3) = 3x1+5x2-2x3+1, przy następujących ograniczeniach: x1 + 3*x2 funkcja linpro(p,C,b,xL,xU,me): x1 + x2 - x3 minimum dla: 2*x1 - x2 T f(X)= p *X x1 + x2 + x3

= 5 = 2 ≤ 3 ≤ 25

0 ≤ x1 ≤ 5 0 ≤ x2 ≤ 10 0 ≤ x3 ≤ 3

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 5

Ćwiczenie 1-cd

Znajdź minimum funkcji f(x1,x2,x3) = 3x1+5x2-2x3+1, przy następujących ograniczeniach: x1 + 3*x2 funkcja linpro(p,C,b,xL,xU,me): x1 + x2 - x3 minimum dla: 2*x1 - x2 T f(X)= p *X x1 + x2 + x3

= 5 = 2 ≤ 3 ≤ 25

0 ≤ x1 ≤ 5 xL = [0;0;0]; 0 ≤ x2 ≤ 10 xU = [5;10;3]; 0 ≤ x3 ≤ 3 p = [3;5;-2]; b = [5;2;3;25]; C = [1,3,0; 1,1,-1; 2,-1,0; 1,1,1 ]; [xopt,lagr,fopt] = linpro(p,C,b,xL,xU,2) fopt = fopt +1 // xopt = [0.5, 1.5, 0], fopt = 10 Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 6

Ćwiczenie 2 Znajdź minimum funkcji f(x1,x2,x3) = x12+x1x2+3x1+5x2-2x3+1, przy następujących ograniczeniach: x1 + 3*x2 = 5 funkcja quapro(Q,p,C,b,xL,xU,me): x1 + x2 - x3 = 2 minimum dla: 2*x1 - x2 ≤ 3 T T f(X)= 0.5*X *Q*X + p *X x1 + x2 + x3 ≤ 25 0 ≤ x1 ≤ 5 0 ≤ x2 ≤ 10 0 ≤ x3 ≤ 3

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 7

Ćwiczenie 2-cd Znajdź minimum funkcji f(x1,x2,x3) = x12+x1x2+3x1+5x2-2x3+1, przy następujących ograniczeniach: x1 + 3*x2 = 5 funkcja quapro(Q,p,C,b,xL,xU,me): x1 + x2 - x3 = 2 minimum dla: 2*x1 - x2 ≤ 3 T T f(X)= 0.5*X *Q*X + p *X x1 + x2 + x3 ≤ 25 xL = [0;0;0]; 0 ≤ x1 ≤ 5 xU = [5;10;3]; 0 ≤ x2 ≤ 10 Q = [2,1,0; 1,0,0; 0,0,0] 0 ≤ x3 ≤ 3 p = [3;5;-2]; C = [1,3,0; 1,1,-1; 2,-1,0; 1,1,1 ]; b = [5;2;3;25]; [xopt,lagr,fopt] = quapro(Q,p,C,b,xL,xU,2) fopt = fopt +1 // xopt = [0.5, 1.5, 0], fopt = 10.25 Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 8

Ćwiczenie 3 Znajdź najmniejszą wartość funkcji (punkt startowy: (1,1)): f(x,y) = sin(x*y) + cos(x) na obszarze ograniczonym poprzez nierówności: 0 ≤ x ≤ 10, 0 ≤ y ≤ 10

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 9

Ćwiczenie 3-cd Znajdź najmniejszą wartość funkcji (punkt startowy: (1,1)): f(x1,x2) = sin(x1*x2) + cos(x1) na obszarze ograniczonym poprzez nierówności: 0 ≤ x1 ≤ 10, 0 ≤ x2 ≤ 10 function [f,g,ind] = fst(x,ind) // f – minimalizowana funkcja // g – gradient funkcji f endfunction

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 10

Ćwiczenie 3-cd Znajdź najmniejszą wartość funkcji (punkt startowy: (1,1)): f(x1,x2) = sin(x1*x2) + cos(x1) na obszarze ograniczonym poprzez nierówności: 0 ≤ x1 ≤ 10, 0 ≤ x2 ≤ 10 function [f,g,ind] = fst(x,ind) f = sin(x(1)*x(2))+cos(x(1)) g = [0;0] g(1)= x(2)*cos(x(1)*x(2)) - sin(x(1)) g(2)= x(1)*cos(x(1)*x(2)) endfunction [wart,xp] = optim(fst,'b',[0;0],[10;10],[1;1]) // xp=(π,0), wart= -1

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 11

Ćwiczenie 4 Zadanie optymalnego wyboru asortymentu produkcji Niech m=2, (w fabryce wytwarzane są 2 produkty), n=2 (do wytworzenia jednego produktu potrzebne są 2 surowce). – –

do wytworzenia produktu I – 8 jednostek surowca A, 2 jednostki surowca B, do wytworzenia produktu II – 5 jednostek surowca A, 5 jednostek surowca B.

Zysk ze sprzedaży – –

jednostki produktu I - 9 tys. złotych jednostki produktu II -8 tys. złotych

Wielkość dziennej dostawy – –

surowca A – 40 jednostek surowca B – 25 jednostek

Zadanie (X – zbiór rozwiązań dopuszczalnych, warstwicami funkcji f(x) są linie proste 9x1 + 8x2 = const.)

f ( x) = 9 x1 + 8 x2 → x1 ≥ 0,

max

x2 ≥ 0

A : 8 x1 + 5 x2 ≤ 40 B : 2 x1 + 5 x2 ≤ 25 Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 12

Ćwiczenie 4-cd // definicje macierzy c=[-9;-8]; xL=[0;0]; xU=[1e10;1e10]; C=[8,5;2,5]; d=[40;25]; [xopt,lagr,fopt] = linpro(c,C,d,xL,xU,0);

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 13

Ćwiczenie 4-cd // prezentacja graficzna deff('[w]=f(x,y)','w=c(1)*x+c(2)*y') xx = [0:0.5:6]; yy = [0:0.5:6]; zz = feval(xx,yy,f); contour2d(xx,yy,zz,10); deff('[y1]=f1(x)','y1=-8*x/5+40/5') deff('[y2]=f2(x)','y2=(25-2*x)/5') xxx = [0:0.5:6]; yy1 = f1(xxx); yy2 = f2(xxx); plot2d([xxx',xxx'],[yy1',yy2']) //,[-1,-1],'011',' ',[0 0 6 6]) xstring(xopt(1)+0.5,xopt(2)+0.05,'Rozwiazanie') xtitle('Fabryka') Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 14

Ćwiczenie 5 Firma X ma wytwórnie mas bitumicznych w Skwierzynie oraz Gorzowie Wlkp., w których produkuje MMA na budowę drogi S3 odpowiednio 800 ton na dobę oraz 1200 ton na dobę. Firma ma również pięć mniejszych budów w miejscowościach: a, b, c, d, e. 60% dziennej produkcji pozostaję na budowie S3 (Skwierzyna, Gorzów Wlkp.), a pozostałą cześć produkcji MMA (800 ton) przeznacza w proporcjach 30%, 10%, 16%, 28,5%, 15,5% na budowy w miejscowościach a, b, c, d, e. Znając koszt przewozu 1 tony mieszanki (samochód samowyładowczy 4 osiowy) z wytwórni na poszczególne budowy, należy wyznaczyć plan przewozów MMA minimalizując globalne koszty transportu MMA.

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 15

Ćwiczenie 5-cd [x,fval]=linpro(f,A,b,lb,ub) 36x11+37x21+60x12+48x22+75x13+72x23+… 84x14+85x24+54x15+56x25 --> min

x11 x12 x13 x14 x15

∑x1i = 320 ∑x2i = 480

+ + + + +

x21 x22 x23 x24 x25

= = = = =

240 80 128 228 124

xi ≥ 0

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 16

Ćwiczenie 5-cd f = [36;37;60;48;75;72;84;85;54;56]; A = [ 1, 0, 0, 0, 0, 1, 0,

1, 0, 0, 0, 0, 0, 1,

0, 1, 0, 0, 0, 1, 0,

0, 1, 0, 0, 0, 0, 1,

0, 0, 1, 0, 0, 1, 0,

0, 0, 1, 0, 0, 0, 1,

0, 0, 0, 1, 0, 1, 0,

0, 0, 0, 1, 0, 0, 1,

0, 0, 0, 0, 1, 1, 0,

0; 0; 0; 0; 1; 0; 1];

b = [240;80;128;228;124;320;480]; lb = zeros(10,1); ub = ones(10,1)*%inf; [x,fval] = linpro(f,A,b,lb,ub,7) Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

Optymalizacja

16 marzec 2013

Slajd 17

Ćwiczenie 6 // Wyznacz parametr x(1) i x(2) w modelu: function y = yth(t,x) y = x(1)*exp(-x(2)*t) endfunction // dla danych pomiarowych: tm = [0.25;0.50;0.75;1.00;1.25;1.50;1.75;2.00;2.25;2.50]; ym = [0.79;0.59;0.47;0.36;0.29;0.23;0.17;0.15;0.12;0.08]; // tak aby wyniki uzyskane z modelu były dopasowane // do wyników pomiarów, // wykorzystując metodę najmniejszych kwadratów:

Instytut Konstrukcji Budowlanych

� 𝐲𝐲𝐲 𝐭𝐭 𝐢 𝑖

Zakład Komputerowego Wspomagania Projektowania

− 𝐲(𝐢)

𝟐 Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 18

Ćwiczenie 6-cd // wartości początkowe parametrów x0 = [1.5 ; 0.8]; // definicja funkcji fun oraz dfun function e = myfun(x, tm, ym) e = yth(tm, x) - ym endfunction function g = mydfun(x, tm, ym) v = exp(-x(2)*tm) g = [v , -x(1)*tm.*v] endfunction

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 19

Ćwiczenie 6-cd // kilka możliwości wywołania funkcji leastsq // 1-rozwiązanie [f,xopt,gopt] = leastsq(list(myfun,tm,ym),x0) // 2-rozwiązanie [f,xopt,gopt] = leastsq(list(myfun,tm,ym),mydfun,x0) // grafika tt = linspace(0,1.1*max(tm),100)’; yy = yth(tt, xopt); plot2d(tm, ym, style =-2) plot2d(tt, yy, style = 2) legend(["punkty z pomiaru", "punkty dopasowane"]); xtitle("dopasowanie metodą najmniejszych kwadratów") Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 20

Ćwiczenie 6-cd // 3-rozwiązanie [f,xopt,gopt] = leastsq(1,list(myfun,tm,ym),mydfun,x0) // 4-rozwiązanie (algorytm sprzężonych gradientów) [f,xopt,gopt] = leastsq(1,list(myfun,tm,ym),mydfun,x0,"gc") // 5-rozwiązanie (z ograniczeniami) xinf = [-%inf,-%inf]; xsup = [%inf, %inf]; // bez Jakobiana: [f,xopt,gopt] = leastsq(list(myfun,tm,ym),"b",xinf,xsup,x0)

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2

16 marzec 2013

Optymalizacja

Slajd 21

Ćwiczenie 6-cd // z Jakobianem: [f,xopt,gopt] = leastsq(list(myfun,tm,ym),mydfun,"b",xinf,xsup,x0) // 6-rozwiązanie (niestandardowe opcje) // 40 wywołań funkcji, // 8 iteracji oraz // min zmiana długości gradientu: epsg=0.01, // min zmiana funkcji: epsf=0.1 [f,xopt,gopt] = leastsq(1,list(myfun,tm,ym),mydfun,x0,"ar",40,8,0.01, 0.1)

Instytut Konstrukcji Budowlanych

Zakład Komputerowego Wspomagania Projektowania

Metody Obliczeniowe Semestr 2