Т оптимизация әдістері пәнінен практикум

ББК 22.18

А13

Авторлары:

Абатов Н.Т, ф.м.ғ к, доцент

Кудубаева С.А., т.ғ.к, А.Байтұрсынов атындағы ҚМУ электроника және есептеуіш техника кафедрасының меңгерушісі

Жунусов К.М., э.ғ.к, А.Байтұрсынов атындағы ҚМУ ақпараттық жүйелер кафедрасының меңгерушісі

Калаков Б.А, ф.м.ғ.к, З.Алдамжар атындағы ҚӘТУ деканы

А13. Абатов Н.Т., Серкебаева Л.Т

Тиімді әдістер. Практикум. Қостанай: А.Байтұрсынов атындағы ҚМУ, 70 бет.

Берілген практикум «Оптимизацяи әдістері» пәнінің тақырыптарын қарастырады. Практикум құрамына аталған тақырыптар бойынша қысқаша теориялық деректер, есептер, олардың MS Excel, MatCad программалары арқылы шешімдері қарастырылған, сонымен қатар өзіндік тапсырмалар, тест сұрақтары берілген.

«Ақпараттық жүйелер» мамандығы бойынша оқитын студенттерге арналған.

ББК 22.18

А.Байтұрсынов атындағы ҚМУ оқу-әдістемелік кеңесінің отырысында бекітілген, хаттама № ___, ___.___.2010 ж.

© А.Байтұрсынов атындағы

Қостанай мемлекеттік университеті

МАЗМҰНЫ

Кіріспе

Зерттеуге жататын әлеуметтік-экономикалық процесті немсе құбылысты белгілі бір математикалық өрнектер түрінде бейнелеу дегеніміз сол процестің немесе құбылыстың математикалық моделін құру деген сөз.

Қазіргі таңда математикалық модель қоғамның әр саласында талдау, болжау және тиімді шешім құру үшін пайдаланады.

Оптимизация – барлық мүмкін шешімдер арасында ең тиімді шешімді таңдау.

Егер де таңдау критериі белгілі болып және нұсқалары көп болмаса, тиімді шешім барлық шешімдерді салыстыру бойынша табылады. Бірақ көбінесе нұсқалардың саны көп болады, бұл жағдайда шешімдерді салыстуры ыңғайсыз. Сондықтан есептің математикалық моделін құрастырып, оның тиімді шешімін табу әдістерін іздестіру.

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

Математикалық әдістерді пайдалану үшін, ең алдымен, тиімді шешімін таппақшы болған есептің өзінің қойылымын жазуымыз қажет. Математикалық қойылымда берілген ресурстар, өңдірістік технология, қорытынды шешімдер және олардың арасындағы байланыстар математикалық өрнектер, теңсіздіктер арқылы көрсетіледі.

Берілген практикумда оптимизациялық есептер қойылымдарының математикалық модельдері және олардың шығару жолдарының әдістері қарастырылған, яғни сызықты программалау есептері және сызықты емес программалау есептері.

Аталған тақырыптар бойынша теориялық және тәжірибелік негіздері, типтік есептердің шешімдері, бақылау сұрақтары, тест тапсырмалары қарастырылған.

Тақырып 1. Сызықты программалау
Негізгі ұғымдар
Анықтама 1.

СП жалпы есептері деп төмендегі шарттарды қанағаттандыра отырып, мақсатты функциясына максимум не минимум мән табылатын есепті айтады.

a_ijx_j=b_i (i=1+k,m) (1)

a_ijx_j≥b_i (i=1,k)

x_j≥0 j=1,n (2)

F=C_jx_j→extr (3)

Егер (1) шектеу шартында теңсіздік a_ijx_j≤b_i , (i=1,n) немесе a_ijx_j≥b_i (i=1,m) болса онда СПЕ стандартты түрде берілген деп есептелінеді. Егер СПЕ мына түрде берілген болса, F=C_jx_j→max, (i=1,m), x_j≥0 j=1,n болады.

Егер жүйелер шарты теңдік түрінде берілетін болса, онда есепті негізгі түрде берілген деп есептейміз.

Анықтама 3.

СПЕ-нің (1)-сі - шектеулер жүйесі (2)-сі - теріс емес шарты (3)-сі - мақсатты функци деп аталады.

1. 
   Жалпы формасы:
   

шектеулері

aijxj≤bi (i=1,m)

aijxj=bi (i=m1+1, m2)

aijxj≥bi (i=m2+1, m)

xj≥0 (j=n1+1,n)

2. Симметриялық формасы:

max F=cjxj min F==cjxj

aijxj≤bi (i=1,m) aijxj≥bi (i=1,m)

xj≥0 (j=1,n) xj≥0 (j=1,n)

3. 
   Негізгі формасы:
   

aijxj=bi (i=1,m)

xj≥0 (j=1,n)

Сызықты программалау есептері әр формаларда жазулы мүмкін, бірақ оларды негізгі формасына келтіруге болады. Ол үшін F мақсатты функциясын максималдау қажет және барлық шектеулер теріс емес айнымалылары бар теңдіктер ретінде жазылуы тиіс. Сызықты программалау есептері негізгі формасына келесі ережелер бойынша келтіріледі:

1. 
   F мақсатты функцияның минималдауы мақсатты функцияның максималдауына сәйкес (-F).
   
2. 
   ≥ түрлі теңсіздіктердің сол және оң жақтары -1 санына көбейтіледі, осылайша олар ≤ түрлі теңсіздіктерге аударылады және керісінше
   
3. 
   ai1x1+ai2x2+…ainxn (≥немесе≤) bi түрлі шектеулер теңсіздіктер шектеулер теңдіктерге сол жақтарына қосымша баланстық айнымалылар қосылып (алынып) аударылады
   
4. 
   егер сызықты программалау есебінде берілген айнымалылардың Х біреуі теріс емес шартына сәйкес келмесе, онда оны басқа екі теріс емес айнымалылардың айырмашылығымен ауыстырады.
   

min Z=6x₁+5x₂

5x₁+11x₂≥55

x₁+x₂ ≥8

11x₁+3x₂ ≥32

16x₁+13x₂≤210

17x₁+12x₂≤205

x₁ ≥0, x₂≥0

Z функциясың Z^I – Z функциясына ауыстырамыз. ≥ түрлі шектеулердің сол жақтарынан х3,х4,х5 теріс емес айнымалыларын аламыз, ≤ түрлі шектеулердің сол жақтарына х6,х7 теріс емес айнымалаларын қосамыз.

max Z=-2x₁-x₂-x₃+2x₄+x₅

-2x₃-x₄+x₅=4

-x₂+4x₃+2x₄=8

x₁+x₃+x₄=6

x_j≥0 (j=1,5)

Шектеулер-тендіктерден 3 айнымалыны аламыз. Берілген мысалда 1 шектеуден х5, екінші шектеуден х2, үшінші шектеуден х1 айнымалыларын алу ыңғайлы. Айнымалылардың теріс емес шартын пайдалана отырып, келесі шектеулерді анықтаймыз:

х₅=4+2х₃+х₄≥0

х₂=-8+4х₃+2х₄≥0

х₁=6-х₃-х₄≥0

х5,х2,х1 айнымалыларын түсіріп, эквивалентті теңсіздіктерге жетеміз. х5,х2,х1 мақсатты функцияға енгізіп,

max Z=-2х1-х2-х3+2х4+х5= -2*(6-х3-х4)-(-8+4х3+2х4)-х3+2х4+(4+2х3+х4)=

-12+2х3+2х4+8-4х3-2х4-х3+2х4+4+2х3+х4=-х3+3х4,

сызықты программалау есебінің симметриялық формасын анықтаймыз:

max Z=-x₃+3x₄

-2x₃-x₄≤4

4x₃+2x₄≤-8

x₃+x₄≤6

x₃≥0, x₄≥0

Сызықтық программалаудың негізгі есебі түрінде келесі есепті жазамыз:

шарттары: