5В070300 Ақпараттық жүйелер мамандығының студенттері үшін


с. 1

Әдістемелік нұсқаулар



Форма

Ф СО ПГУ 7.18.2/05



Қазақстан республикасының ғылым және білім министрлігі
С.Торайғыров атындағы Павлодар мемлекеттік университеті
Информатика және ақпараттық жүйелер кафедрасы

5В070300 Ақпараттық жүйелер мамандығына арналған

Оңтайландыру әдістері және операцияны зерттеу пәні бойынша тәжірибелік жұмыстарды орындауға арналған

ӘДІСТЕМЕЛІК НҰСҚАУ

Павлодар





Әдістемелік нұсқауларды

бекіту беті





Форма

Ф СО ПГУ 7.18.1/05






БЕКІТЕМІН

ФМжАТ факультет деканы

__________ Нұрбекова Ж.К.

____ ______ 2010 ж.


Құрастырушы: оқытушы Ардабаева А.К.


Информатика және ақпараттық технологиялар кафедрасы

5В070300 Ақпараттық жүйелер мамандығының студенттері үшін


Оңтайландыру әдістері және операцияны зерттеу

практикалық жұмыстарды орындауға арналған


Әдістемелік нұсқаулар

Кафедра отырысында ұсынылған «__»___________2010ж. №_____ хаттама


Кафедра меңгерушісі _____________________________А.Ж.Асаинова

ФМжАТ факультеттің әдістемелік кеңесінде құпталған

«___»___________200__ж. №______ хаттама
ӘК торайымы __________________ Муканова Ж.Г.

Практикалық жұмыс 1. Бірөлшемді оптимизация

Практика 1. Алтын қима әдісін қолданып функция минимумын дәлдікпен табу қажет. Алынған шешімді бастапқы жақындату ретінде таңдап теңдеу шешімін бисекция әдісі бойынша дәлдікпен және Ньютон әдісі бойынша табу қажет.

1.

2.

3. x4-14x3+60x2-70x



4) –e-xln(x)



5) 2x2-ex




Бастапқы интервал [0;2].

Салыстырмалы қателік =10-5.


2. Тапсырманы орындауға арналған нұсқаулар

Қандай да бір f(x) функциясы берілсін және (a,b) бастапқы кесінді. Алтын қима әдісінің алгоритмін қарастырайық:



  1. екі қосымша нүктелері табылады x1:=a+sech*(b-a) және x2:=a+(1-sech)*(b-a), мұндағы sech=0.3819660113;

  2. функцияның бұл нүктелеріндегі мәнін табу: y1 и y2;

  3. қосымша айнымалыны қарастырайық int – бастапқы мәндері a-b болатын жұмыс нүктелері арасының ұзындығы (ағымды итерациялық кесінді ұзындығы).

  4. Егер int>e*x1, мұндағы е – салыстырмалы қателік, онда 5 пункке көшеміз, әйтпесе итерация процесі аяқталады да x1 – іздеген минимум нүктесі.

  5. Егер y2>y1, онда жұмыс интервалын кішірейтеміз int=x2-a. Қайтадан меншіктейміз: b=x2; x2=x1; y2=y1; x1=a+sech*int; y1=f3(x1).

  6. Егер y2>y1, онда жұмыс интервалын кішірейтеміз int=b-x1. Қайтадан меншіктейміз: int=b-x1; a=x1; x1=x2; y1=y2; x2=a+(1-sech)*int; y2=f3(x2).

  7. 4 пункке көшеміз.


Блок схема
Практикалық жұмыс 2

ε=0,01 дәлдікпен f(x) = 2x2 – 12x функцияның минимумын Фибоначчи әдісін қолданып табу.
Анықтама:

Фибоначчи сандары төмнегі формулалар бойынша есептеледі:

F0 = F1 = 1, Fk = Fk-1 + Fk-2 , k = 2, 3, 4,…

Фибоначи тізбегі: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,…


Әдістеменің жинақталуы:

FN > , N – есептеу саны.

Анықталмаған интервал ұзындығы азаюы R(N) = формуламен анықталады, мұндағы N - есептеулер саны.
Есепті шешу:

1. Бастапқы анықталмаған интервалы берілсін: L0 =[0,10]. l = 1 есептеу дәлдігі, ε = 0,01 болсын,

F6 = 13 > = 10 сондықтан N=6.

2. Фибоначчи сандары: F0 = F1 = 1, F2 =2, F3 = 3, F4 = 5, F5 = 8, F6 = 13.

3. k = 0 болсын.

40. Аралық мәндерін есептейік:

y0 = a0 + (b0 – a0 ) = 0 + ∙10 = 3,846; z0 = a0 + (b0 – a0 ) = 0 + ∙10 = 6,154.

50. f(y0) = -16,57; f(z0) = 1,893.

60 . f(y0) < f(z0) болғндықтан a1 = a0 = 0; b1 = z0 = 6, 154; y1 = a1 + (b1 – a1 ) =

= 0 + ∙6,154=2,308;

z1 = y0 = 3,846.

70. Есеп аяқталу шартын тексерейік k = 0  N – 3 = 6 – 3 = 3; L2 = [0, 6,154].

k = 1 Деп 5 қадамға көшейік

51. f(y1) = -17,04; f(z1) = -16,57 мәндерін ессептеп салыстырайық:

61. f(y1) < f(z1) болғандықтан a2 = a1 = 0, b2 = z1 = 3,846;

y2 = a2 + (b2 – a2 ) = 0 + ∙3,846 = 1,536; z2 = y1 = 2,308.

71. Есеп аяқталу шартын тексерейік k = 1 ¹ N – 3 = 6 – 3 = 3; L2 = [0; 3,846].

k = 2 Деп 5 қадамға көшейік

52 . f(y2) = -13,73; f(z2) = -17,04

62. f(y2) > f(z2) болғандықтан a3 = y2 = 1,538, b3 = b2 = 3,846; y3 = z2 = 2,308;

z3 = a3 + (b3 – a3) = 1,538 + ∙ (3,846 – 1,538) = 3,077.

72. Есеп аяқталу шартын тексерейік k = 2 ¹ N – 3 = 6 – 3 = 3; L4 = [1,538; 3,846].

k = 3 Деп 5 қадамға көшейік.

53. f(y3) = f(z2) = -17,04; f(z3) = -17, 9884.

63. f(y3) > f(z3) болғандықтан

a4 = y3 = 2,308, b4 = b3 = 3,846; y4 = z3 = 3,077;

z4 = a4 + (b4 – a4) = 2,308 + ∙ (3,846 – 2,308) = 3,077.

73. Есеп аяқталу шартын тексерейік k = 3 ¹ N – 3 = 6 – 3 = 3; L5 = [2,308; 63,846].

y5 = y4 = z4 = 3,077; z5 = y5 + ε = 3,077 + 0,01 = 3,087.

f(y5) = -17,9884; f(z5) = -17,985. f(y5) < f(z5) болғандықтан a5 = a4 = 2,308, b5 = z5 = 3,087.


x*  [2,308; 3,087]; = 3,087 – 2,308 = 0,78 < l = 1.

Жуық шешімі x*  = 2,697, L6 интервалдың ортасы болады.


= 0,078 = = 0,077


Практикалық жұмыс 3

Дихотомия әдісін қолданып келесі функциялардың экстремум нүктелерін тап


а) x4-14x3+60x2-70x

б) –e-xln(x)



в) 2x2-ex




Бастапқы интервал [0;2].

Салыстырмалы қателік =10-5.



Тапсырманы орындауға арналған нұсқаулар
Итерацияның әр бір қадамында минимум ізделініп жатқан кесінді жартылай бөлінеді.

Кесіндінің ортасынан екі жағына /2 ге тең Минмумы жоқ кесінді алынып тастайды.



  1. [a,b] бастапқы кесіндіні қарастырайық және кесіндінің ортасы табылады xk=(a+b)/2.

  2. Екі қосымша нүктелер алынады xk+xk*/2 және xk-xk*/2, мұндағы  - салыстырмалы қателік.

  3. Функцияның мәндерін салыстырамыз. Егер f0(xk+xk*/2)>f0(xk-xk*/2), онда k+1-нші итерация үшін ak+1=ak bk+1=xk. Егер f0(xk+xk*/2)0(xk-xk*/2), k+1-нші итерация үшін ak+1=xk bk+1=bk.

  4.  - титерация дәлдігі, онда итерациялық процесс bk-ak*x болғанда аяқталады.

Мысал: Дихотомия әдісімен f(x)=2x2-12x функцияның минимумын табайық.



  1. Бастапқы интервалын анықтайық: L0=[0;10]. ε =0,2 - кейбір аз шама, дәлдігі l =1болсын.

  2. k=0 (индекс) болсын.

30 y0 , z0 есептейік; y0 ==4,9; z0==5,1

f(y0)=-10,78; f(z0)=-9,18.

40 f(y0)< f(z0) болғндықтан, a1 =a0 =0, b1 =z0 =5,1 болады.

50 L2 =[0;5,1], L2 =5,1>1болады, осы себептен k=1 деп 3 қадамға көшеміз.

31 y1, z1 есептейік:



y1==2,45; z1==2,65

f(y1)=-17,395; f(z1)=-17,755.

41 f(y1)> f(z1) болғaндықтан, a2 =y1 =2,45, b2 =b1 =5,1 болады.

51 L4 =[2,45;5,1], ïL4 ï =5,1-2,45=2,65>1болады, осы себептен k=2 деп 3 қадамға көшеміз.

32 y2, z2 есептейік:



y2==3,675; z2==3,875

f(y1)=-17,089; f(z1)=-16,469.

42 f(y0)< f(z0) болғaндықтан, a3 =a2 =2,45, b3 =z2 =3,875 болады.

52 L6 =[2,45;3,875], ïL6 ï =3,875-2,45=1,45>1 болады, осы себептен k=3 деп 3 қадамға көшеміз.

33 y3, z3 есептейік:



y3==3,06; z3==3,26

f(y3)=-17,99; f(z3)=-17,86.

43 f(y3)< f(z3) болғaндықтан, a4 =a3 =2,45, b4 =z3 =3,26 болады.

53 L8 =[2,45;3,26], ïL8ï =3,26-2,45=0,81<1болады, осы себептен

x* [2,45;3,26], N=8, x* =2,855.

Есептеу кестесін келтірейік:


k

a

b

y

z

f(y)

f(z)

f(y0)< f(z0)

b-a




0

0

10

4,9

5,1

-10,78

-9,18

+

10

L2

1

0

5,1

2,45

2,65

-17,395

-17,755



5,1

L4

2

2,45

5,1

3,675

3,875

-17,089

-16,469

+

1,425

L8

3

2,45

3,875

3,06

3,26

-17,99

-17,86

+

0,81

L8

4

2,45

3,26





















Ә
дістің тиімділігі n-ші итерация қорытындысында айқынсыз интервалдың бастапқы интервал қатынасы ретінде анықталады. Әдіс тиімділігі E=1/2n.

Блок схемасы

Практикалық жұмыс № 4
Сызықтық программалаудың элементтері
Тапсырмалар:
№ 1

2x1 + 3x2 – 120 теңсіздігімен анықталатын жарты жазықтықты табыңыз

Ш
ешімі: 2x1 + 3x2 – 12 = 0 теңдеумен анықталатын шекараны x2 = 12/3 – 2/3*x1 түрінде жазып, түзу сызықтың графигін жүргізіп жоғары жартыжазығын таңдаймыз.
№ 2

2x1 – 3x2 ³ 0 теңсіздігі қай жарты жазықтықты анықтайды?


№ 3

x1 +x2 – 5 £ 0 теңсіздігі қай жарты жазықтықты анықтайды?


№ 4

4x1 + x2 + 3 £ 0 теңсіздігі қай жарты жазықтықты анықтайды?


№ 5

x1 – 1 ³ 0, x2 –1 ³ 0, x1 + x2 – 3 ³ 0, –6x1 –7x2 +42 ³ 0

теңсізідіктермен анықталатын жазықтықтың бөлігін табыңыз
№ 6

x1 ³ 0, x1 + x2 – 2 ³ 0, x1 – x2 + 1 £ 0, x1 £ 2

теңсіздіктктер жүйесімен анықталатын жазықтықтың бөлігін табыңыз
№ 7

x1 ³ 0, x1 +3x2 £ 3, x1 – x2 + 1 £0

теңсіздіктктер жүйесімен анықталатын жазықтықтың бөлігін табыңыз
№ 8

2x1 – x2 ³ –2, x1 – x2 ³ –2, x1 £ 1, 2x1 – x2 ³ 3

теңсіздіктктер жүйесімен анықталатын жазықтықтың бөлігін табыңыз
№ 9

x1 – x2 + 1 ³ 0, 2x1 + x2 – 7 ³ 0, x1 – 2x2 + 4 ³ 0

теңсіздіктктер жүйесімен анықталатын жазықтықтың бөлігін табыңыз
№10

x1 – x2 + 1 ³ 0, 2x1 + x2 – 7 ³ 0, x1 –2x2 + 4 ³ 0

теңсіздіктктер жүйесімен анықталатын жазықтықтың бөлігін табыңыз

Практикалық жұмыс 5


Сызықтық программалаудың негізгі есебі
1 Берілген шектеулерде L(x)=12x1 +4x2 сызықтық форманы минимумдау қажет.

x1 + x2  2, x1 ³1/2, x2  4, x1 - x2 £ 0

Шешу:


x1 + x2 = 2, x1 =1/2, x2 = 4, x1 - x2 = 0 түзулермен шектелген облысты құрып, С(12,4)

векторын сызайық. Осы вектордың бойымен L(x) түзуі оң бағытта жылжыса, оның мяні өседі, кері бағытта кемиді. Осы себепте, оталған облясқа алғашқы кіріс нүктесінде сызықтық форманың ең кіші, ал шығу нүктесінде ең улкен мәні қабылданады.

2 Берілген шектеулерде L(x)=2x1 +2x2 сызықтық форманы минимумдау қажет

3x1 - 2x2 ³ -6, 3x1 + x2 ³ 3, x1 £ 3
3 Берілген шектеулерде L(x)=x1 +3x2+ x3 сызықтық форманы минимумдау қажет

x2 + x3 £ 3, x1 - x2 ³ 0 3x1 + x2 £ 15, x2 ³ 1
4 Берілген шектеулерде сызықтық форманы минимумдау қажет

L(x)=3x1 -6x2 + 2x3 3x1 + 3x2 + 2x3 £ 6, x1 + 4x2 +8x3 £ 8


Сиплекс әдісі



Мысал Қойылған шектеулерде: x1 + x4 -2x5 =1, x2 -2x4 + x5 =2, x3+3x4 +x5 =3 сызықтық форманы L = -x4 +x5 минимумде:

Шешу:


Берілген жүйе ұйлесімді, себебі жүйенің матрицасы мен кеңейтілген матрица рангтары бідей және 3-ке тең.




Салдарында үш базистық айнымалыларын қалған екі бос айнымалылары арқылы өрнектеуге болады. Біз x1, x2, x3 айнымалыларды x4, x5 арқылы өрнектейміз:
()
Сызықтық форманы бос айнымалылар арқылы өрнектейміз: L = -x4 +x5 (есептің берілгені бойынша өрнектелген)

Енді x4 =0, x5 =0 мәндеріндегі базистық айнымалылардың мәндерін табайық x1 =1, x2 =2 x3 =3 x4 =0, x5 =0 немесе (1,2,3,0,0). Бұл нүктедегі сызықтық форманың мәні L1 =0.


Енді L форманың мәнін жоғарлатайық. x4 Мәнін өсірсек L мәні азаяды, себебі x4 таңбасы теріс, ал x5 мәнімен бірге форманың да мәні өседі.

x5 мәнін x1 , x2 , x3 мәндері теріс болмайтындай және x4=0 ғылып өсірейік.

() жүйесінің екінші теңдеуінен x5- тің мәнін 2-ге дейін көтеруге болатынын көреміз. Салдарында келесі мәндерге келеміз: x1 =5, x2 =0, x3 =1, x4 =0, x5=2 немесе (5,0,1,0,2). Бұл нүктедегі сызықтық форманың мәні L2=2 яғни өсті. Осы мақсатта жүйенің екінші теңдеуінен арқылы өрнектейміз:

()

L =2 -x2 +x4
L мәнін өсіру үшін x4 мәнін өсірейік. (**) жүйенің екінші теңдеуінен x3 теріс емес шартында x4 -ті x4=1/5 мәніне дейін өсіруге болатынын көреміз. Олай болса жаңа мұмкін шешімі x1 =28/5, x2=0 x3 =0, x4 =1/5, x5 =12/5 немесе (28/5,0,0,1/5,12/5) болады. Сызықтық форма мәні мұнда L3 =11/5.

Келесі қадамда бос айнымалы ретінде x2, x3 алайық. Олар табылған шешімде нөлге тең. x1 , x4 , x5 айнымалылары былай өрнектеледі:



(***)

L = 11/5-(1/5)x3 –(4/5)x2
Соңғы формада айнымалылардың екеуіде теріс таңбамен болғандықтан L дің ең үлкен мәні

xә =0, xі =0 мәндерінде қабылданады. Демек, (28/5,0,0,1/5,12/5) шешімі тиімді болады:

Lmax = 11/5.

Практикалық жұмыс №6

Тасымалдау есебі


Мысал 1. «Солтүстік-батыс» әдісі
A мен B қоймаларында сәйкес 150т және 90т жанармай бар. 1, 2 және 3 тұтынушылат пунктілеріне сәйкес 60, 70 және 110т жеткізу қажет A қоймасынан 1, 2 және 3 пунктілеріне бір тонна жанармайын жеткізу бағасы 6, 10 және 4 жүз тенгеге сәйкес, ал B қоймасынан 12, 2, 8 жүз теңгеге тең. Тасымалдаудың бағасы ең аз болатын тиімді жоспарын құрыңыз.







1

2

3




ai bk

60

70

110

A

150




6




10




4

60




70




20




B

90




12




2




8













90



Алғашкы берілгендерін кестеге толтырайық. Кесте толтыруды (1,1) ұящығынан бастайық : x11 = min (150,60) =60. Бірінші баған толтырылды. (1,2) ұяшығына көшейік: x12 =min{150-60,70}=70, екінші баған толтырылды. (1,3) ұяшығына қойылатын мән:x13 = min{150-60-70, 110} =20.


Ұшінші бағанда қалдығы 90 болғандықтан (2,3) ұяшығын толтырамыз: x23 = min{90,90}=90. Баған мен жол бойынша қалдықтары 0 болғандықтан, бастапқы тірек шешімі табылды. Бұл жоспар бойынша шығындары

L=6*60+10*70+4*20+8*90=1860 теңге болады.
«Солтүстік-батыс» ережесі бойынша cik бағалары ескерілмейді, бұл себептен бастапқы тірек шешімі тиімді шешеімнен алшақтау болады. cik бағасы ескерілетін «Минимальды элементі» әдісін қолданайық.


  1. «Минимальды элементі» әдісі

Бастапқы тірек шешімін іздеу cik мәні ең кіші болатын ұяшықтан басталады. Біздің есепте ол – (2,2) ұяшығы. Мұндағы c22 мәні 2 тең. Осы ұяшыққа x12=min{a2,b2}= min{90,70}=70 мәнін қоямыз.
Баған мен жол бойынша есептелген қалдықтарын, қалдықтар жолында толтырамыз. (1,3) ұяшығындағы мәні 20-дан кейінгі келесі ең кішісі болғнадықтан: c13=4 , осы ұяшықты толтырайық.

x13 =min{a1 –b1 ,b3 }={150-60, 110}=90.
Енді (1,1) ұяшықтағы мәнін табамыз:

x11 =min{a1 ,b1}= min{150,60}=60.
(2,3)-ке x23 =min{ a2 - b2,b3}= min{90-70,110}=20 мәнін қоямыз.
Шешумнің осы нусқасы бойынша бастапқы тірек шешімнің екінші түрін таптық. Мұндағы шығын мәні

L= 66*60 +4*90 +2*70 +8*20=1020 жүз теңге, тиімді жоспарға жақынырақ.







1

2

3




ai bk

60

70

110

A

150




6




10




4

60










90




B

90




12




2




8







70




20










0

0

20.0


60.0
20.0

L=6*60+10*70+4*20+8*90=1860 теңге болады.

Практикалық жұмыс №7

Тасымалдау есебі


Итерациялар тізбегін құру. Потенциалдар ережесі

Мысал. «минимум» ережесі бойынша біз бастапқы тірек шешімін таптық:
x11 = 60, x12 =0, x13 =90, x21 =0, x22 =70, x23 =20, L=1020
Потенциалдарын табу үшін төмендегі жүйені шешу қажет:
u1 + v1 =c11 =6, u1 + v3 =c13 =4, u2 + v2 =c22 =2, u2 + v3 =c23 =8
Айнымалылардың біреуінің мәнін өзіміз алайық, мысалы, u1 =1. Олай болса

v1 =5, v3 =3, u2 =5, v2 =-3.
Енді c'pq үақытша бағасының мәнін табайық.:
c'12 = u1 + v2 = -2, c'21 = u2 + v1 = 10
pq= cpq- c'pq айрымдарының мәндері:
12= c12- c'12 = 10-(-2) 21= c21- c'21 = 12-10 = 2
Салдарында бос айнымлылары арқылы L өрнегінің түрі:
L = 1020+12x12 + 2x21
Оңжақтағы коэффициенттер арасында терісі жоқ. Осы себепте табылған шешімі тиімді болады. Бұл есепте «минимум элементі» ережесі тиімді шешімге келтірді.

Енді бастапқы шешімі «солтүстік –шығыс» ережесі бойынша табылған шартында осы есепті шешейік. Мұндағы


x11 = 60, x12 =70, x13 =20, x23 =90, L=1860
Потенциалдарын табу үшін
u1 + v1 =c11 =6, u1 + v2 =c12 = 10, u1 + v3 =c13 = 4, u2 + v3 =c23 =8
Жүйесін шешу қажет..
u1 =1деп алып, v1= 5, v2 =9, v3 =3, u2 = 5 табамыз
c'pq жанама бағаларын есептейік:
c'21 = u2 + v1 = 10, c'22 = u2 + v2 = 14.
Енді pq= cpq- c'pq айырымдар мәндерін табамыз:
21 = c21- c'21 = 12-10=2, 22= c22- c'22 = 2-14 = -12
Салдарында L бос айнымалылар арқылы өрнектелген түрі:
L= 1860 + 2x21 – 12x22
Оңжақты коэффициенттер арасында теріс мәндері бар. Ол x22-ның коэффициенті. x22 мәнін өсіріп (x21 мәнінің ноль болу шартында) L азайтуға болады. x22= болсын. Багандар мен жолдардағы элементтер қосындысы өзгермейтін шартында төмендегідей баланстық кайта есептеуді жүргізуге болады:


60

70-l………



20+l






:

:

l … …



:

:

……90:- l





x22 -ге l -ның қосылғаны оны x22 -ден алғанымен орны толтырылады; өз кезегінде бұл l -ны x13 -ке косумен және т.с.с. x22 мәніне қайта оралғанымызша. Торларды бір төбесі x22 болатын, ал қалғандарында базистық айнымалылар орналасқан (барлығы болу міндетті емес) пунктир сынықсызық бойымен айналып; біз x22 бос торапқа сәйкестендірілген қайта есептеу цикілына келеміз (сынықсызық цикл аталады). Кестеден l айнымалының оң болу шартында оны l =70-ке дейін өсіруге болады. Олай болса екінші тірек шешімі табылады:


60

0

90

0

70

20


x11 = 60, x12 =0, x13 =90, x21 = 0, x22 = 70, x23 = 20.
Оған сәйке L мәні L=1860 болады. Демек біз тиімді шешімін таптық (жоғарыдағы шешімге қарағанда).

Тапсырмалар:



  1. A мен B қоймаларынның әбірінде 90т–дан жанармай бар. 1, 2 және 3 тұтынушылат пунктілеріне көлемі бірдей жанармай жеткізу қажет. A қоймасынан 1, 2 және 3 пунктілеріне бір тонна жанармайын жеткізу бағасы 1, 3 және 5 жүз тенгеге сәйкес, ал B қоймасынан 2, 5, 4 жүз теңгеге тең. Тасымалдаудың бағасы ең аз болатын тиімді жоспарын құрыңыз.

  2. A, B, C Теміржол станциялары резервінде сәйкес 60, 80, 100 вагондары бар. Төрт астық тиеу пунктілеріне вагондарды жеткізудің тиімді жоспарын құрыңыз. №1 пунктіге 40 вагон қажет, №2–ге 60 вагон, №3–ге 80 вагон, №4–ге 60 вагон қажет болса. Бір вагонды сәйкес пунктіге жеткізу бағалары: А–дан: 1, 2, 3, 4 жүз теңге, В–дан: 4, 3, 2, 0, С–дан: 0, 2, 2, 1 жүж теңге болса,



Практикалық жұмыс №8


Берілген функциялардың минимумын табу.

1. ,


Тапсырманы орындауға әдістемесі. функцияның [a,b] кесіндісінде алтын қима әдісін қолданып минимумын табу. а және b мәндерін қолданушы өз еркімен енгізетіндей бағдарлама құр.

Mathcad қолданып функция графигін сызып, минимум нүктелерін графиктен көреміз.

Қорытындыны Excel-де тексер.



Екеуінің графиктері бердей, осыдан функция бір минимумы бар екенін көруге болады. Минимум болу кесіндісі [-1;1].

Жасалынған бағдарлама мысалы. .


Excel-де шығарылған қорындысы.



Mathcad пакетінде бір айнымалысы бар функцияның минимумын табу.

Функцияны оңтайландырғанда миинмумның жуық мәндерін көсету қажет. Бұл жуық мәндерді функцияның графигінен көруге болады. Алдымен cos(x)/x функцияның графигін саламыз.



  • Жұмыс өрісінің жоғарғы жағында функция аргументі диапазонын анықтайтын суретте көрсетілген формуланы енгіз.

  • Enter батырмасын бас

  • Суретте көрсетілгендей функция графигін сал.

Графигтен функцияның х=5 маңайында минимумы бар екенін көреміз.

  • Enter батырмасын бас

Енді функция минимумын табамыз.

  • Суретте көрсетілген формуланы енгіз. Берілген функция минимизациялауға болатын жаңа функция тудырады.

  • Enter батырмасын бас

  • Формуласын енгіз. Бұл формула айнымалыға – функция аргументіне минимум 5 жуық мәндерін меншіктейді.

  • Enter батырмасын бас.

  • Клавиатурадан Minimize(f,y) тер. Ендірілген Minimize функциясы f функция минимумға жеткендегі айнымалы у мәнін анықтайды.

  • Calculator саймандар тақтасындағы = батырмасын бас. Экранда енгізілген функция минимумы көрсетіледі.

Практикалық жұмыс 9.

MS Excel қолданып функцияның минимумын және максимумын тауып графигін салу әдістемесі.











Функцияның шартсыз экстремумдарын табу үшін электронды таблица бетін ашамыз. Функцияны А2 ұяшығына жазамыз.

Минимумды табу үшін келесі іс-“әрекет тізбегін орындау қажет:

1. Сервис/Поиск решения…(1 суреттегідей).

2.Терезені толтыру Поиск решения…(2суреттегідей)

2.1.Өрісте тышқанның сол жағын шерту. Установить целевую ячейку и щелкнуть на ячейке с формулой, в нашем случае это ячейка А2, абсолютный адрес которой. $А$2 появится в поле.

2.2. Минималды мән өрісін таңдау.

2.3. В поле. Изменяя ячейки ввести адреса ячеек, значения которых будут варьироваться в процессе поиска решения. В нашем случае это клеикаА1, абсолютный адрес которой. $А$1.

После выполнения пунктов 1-2 лист электронной таблицы будет выглядеть так, как показано на рис 21.

После щелчка на кнопке Выполнить получим решение поставленной задачи. В клетке А1 находится значение переменной Х равное 0.769231 при котором функция (5 ) достигает минимального значения равного –167,692. Рис22


Практикалық жұмыс №10


Қадамы тұрақты градиенттік түсіру әдісі
Есептің қойылымы

Rn жиынында анықталған, шектеулі және Rn-ның барлық нүктелерінде дифференциалданатын f(x) функциясы берілсін.

Барлық мүмкін шешімдер жиынында X= Rn оның локальді минимумын табу қажет: шарты орындалатын x* Rn нүктесін.
Шешімді табу стратегиясы

Есептің шешімін табу үшін шартын f(xk+1)k), k=0,1,.. қанағаттандыратын {xk}, k=0,1,2,… нүктелер тізбегін құруда тұрады.

Тізбектің нүктелерін

xk+1 = xk – tk f(xk), k=0,1.2….

формула бойынша табамыз. Мұндағы x0 мәнін өзіміз таңдаймыз, Ñf(xk) - xk нүктесіндегі f(x) функциясының градиенті, tk қадамын қолданушы қояды. Оның мәні функция кемімелі болып тұрғаныда тұрақты, ал бұл шарт кейбір қадамда бұзылса оның мәнін өзгертеміз. Функцияның кему жағыдайы f(xk+1)- f(xk)<0, шартының орындалуымен бақыланады немесе f(xk+1)- f(xk)<-, 0<e<1. {xk} тізімін құру үрдісі <e1 шарты қанағаттандырылатын xk нүктесінде тоқтатылады. Мұндағы e1 алдынала берілген кейбір аз шама. Немесе итерацияны төменгі шарты орындалғанда тоқтатамыз:


M- итерациялардың шекті саны болса, kM болған жағдайда немесе 2 аз шама үшін төменгі екі шарт қатар орындалса:

Табылған xk мәні минимум нүктесінің жуықтауы болуы не болмауы қосымша зерттеуді талап етеді.


Мысал: f(x)=2x12 + x1 x2 +x22 функцияның локальді минимумын табу.


  1. итерацияны тоқтатудың тым болмаса бір критериі орындалатын xk нүктесін табу.

  1. x0 , e1 , e2 , M мәндерін алдын ала таңдап алайық; x0 =(0,5; 1), e1 =0,1: e2 = 0,15, M=10. Кез келген нүктедегі функциянвң градиенті:

f(x) = (4x1+x2 ; x1+2x2).

  1. k=0 болсын.

30 Ñf(x0) есептейік: Ñf(x0)=(3; 2,5).

40 есептейік; = 3,9 > 0,1 5 қадамға көшеміз.

50 kM шартын тексерейік: k=0 <10=M. 6 қадамға көшейік.

60 t0 =0,5 мәнін берейік.

70 x1 мәнін есептейік: x1 = (0,5; 1) – 0,5(3;2,5)= (-1; -0,25); f(x1)= 2,31.

80 f(x1) мен f(x0) = 2 мәндерін салыстырайық. f(x1)>f(x0) болады. Қортынды: f(xk+1)k) шарты k = 0 мәні үшін орындалмады,. t0 =0,25 мәнін беріп 7, 8 қадамдарына көшеміз.

701 x1 мәнін есептейік: x1 = (0,5; 1)- 0,25(3; 2,5) = (-0,25; 0,375); f(x1) = 0,171

801 f(x1) мен f(x0) мәндерін салыстырып, f(x1) < f(x0) шарты орындалатынын көреміз. 9 қадамына көшеміз.

90 мен мәндерін есептейік:

=0,976>0,15; =1,829>0,15

Қортынды: k=1 деп 3 қадамына көшеміз.

31 Ñf(x1) мәнін есептейік: Ñf(x1)=(-0,625; 0,51).

41 мәнін есептейік:=0,81. 5 қадамға көшеміз.

51 kM шартын тексерейік: k=1<10=M. 6 өадамға көшеміз.

61 t1=0,25 болсын.

71 x2 есептейік: x2=(-0,25; 0,375) – 0,25(-0,625; 0,25)=(-0,094; 0,25); f(x2)-0,056

81 f(x2) мен f(x1) салыстырайық. Қортынды: f(x2)< f(x1). 9 қадамға көшеміз.

91 мен есептейік;

=0,2>0,15; =0,115<0,15

Қортынды: k=2 деп 3 қадамына көшеміз.

32 Ñf(x2) мәнін есептейміз: Ñf(x2) = (-0,126; 0,406)

42 есептейік: = 0,425>0,1. 5 қадамға көшейік.

52 k M шартын тексеріп: k = 2 < 10=M, 6 қадамға көшеміз.

62 t2=0,25 деп

72 x3 мәнін табайық: x3 = (-0,094; 0,25) – 0,25(-0,126; 0,406) = (-0,063; 0,15); f(x3) = 0,021

82 f(x3) пен f(x2) мәндерін салыстырайық: f(x3) < f(x2) қортып 9 қадамға көшеміз.

92 пен мәндерін есептейміз:

= 0,105<0,15; = 0,035 < 0,15

Қортынды: k=3 деп 3 қадамға көшеміз.

33 Ñf(x3): Ñf(x3) = (-0,102; 0,237)

43 есептейік: = 0,257 > 0,1

53 k M шартын тексереміз: k = 3 < 10 =M, 6 қадамына көшеміз

63 t3 = 0,25.

73 x4 есептейік: x4= (-0,063; 0,15) – 0,25(-0,102; 0,237) = (-0,038; 0,091);

f(x4) = 0,0076

83 f(x4)мен f(x3) салыстырамыз: f(x4) < f(x3)

93 , есептейміз:

= 0,064 < 0,15; = 0,015 < 0,15
шарттары k= 2,3 мәндері үшін орындалды; есептеуді тоқтатамыз.

x4 = (-0,038; =0,091) нүктесі табылды; f(x4) = 0,0076


  1. x4 нүктесін зерттеу.

f(x)=2x12 + x1 x2 +x22 функциясы екі рет дифференциалданады, сонықтан x4 нүктесіндегі минимумның жеткілікті шартын тексерейік.

Ол үшін Гессе матрицасын зерттейміз:



H=. Матрица тұрақты және де оңмәнді (H>0), себебі, оның бұрыштық минорлары оңтаңбалы: 1 = 4 2 = 7. Салдарында x4= (-0,038; =0,091) локальді минимум нүктесінің жуықтауы, ал f(x4) = 0,0076 мәні локальді минимум f(x*)=0 мәнінің жуықтауы болады.

ӘДЕБИЕТТЕР ТІЗІМІ


Негізгі әдебиеттер

  1. Н.Н. Калиткин. Численные методы. - М.: Наука, 1978.

  2. И.С. Бахвалов. Численные методы. - Ч.1, - М..: Наука, 1973.

  3. Л.И. Турчак. Основы численных методов. -М.: Наука, 1987. -320с.

  4. В.М. Монахов и другие. Методы оптимизации. Применение математических методов в экономике. Пособие для учителя. - М.: Просвещение, 1978. - 175 с.

  5. В.М. Заварыкин. Численные методы. – М.: Просвещение, 1990. – 176с.

  6. Г.И. Воробьева, А.И. Данилова. Практикум по численным методам. - М., Наука, 1979.

Қосымша әдебиеттер

  1. И.Л. Акулич. Математическое программирование в примерах и задачах. – М.: Высш. шк., 1986. – 319 с.

  2. Вагнер Г. Основы исследования операций. В 3-х томах. Мир, 1972-1973

  3. Таха Х. Введение в исследование операций. В 2-х томах. Мир, 1985г.

  4. Куралбаев З.К. Решение задач по математическому программированию

  5. Протасов И.Д. Теория игр в исследований операций. Москва, «Гелиос АРВ», 2003г.

  6. Исследование операций в экономике. Под редакцией профессора Н.Ш. Кремера, ЮНИТИ, Москва, 2000

  7. Н. Культин. Программирование на Object Pascal в Delphi 5. Спб, БХБ. - Санкт-Петербург, 1999.

  8. Фаронов В.В. Турбо Паскаль 7.0 Учебный курс. -М., 1998. -433 с.

  9. Фаронов В.В. DELPHI 4. Учебный курс. - М., 1999. - 464 с.

  10. Электронные учебники по языкам программирования.

  11. Численные методы и задачи оптимизации. /под ред. В.Н. Игнатьева, Г.Ш. Фридмана. - Томск: Томского ун-та, 1983. - 165 с.

  12. Е.С. Вентцель. Исследование операций. Задачи, принципы, методология.- М.: Наука, 1980г.



с. 1

скачать файл