Нұсқаулар Форма ф со пгу 18. 2/05

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

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

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

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

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

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

1.

2.

3. x⁴-14x³+60x²-70x

4) –e^-xln(x)

5) 2x²-e^x

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

Қандай да бір 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 пункке көшеміз.
   

Блок схема

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

F₀ = F₁ = 1, F_k = F_k-1 + F_k-2 , k = 2, 3, 4,…

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

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

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

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

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

2. Фибоначчи сандары: F₀ = F₁ = 1, F₂ =2, F₃ = 3, F₄ = 5, F₅ = 8, F₆ = 13.

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

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

y₀ = a₀ + (b₀ – a₀ ) = 0 + ∙10 = 3,846; z₀ = a₀ + (b₀ – a₀ ) = 0 + ∙10 = 6,154.

5⁰. f(y₀) = -16,57; f(z₀) = 1,893.

6⁰ . f(y₀) < f(z₀) болғндықтан a₁ = a₀ = 0; b₁ = z₀ = 6, 154; y₁ = a₁ + (b₁ – a₁ ) =

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

z₁ = y₀ = 3,846.

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

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

5¹. f(y₁) = -17,04; f(z₁) = -16,57 мәндерін ессептеп салыстырайық:

6¹. f(y₁) < f(z₁) болғандықтан a₂ = a₁ = 0, b₂ = z₁ = 3,846;

y₂ = a₂ + (b₂ – a₂ ) = 0 + ∙3,846 = 1,536; z₂ = y₁ = 2,308.

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

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

5² . f(y₂) = -13,73; f(z₂) = -17,04

6². f(y₂) > f(z₂) болғандықтан a₃ = y₂ = 1,538, b₃ = b₂ = 3,846; y₃ = z₂ = 2,308;

z₃ = a₃ + (b₃ – a₃) = 1,538 + ∙ (3,846 – 1,538) = 3,077.

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

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

5³. f(y₃) = f(z₂) = -17,04; f(z₃) = -17, 9884.

6³. f(y₃) > f(z₃) болғандықтан

a₄ = y₃ = 2,308, b₄ = b₃ = 3,846; y₄ = z₃ = 3,077;

z₄ = a₄ + (b₄ – a₄) = 2,308 + ∙ (3,846 – 2,308) = 3,077.

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

y₅ = y₄ = z₄ = 3,077; z₅ = y₅ + ε = 3,077 + 0,01 = 3,087.

f(y₅) = -17,9884; f(z₅) = -17,985. f(y₅) < f(z₅) болғандықтан a₅ = a₄ = 2,308, b₅ = z₅ = 3,087.

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

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

б) –e^-xln(x)

в) 2x²-e^x

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

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

1. 
   [a,b] бастапқы кесіндіні қарастырайық және кесіндінің ортасы табылады x_k=(a+b)/2.
   
2. 
   Екі қосымша нүктелер алынады x_k+x_k*/2 және x_k-x_k*/2, мұндағы  - салыстырмалы қателік.
   
3. 
   Функцияның мәндерін салыстырамыз. Егер f₀(x_k+x_k*/2)>f₀(x_k-x_k*/2), онда k+1-нші итерация үшін a_k+1=a_k b_k+1=x_k. Егер f₀(x_k+x_k*/2)0(x_k-x_k*/2), k+1-нші итерация үшін a_k+1=x_k b_k+1=b_k.
   
4. 
    - титерация дәлдігі, онда итерациялық процесс b_k-a_k*x болғанда аяқталады.
   

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

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

4⁰ f(y₀)< f(z₀) болғндықтан, a₁ =a₀ =0, b₁ =z₀ =5,1 болады.

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

3¹ y_1, z₁ есептейік:

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

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

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

60	70-l……… 	20+l 
	: : l … …	: : ……90:- l

60	0	90
0	70	20

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

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 батырмасын бас
  
• 
  Суретте көрсетілгендей функция графигін сал.
  

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

• 
  Суретте көрсетілген формуланы енгіз. Берілген функция минимизациялауға болатын жаңа функция тудырады.
  
• 
  Enter батырмасын бас
  
• 
  Формуласын енгіз. Бұл формула айнымалыға – функция аргументіне минимум 5 жуық мәндерін меншіктейді.
  
• 
  Enter батырмасын бас.
  
• 
  Клавиатурадан Minimize(f,y) тер. Ендірілген Minimize функциясы f функция минимумға жеткендегі айнымалы у мәнін анықтайды.
  
