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: 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
x
0
dla której
f(x
0
)=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
x
0
dla której
f(x
0
)=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
1.5
przedział
izolacji
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 funkcja
f(x),
oraz przedział
[a,b]
funkc ja f(x) = 1/x - nie c iąg ło ś ć funkc ji w 0
-25
-20
-15
-10
-5
0
5
10
15
20
25
-4
-3
-2
-1
0
1
2
3
4
-4,5
-4
-3,5
-3
-2,5
-2
-1,5
-1
-0,5
0
-2
-1
0
1
2
3
4
5
-5
-4
-3
-2
-1
0
1
2
3
4
-2
-1
0
1
2
3
4
5
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 6
Równanie nieliniowe
Dana jest funkcja
f(x),
oraz przedział
[a,b]
funkc ja f(x) = 1/x - nie c iąg ło ś ć funkc ji w 0
-25
-20
-15
-10
-5
0
5
10
15
20
25
-4
-3
-2
-1
0
1
2
3
4
-4,5
-4
-3,5
-3
-2,5
-2
-1,5
-1
-0,5
0
-2
-1
0
1
2
3
4
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
x
0
równania
f(x)=0
-5
-4
-3
-2
-1
0
1
2
3
4
-2
-1
0
1
2
3
4
5
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 7
Równanie nieliniowe – metody rozwi
ą
za
ń
• Metoda bisekcji
(pierwsza iteracja)
(
)
b
a
x
+
=
2
1
a
b
( )
b
f
( )
x
f
( )
a
f
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 8
Metoda bisekcji
• i – ty krok iteracji
(
)
i
i
i
i
i
x
b
b
a
x
=
+
=
−
−
1
1
2
1
b
i
−
1
( )
f b
i
−
1
( )
i
x
f
( )
f a
i
−
1
i
b
a
a
i
i
−
=
1
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 9
Metoda bisekcji
w i-tym kroku metody
:
– znajdujemy środek przedziału
– jeśli
|f(x
i
)|<
εεεε
⇒
znaleźliśmy pierwiastek
=
x
i
– w przeciwnym razie (gdy
|f(x
i
)|
≥≥≥≥ εεεε
)
wyznaczamy nowy przedział do podziału
– powtarzamy procedurę podziału
[
] [
]
( ) ( )
[
]
( ) ( )
>
<
=
−
−
−
−
0
,
0
,
,
1
1
1
1
i
i
i
i
i
i
i
i
i
i
x
f
a
f
gdy
b
x
x
f
a
f
gdy
x
a
b
a
;
2
1
1
−
−
+
=
i
i
i
b
a
x
x = (a + b)/2
while abs(f(x)) >= eps
if f(a)*f(x) < 0
b = x
else
a = x
end
x = (a + b)/2
end
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
)
y
x
b
x
1
a
x
2
x
3
y=f(x)
1)
przez punkty
(a,f(a))
i
(b,f(b))
prowadzimy cięciwę o równaniu:
2)
przybliŜeniem pierwiastka jest punkt
przecięcia tej cięciwy z osią OX
3)
jeśli
f(x
1
)=0
(lub
|f(x
1
)|<
εεεε
)
to
x
1
jest szukanym pierwiastkiem
4)
jeśli
f(a)f(x
1
)<0
to przyjmujemy
b=x
1
,
w przeciwnym przypadku
a=x
1
powracamy do punktu 1)
)
(
)
(
)
(
)
(
a
x
a
b
a
f
b
f
a
f
y
−
−
−
=
−
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
załoŜenia dodatkowe
– funkcja jest klasy
C
2
[a,b]
– pierwsza i druga
pochodna
f
mają
stały znak
metoda ma stały punkt
iteracji (
ff’’>0)
( )
f x
1
( )
f x
2
( )
f x
3
( )
f x
0
( ) ( )
f x
f
x
0
0
0
"
>
x
0
x
3
x
2
x
1
( )
( ) ( )(
)
0
0
1
1
0
,
x
x
x
f
x
f
x
f
x
x
b
x
a
x
i
i
i
i
i
−
−
−
=
=
=
+
( ) ( )(
)
( ) ( )(
)
i
i
i
i
i
i
i
i
i
i
i
x
x
x
x
x
f
x
f
x
f
x
x
x
x
x
f
x
f
x
f
x
f
−
−
−
=
−
⇒
−
−
−
=
−
+
+
+
1
0
0
1
0
0
1
)
(
)
(
)
(
( ) ( ) ( )
1
1
1
1
|
|
+
+
+
+
−
−
≈
−
i
i
i
i
i
i
x
f
x
f
x
f
x
x
x
x
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Ŝ
• 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 x
C
a b
∈
1
,
( )
( )
[ ]
b
a
C
x
f
,
2
∈
( )
( )
( )
( )
i
i
i
i
i
i
i
i
x
f
x
f
x
x
x
x
x
f
x
f
'
)
(
'
1
1
−
=
−
=
−
+
+
( )
( )
i
i
i
x
f
x
f
x
x
'
≈
−
( ) ( )(
)
( ) ( )(
)
i
i
i
i
i
i
i
i
i
i
i
x
x
x
x
x
f
x
f
x
f
x
x
x
x
x
f
x
f
x
f
x
f
−
−
−
=
−
⇒
−
−
−
=
−
+
+
+
1
0
0
1
0
0
1
)
(
)
(
)
(
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)
0
1
2
4
3
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)=0
ma dokładnie jeden pierwiastek w
[a,b]
i
metoda Newtona-Raphsona jest zbieŜna do tego pierwiastka dla
dowolnego punktu startowego
x
0
∈
∈
∈
∈
[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
x
i
jest jego przybliŜeniem, to
•
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):
–
dla
p=2
(metoda Newtona-Raphsona stopnia II):
L
+
−
+
−
+
−
+
=
=
)
(
!
3
)
(
)
(
''
!
2
)
(
)
(
'
)
(
)
(
0
)
(
)
3
(
3
2
i
i
i
i
i
i
i
x
f
x
x
f
x
x
f
x
x
f
f
ξ
ξ
ξ
ξ
)
x
(
'
f
)
x
x
(
)
x
(
f
i
i
i
i
−−−−
++++
====
++++
1
0
)
x
(
'
f
)
x
(
f
x
x
i
i
i
i
−−−−
====
++++
1
)
x
(
'
'
f
!
)
x
x
(
)
x
(
'
f
)
x
x
(
)
x
(
f
i
i
i
i
i
i
i
2
0
2
1
1
−−−−
++++
−−−−
++++
====
++++
++++
)
(
''
)
(
''
)
(
2
)
(
'
)
(
'
2
1
i
i
i
i
i
i
i
x
f
x
f
x
f
x
f
x
f
x
x
−
±
−
=
+
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
x
i
i
x
i-1
, a jako kolejne przybliŜenie
x
i+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)
(
)
( ) ( ) ( )
i
i
i
i
i
i
i
x
f
x
f
x
f
x
x
x
x
1
1
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
|x
i
-x
i-1
|
jest tego
samego rzędu co
oszacowanie błędu, następne
przybliŜenie moŜe nie być
poprawne
– gdy początkowe przybliŜenia
nie leŜą dostatecznie blisko
pierwiastka, metoda moŜe
nie być zbieŜna
– jeśli w trakcie obliczeń
odległości między kolejnymi
przybliŜeniami zaczynają
wzrastać, naleŜy je przerwać
i zawęzić przedział izolacji
( )
f x
1
( )
f x
2
( )
f x
4
( )
f x
0
( )
f x
3
x
1
x
2
x
4
x
0
x
3
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
0
1
2
3
4
5
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 :
( )
( )
(
)
( )
i
i
i
i
i
i
i
i
i
x
f
x
f
x
f
x
f
x
g
x
g
x
f
x
x
)
(
)
(
)
(
,
1
−
+
=
−
=
+
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
•
Równanie
f(x)=0
przekształcamy do
równania równowaŜnego
x=
ϕϕϕϕ
(x)
•
pierwsze przybliŜenie obliczamy
x
1
=
ϕϕϕϕ
(x
0
), x
0
-
rozwiązanie początkowe
•
kolejne przybliŜenia obliczamy
x
k
=
ϕϕϕϕ
(x
k-1
)
•
problemy
–
jak znaleźć funkcję
ϕϕϕϕ
?
–
przy jakich warunkach ciąg rozwiązań jest
zbieŜny?
jeśli istnieje q takie, Ŝe
|
ϕϕϕϕ
’(x)|
≤≤≤≤
q <1 x
∈
∈
∈
∈
[a,b]
to proces iteracji prostej jest zbieŜny niezaleŜnie
od przybliŜenia początkowego
x
0
∈
∈
∈
∈
[a,b].
Przykład
f(x)=x+ln(x)
⇒
ϕϕϕϕ
(x)=-ln(x)
x
k
= -ln(x
k-1
)
przypadek zbieŜny
przypadek rozbieŜny
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
K
taka, Ŝe dla dwu kolejnych przybliŜeń
x
i
i
x
i+1
zachodzi nierówność
|
x
i+1
-
α
|
≤
K |
x
i
-
α
|
p
2
Steffensena
≈≈≈≈
1,62
siecznych
2
Netona
1
regula falsi
1
bisekcji
Rz
ą
d
Metoda
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 26
Przykład – porównanie zbie
Ŝ
no
ś
ci metod
•
Szukamy dodatniego pierwiastka
równania
•
otrzymujemy
0
3
3
)
(
2
3
=
−
−
+
=
x
x
x
x
f
2
6
)
(
''
3
2
3
)
(
'
2
+
=
−
+
=
x
x
f
x
x
x
f
-20
-10
0
10
20
30
-4
-3
-2
-1
0
1
2
3
4
•
przedziałem izolacji moŜe być
[1,2]
•
obie pochodne są w tym przedziale
dodatnie
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 27
Przykład – porównanie zbie
Ŝ
no
ś
ci metod – cd.
a = 1
b = 2
x
1
= 1,5
x
2
= 1,75
x
3
=1,625
x
4
= 1,687
x
5
= 1,719
x
Metoda bisekcji
-4
3
-1,875
0,172
-0,943
-0,409
-0,124
f(x)
3
0,36048
0,00823
-0,000008
f(x)
x
0
= 2
x
1
= 1,76923
x
2
= 1,73292
x
3
= 1,73205
x
Metoda Newtona
-4
24
5,88800
0,98899
0,24782
-0,00095
x
0
= 1
x
1
= 3
x
2
= 2,2
x
3
= 1,83015
x
4
= 1,7578
x
5
= 1,73195
-4
3
-1,36449
-0,24784
0,02920
0,000576
a = 1
b = 2
x
1
= 1,57142
x
2
= 1,70540
x
3
= 1,73513
x
4
= 1,73199
-4
3
-1,36449
-0,24784
-0,03936
-0,00615
a = 1
b = 2
x
1
= 1,57142
x
2
= 1,70540
x
3
= 1,72788
x
4
= 1,73240
f(x)
x
f(x)
x
f(x)
x
Metoda siecznych
Regula falsi
-20
-10
0
10
20
30
-4
-3
-2
-1
0
1
2
3
4
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 28
Układy równa
ń
nieliniowych
Metoda Newtona
•
dla równania nieliniowego
– x
jest zmienną rzeczywistą
( )
0
x
=
f
)
x
(
'
f
)
x
x
(
)
x
(
f
i
i
i
i
−−−−
++++
====
++++
1
0
( )
=
n
n
n
n
n
n
i
x
f
x
f
x
f
x
f
x
f
x
f
x
f
x
f
x
f
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
∂
...
...
...
...
...
...
...
2
1
2
2
2
1
2
1
2
1
1
1
)
(
x
J
)
(
)
(
)
(
0
)
(
)
(
)
1
(
)
(
i
i
i
i
x
J
x
x
x
f
−
+
=
+
•
równanie nieliniowe
•
układ równań nieliniowych
(
)
(
)
=
=
0
0
n
n
n
x
x
f
x
x
f
,....,
,....,
1
1
1
( )
)
,...,
(
)
,...,
(
,
1
1
n
n
x
x
x
f
f
f
f
=
=
=
0
x
( )
0
x
=
f
( )
)
,...,
(
)
,...,
(
,
1
1
n
n
x
x
x
f
f
f
f
=
=
=
0
x
•
dla układu równań nieliniowych
– x
jest wektorem
n-
wymiarowym
(macierz Jacobiego)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 29
-5
-4
-3
-2
-1
0
1
2
3
4
5
3
7
1 1
1 5
1 9
2 3
2 7
3 1
3 5
3 9
Układy równa
ń
nieliniowych – rozwi
ą
zanie w SciLabie
wykorzystanie funkcji
fsolve(punkt_startowy, funkcja)
( )
0
4
2
0
8
cos
2
1
1
2
1
2
=
−
−
−
=
−
−
x
x
x
x
x
=
−
−
+
−
+
−
+
−
2
1
2
1
2
2
1
2
1
4
8
)
cos(
0
0
0
1
0
1
0
0
1
2
1
0
y
y
x
x
x
x
x
x
( )
2
2
1
1
2
1
1
2
4
2
8
cos
y
x
x
x
y
x
x
=
−
−
−
=
−
−
=
−
−
=
−
=
−
=
−
=
=
=
+
⋅
+
+
2
1
2
1
2
,
4
8
,
0
0
0
1
,
0
1
0
0
,
1
2
1
0
,
)
cos(
y
y
Y
d
c
b
a
x
x
X
Y
d
X
c
bX
aX
function [Y]=fst(X)
// w definiowanej funkcji przyjmujemy X=[x
1
;x
2
], Y=[y
1
;y
2
]
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=[x
1
,x
2
,...,x
n
]
jest
wektorem
• uwzględnienie warunków ograniczających:
– równania
A
i
(x)= b
i
dla
i=1,...,m
– nierówności
C
i
(x
i
)
≥≥≥≥
c
i
dla
i=1,...,p
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 31
Metody optymalizacji – przykład
Zadanie transportowe
Dana jest sieć
m
punktów wytwarzających
określony produkt i
wysyłających go do
n
punktów odbiorczych
. Określono
•
x
ij
– ilość produktu wysłanego z punktu
i-
tego
(
i=1,...,m
) do
j-
tego (
j=1,...,n
)
•
a
i
– ilość produktu wytwarzana przez i-ty punkt,
•
b
i
– ilość zapotrzebowania na produkt przez j-ty punkt,
•
c
ij
– koszt transportu jednostki produktu z punktu i-tego do
punktu j-tego
•
łączne zapotrzebowanie jest równe całości produkcji, tzn.
NaleŜy
znaleźć takie wartości
x
ij
aby całkowity koszt
transportu był
jak najmniejszy
. Szukamy minimum
wyraŜenia
przy warunkach
∑
∑
=
=
=
n
j
j
m
i
i
b
a
1
1
∑∑
=
=
=
m
i
n
j
ij
ij
x
c
x
f
1
1
)
(
n
j
m
i
x
n
j
x
b
m
i
x
a
ij
m
i
ij
j
n
j
ij
i
,...,
1
;
,...,
1
,
0
,...,
1
,
;
,...,
1
,
1
1
=
=
≥
=
=
=
=
∑
∑
=
=
P_1
a
1
P_2
a
2
P_m
a
m
O_1
b
1
O_2
b
2
O_n
b
n
x
12
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.
(x
0
,y
0
) –
punkt startowy
2.
ustalamy krok
k
3.
sprawdzamy wartości funkcji w 4 punktach:
(x
0
,y
0
+k),(x
0
,y
0
-k),(x
0
+k,y
0
),(x
0
-k,y
0
)
4.
jeŜeli w jednym z punktów wartość funkcji
f(x,y)
jest
mniejsza niŜ w punkcie
(x
0
,y
0
)
(„jest połoŜony niŜej”)
to „przenosimy się do niego” i powtarzamy procedurę w
kroku 3.
5.
jeśli w punkcie 4. nie znaleziono takiego punktu to
zmniejszamy krok (np. 2-krotnie) i powtarzamy punkt 3.
(x
0
+k,y
0
)
(x
0
-k,y
0
)
(x
0
,y
0
-k)
(x
0
,y
0
+k)
(x
0
,y
0
)
Zadanie: zapisz kod programu realizujący metodę,
przetestować dla f(x
1
,x
2
)=-4x
1
2
-(2x
2
+3)
2
)
• kierunek poszukiwań nie zaleŜy od postaci funkcji
• metoda zawodna w przypadku istnienia wielu
minimów lokalnych funkcji
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=[x
1
,x
2
,...,x
n
]
jest wektorem) jest klasy
C
1
.
•
Gradientem funkcji
f(x)
nazywamy wektor:
•
gradient określa kierunek największego
wzrostu funkcji
f(x)
T
x
x
f
x
x
f
x
x
f
x
x
f
x
x
f
x
x
f
x
f
∂
∂
∂
∂
∂
∂
=
∂
∂
∂
∂
∂
∂
=
∇
n
2
1
n
2
1
)
(
)
(
)
(
)
(
)
(
)
(
)
(
L
M
x
3
x
1
X
ˆ
)
ˆ
( X
f
∇
Przykład (obliczenie gradientu):
f(x
1
,x
2
)=-(x
1
-2)
2
-(x
2
-3)
2
∇
∇
∇
∇
f(x)= [-2(x
1
-2),-2(x
2
-3)]
T
∇
∇
∇
∇
f((1,2))=[2,2]
T
x
1
x
2
)
ˆ
( X
f
∇
X
ˆ
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 34
Metody optymalizacji - sposoby poszukiwania rozwi
ą
za
ń
Metody gradientowe
•
Procesy iteracyjne – kolejne przybliŜenie
– x
k+1
= x
k
+ h
k
ξξξξ
k
• x
k
poprzednie przybliŜenie (wektor n-wymiarowy),
• h
k
długość kroku (liczba rzeczywista),
•
ξξξξ
k
wektor (n-wymiarowy), określający kierunek poszukiwań.
– jeśli funkcja
f(x)(x=[x
1
,x
2
,...,x
n
])
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(x
k
)
(lub względna zmiana wartości ) spadnie poniŜej zadanego
poziomu,
• gdy długość gradientu
||
∇
f(x
k
)||
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
x
0
wartość funkcji
f(x
0
)
oraz jej gradientu
g
0
= g(x
0
)
2.
Wyznaczenie kierunku poszukiwań
ξξξξ
=-g
0
3.
WzdłuŜ kierunku
ξξξξ
wykonujemy krok o długości
h
oraz
określamy współrzędne nowego punktu :
x
i+1
=x
i
+h
*
ξξξξ
4.
Obliczenie w nowym punkcie wartość funkcji
f(x
i+1
)
oraz gradientu
g= g(x
i+1
),
jeŜeli krok był pomyślny,
tzn.
f(x
i+1
)
<
f(x
i
)
to powtarzamy od punktu 2
podstawiając
g
(gradient) w miejsce
g
0
5.
JeŜeli nie osiągnięto minimum, naleŜy wrócić do
poprzedniego punktu podstawiając :
x
i
=x
i+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(x
1
,x
2
)=-2x
1
2
-(x
2
-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
x
0
wartości
funkcji
f(x
0
)
oraz jej gradientu
g
0
= g(x
0
),
przyjmujemy
i=0
2.
Wyznaczenie kierunku poszukiwań
ξξξξ
=-g
i
3.
WzdłuŜ kierunku
ξξξξ
określamy
λλλλ
i
takie dla której
wartość
f(x
i-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(x
i+1
)
oraz gradientu
g= g(x
i+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(x
1
,x
2
)=-x
1
2
-(2x
2
-3)
4
)
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 37
Metoda najszybszego spadku - przykład
Znajdujemy minimum funkcji:
f(x
1
,x
2
)=x
1
2
+ x
2
2
Punkt startowy:
(x
1
(1)
,x
2
(1)
)= [1,1]
T
Gradient:
∇
∇
∇
∇
f(x
1
,x
2
)= [2x
1
,2x
2
]
T
Szukamy przybliŜenia postaci:
x
(2)
= x
(1)
+h
(1)
·(-
∇
∇
∇
∇
f(x
(1)
))
-2
-1
0
1
2
-2
-0.5
1
0
1
2
3
4
5
6
7
8
wielkość
h
0
- miejsce w którym funkcja
f(x
1
,x
2
)
na wyznaczonym przez gradient kierunku
przyjmuje minimalną wartość):
h
0
= min
h
(f(x
(1)
-h·
∇
∇
∇
∇
f(x
(1)
)
)
)
Znajdujemy wielkość
h
0
- definiujemy pomocniczą funkcję
H
(1)
(h)
, znajdujemy jej minimum
H
(1)
(h) =f(x
(1)
-h·
∇
∇
∇
∇
f(x
(1)
))=
=f([1,1]
T
-h·[2,2]
T
)= f([1-2h,1-2h]
T
)=
=(1-2h)
2
+(1-2h)
2
= 2(1-2h)
2
H
(1)’
(h)= 2·2(1-2h)·(-2) = -8(1-2h)
H
(1)’
(h)=0
⇔
⇔
⇔
⇔
h=1/2
x
(2)
= [1,1]
T
+1/2·(-[2,2
]
T
)=[0,0]
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
ξξξξ
i
T
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(x
1
)=-A*x
1
-b
(dobieramy macierz
A
i
wektor
b
tak by spełniona była powyŜsza równość)
–
minimalizacja
f(x)
wzdłuŜ tego kierunku : z równania
(
ξ
1
)
T
*[A(x
1
+
ββββ
1
*
ξ
1
+b]=0
otrzymujemy wartość
ββββ
1
, następnie określamy punkt
x
2
=x
1
+
ββββ
1
*
ξ
1
•
i-ty krok
: nowy kierunek w punkcie
x
i
jest wyznaczany według reguły :
ξ
i
=-
∇
∇
∇
∇
f(x
i
) +
ββββ
i
*
ξ
i-1
- współczynnik
ββββ
i
jest tak dobierany aby kierunki
ξ
i
,
ξ
i-1
były
sprzęŜone (punkt
x
i+1
wyznaczamy minimalizując
f(x)
wzdłuŜ tego kierunku) :
)
(
)
(
)
(
)
(
1
1
−
−
∇
⋅
∇
∇
⋅
∇
=
i
T
i
i
T
i
i
x
f
x
f
x
f
x
f
β
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
Zadanie minimalizacji
a)
ograniczenie równościowe
h(x
1
,x
2
)=0
b)
ograniczenie nierównościowe (aktywne)
g(x
1
,x
2
)
≤≤≤≤
0
c)
ograniczenie nierównościowe (nieaktywne)
g(x
1
,x
2
)
≤≤≤≤
0
Przykład:
znaleźć minimum
funkcji
f(x
1
,x
2
)=x
1
2
+ x
2
2
z warunkiem
2-x
1
-x
2
=0
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
}
,
,
0
,
:
{
}
)
(
{
min
n
m
R
b
x
b
Ax
R
x
X
x
c
x
f
m
n
T
X
x
≤
∈
≥
=
∈
=
=
∈
}
,
,
0
,
:
{
}
)
(
{
min
n
m
R
b
x
b
Ax
R
x
X
x
c
x
f
m
n
T
X
x
≤
∈
≥
≤
∈
=
=
∈
ograniczenie nierównościowe moŜna sprowadzić do równościowego
wprowadzając pomocniczą zmienną:
• x
1
+ 2x
2
≤≤≤≤
3
,
x
1
≥≥≥≥
0, x
2
≥≥≥≥
0
•
wprowadzamy pomocniczą zmienną
x
3
≥≥≥≥
0
zapisując
x
1
+ 2x
2
+ x
3
= 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
n
surowców.
Określono
•
x
i
– ilość wytworzonych jednostek
i-
tego (
i=1,...,m)
produktu,
•
a
i
– zysk osiągnięty ze sprzedaŜy
i-
tego (
i=1,...,m)
produktu,
•
b
j
– ilość dziennej dostawy jednostek
j-
tego (
j=1,...,n)
surowca,
•
c
ij
– ilość jednostek
j-
tego (
j=1,...,n)
surowca potrzebna do wytworzenia jednostki
i-
tego
(
i=1,...,m)
produktu
NaleŜy
znaleźć takie wartości
x
i
aby osiągnięty zysk dzienny był jak największy. Szukamy
maksimum wyraŜenia
przy warunkach
∑
=
=
m
i
i
i
x
a
x
f
1
)
(
;
,...,
1
,
0
,...,
1
,
1
m
i
x
n
j
b
x
c
i
j
m
i
i
ij
=
≥
=
≤
∑
=
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
9x
1
+8x
2
= const.)
25
5
2
:
40
5
8
:
0
,
0
max
8
9
)
(
2
1
2
1
2
1
2
1
≤
+
≤
+
≥
≥
→
+
=
x
x
B
x
x
A
x
x
x
x
x
f
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 44
Zastąpienie kryteriów nierównościowych kryteriami równościowymi
•
wprowadzamy dodatkowe zmienne x
3
, x
4:
•
zadanie (ograniczenia równościowe) opisujemy układem równań
0
,
,
,
25
5
2
25
5
2
:
40
5
8
40
5
8
:
4
3
2
1
4
2
1
2
1
3
2
1
2
1
≥
=
+
+
≤
+
⇒
=
+
+
≤
+
x
x
x
x
x
x
x
x
x
B
x
x
x
x
x
A
[
]
=
⋅
=
25
40
1
0
5
2
0
1
5
8
:
4
3
2
1
T
x
x
x
x
b
Ax
Programowanie liniowe – przykład liczbowy
Zadanie optymalnego wyboru asortymentu produkcji
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 45
25
5
2
:
40
5
8
:
0
,
0
max
8
9
)
(
2
1
2
1
2
1
2
1
≤
+
≤
+
≥
≥
→
+
=
x
x
B
x
x
A
x
x
x
x
x
f
[x, lagr, f] = linpro(p, C, b, ci, cs)
f(X)= p
T
*X ->
minimum
≤
≤
⇒
≤
≤
≤
⇒
≤
−
−
=
⇒
−
=
=
1000
1000
0
0
25
40
*
5
2
5
8
*
*
]
8
,
9
[
)
(
*
)
(
2
1
2
1
2
1
2
1
x
x
cs
X
ci
x
x
b
X
C
x
x
X
f
X
p
X
f
x
x
X
T
[x, lagr, f]=-linpro([-9;-8],[8,5;2,5],[40;25],[0;0],[1000;1000])
// x=[2.5;4], f=54.5
Programowanie liniowe – przykład liczbowy
Zadanie optymalnego wyboru asortymentu produkcji
funkcja
linpro()
Metody obliczeniowe - Budownictwo semestr 2 - wykład nr 2
Nr: 46
Programowanie kwadratowe – przykład liczbowy
funkcja
quapro()
25
5
2
:
40
5
8
:
0
,
0
min
)
(
2
1
2
1
2
1
2
1
2
1
≤
+
≤
+
≥
≥
→
−
−
=
x
x
B
x
x
A
x
x
x
x
x
x
f
[x, lagr, f] = quapro(Q, p, C, b, ci, cs)
f(X)= 0.5*X
T
*Q*X + p
T
*X ->
minimum
[
]
[
]
[
]
[
]
≤
≤
⇒
≤
≤
≤
⇒
≤
−
−
+
=
+
=
=
1000
1000
0
0
25
40
*
5
2
5
8
*
*
1
1
*
0
0
0
2
*
*
5
.
0
)
(
*
*
*
*
5
.
0
)
(
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
22
21
12
11
2
1
2
1
x
x
cs
X
ci
x
x
b
X
C
x
x
x
x
x
x
X
f
x
x
p
p
x
x
q
q
q
q
x
x
X
f
x
x
X
[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()
Znajdź 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:
x
≥≥≥≥
0, y
≥≥≥≥
0, z
≥≥≥≥
0, x
≤≤≤≤
10, y
≤≤≤≤
10, z
≤≤≤≤
10
// zdefiniowanie funkcji SciLaba która b
ę
dzie optymalizowana:
// zmienne (x
1
,x
2
,x
3
) 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
•
x
ij
– ilość
j-
tego (
j=1,...,n
) produktu wytworzonego na
i-
tej (
i=1,...,m
) maszynie w danym okresie czasu;
•
a
ij
– czas potrzebny do wyprodukowania jednostki produktu
j-
tego (
j=1,...,n
) na
i-
tej (
i=1,...,m
) maszynie;
•
a
i
– dysponowany czas pracy
i-
tej (
i=1,...,m
) maszyny
•
b
j
– ilość produktu
j-
tego (
j=1,...,n
), który powinien być
wytworzony;
•
c
ij
– koszt wytworzenia jednostki produktu
j
(
j=1,...,n
)
na
i-
tej (
i=1,...,m
) maszynie;
NaleŜy
znaleźć takie (nieujemne) wartości
x
ij
minimalizujący
wskaźnik jakości (najniŜszy koszt wytworzenia określonej
liczby wyrobów)
przy warunkach
∑∑
=
=
=
m
i
n
j
ij
ij
x
c
x
f
1
1
)
(
n
j
b
x
m
i
a
x
a
m
i
j
ij
i
n
j
ij
ij
,...,
1
,...,
1
,
1
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)
•
a
ij
– zawartość
j-
tego (
j=1,...,n
) składnika w jednostce
i-
tego
(
i=1,...,m
) produktu;
•
b
j
– wymagana zawartość
j-
tego (
j=1,...,n
) składnika w całości produktów;
•
c
i
– cena jednostki
i-
tego (
i=1,...,m
) produktu
Zadanie polega na wyznaczeniu
nieujemnych wielkości otrzymanych produktów
x
i
które minimalizują całkowity koszt
przy warunkach
∑
=
=
m
i
i
i
x
c
x
f
1
)
(
n
j
b
x
a
j
m
i
i
ij
,...,
1
,
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
a
1
, a
2
, ..., a
n
o
wartościach
c
1
, ...,c
n
naleŜy załadować na samochód o
dopuszczalnych ładowności
b
takie, aby łączna ich wartość była jak
największa.
oznaczamy zmienne
x
i
(i=1,...,n)
:
– 1: gdy i-ty ładunek jest załadowany
– 0: w przeciwnym przypadku
zadanie przyjmuje postać:
n
i
x
b
x
a
x
c
x
f
i
n
i
i
i
n
i
i
i
,...,
1
},
1
,
0
{
max
)
(
1
1
=
∈
≤
→
=
∑
∑
=
=
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
b
1
,b
2
,...,b
m
. Mamy wyróŜnionych
n
sposobó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):
gdzie
z
j
– minimalne,
y
j
– maksymalne zapotrzebowanie na wstęgi o szerokościach
b
j
c
i
– odpad powstający w
i-
tym sposobie rozkroju
s
ij
– (całkowita) liczba wstęg o szerokości
b
j
wyciętych z arkusza w
i-
tym
sposobie rozkroju
n
i
x
m
j
y
x
s
z
n
i
b
s
w
c
x
c
x
f
i
j
n
i
i
ij
j
m
j
j
ij
i
n
i
i
i
,...,
1
,
0
,...,
1
,...,
1
min,
)
(
1
1
1
=
≥
=
≤
≤
=
−
=
→
=
∑
∑
∑
=
=
=
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
.
c
ij
– odległość miasta
i
od miasta
j
niech
x
ij
=1
jeśli komiwojaŜer przejeŜdŜa z miasta
i
do miasta
j
,
x
ij
=0
w przeciwnym przypadku
Zadanie formułujemy:
)
(
,...,
2
,
,
1
)
3
(
,...,
1
;
,...,
1
},
1
,
0
{
,...,
1
,
1
)
2
(
,...,
1
,
1
)
1
(
min
)
(
1
1
1
1
j
i
n
j
i
n
nx
z
z
n
j
n
i
x
n
i
x
n
j
x
x
c
x
f
ij
j
i
ij
n
j
ij
n
i
ij
n
i
n
j
ij
ij
≠
=
−
≤
+
−
=
=
∈
=
=
=
=
→
=
∑
∑
∑∑
=
=
=
=
1.
komiwojaŜer do kaŜdego
miasta tylko raz,
2.
wyjeŜdŜa z kaŜdego miasta
tylko raz,
3.
droga komiwojaŜera składa
się z jednego cyklu
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
Ł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:
•
x
ij
– ilość kursów
i-
tego pojazdu (
i=1,2
)
na
j-
tą budowę (
j=1,2,3
)
3
,
2
,
1
;
2
,
1
,
0
min
}
6
/
)
(
,
6
/
)
max{(
7000
)
(
10
400
3
2
600
3
2
800
3
2
23
22
21
13
12
11
23
13
22
12
21
11
23
13
22
12
21
11
=
=
≥
→
+
+
+
+
=
≤
+
+
+
+
+
⋅
=
=
+
=
+
=
+
j
i
x
x
x
x
x
x
x
czas
x
x
x
x
x
x
koszt
x
x
x
x
x
x
ij
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
Ł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:
•
x
ij
– ilość kursów
i-
tego pojazdu (
i=1,2
)
na
j-
tą budowę (
j=1,2,3
)
3
,
2
,
1
;
2
,
1
,
0
min
}
6
/
)
(
,
6
/
)
max{(
7000
)
(
10
400
3
2
600
3
2
800
3
2
23
22
21
13
12
11
23
13
22
12
21
11
23
13
22
12
21
11
=
=
≥
→
+
+
+
+
=
≤
+
+
+
+
+
⋅
=
=
+
=
+
=
+
j
i
x
x
x
x
x
x
x
czas
x
x
x
x
x
x
koszt
x
x
x
x
x
x
ij
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
Ł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:
•
x
ij
– ilość kursów
i-
tego pojazdu (
i=1,2
)
na
j-
tą budowę (
j=1,2,3
)
3
,
2
,
1
;
2
,
1
,
0
min
}
6
/
)
(
,
6
/
)
max{(
7000
)
(
10
400
3
2
600
3
2
800
3
2
23
22
21
13
12
11
23
13
22
12
21
11
23
13
22
12
21
11
=
=
≥
→
+
+
+
+
=
≤
+
+
+
+
+
⋅
=
=
+
=
+
=
+
j
i
x
x
x
x
x
x
x
czas
x
x
x
x
x
x
koszt
x
x
x
x
x
x
ij
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
Ł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:
•
x
ij
– ilość kursów
i-
tego pojazdu (
i=1,2
)
na
j-
tą budowę (
j=1,2,3
)
3
,
2
,
1
;
2
,
1
,
0
min
}
6
/
)
(
,
6
/
)
max{(
7000
)
(
10
400
3
2
600
3
2
800
3
2
23
22
21
13
12
11
23
13
22
12
21
11
23
13
22
12
21
11
=
=
≥
→
+
+
+
+
=
≤
+
+
+
+
+
⋅
=
=
+
=
+
=
+
j
i
x
x
x
x
x
x
x
czas
x
x
x
x
x
x
koszt
x
x
x
x
x
x
ij
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
Ł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:
•
x
ij
– ilość kursów
i-
tego pojazdu (
i=1,2
)
na
j-
tą budowę (
j=1,2,3
)
3
,
2
,
1
;
2
,
1
,
0
min
}
6
/
)
(
,
6
/
)
max{(
7000
)
(
10
400
3
2
600
3
2
800
3
2
23
22
21
13
12
11
23
13
22
12
21
11
23
13
22
12
21
11
=
=
≥
→
+
+
+
+
=
≤
+
+
+
+
+
⋅
=
=
+
=
+
=
+
j
i
x
x
x
x
x
x
x
czas
x
x
x
x
x
x
koszt
x
x
x
x
x
x
ij
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