Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 1
Metody obliczeniowe
" wykład nr 2
 metody rozwiązywania równań nieliniowych
 zadanie optymalizacji
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 2
Postać równania nieliniowego
Równanie nieliniowe jednej zmiennej o ogólnej postaci:
f(x)=0
 rozwiązanie analityczne : znalezienie takiej wartości x0 dla której
f(x0)=0
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 3
Postać równania nieliniowego
Równanie nieliniowe jednej zmiennej o ogólnej postaci:
f(x)=0
 rozwiązanie analityczne : znalezienie takiej wartości x0 dla której
f(x0)=0
 rozwiązanie przybli\
one :
" skomplikowana postać funkcji f(x)=0 uniemo\
liwia znalezienie
rozwiązania analitycznego (dokładnego)
" 2 etapy:
 lokalizacja pierwiastków odosobnionych (określenie tzw. przedziałów izolacji w
których znajdują się pojedyncze pierwiastki)
 znajdywanie z zadaną dokładnością pierwiastków metodami przybli\
onymi
(iteracyjnymi)
1.5
1
0.5
0
-0.5
-1
przedział
izolacji
-1.5
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 4
Równanie nieliniowe
Metody przybli\
one rozwiązań  metody iteracyjne:
 startują z przybli\
enia początkowego x(0)
 polegają na konstrukcji nieskończonego ciągu rozwiązań
przybli\
onych, zbie\
nych do szukanego rozwiązania,
x(0) x(1) x(2) ...



 przerywane w momencie osiągnięcia \
ądanej dokładności
|f (x(i))|< �
�
�
�
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 5
Równanie nieliniowe
Dana jest funkcjaf(x), oraz przedział [a,b]
4
0 funkcja f(x) = 1/x - nie ciągłoś ć funkcji w 0
-2 -1 0 1 2 3 4 5
-0,5 3
25
20
-1
2
15
-1,5
1
10
-2
0
5
-2 -1 0 1 2 3 4 5
-2,5
0
-1
-4 -3 -2 -1 0 1 2 3 4
-5
-3
-2
-10
-3,5
-3
-15
-4
-4
-20
-4,5 -25
-5
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 6
Równanie nieliniowe
Dana jest funkcjaf(x), oraz przedział [a,b]
4
0 funkcja f(x) = 1/x - nie ciągłoś ć funkcji w 0
-2 -1 0 1 2 3 4 5
-0,5 3
25
20
-1
2
15
-1,5
1
10
-2
0
5
-2 -1 0 1 2 3 4 5
-2,5
0
-1
-4 -3 -2 -1 0 1 2 3 4
-5
-3
-2
-10
-3,5
-3
-15
-4
-4
-20
-4,5 -25
-5
Funkcja f(x)
 jest ciągła na przedziale [a,b]
 spełnia warunek f(a)�f(b)< 0
 posiada w przedziale [a,b] tylko jeden pierwiastek x0 równania f(x)=0
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 7
Równanie nieliniowe  metody rozwiązań
" Metoda bisekcji (pierwsza iteracja)
f (b)
f (x)
b
a
1
x = (a + b)
2
f (a)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 8
Metoda bisekcji
" i  ty krok iteracji
f bi -1
( )
f (xi)
ai -1 = ai bi -1
bi
1
xi = (ai-1 + bi-1)
2
f ai -1
( )
bi = xi
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 9
Metoda bisekcji
x = (a + b)/2
while abs(f(x)) >= eps
w i-tym kroku metody:
if f(a)*f(x) < 0
 znajdujemy środek przedziału b = x
ai-1 + bi-1
else
xi = ;
2
a = x
end
 jeśli |f(xi)|< � �!
�
�
�
x = (a + b)/2
znalez
liśmy pierwiastek = xi
 w przeciwnym razie (gdy |f(xi)| e" �)
e" �
e" �
e" �
end
wyznaczamy nowy przedział do podziału
[ai -1, xi ] gdy f (ai -1)f (xi )< 0
ńł
[ai , bi ]=
�ł
[xi , bi -1] gdy f (ai -1)f (xi ) > 0
ół
 powtarzamy procedurę podziału
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 10
Metoda bisekcji
Własności metody
" prosta idea metody
" metoda jest zawsze zbie\
na
 kontynuując podziały odpowiednio długo otrzymamy ZAWSZE
wynik z \
ądaną dokładnością
" szybkość metody nie zale\
y od postaci funkcji f
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 11
Metoda bisekcji
Własności metody
" prosta idea metody
" metoda jest zawsze zbie\
na
 kontynuując podziały odpowiednio długo otrzymamy ZAWSZE
wynik z \
ądaną dokładnością
" szybkość metody nie zale\
y od postaci funkcji f
" wady
 metoda wolno zbie\
na (jedną cyfrę dziesiętną zyskuje się średnio
w 3,3 krokach)
" stosowana często do przybli\
eń początkowych
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 12
Regula falsi
(regula - linia, falsus - fałszywy )
1) przez punkty(a,f(a))i (b,f(b))
f (b) - f (a)
prowadzimy cięciwę o równaniu: y - f (a) = (x - a)
b - a
2) przybli\
eniem pierwiastka jest punkt
przecięcia tej cięciwy z osią OX
y
y=f(x)
3) jeśli f(x1)=0(lub |f(x1)|< � to
�)
�
�
x1 jest szukanym pierwiastkiem
4) jeśli f(a)f(x1)<0to przyjmujemy b=x1,
x3
w przeciwnym przypadku a=x1 x
powracamy do punktu 1)
a x2 x1 b
Zadanie: zapisz kod programu realizujący metodę, pokazujący oszacowanie błędu
(wykonaj obliczenia dla przykładu  slajd 26)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 13
Regula falsi
f (xi )- f (x0)(x - xi)
zało\
enia dodatkowe
f (xi+1) - f (xi ) =
i+1
xi - x0
 funkcja jest klasy
f (xi)- f (x0)(x - xi)
C2[a,b]
�! - f (xi ) =
i+1
xi - x0
 pierwsza i druga
f x1
( )
pochodna f mają
f x2
( )
stały znak
f x3
( )
metoda ma stały punkt
iteracji (ff  >0) x3
x0 x2 x1
f x0
( )
f x0 f " x0 > 0
( ) ( )
x0 = a, x1 = b
f (xi )
xi+1 = xi -
i
xi+1 - xi
f (xi )- f (x0)(x - x0)
| x - xi+1 |H" f (xi+1)
f (xi+1)- f (xi )
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 14
Regula falsi
przy dodatkowych zało\
eniach otrzymujemy jeden z mo\
liwych przypadków:
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 15
Regula falsi
Własności metody
 w kolejnych punktach wytyczających cięciwę funkcja f
ma ró\
ne znaki
 jest zbie\
na dla funkcji ciągłej na [a,b]jeśli f (x)jest
ograniczona i ró\
na od zera w otoczeniu pierwiastka
 jeśli f  (x) ma stały znak w [a,b]to ten punkt skrajny
w którym ff  >0 jest punktem stałym iteracji
 metoda jest wolno zbie\
na
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 16
Metoda Newtona-Raphsona (stycznych)
" zakładamy dodatkowo i\

f x " C(1) a,b
( )
[ ]
(2)
f (x)" C [a, b]
" dla oszacowania błędu przyjmujemy i\

oraz pierwsza i druga pochodna mają stały znak w [a,b]
 styczną do wykresu funkcji f(x)prowadzimy od końca
przedziału w którym ff  >0
f (xi )- f (x0)(x - xi)
f (xi+1) - f (xi ) =
i+1
xi - x0
f (xi)- f (x0)(x - xi)
�! - f (xi ) =
i+1
xi - x0
- f (xi)= f '(xi)(xi+1 - xi )
f (xi)
xi+1 = xi -
f '(xi)
f (xi)
x - xi H"
f '(xi)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 17
Metoda Newtona-Raphsona (stycznych)
" Przykład braku zbie\
ności
druga pochodna funkcji f zmienia znak,
(cyframi 0,1,...,4 oznaczono kolejne przybli\
enia pierwiastka)
1 3
4 2 0
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 18
Metoda Newtona-Raphsona
Własności metody
 metoda jest zbie\
na warunkowo (lokalne ekstrema, punkty
przegięcia)
Je\
eli
" w pewnym przedziale [a,b],f(a)i f(b)mają przeciwne
znaki,
" f  jest ciągła i nie zmienia znaku na [a,b],
" styczne do krzywej y=f(x)poprowadzone w punktach o
odciętych a i b przecinają oś OX wewnątrz przedziału [a,b]
to równanie f(x)=0ma dokładnie jeden pierwiastek w [a,b]i
metoda Newtona-Raphsona jest zbie\
na do tego pierwiastka dla
dowolnego punktu startowego x0"[a,b]
"
"
"
 jest stosunkowo szybko zbie\
na (jeśli algorytm jest zbie\
ny)
 wymaga tylko jednego punktu startowego
 konieczność obliczania pochodnej funkcji f
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 19
Metoda Newtona-Raphsona
uogólnienie metody (wyprowadzenie z wzoru Taylora)
" Je\
eli pierwiastkiem równania jest �
�, a xi jest jego przybli\
eniem, to
�
�
(� - xi )2 (� - xi )3 (3)
f (�) = 0 = f (xi ) + (� - xi ) f '(xi ) + f ''(xi ) + f (xi ) +L
2! 3!
" zaniedbując wyrazy rzędu większego ni\
p otrzymujemy równanie do
wyznaczenia kolejnego przybli\
enia
 dla p=1 (metoda Newtona-Raphsona stopnia I):
f ( xi )
xi +1 = xi -
= -
= -
= -
0 = f ( xi ) + ( xi +1 - xi ) f' ( xi )
= + -
= + - +
= + -
+
+
+
+
+
f' ( xi )
 dla p=2(metoda Newtona-Raphsona stopnia II):
( xi +1 - xi )2
-
-
-
+
+
+
0 = f ( xi ) + ( xi +1 - xi ) f' ( xi ) + f'' ( xi )
= + - +
= + - +
= + - +
+
+
+
2!
f '(xi ) ą f '(xi )2 - 2 f (xi ) f ''(xi )
xi+1 = xi -
f ''(xi )
Zadanie: zapisz kod programu realizujący metodę Newtona-Raphsona stopnia II
(wykonaj obliczenia dla przykładu  slajd 26)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 20
Metoda siecznych
" pochodna funkcji f(x)jest przybli\
ana ilorazem
ró\
nicowym
" w i-tym kroku prowadzimy sieczną do wykresu funkcji w
punktach o odciętych xi i xi-1 , a jako kolejne przybli\
enie
xi+1 przyjmujemy jej punkt przecięcia z osią OX
" nie jest wymagane aby w punktach wyznaczających kolejną
sieczną funkcja miała ró\
ne znaki (warunek obowiązuje dla
pierwszej stycznej)
(xi - xi-1)
xi+1 = xi - f (xi)
f (xi)- f (xi-1)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 21
Metoda siecznych
Własności metody
 zbie\
ność na ogół szybsza
ni\
dla regula falsi
 gdy |xi-xi-1| jest tego
f x1
( )
samego rzędu co
oszacowanie błędu, następne
f x2
( )
x0
przybli\
enie mo\
e nie być
f x4
( )
poprawne
x1 x3
x2
 gdy początkowe przybli\
enia
x4
nie le\
ą dostatecznie blisko
f x0
( )
pierwiastka, metoda mo\
e
nie być zbie\
na
f x3
( )
 jeśli w trakcie obliczeń
odległości między kolejnymi
przybli\
eniami zaczynają
wzrastać, nale\
y je przerwać
i zawęzić przedział izolacji
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 22
Metoda siecznych
" Przykład braku zbie\
ności
druga pochodna funkcji f zmienia znak
4 5 2
0 1 3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 23
Metoda siecznych - modyfikacje
" metoda Steffensena
 szybciej zbie\
na ni\
metoda siecznych
 wymagająca obliczeń dwóch wartości funkcji f(x)
 nie korzystająca z pochodnych
 dana wzorem :
f (xi ),
xi +1 = xi -
g (xi )
f (xi + f ( xi ))- f ( xi )
g ( xi ) =
f (xi )
Zadanie: zapisz kod programu realizujący metodę (wykonaj
obliczenia dla przykładu  slajd 26)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 24
Metoda iteracji prostej
przypadek zbie\
ny
" Równanie f(x)=0 przekształcamy do
równania równowa\
nego x=�
�(x)
�
�
" pierwsze przybli\
enie obliczamy
x1=�
�(x0), x0-rozwiązanie początkowe
�
�
" kolejne przybli\
enia obliczamy
xk=�
�(xk-1)
�
�
" problemy
 jak znalez
ć funkcję �
�?
�
�
 przy jakich warunkach ciąg rozwiązań jest
zbie\
ny? przypadek rozbie\
ny
jeśli istnieje q takie, \
e
|� (x)|d" q <1 x"
� d" "
� d" "[a,b]
� d" "
to proces iteracji prostej jest zbie\
ny niezale\
nie
od przybli\
enia początkowego x0"[a,b].
"
"
"
Przykład
f(x)=x+ln(x) �! �(x)=-ln(x)
�
�
�
xk= -ln(xk-1)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 25
Rząd metod przybli\
onego obliczania pierwiastków
Metoda jest rzędu p (ma wykładnik zbie\
ności równy p)
je\
eli istnieje stała Ktaka, \
e dla dwu kolejnych przybli\
eń
xi i xi+1 zachodzi nierówność
| xi+1- ą | d" K |xi - ą |p
Metoda Rząd
bisekcji 1
regula falsi 1
Netona 2
siecznych H" 1,62
H"
H"
H"
Steffensena 2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 26
Przykład  porównanie zbie\
ności metod
" Szukamy dodatniego pierwiastka
" przedziałem izolacji mo\
e być [1,2]
równania
" obie pochodne są w tym przedziale
f (x) = x3 + x2 - 3x - 3 = 0
dodatnie
" otrzymujemy
f '(x) = 3x2 + 2x - 3
f ''(x) = 6x + 2
30
20
10
0
-4 -3 -2 -1 0 1 2 3 4
-10
-20
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 27
Przykład  porównanie zbie\
ności metod  cd.
30
20
10
0
-4 -3 -2 -1 0 1 2 3 4
-10
-20
Metoda bisekcji Regula falsi Metoda siecznych Metoda Newtona
x f(x) x f(x) x f(x) x f(x) x f(x)
a = 1 -4 a = 1 -4 a = 1 -4
b = 2 3 b = 2 3 b = 2 3 x0 = 2 3 x0 = 1 -4
x1= 1,5 -1,875 x1= 1,57142 -1,36449 x1= 1,57142 -1,36449 x1 = 1,76923 0,36048 x1 = 3 24
x2= 1,75 0,172 x2= 1,70540 -0,24784 x2= 1,70540 -0,24784 x2= 1,73292 0,00823 x2= 2,2 5,88800
x3=1,625 -0,943 x3= 1,72788 -0,03936 x3= 1,73513 0,02920 x3= 1,73205 -0,000008 x3= 1,83015 0,98899
x4= 1,687 -0,409 x4= 1,73240 -0,00615 x4= 1,73199 0,000576 x4= 1,7578 0,24782
x5= 1,719 -0,124 x5= 1,73195 -0,00095
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 28
Układy równań nieliniowych
" równanie nieliniowe f (x)= 0
f1(x1,...., xn)= 0
ńł
f (x)= 0, f = ( f1,..., fn )
" układ równań nieliniowych �ł
�ł
x = (x1,..., xn )
�ł
fn(x1,...., xn)= 0
ół
Metoda Newtona
" dla równania nieliniowego
f (x)= 0 0 = f ( xi ) + ( xi +1 - xi ) f' ( xi )
= + -
= + -
= + -
+
+
+
 xjest zmienną rzeczywistą
" dla układu równań nieliniowych
f (x)= 0, f = ( f1,..., fn )
 xjest wektorem n-wymiarowym
x = (x1,..., xn )
0 = f (x(i)) + (x(i+1) - x(i))J (x(i))
"f1 "f1 "f1
�ł łł
(macierz Jacobiego)
�ł"x "x2 ... "xn śł
1
�ł śł
2
�ł"f "f2 ... "f2 śł
J(x(i))=
�ł śł
"x1 "x2 "xn
�ł śł
... ... ... ...
�ł"fn "fn
"fn śł
�ł ... śł
"x2 "xn �ł
�ł śł
�ł"x1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 29
Układy równań nieliniowych  rozwiązanie w SciLabie
wykorzystanie funkcji fsolve(punkt_startowy, funkcja)
39
35
x - cos (x1 )- 8 = 0 x2 - cos(x1)-8 = y1
2
31
27
x - 2 x1 - x1 2 - 4 = 0 x2 - 2x1 - x12 - 4 = y2
2
23
19
2
0 1 x1 0 0 x1 -1 0 x1 - 8 y1
�ł łł�ł łł �ł łł�ł łł �ł łł �ł łł �ł łł �ł łł 15
+ + cos(�ł + =
11
�ł- 2 1śł�łx2 śł �ł-1 0śł�łx2 śł �ł
0 0śł �łx2 śł) �ł- 4śł �ły2 śł
7
�ł �ł�ł �ł �ł �ł�ł �ł �ł �ł �ł �ł �ł �ł �ł
3
-5 -4 -3 -2 -1 0 1 2 3 4 5
2
aX + bX + c �"cos(X ) + d = Y
x1 0 1 0 0 -1 0 -8 y1
�ł łł �ł łł �ł łł �ł łł �ł łł �ł łł
X = ,d = ,Y =
�łx śł, a = �ł- 2 1śł,b = �ł-1 0śł,c = �ł �ły śł
0 0śł �ł- 4śł
�ł 2�ł �ł �ł �ł �ł �ł �ł �ł �ł �ł 2�ł
function [Y]=fst(X) // w definiowanej funkcji przyjmujemy X=[x1;x2], Y=[y1;y2]
a=[0,1;-2,1]; b=[0,0;-1,0]; c=[-1,0;0,0]; d=[-8;-4];
Y= a*X +b*X^2 + c*cos(X) + d
endfunction
// lub inny sposób:
function [Y]=fst(X)
Y= [X(2)-cos(X(1))-8; X(2)-2*X(1)-X(1)^2-4 ]
endfunction
// u\
ycie funkcji fsolve()  początkowym rozwiązaniem punkt (0,0)
xy1=fsolve([0;0],fst);
// znalezione rozwiązanie: xy1=[ 1.2959523; 8.2713968]
xy2=fsolve([-3;0],fst);
// znalezione rozwiązanie: xy2=[ - 3.0024159; 7.0096695]
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 30
Metody optymalizacji
Metody wyznaczania optymalnych rozwiązań
 rozwiązanie optymalne to rozwiązanie najlepsze ze
względu na przyjęte kryterium
 ró\
ne kryteria prowadzą na ogół do odmiennych
rozwiązań
 kryterium ściśle związane z rozwiązywanym zadaniem
 postać zadania:
" wyznaczenie minimum (maksimum) danej funkcji f(x)
(tzw. funkcji celu),gdzie x=[x1,x2,...,xn] jest
wektorem
" uwzględnienie warunków ograniczających:
 równania Ai(x)= bi dla i=1,...,m
 nierówności Ci(xi)e" ci dla i=1,...,p
e"
e"
e"
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 31
Metody optymalizacji  przykład
Zadanie transportowe
Dana jest sieć mpunktów wytwarzających określony produkt i
wysyłających go do npunktów odbiorczych. Określono
" xij  ilość produktu wysłanego z punktu i-tego
(i=1,...,m) do j-tego (j=1,...,n)
" ai  ilość produktu wytwarzana przez i-ty punkt,
P_1 P_2 P_m
a1 a2 am
" bi  ilość zapotrzebowania na produkt przez j-ty punkt,
" cij  koszt transportu jednostki produktu z punktu i-tego do
punktu j-tego
" łączne zapotrzebowanie jest równe całości produkcji, tzn.
x12
m n
=
"ai "bj
i=1 j=1
Nale\
y znalez
ć takie wartości xij aby całkowity koszt
transportu był jak najmniejszy. Szukamy minimum
O_1 O_2
O_n
m n
b1 b2
wyra\
enia
bn
f (x) = xij
""cij
i=1 j=1
przy warunkach n m
ai = , i =1,...,m; bj = , j =1,...,n
"x "x
ij ij
j=1 i=1
xij e" 0, i =1,...,m; j =1,...,n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 32
Metoda spadku względem współrzędnych
Przykład  minimalizujemy funkcję f(x,y)
1. (x0,y0)  punkt startowy
(x0,y0+k)
2. ustalamy krok k
3. sprawdzamy wartości funkcji w 4 punktach:
(x0,y0+k),(x0,y0-k),(x0+k,y0),(x0-k,y0)
4. je\
eli w jednym z punktów wartość funkcji f(x,y)jest
mniejsza ni\
w punkcie (x0,y0)( jest poło\
ony ni\
ej )
(x0-k,y0) (x0,y0)
to  przenosimy się do niego i powtarzamy procedurę w
(x0+k,y0)
kroku 3.
5. jeśli w punkcie 4. nie znaleziono takiego punktu to
zmniejszamy krok (np. 2-krotnie) i powtarzamy punkt 3.
(x0,y0-k)
" kierunek poszukiwań nie zale\
y od postaci funkcji
" metoda zawodna w przypadku istnienia wielu
minimów lokalnych funkcji
Zadanie: zapisz kod programu realizujący metodę,
przetestować dla f(x1,x2)=-4x12-(2x2+3)2)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 33
Metody gradientowe - sposoby poszukiwania rozwiązań
Metody gradientowe - kierunek poszukiwań wyznaczany w ka\
dym kolejnym kroku
" niech funkcja f(x)(x=[x1,x2,...,xn]jest wektorem) jest klasy C1.
" Gradientem funkcjif(x)nazywamy wektor:
Ć
"f ( x)
�ł łł
" f ( X )
�ł x3
"x1 śł
�ł śł
T
"f ( x)
�ł śł
�ł łł
"f ( x ) "f ( x) "f ( x)
" f ( x ) = L
�ł "x2 = "x1
śł
�ł
Ć
X
"x2 "xn śł
�ł �ł
�ł śł
M
�ł śł
"f ( x)
�ł śł
"xn �ł
�ł
" gradient określa kierunek największego
x1
wzrostu funkcji f(x)
Przykład (obliczenie gradientu):
x2
f(x1,x2)=-(x1-2)2-(x2-3)2
Ć
X
Ć
" f ( X )
"f(x)= [-2(x1-2),-2(x2-3)]T
"
"
"
"f((1,2))=[2,2]T
"
"
"
x1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 34
Metody optymalizacji - sposoby poszukiwania rozwiązań
Metody gradientowe
" Procesy iteracyjne  kolejne przybli\
enie
 xk+1= xk + hk�k
�
�
�
" xk poprzednie przybli\
enie (wektor n-wymiarowy),
" hk długość kroku (liczba rzeczywista),
" �k wektor (n-wymiarowy), określający kierunek poszukiwań.
�
�
�
 jeśli funkcja f(x)(x=[x1,x2,...,xn])ma więcej ni\
jedno minimum
lokalne, otrzymany wynik mo\
e zale\
eć od punktu startowego,
 wybierając ró\
ne punkty startowe, porównując kolejne wartości, mo\
emy
wybrać najlepsze z otrzymanych rozwiązań
 w sytuacjach gdy istnieje wiele minimów lokalnych wykorzystuje się sposoby
dające mo\
liwość wyjścia z optimum lokalnego  rozszerzenie lokalnych
poszukiwań
 zatrzymanie obliczeń
" po zadanej liczbie iteracji, lub po upływie określonego czasu obliczeń,
" gdy wartość f(xk)(lub względna zmiana wartości ) spadnie poni\
ej zadanego
poziomu,
" gdy długość gradientu ||"f(xk)||spadnie poni\
ej zadanego poziomu.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 35
Metody gradientowe - Metoda gradientu prostego
Algorytm obliczeń :
1. Obliczanie w punkcie startowym x0 wartość funkcji
f(x0)oraz jej gradientu g0= g(x0)
2. Wyznaczenie kierunku poszukiwań �
�=-g0
�
�
3. Wzdłu\
kierunku � wykonujemy krok o długości horaz
�
�
�
określamy współrzędne nowego punktu : xi+1=xi+h*�
�
�
�
4. Obliczenie w nowym punkcie wartość funkcji f(xi+1)
oraz gradientu g= g(xi+1), je\
eli krok był pomyślny,
tzn. f(xi+1)< f(xi)to powtarzamy od punktu 2
podstawiając g(gradient) w miejsce g0
5. Je\
eli nie osiągnięto minimum, nale\
y wrócić do
poprzedniego punktu podstawiając :
xi=xi+1-h*�
�
�
�
oraz zmniejszamy krok (np. 2-krotnie) i przechodzimy
do punktu 3.
Zadanie: zapisz kod programu realizujący metodę,
(przyjąć funkcje f, g jako znane  przetestować dla f(x1,x2)=-2x12-(x2-1)2)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 36
Metody gradientowe  Metoda najszybszego spadku
Algorytm obliczeń :
1. Obliczenie w punkcie startowym x0 wartości
funkcji f(x0)oraz jej gradientu g0= g(x0),
przyjmujemy i=0
2. Wyznaczenie kierunku poszukiwań �
�=-gi
�
�
3. Wzdłu\
kierunku � określamy i takie dla której
� 
� 
� 
wartość f(xi-1 +�i i ) osiąga minimum.
� 
� 
� 
Współrzędne nowego punktu
x i = x i-1 +�i i
� 
� 
� 
4. Obliczenie w nowym punkcie wartość funkcji
f(xi+1)oraz gradientu g= g(xi+1), je\
eli
nie osiągnięto minimum, powrót do punktu 2.
Zadanie: zapisz kod programu realizujący metodę
(przyjąć funkcje f, g jako znane  przetestować dla f(x1,x2)=-x12-(2x2-3)4)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 37
Metoda najszybszego spadku - przykład
Znajdujemy minimum funkcji: f(x1,x2)=x12+ x22
Punkt startowy: (x1(1),x2(1))= [1,1]T
Gradient: "f(x1,x2)= [2x1,2x2]T
"
"
"
Szukamy przybli\
enia postaci: x(2)= x(1)+h(1)�(-"
"f(x(1)))
"
"
wielkość h0 - miejsce w którym funkcja f(x1,x2)na wyznaczonym przez gradient kierunku
przyjmuje minimalną wartość):
h0 = minh(f(x(1)-h�"
"f(x(1))))
"
"
Znajdujemy wielkość h0 - definiujemy pomocniczą funkcję H(1)(h), znajdujemy jej minimum
H(1)(h) =f(x(1)-h�"
"f(x(1)))=
"
"
8
7
=f([1,1]T-h�[2,2]T)= f([1-2h,1-2h]T)=
6
5
=(1-2h)2+(1-2h)2 =2(1-2h)2
4
3
2
H(1) (h)=2�2(1-2h)�(-2)= -8(1-2h)
1
1
0
-0.5
H(1) (h)=0 �! h=1/2
�!
�!
�!
-2
x(2)= [1,1]T+1/2�(-[2,2]T)=[0,0]
-2
-1
0
1
2
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 38
Inne (ulepszone) metody gradientowe
metoda sprzę\
onych gradientów
" Kierunki poszukiwań tworzone są tak, aby ka\
dy kolejny był sprzę\
ony do wszystkich
poprzednich. Dwa kierunki �i oraz �j są wzajemnie sprzę\
one względem dodatnio
� �
� �
� �
określonej macierzy A, je\
eli
�iT A �j=0 dla i <> j
� �
� �
� �
" kierunki wzajemnie sprzę\
one są liniowo niezale\
ne.
" tworzenie kierunków sprzę\
onych :
" pierwszy krok: minus gradient : �1=-"
� "
� "f(x1)=-A*x1-b (dobieramy macierz Ai
� "
wektor btak by spełniona była powy\
sza równość)
 minimalizacja f(x)wzdłu\
tego kierunku : z równania (�1)T*[A(x1+�1*�1+b]=0
�
�
�
otrzymujemy wartość �1, następnie określamy punkt x2=x1+ �1*�1
� �
� �
� �
" i-ty krok: nowy kierunek w punkcie xi jest wyznaczany według reguły :
�i =- "f(xi) + �i*�i-1 - współczynnik �i jest tak dobierany aby kierunki �i , �i-1 były
" � �
" � �
" � �
sprzę\
one (punkt xi+1 wyznaczamy minimalizując f(x)wzdłu\
tego kierunku) :
"f (xi )T �""f (xi )
�i =
"f (xi-1)T �""f (xi-1)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 39
Metody optymalizacji globalnej
" Konwencjonalne metody poszukiwania minimum
 startują z obranego punktu początkowego,
 poszukując w jego pobli\
u mniejszej (ni\
poprzednia) wartości funkcji celu, zmierzają
do minimum,
 poszukiwanie takie uzale\
nione jest od obranego punktu startowego i nie zawsze
kończy się w minimum globalnym.
" Algorytmy globalnej optymalizacji
 ukierunkowane są na zwiększenie prawdopodobieństwa osiągnięcia minimum
globalnego,
 wykorzystywane są w tym celu ró\
ne metody stochastyczne, lub algorytmy genetyczne
 nie gwarantują uzyskania rozwiązania optymalnego, jednak prawdopodobieństwo błędu
mo\
na uczynić bardzo małym.
 w metodach optymalizacji globalnej obliczane są wartości funkcji celu dla pewnego
zestawu stochastycznie wybranych punktów - ró\
ne metody to ró\
ne strategie doboru
zestawu punktów,
 skuteczność konkretnej metody zale\
y od właściwości danej funkcji celu, dlatego nie
mo\
na mówić o metodach globalnej optymalizacji ogólnego zastosowania. Metoda i jej
parametry muszą być dopasowane do specyfiki problemu.
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 40
Metody optymalizacji  przy zadanych ograniczeniach
Przykład:
znalez
ć minimum
funkcji
f(x1,x2)=x12+ x22
z warunkiem
Zadanie minimalizacji
2-x1-x2=0
a) ograniczenie równościowe h(x1,x2)=0
b) ograniczenie nierównościowe (aktywne)
g(x1,x2)d"
d"0
d"
d"
c) ograniczenie nierównościowe (nieaktywne)
g(x1,x2)d"
d"0
d"
d"
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 41
Metody optymalizacji - Programowanie liniowe
Programowanie liniowe  funkcja celu f(x)i funkcje ograniczeń są
liniowe
Metoda simplex  jedna z podstawowych metod rozwiązywania zadań
programowania liniowego
Postać zadania programowania liniowego
min{ f (x) = cT x}
min{ f (x) = cT x}
x"X
x"X
X = {x " Rn : Ax = b, x e" 0,b" Rm,m d" n}
X = {x " Rn : Ax d" b, x e" 0,b " Rm,m d" n}
ograniczenie nierównościowe mo\
na sprowadzić do równościowego
wprowadzając pomocniczą zmienną:
" x1 + 2x2 d" 3, x1e" 0, x2e" 0
d" e" e"
d" e" e"
d" e" e"
" wprowadzamy pomocniczą zmienną x3e"0 zapisując
e"
e"
e"
x1 + 2x2 + x3 = 3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 42
Programowanie liniowe
Zadanie optymalnego wyboru asortymentu produkcji
W fabryce wytwarzanych jest m produktów. Ka\
dy produkt wytwarzany jest z nsurowców.
Określono
" xi  ilość wytworzonych jednostek i-tego (i=1,...,m)produktu,
" ai  zysk osiągnięty ze sprzeda\
y i-tego (i=1,...,m)produktu,
" bj  ilość dziennej dostawy jednostek j-tego (j=1,...,n)surowca,
" cij  ilość jednostek j-tego (j=1,...,n)surowca potrzebna do wytworzenia jednostki i-tego
(i=1,...,m)produktu
Nale\
y znalez
ć takie wartości xi aby osiągnięty zysk dzienny był jak największy. Szukamy
maksimum wyra\
enia
m
f (x) = xi
"ai
i=1
przy warunkach
m
xi d" bj , j = 1,...,n
"cij
i=1
xi e" 0, i = 1,...,m;
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 43
Programowanie liniowe  przykład liczbowy
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 potrzeba 8 jednostek surowca A, oraz 2 jednostki surowca B,
 do wytworzenia produktu II potrzeba 5 jednostek surowca A, oraz 5 jednostek surowca B.
Zysk ze sprzeda\
y : (szukamy największego zysku)
 jednostki produktu I - 9 złotych
 jednostki produktu II -8 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) = 9x1 + 8x2 max
x1 e" 0, x2 e" 0
A: 8x1 + 5x2 d" 40
B : 2x1 + 5x2 d" 25
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 44
Programowanie liniowe  przykład liczbowy
Zadanie optymalnego wyboru asortymentu produkcji
Zastąpienie kryteriów nierównościowych kryteriami równościowymi
" wprowadzamy dodatkowe zmienne x3, x4:
A: 8x1 + 5x2 d" 40 8x1 + 5x2 + x3 = 40
�!
B : 2x1 + 5x2 d" 25 2x1 + 5x2 + x4 = 25
x1, x2, x3, x4 e" 0
" zadanie (ograniczenia równościowe) opisujemy układem równań
8 5 1 0 40
�ł łł �ł łł
T
Ax = b :
�ł2 5 0 1śł �"[x1 x2 x3 x4] = �ł25śł
�ł �ł �ł �ł
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 45
Programowanie liniowe  przykład liczbowy
Zadanie optymalnego wyboru asortymentu produkcji
funkcja linpro()
[x, lagr, f] = linpro(p, C, b, ci, cs)
f(X)= pT*X -> minimum
f (x) = 9x1 + 8x2 max
x1
�ł łł
X =
�łx śł
x1 e" 0, x2 e" 0
�ł 2 �ł
A: 8x1 + 5x2 d" 40
x1
�ł łł
f (X ) = - pT * X �! f (X ) = [-9,-8]*
�łx śł
B : 2x1 + 5x2 d" 25
�ł 2 �ł
8 5 x1 40
�ł łł �ł łł �ł łł
C * X d" b �! d"
�ł2 5śł *�ł śł �ł25śł
�ł �ł �łx2 �ł �ł �ł
0 x1 1000
�ł łł �ł łł �ł łł
ci d" X d" cs �! d" d"
�ł0śł �łx śł �ł1000śł
�ł �ł �ł 2 �ł �ł �ł
[x, lagr, f]=-linpro([-9;-8],[8,5;2,5],[40;25],[0;0],[1000;1000])
// x=[2.5;4], f=54.5
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 46
Programowanie kwadratowe  przykład liczbowy
funkcja quapro()
[x, lagr, f] = quapro(Q, p, C, b, ci, cs)
f(X)= 0.5*XT*Q*X + pT*X -> minimum
x1
�ł łł
f (x) = x12 - x1 - x2 min
X =
�łx śł
�ł 2 �ł
x1 e" 0, x2 e" 0
q11 q12 x1 x1
�ł łł �ł łł �ł łł
A: 8x1 + 5x2 d" 40
f (X ) = 0.5*[x1 x2]* * +[p1 p2]*
�łq q22 śł �łx śł �łx śł
B : 2x1 + 5x2 d" 25 �ł 21 �ł �ł 2 �ł �ł 2 �ł
2 0 x1 x1
�ł łł �ł łł �ł łł
f (X ) = 0.5*[x1 x2]* +[-1 -1]*�ł śł
�ł0 0śł *�ł śł
�ł �ł �łx2 �ł �łx2 �ł
8 5 x1 40
�ł łł �ł łł �ł łł
C * X d" b �! d"
�ł2 5śł * �łx śł �ł25śł
�ł �ł �ł 2 �ł �ł �ł
0 x1 1000
�ł łł �ł łł �ł łł
ci d" X d" cs �! d" d"
�ł0śł �łx śł �ł1000śł
�ł �ł �ł 2 �ł �ł �ł
[x,lagr,f]=quapro([2,0;0,0],[-1;-1],[8,5;2,5],[40;25],[0;0],[1000;1000])
// x=[0.3;4.88]; f=-5.09
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 47
Przykład zastosowania funkcji optim()
Znajdz
największą wartość funkcji (punkt startowy: [1,1,1]):
f(x,y,z)=sin(xy)+cos(xz)+sin(y-z)
na obszarze ograniczonym poprzez nierówności:
xe"0,ye"0,ze"0, xd"10,yd"10, zd"10
e" e" e" d" d" d"
e" e" e" d" d" d"
e" e" e" d" d" d"
// zdefiniowanie funkcji SciLaba która będzie optymalizowana:
// zmienne (x1,x2,x3) zapisane zostają w postaci wektora x
// f - zwraca wartość funkcji
// g - zwraca gradient funkcji
// ind - parametr wymagany w funkcji optim()
function [f,g,ind]=fst(x,ind)
f = sin(x(1)*x(2))+cos(x(1)*x(3))+sin(x(2)-x(3))
g = [0;0;0]
g(1)= x(2)*cos(x(1)*x(2))-x(3)*sin(x(1)*x(3))
g(2)= x(1)*cos(x(1)*x(2))+cos(x(2)-x(3))
g(3)= -x(1)*sin(x(1)*x(3))-cos(x(2)-x(3))
endfunction
//u\
ycie optim(fst, [ b ],start,[ograniczenie_dolne,ograniczenie_górne])
// wart optymalna (minimalna)wartość poszukiwanej funkcji,
// xp  punkt (wektor 3 współrzędnych) w którym wartość zostaje obliczona
[wart,xp]=optim(fst,'b',[0;0;0],[10;10;10],[1;1;1])
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 48
Programowanie liniowe - Problem przydziału maszyn
Dany zakład produkcyjny mający m maszyn, wytwarzających n
wyrobów.
Określono
" xij  ilość j-tego (j=1,...,n) produktu wytworzonego na
i-tej (i=1,...,m) maszynie w danym okresie czasu;
" aij  czas potrzebny do wyprodukowania jednostki produktu
j-tego (j=1,...,n) na i-tej (i=1,...,m) maszynie;
" ai  dysponowany czas pracy i-tej (i=1,...,m) maszyny
" bj  ilość produktu j-tego (j=1,...,n), który powinien być
wytworzony;
" cij  koszt wytworzenia jednostki produktu j (j=1,...,n)
na i-tej (i=1,...,m) maszynie;
Nale\
y znalez
ć takie (nieujemne) wartości xij minimalizujący
m n
wskaz
nik jakości (najni\
szy koszt wytworzenia określonej
f (x) = xij
""cij
i=1 j=1
liczby wyrobów)
n
xij d" ai, i = 1,...,m
"aij
przy warunkach j=1
m
"x = bj j = 1,...,n
ij
i=1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 49
Programowanie liniowe
Problem optymalnego mieszania surowców
Określono (mieszając n surowców otrzymujemy m produktów)
" aij  zawartość j-tego (j=1,...,n) składnika w jednostce i-tego
(i=1,...,m) produktu;
" bj  wymagana zawartość j-tego (j=1,...,n) składnika w całości produktów;
" ci  cena jednostki i-tego (i=1,...,m) produktu
Zadanie polega na wyznaczeniu nieujemnych wielkości otrzymanych produktów xi
które minimalizują całkowity koszt
m
f (x) =
"c xi
i
i=1
przy warunkach
m
xi e" bj, j =1,...,n
"aij
i=1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 50
Programowanie liniowe - Zadanie załadunku (plecakowe)
Spośród n ładunków wa\
ących odpowiednio a1, a2, ..., an o
wartościach c1, ...,cn nale\
y załadować na samochód o
dopuszczalnych ładowności b takie, aby łączna ich wartość była jak
największa.
oznaczamy zmienne xi (i=1,...,n):
 1: gdy i-ty ładunek jest załadowany
 0: w przeciwnym przypadku
zadanie przyjmuje postać:
n
f (x) =
"c xi max
i
i=1
n
"a xi d" b
i
i=1
xi "{0,1}, i = 1,..., n
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 51
Programowanie liniowe - Zadanie rozkroju
Zadanie polega na minimalizacji odpadów powstających podczas np. rozkroju arkusza na
części.
arkusz o szerokości w ma być pocięty na wstęgi o szerokościach odpowiednio
b1,b2,...,bm. Mamy wyró\
nionych nsposobów).
Zadanie mo\
na sformułować (wyznaczenie krotności ka\
dego ze sposobów rozkroju, tak
by zmieścić się w tolerancji zapotrzebowań i zminimalizować łączny odpad):
n m
f (x) = xi min, ci = w - bj i = 1,...,n
"ci "sij
i=1 j=1
n
z d" xi d" y j =1,...,m
j "sij j
i=1
xi e" 0, i =1,...,n
gdzie
zj  minimalne, yj  maksymalne zapotrzebowanie na wstęgi o szerokościach bj
ci  odpad powstający w i-tym sposobie rozkroju
sij  (całkowita) liczba wstęg o szerokości bj wyciętych z arkusza w i-tym
sposobie rozkroju
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 52
Programowanie liniowe - Zadanie komiwoja\
era
Komiwoja\
er startując z miasta nr 1 ma odwiedzić
(n-1)miast i wrócić do punktu startu. Nale\
y
ustalić, w jakiej kolejności ma on odwiedzić te
miasta, aby przebyta droga była jak
najkrótsza.
cij  odległość miasta i od miasta j
niech
xij=1 jeśli komiwoja\
er przeje\
d\
a z miasta i
do miasta j, xij=0 w przeciwnym przypadku
Zadanie formułujemy:
1. komiwoja\
er do ka\
dego
n n
f (x) = xij min
""cij miasta tylko raz,
i=1 j=1
n
2. wyje\
d\
a z ka\
dego miasta
(1) = 1, j =1,...,n
"xij
tylko raz,
i=1
n
3. droga komiwoja\
era składa
(2) = 1, i =1,...,n
"xij
j=1
się z jednego cyklu
xij "{0,1}, i = 1,...,n; j = 1,...,n
(3) zi - z + nxij d" n -1, i, j = 2,...,n (i `" j)
j
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 53
MS Excel  rozwiązywanie równań nieliniowych
narzędzie: Szukaj wyniku
1. wpis początkowej wartości do komórki C37
2. wpis formuły która ma przyjąć określoną wartość do
komórki C38
3. wpis do okna Szukaj wyniku określonej wartości którą
ma przyjąć formuła wpisana do komórki C38
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 54
Zadanie transportowe  przykład rozwiązania w MS Excel
2 samochody dostarczają cement na 3 budowy (budowa A, budowa B, budowa C)
zapotrzebowanie cementu:
" budowa A 800 t
" budowa B 600 t
" budowa C 400 t
A
adowność samochodów:
" samochód 1 2 t
" samochód 2 3 t
Ile kursów na poszczególne budowy musiałby wykonać ka\
dy
z pojazdów, wiedząc \
e koszt jednego kursu wynosi 10 zł,
czas dojazdu 10 minut, tak aby
" czas w którym zostanie dostarczony beton był jak najkrótszy
" koszt transportu nie przekroczyłby 7000 zł.
Oznaczenia:
" xij  ilość kursów i-tego pojazdu (i=1,2)
na j-tą budowę (j=1,2,3)
2x11 + 3x21 = 800
2x12 + 3x22 = 600
2x13 + 3x23 = 400
koszt = 10�"(x11 + x21 + x12 + x22 + x13 + x23) d" 7000
czas = max{(x11 + x12 + x13) / 6,(x21 + x22 + x23) / 6} min
xij e" 0, i =1,2; j = 1,2,3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 55
Zadanie transportowe  przykład rozwiązania w MS Excel
2 samochody dostarczają cement na 3 budowy (budowa A, budowa B, budowa C)
zapotrzebowanie cementu:
" budowa A 800 t
" budowa B 600 t
" budowa C 400 t
A
adowność samochodów:
" samochód 1 2 t
" samochód 2 3 t
Ile kursów na poszczególne budowy musiałby wykonać
ka\
dy z pojazdów, wiedząc \
e koszt jednego kursu
wynosi 10 zł, czas dojazdu 10 minut, tak aby
" czas w którym zostanie dostarczony beton był jak
najkrótszy
" koszt transportu nie przekroczyłby 7000 zł.
Oznaczenia:
" xij  ilość kursów i-tego pojazdu (i=1,2)
na j-tą budowę (j=1,2,3)
2x11 + 3x21 = 800
2x12 + 3x22 = 600
2x13 + 3x23 = 400
koszt = 10�"(x11 + x21 + x12 + x22 + x13 + x23) d" 7000
czas = max{(x11 + x12 + x13) / 6,(x21 + x22 + x23) / 6} min
xij e" 0, i =1,2; j = 1,2,3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 56
Zadanie transportowe  przykład rozwiązania w MS Excel
2 samochody dostarczają cement na 3 budowy (budowa A, budowa B, budowa C)
zapotrzebowanie cementu:
" budowa A 800 t
" budowa B 600 t
" budowa C 400 t
A
adowność samochodów:
" samochód 1 2 t
" samochód 2 3 t
Ile kursów na poszczególne budowy musiałby wykonać
ka\
dy z pojazdów, wiedząc \
e koszt jednego kursu
wynosi 10 zł, czas dojazdu 10 minut, tak aby
" czas w którym zostanie dostarczony beton był jak
najkrótszy
" koszt transportu nie przekroczyłby 7000 zł.
Oznaczenia:
" xij  ilość kursów i-tego pojazdu (i=1,2)
na j-tą budowę (j=1,2,3)
2x11 + 3x21 = 800
2x12 + 3x22 = 600
2x13 + 3x23 = 400
koszt = 10�"(x11 + x21 + x12 + x22 + x13 + x23) d" 7000
czas = max{(x11 + x12 + x13) / 6,(x21 + x22 + x23) / 6} min
xij e" 0, i =1,2; j = 1,2,3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 57
Zadanie transportowe  przykład rozwiązania w MS Excel
2 samochody dostarczają cement na 3 budowy (budowa A, budowa B, budowa C)
zapotrzebowanie cementu:
" budowa A 800 t
" budowa B 600 t
" budowa C 400 t
A
adowność samochodów:
" samochód 1 2 t
" samochód 2 3 t
Ile kursów na poszczególne budowy musiałby wykonać
ka\
dy z pojazdów, wiedząc \
e koszt jednego kursu
wynosi 10 zł, czas dojazdu 10 minut, tak aby
" czas w którym zostanie dostarczony beton był jak
najkrótszy
" koszt transportu nie przekroczyłby 7000 zł.
Oznaczenia:
" xij  ilość kursów i-tego pojazdu (i=1,2)
na j-tą budowę (j=1,2,3)
2x11 + 3x21 = 800
2x12 + 3x22 = 600
2x13 + 3x23 = 400
koszt = 10�"(x11 + x21 + x12 + x22 + x13 + x23) d" 7000
czas = max{(x11 + x12 + x13) / 6,(x21 + x22 + x23) / 6} min
xij e" 0, i =1,2; j = 1,2,3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 58
Zadanie transportowe  przykład rozwiązania w MS Excel
2 samochody dostarczają cement na 3 budowy (budowa A, budowa B, budowa C)
zapotrzebowanie cementu:
" budowa A 800 t
" budowa B 600 t
" budowa C 400 t
A
adowność samochodów:
" samochód 1 2 t
" samochód 2 3 t
Ile kursów na poszczególne budowy musiałby wykonać
ka\
dy z pojazdów, wiedząc \
e koszt jednego kursu
wynosi 10 zł, czas dojazdu 10 minut, tak aby
" czas w którym zostanie dostarczony beton był jak
najkrótszy
" koszt transportu nie przekroczyłby 7000 zł.
Oznaczenia:
" xij  ilość kursów i-tego pojazdu (i=1,2)
na j-tą budowę (j=1,2,3)
2x11 + 3x21 = 800
2x12 + 3x22 = 600
2x13 + 3x23 = 400
koszt = 10�"(x11 + x21 + x12 + x22 + x13 + x23) d" 7000
czas = max{(x11 + x12 + x13) / 6,(x21 + x22 + x23) / 6} min
xij e" 0, i =1,2; j = 1,2,3
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 59
Równanie nieliniowe, zadanie optymalizacji  funkcje
SciLaba
" fsolve()  funkcja rozwiązująca układ równań
nieliniowych
" linpro()  narzędzie rozwiązywania zadań programowania
liniowego
" quapro()  narzędzie rozwiązywania zadań
programowania kwadratowego
" optim()  funkcja rozwiązująca nieliniowe zadania
optymalizacji
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 60
Podsumowanie
Metody rozwiązywania równań nieliniowych.
Zadanie optymalizacji
" Rozwiązywanie równań nieliniowych
 Postać równania nieliniowego
 Iteracyjne metody rozwiązań
" idee poszczególnych metod,
" sposób wyznaczania kolejnych przybli\
eń,
" własności
 Metoda bisekcji
 Regula falsi
Metoda Newtona-Raphsona (stycznych)
 Metoda siecznych i jej modyfikacje
 Porównanie metod rozwiązania
 pojęcie rzędu metody
" Układy równań nieliniowych  sposoby rozwiązania
" Metody optymalizacji  postać zadania
 sposoby poszukiwania rozwiązań
" Metoda spadku względem współrzędnych
" Metody gradientowe  własności, sposoby wyznaczania kierunków poszukiwań
" Metoda gradientu prostego
" Metoda najszybszego spadku
" metoda Newtona
" metoda sprzę\
onych gradientów
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 61
Podsumowanie cd.
Metody rozwiązywania równań nieliniowych.
Zadanie optymalizacji
" Zadanie programowania liniowego
 sposób rozwiązywania metodą simplex
 Przykłady standardowych zadań programowania liniowego
" Zadanie transportowe
" Zadanie optymalnego wyboru asortymentu produkcji
" Problem przydziału maszyn
" Problem optymalnego mieszania surowców
" Zadanie załadunku
" Zadanie rozkroju
" Zadanie komiwoja\
era
" Mo\
liwości rozwiązania zadań optymalizacji przy u\
yciu arkusza
kalkulacyjnego MS Excel i programu SciLab