• 
  Calculator саймандар тақтасындағы = батырмасын бас. Экранда енгізілген функция минимумы көрсетіледі.
  

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

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

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

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

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

x^k+1 = x^k – t_k f(x^k), k=0,1.2….

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

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

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

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

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

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

f(x) = (4x₁+x₂ ; x₁+2x₂).

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

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

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

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

6⁰ t₀ =0,5 мәнін берейік.

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

8⁰ f(x¹) мен f(x⁰) = 2 мәндерін салыстырайық. f(x¹)>f(x⁰) болады. Қортынды: f(x^k+1)^k) шарты k = 0 мәні үшін орындалмады,. t⁰ =0,25 мәнін беріп 7, 8 қадамдарына көшеміз.

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

8⁰¹ f(x¹) мен f(x⁰) мәндерін салыстырып, f(x¹) < f(x⁰) шарты орындалатынын көреміз. 9 қадамына көшеміз.

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

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

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

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

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

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

6¹ t₁=0,25 болсын.

7¹ x² есептейік: x²=(-0,25; 0,375) – 0,25(-0,625; 0,25)=(-0,094; 0,25); f(x²)-0,056

8¹ f(x²) мен f(x¹) салыстырайық. Қортынды: f(x²)< f(x¹). 9 қадамға көшеміз.

9¹ мен есептейік;

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

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

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

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

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

6² t₂=0,25 деп

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

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

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

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

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

3³ Ñf(x³): Ñf(x³) = (-0,102; 0,237)

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

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

6³ t₃ = 0,25.

7³ x⁴ есептейік: x⁴= (-0,063; 0,15) – 0,25(-0,102; 0,237) = (-0,038; 0,091);

f(x⁴) = 0,0076

8³ f(x⁴)мен f(x³) салыстырамыз: f(x⁴) < f(x³)

9³ , есептейміз:

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

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

2. 
   x⁴ нүктесін зерттеу.
   

f(x)=2x₁² + x₁ x₂ +x₂² функциясы екі рет дифференциалданады, сонықтан x⁴ нүктесіндегі минимумның жеткілікті шартын тексерейік.

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

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

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

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

1. 
   Н.Н. Калиткин. Численные методы. - М.: Наука, 1978.
   
2. 
   И.С. Бахвалов. Численные методы. - Ч.1, - М..: Наука, 1973.
   
3. 
   Л.И. Турчак. Основы численных методов. -М.: Наука, 1987. -320с.
   
4. 
   В.М. Монахов и другие. Методы оптимизации. Применение математических методов в экономике. Пособие для учителя. - М.: Просвещение, 1978. - 175 с.
   
5. 
   В.М. Заварыкин. Численные методы. – М.: Просвещение, 1990. – 176с.
   
6. 
   Г.И. Воробьева, А.И. Данилова. Практикум по численным методам. - М., Наука, 1979.
   

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

7. 
   И.Л. Акулич. Математическое программирование в примерах и задачах. – М.: Высш. шк., 1986. – 319 с.
   
8. 
   Вагнер Г. Основы исследования операций. В 3-х томах. Мир, 1972-1973
   
9. 
   Таха Х. Введение в исследование операций. В 2-х томах. Мир, 1985г.
   
10. 
    Куралбаев З.К. Решение задач по математическому программированию
    
11. 
    Протасов И.Д. Теория игр в исследований операций. Москва, «Гелиос АРВ», 2003г.
    
12. 
    Исследование операций в экономике. Под редакцией профессора Н.Ш. Кремера, ЮНИТИ, Москва, 2000
    
13. 
    Н. Культин. Программирование на Object Pascal в Delphi 5. Спб, БХБ. - Санкт-Петербург, 1999.
    
14. 
    Фаронов В.В. Турбо Паскаль 7.0 Учебный курс. -М., 1998. -433 с.
    
15. 
    Фаронов В.В. DELPHI 4. Учебный курс. - М., 1999. - 464 с.
    
16. 
    Электронные учебники по языкам программирования.
    
17. 
    Численные методы и задачи оптимизации. /под ред. В.Н. Игнатьева, Г.Ш. Фридмана. - Томск: Томского ун-та, 1983. - 165 с.
    
18. 
    Е.С. Вентцель. Исследование операций. Задачи, принципы, методология.- М.: Наука, 1980г.
    

жүктеу/скачать 272.41 Kb.

Достарыңызбен бөлісу: