Instytut Sterowania i Systemów Informatycznych

Politechnika Zielonogórska

Metody i techniki optymalizacji

Warunki optymalno´sci dla zada ´n bez ogranicze ´n

Na stronie internetowej odpowiadaj ˛

acej cz˛e´sci Wykłady odnale´z´c pliki

newton1D.m

oraz

newtonND.m

b˛ed ˛

ace matlabowymi implementacjami metody Newtona odpowiednio dla funkcji jednej i wielu zmiennych

(przykładowe skrypty z ich wywołaniami to pliki

script_newton1D.m

i

script_newtonND.m

);

zwróci´c uwag˛e na to jak podaje si˛e informajc˛e o minimalizowanych funkcjach (w przypadku wielowymia-
rowym potrzebne s ˛

a jeszcze pliki

fun.m

,

grad.m

oraz

hessian.m

).

Program ´cwiczenia obejmuje nast˛epuj ˛

ace zadania:

1. Z zastosowaniem procedury

newton1D

okre´sli´c minimum funkcji


  

z dokład-

no´sci ˛

a do czterech miejsc po przecinku. Jako punkt startowy wybra ´c





. Co otrzymuje si˛e po

zmianie punktu startowego? Narysowa´c wykresy charakteryzuj ˛

ace zbie˙zno´s´c metody (warto´sci



i




wzgl˛edem liczby wykonanych iteracji). Wykona ´c to samo dla funkcji



 

.

W podobny sposób przeanalizowa´c prac˛e algorytmu dla funkcji



!#"$&%')(
*,+

-

.

+0/

1 

,

badaj ˛

ac szczególnie wra˙zliwo´s´c na zmian˛e punktu startowego. Wyja´sni´c dziwne zachowanie metody

gdy np.

2*

+





.

2. (Zadanie dla fanów) Funkcja




13



5464

87

:9;

/

4

+

1<

=6>



54

1

+



/



+



posiada cztery ekstrema w przedziale

?

@

+BA

; zauwa˙zy ´c, ˙ze

1CD
EF
G

+

;.
HG

+



=


HG

+

I9J.
G

+

;

Przedstawi´c na wykresie zale˙zno´s´c punktu ekstremum, do którego jest zbie˙zna metoda Newtona, od
punktu startowego (zało˙zy´c, ˙ze punkty startowe wybiera si˛e z przedziału

?

@

+BA

).

3. Okre´sli´c punkty minimum i maksimum funkcji (a)


KL
M

+



oraz (b)


K


/ +



.

4. Pokaza´c, ˙ze minimaln ˛

a warto´sci ˛

a funkcji

N

%PO;8Q

/SR

TQ

jest

VU

N

/R

. Czy mo˙zna ten rezultat

otrzyma´c bez u˙zycia pochodnych?

5. Zbada´c funkcj˛e


W! XY<Z

+

. Narysowa´c jej wykres. Pokaza´c, ˙ze




posiada minimum w

punkcie

W 

. Czemu równa jest warto´s´c

C



dla

W 

? Czy

C



zmienia znak przy przej´sciu



przez zero?

6. Zbada´c funkcj˛e


*\[

[

. Znale´z´c jej minimum. Co mo˙zna powiedzie´c o zachowaniu si˛e

C



w

punkcie minimum?

7. Znale´z´c minimum funkcji

]6^`_

a%PO;`

.

1





















15 cm

9 cm

Rysunek 1: Szablon pudełka z zadania 9.





Rysunek 2: Okno z zadania 10.

8. Wyznaczy´c punkty stacjonarne funkcji


K7

+

961<

/

>

1 

+

4



.

9. Z kartonu o rozmiarach podanych na rys. 1 nale˙zy wyci ˛

a ´c pudełko o maksymalnej obj˛eto´sci. Okre´sli´c

optymalne rozmiary pudełka.

10. Architekt ma zaprojektowa´c okno o kształcie przedstawionym na rys. 2 w taki sposób, ˙ze jego obwód

wynosi 12 m, a powierzchnia jest maksymalna. Okre´sli´c optymalne rozmiary okna.

11. Nale˙zy poło˙zy´c kabel telefoniczny ł ˛

acz ˛

acy wysp˛e z nadmorskim miastem B (rys. 3). Linia ł ˛

acz ˛

aca

punkty A i B odpowiada brzegowi morskiemu. Poło˙zenie 1 km kabla wzdłu˙z brzegu kosztuje 6000
PLN, a 1 km pod wod ˛

a – 9000 PLN. Okre´sli´c najta ´nszy sposób poł ˛

aczenia wyspy z miastem B.

12. Dana jest zmienna losowa



. Znale´z´c liczb˛e

N

, dla której warto´s´c oczekiwana zmiennej losowej

[





N

[

jest najmniejsza.

13. Udowodni´c, ˙ze warunki wystarczaj ˛

ace optymalno´sci




E  




6



2

Morze

Wyspa

A

B



+

a

12 km

7 km

Rysunek 3: Kabel telefoniczny z zad. 11.

s ˛

a w przypadku funkcji dwóch zmiennych równowa˙zne zestawowi warunków





)

E  





)

E  







)





 







)











)















)







14. Stosuj ˛

ac warunki optymalno´sci pokaza´c, ˙ze dla wszystkich





zachodzi

+



/

KJ

15. Bez odwoływania si˛e do warunków optymalno´sci okre´sli´c punkty minimum globalnego funkcji Ro-

senbrocka




)

F

E

+



/ +

`

Ea





Dokona´c minimalizacji tej funkcji z zastosowaniem procedury

newton2D

wybieraj ˛

ac jako punkty

startowe odpowiednio

(a)

12*F

=

&;

,

(b)

12

F

=



#;

,

(c)

12*F
H





;

.

Wytłumaczy´c zachowanie procedury w ostatnim przypadku (wskazówka: narysowa ´c wykres rozwa-

˙zanej funkcji w obszarze



 






+

oraz







+











+

).

16. Zbada´c punkty stacjonarne funkcji


K

/

96


/

:1

.

17. Zbada´c punkty stacjonarne funkcji


5*



>

1





=

1

<



96


/

>




<

/





<

.

18. Okre´sli´c zbiór punktów stacjonarnych funkcji




)

EK

/



/


)

/



/

:

w zale˙zno´sci od parametru



. Które z nich s ˛

a minimami globalnymi?

3

19. Pokaza´c, ˙ze funkcja




)

EF
1



9J

/

1

ma dwa minima globalne oraz jeden punkt stacjonarny,

który nie odpowiada ani minimum, ani maksimum.

20. Znale´z´c wszystkie minima lokalne funkcji




)





/


8%PO;`

.

21. W przestrzeni



s ˛

a dane punkty



















. Znale´z´c punkt







, dla którego suma kwadratów

jego odległo´sci od zadanych punktów jest minimalna.

22. Znale´z´c punkt płaszczyzny o równaniu



/





/

 

K9

najmniej oddalony od pocz ˛

atku układu współrz˛ednych. Jaka jest ta odległo ´s´c?

Jak zmieni si˛e rozwi ˛

azanie po zamianie powy˙zszej płaszczyzny na płaszczyzn˛e

WS

?

23. (Problem Fermata-Torricelli’ego-Vivianiego) Maj ˛

ac dany trójk ˛

at na płaszczy´znie, rozwa˙zy ´c zada-

nie okre´slenia punktu, dla którego suma jego odległo´sci od wierzchołków jest minimalna. Pokaza ´c, ˙ze
taki punkt jest albo wierzchołkiem trójk ˛

ata, albo punktem, z którego ka˙zdy bok trójk ˛

ata jest widziany

pod k ˛

atem

+



.

24. Poda´c przykłady gładkich (tzn. posiadaj ˛

acych pochodne dowolnego rz˛edu) funkcji jednej lub dwóch

zmiennych, które spełniaj ˛

a poni˙zsze warunki odno´snie ekstremów bez ogranicze ´n:

(a) Minimum i maksimum globalne jest osi ˛

agane w niesko ´nczonej liczbie punktów.

(b) Funkcja jest ograniczona i posiada maksimum globalne, jednak minimum globalne nie jest osi ˛

a-

gane.

(c) Funkcja jest ograniczona, jednak nie posiada maksimum i minimum globalnego.

(d) Funkcja jest ograniczona i posiada punkty stacjonarne, jednak minimum i maksimum globalne

nie s ˛

a osi ˛

agane.

(e) Funkcja jest ograniczona i posiada zarówno minima, jak i maksima lokalne, jednak nie posiada

maksimum i minimum globalnego.

(f) Jest tylko jedno ekstremum lokalne, które nie jest ekstremum globalnym.

(g) Jest niesko ´nczenie wiele punktów maksimum lokalnego, ale ani jednego punktu minimum lo-

kalnego.

25. Firma produkuje dwa rodzaje lodów A i B. Koszt produkcji jednej szuki A wynosi $0.20, a jednej

sztuki B — $0.25. Popyt na lody okre´slaj ˛

a zale˙zno´sci



N



R





+

66

N

R

(dla A)





N



R

E

66

N

R

(dla B)

gdzie

N

jest cen ˛

a 1 szt. A oraz

R

jest cen ˛

a 1 szt. B.

Okre´sli´c cen˛e lodów maksymalizuj ˛

ac ˛

a zysk firmy.

26. Firma produkuje dwa produkty. Zale˙zno´sci popytów na nie



i



od cen



i



maj ˛

a odpowiednio

posta´c





9;V





/





 6

/



E



4

Koszt produkcji opisuje zale˙zno´s´c







EK

/





/



Okre´sli´c wartos´ci



i



maksymalizuj ˛

ace zysk firmy.

27. W trakcie pewnego eksperymentu badano wpływ zastosowania dwóch nawozów sztucznych A i B na

wielko´s´c plonów pszenicy. Otrzymano w ten sposób zale˙zno´s´c







E

+



/





/

:

/



 :



/ +



gdzie



oznacza ilo´s´c A (w pewnych jednostkach),



— ilo´s´c



, a

— plon z jednostki powierzchni.

Jakie ilo´sci nawozów prowadz ˛

a do maksymalnego plonu?

5