ПӘннің ОҚУ-Әдістемелік кешені «Технологиялық процесстерді оңтайландыру әдістері»



бет63/95
Дата18.12.2019
өлшемі5,43 Mb.
#53747
1   ...   59   60   61   62   63   64   65   66   ...   95
Байланысты:
21ad3594-56e4-11e5-884b-f6d299da70eeУМК новое по МОТП каз (умм)


Теорема. Егер сызықты прграммалаудың бастапқы есебінің Х* тиімді жоспары бар болса, онда Y*= Сб P-1 қосалқы есептің тиімді жоспары болып табылады.

Осылайша, егер симплекс әдісімен (40)-(42) есептің тиімді жоспарын тапсақ, онда соңғы симплекс кестесін пайдалан отырып, Сб мен P-1 анықтауға болады және Y*= Сб P-1 қатынасының көмегімен (43), (44) қосалқы есебінің тиімді жоспарын табуға болады.



(41) теңдеу жүйесінің белгісіздер коэффициенттерінен құралған P1, P2,…, Pn векторларының арасында m бірліктері болған жағдайда, көрсетілген P-1 матрицасын соңғы симплекс-кестесінің берілген векторларының бағаналарында тұрған бірінші m жолындағы сандар құрады. Осы жоспардың компоненттері бірлік векторының бағанының (m+1)-ші жолының сәйкес элементтерімен сәйкес болғандықтан, қосалқы есептің тиімді жоспарын Сб-ні P-1-ге көбейту арқылы анықтаудың қажеті жоқ.. Егер берілген коэффициент cj=0 және осы жолдың сәйкес элементінің қосындысына және cj қосындысына тең, егер cj 0.

Жоғарыда айтылғанымыз қосалқы есептің интерпритациялық жұбында да орын алады. Бастапқы есептің жүйесінің шектеулі теңсіздік түрі болғандықтан, бастапқы есептің соңғы симплекс кестесінің шешімі, қосалқы есептің тиімді жоспарының компоненті жолының (m+1) сандарымен сәйкес келеді. Көрсетілген сандар векторлық бағаналарда, қосымша айнымалыларға сәйкес келеді.


Өзін-өзі тексеру сұрақтары немесе тестер

  1. Математикалық программалаудың жалпы тапсырмасы?

  2. Тұрман (седловая) нүкте және қос қабаттылық әдістері.


Дәріс №11. Сызықты программалаудың негiзгi теоремалары.

Сұрақтар:

  1. Теоремалар.

  2. Геометриялық интерпретация симплекс-әдiсі

1.Теоремалар

Сызықты программалаудың негiзгi теоремаларын қарастырудан бұрын, сызықты алгебралық курста қаралатын ұғымдарды есiмiзге түсiремiз.

Базистік шешіммен (тiрек ) m жүйелердің сызықты теңдеулері п айнымалы теңдеуі деп, барлық жүйелерi (n-m ) дағы негiзгi емес айнымалыға тең нөл шешiмін айтамыз.

Базистiк шешiмдердiң саны түпкi болып табылады, өйткенi ол негiзгi топтарды Cm n аса басым түспейтiн санға айнымалы тең болады.

Негiзгi айнымалы тең азғындалған нөлдердiң бiрi базистiк шешiм деп аталады.



Теорема. Егерде сызықты бағдарламаның есебінің оптималды шешімі болса, онда сызықтық функция осылардың бірінің максималды мәнін алады.

(Шектеулі областағы оптимальды шешім туралы). Теорема. Егерде облыста түсетін шешімдер жүйелері шектелген болса, онда ұйғарымды шешім болады және сондағы шешім жүйесінің біреуімен дәл келеді.

(Шектеусіз областағы оптимальды шешім туралы теорема). Теорема. Егерде облыста түсетін шешімдер жүйелері шектелген болса, онда оптималды шешім, кем дегенде, тірек шешімдердің бірінде бар болады, максимизацияның есебi үшiн үстiнде шектелуге немесе минимизациялауды есеп үшiн астыдан дәл келетiн ұтымды шешiм болады.

(Іргелі). Теорема. Егер сызықты программалауды есеп (шектелген облыста әрдайым, шексiз облыста сызықты мiндеттiң өресiздiгiне байланысты) ұтымды шешiмi болса, онда ол кем дегенде, шектеушi теңдеулердiң жүйесiнiң тiрек шешiмдерiнiң бiрімен дәл келеді.

Талғаулы ұтымдылық туралы. Теорема. Егер сызықты мiндеттiң максимум немесе минимумы бiрнеше тiрек шешiмдерге жетсе, онда кез келген ұтымды шешiм ұтымды шешiмдердiң дөңес сызықты комбинациясында бар болады.
2 Геометриялық интерпретация симплекс-әдiсі

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

Осы негiзде келесi маңызды схемаға апарған сызықты программалауды есептiң шешiмiнiң әдiсi тұрып қалу жеткiлiктiгін ұсынуға болады:


  • жиының түпкi шешімдерін (көп жақтың нүктесi) барлық тiрек шешiмдер табу керек;

  • әрбір тірек шешімдері үшін мақсаттық функцияның мәнiн есептеу.

  • мақсаттық функцияның түпкі шешімдерінің оптимальды мәндерін салыстыру(максимал және минимал).

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

Егер тiрек шешiмдерiнiң көрcетiлген асып кетуi мақсаттық функцияның мәнi (немесе, кем дегенде, нашарлатпай) жақсарта өндiрiп алу бағытталған болса, онда елеп-екшелетiн тiрек шешiмдердiң саны адымдардың санының тiптi маңызды қысқартуына мақсаттық функцияның ұтымдылығының iздеп табуында ақыр соңында алып келгенiн кенет қысқартуға болады, яғни адымдардың әрқайсыларына. Осы сызбаны қолдану ережесіне байланысты, біріншісіне қарағанда, әр қайсысы түпкі шешімі алдынғысынан жаксысын таңдайды, сол себепті әп қадамда мақсаттық функцияның мәні жақсарады.

Іргелі универсалдың әдістің шешімі немесе бағдарламасы, симплекс – әдісі болады, немесе бағытталған асып кету әдiсі болып табылады.(Латынша симплекс – қарапайым деген мағына береді, ал осы жағдайда қарапайым дөңес көп жақ болады.)

Геометриялық интерпретация симплекс-әдiс (көршi төбелердiң бiрге бастапқы таңдаулы төбесiнен, соған атап айтқанда, сызықты мiндетте ең жақсы қабылдайтын немесе кем дегенде, жарамсызы емес мән) басқаға көп жақтың бiр төбесiнен бiртiндеп өткелде тұрады. Бұл процесс оптималды шешім төбеге жеткенде,ондағы оптималды мән функцияға жеткенше дейін ғана жүреді(есепте егер түпкi ұтымдылық болса).

Симплекс – әдісі орыстың ғалымы Л.В. Канторовичтің идеясымен 1939 ж. жасалған. Осы идеяға қарап америка ғалымы Д. Данциг сызықты бағдарламаның кез келген есебін шешуге болатын симплекс - әдісін 1949 ж. Жасады.

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


Өзін-өзі тексеру сұрақтары

  1. Сызықты алгебраның негізгі элементтері. Моделді құрудағы атқаратын ролі.

  2. Моделдердің сезімталдығына анализ жасау. Модел түрлері.



Дәріс №12. Сызықты бағдарламаның екі жақты есептері.

Сұрақтар:

  1. Төте есеп

  2. Екі жақты есеп

1.Төте есеп



Сызықты бағдарламаның ортаңғы және мәнді орны екі жақты есеп болып келеді, сол себепті алғашқы есепте негізгі функция максимумға ұмтылады (минимумға):

F = c1,x1,+с2х2+с3х3+... + сnхn ->max(min), (1)

Функционалды жүйелер шектеулігі өзіне теңсіздіктер жүйесін қосады:

(2)
Тікелей шектеулер жүйесі сондай-ақ өзіне теңсіздіктер жүйесін қосады: : (3)

Екі жақты тапсырманы қамтиды, мұндағы:

· жүйелік функкция минимумға талпынады (максимумға):



Z(y) = y1,b1, +y2b2+...+ ymbm -»min(max) (4)

· функционалды жүйелер шектеулігі өзіне теңсіздіктер жүйесін қосады:



(5)

• сондай-ақ тікелей шектеуліктер жүйесі өзіне теңсіздіктерді қосады:



у1 ³0,У 2 ³0,Уз ³0...У m ³0. (6)

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

Сонымен қатар, екі тапсырмада да бірдей параметрлер қолданылады:

А матрицасының элементтері,В векторы, С векторы.

Тікелей және екіжақты тапсырмалардың айырмашылығы, тікелей тапсырмалар n белгісінің x1,x2,...,xn, айнымалыларымен анықталады, ал екіжақты тапсырмалар — m айнымалысының: y1, y2,, ym белгілерімен айқындалады. Нәтижелі тапсырмада максимум ізделінеді, ал екіжақты тапсырмада –толық фнункцияның минимум ізделінеді, бұл тапсырмаларда теңсіздіктер белгілері қарам-қарсы болады, векторлардың шектеулік коэффициенті бір тапсырмада айнымалы болғанда, толық функцияда айнымалылар коэффициенті бола алады.

Берілген тікелей тапсырман екіжақты тапсырмаға айналдыру үшін, белгілі бір формальды тәртіп жүйесін қолданған жөн.


2.Екі жақты есеп

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



2. Егер тікелей тапсырма максимализация тапсырмасы ретінде берілсе, онда екіжақты-минимализация немесе керісінше түрінде беріледі.

3. Функционалды шектеуліктер векторының құраушылары В=(bi,b2,...bm) тікелей тапсырмада екіжақты тапсырма жүйелік функциясы бола алады.

Осы үш ережені қолдану екіжақты тапсырманың тапсырмасын айқындауға мүмкіндік береді.



Z(y) = y1 b1 + у2b2 +...+ yrabm -> min .

4. Екіжақты функционалды жүйе матрицасының айнымалы жүйесінде тапсырма матрицаның тасымалдану коэффициентімен функционалдық жүйе негізінде айқындалады-

5. Тікелей тапсырмада функционалды шектеуліктер белгісі екіжақты тапсырмаға кері жаққа өзгереді яғни, « £» -------- «³ » өзгереді. .

6. Тікелей тапсырманың тұтас функциясының коэффициенті c1,c2,...,cn, екіжақты тапсырма шектеулік векторына айналады.

4,6 ережелерін қолдану арқылы біз кері тапсырманың функционалды шектеуліктерін қалыптастыра аламыз:



7. Кері еместіктің тікелей шектеуліктері екіжақты тапсырма айнымалылары үшін сақталады.

У 1 ³0 , у2 ³0, у 3 ³0... уm ³0

Осылайша, бұған нәтижелі және екіжақты тапсырма ретінде келесі көрсетуге болады:

Жоғарыда көрсетілген ережелерге сәйкес тікелей және екіжақты тапсырма симметриялы және бір-бірімен жанасқан тапсырмалар деп аталады,.



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

1.СБ екіжақты тапсырмаларының ұғымы.

2.Екіжақтылық теоремасы.

Дәріс №13. Түзу және екi жақты есептiң маңызды интерпретациясы.

Сұрақтар:



  1. Тура есеп

  2. Екi жақты есеп

  3. Екi жақтылықтың теориясының негiзгi теңсiздiгi.

1.Тура есеп

Өнiм кәсiпорын n түрлерiн жасау үшiн санда кәсiпорында ие болған ресурстардың түрлерi m пайдаланады: b1, b2,..., bm. I=l i ресурстардың әрқайсыларының бұл санында.. j=l өнiм бiрлiк j түрдi өндiрiсiне жүретiн...n ), аij технологиялық коэффициенттерiмен менменседi. J=l өнiм j түрдi жасалған бiрлiктiң кәсiпорын алынатын сатулары түсiм...n ), сәйкесiнше c1, c2, сәйкесiнше құрайды...cn. X1, x2 өнiмнiң өндiрiсi X= мұндай жоспар белгiлеуге керек,...xn ), жоспардың берiлгенiнiң орындауы үшiн қолданылатын ресурстардың әрқайсыларының саны ал жоспар мәлiметтермен сәйкестiк жасалған барлық өнiмге өткiзуден кәсiпорынның түсiмiнiң жанында ең жоғары болған олардың әрқайсыларының кәсiпорын бар қоры шектен шықпайды.

Қорыта келгенде, осы есепте:

• мақсаттық функция: F = c1x1, + c2x2 + c3x3 +... + cn xn - max оңтайлы жоспары бар сәйкестiкте жасалған өнiмге сатудан түсiмнiң максимизациясында қосылатын кәсiпорынның мақсатын бейнелеп көрсетедi; X= x1, x2

•функционалдық шектеулердi жүйе кiрушi теңсiздiктердiң әрқайсылары:



ВИАлардың әрқайсыларының сан болған тұратын осы жоспар көрсетiлетiн талапты бейнелеп көрсетедi і(i=l...m), ресурстардың өнiмнiң түрiн әрбiр j-ro өндiрiс үшiн қажеттi )...n ) bj кәсiпорын бар ресурстардың әрқайсыларының Запасовосы асу тиiстi асу тиiстi xj санда;

•шектеулердiң түзулерiн жүйе кiрушi теңсiздiктердiң әрқайсылары: х1 ме?0, х2 ме?0,...,хn?0 талапты бейнелеп көрсетедi.
2.Екi жақты есеп

Болжаймыз, не онда өнiмнiң өндiрiс n түрлерiн үшiн ресурстардың түрлерi m пайдаланатын кәсiпорын, қолданылатын ресурстарға шығын aij дәл сол технологиялық коэффициенттерiнде минимизациялағысы келедi. Бұл ол үшiн мұндай ресурстардың әрқайсыларының (баға ) бағалары табуға керек

— i=l уi.. .m ), ресурс жанында болған iстiң оларына шығынның жанында ең төменгi бұл (баға ) iзделiп отырған баға әрбiр j-ro өнiм бiрлiгi өндiрiске жұмсалған шығын қорыта келгенде орнатылау тиiстi түрі оның өткiзуiнен аспас едi.

Бағалардың астында бұл жағдайда ұғым объективтi түрде мерзiмдi бағалары түсiнедi,алғаш енгiзiлген Л.Канторовичем ), бағалардан айырмашылыққа қай, ,сырттай емес, iшкi пайдалану үшiн өзiнiң кәсiпорынымен анықталғанында.

Қорыта келгенде, осы есепте:

•мақсаттық функция: Z(y ) = y1 + у2b2... + ymbm - min шығындарды барынша азайтуда қосылатын кәсiпорынның мақсатын бейнелеп көрсетедi;

•функционалдық шектеулердi жүйе кiрушi теңсiздiктердiң әрқайсылары:

y1, y2 iзделiп отырған бағалар көрсетiлетiн талапты бейнелеп көрсетедi, ym j=l әрбiр j бiрлiк өндiрiске жұмсалған шығын болған байқалған...n ) өнiмнiң түрi оның (яғни оның бағасы) өткiзуiнен түсiмдi аспайды;

•шектеулердiң түзулерiн жүйе кiрушi теңсiздiктердiң әрқайсылары: У1 ме?0, у2 ме?0,...,уm?0

олардың әрқайсы болған баға көрсетiлетiн талапты бейнелеп көрсетедi —

i = l уi...m ) терiс емес болуы керек.
3 Екi жақтылықтың теориясының негiзгi теңсiздiгi.

X=(х, 2х ,..., хn ) және Y = (y1, y2, ym) бастапқы және екi жақты есептермен әдiл теңсiздiк



Теорема. (ұтымдылықтың жеткiлiктi белгiсi )

Егер X*= ( x* 1, x* 2,...,- X*n ) жәнеY =(y *1, y *2 *,..,ym ) - есептердiң шешiмі,

үшiн қайтадан орнатады : F(X)=Z(Y*),

бiрде X* - бастапқы есеп оңтайлы шешiм, Y* ал - оңтайлы шешiм екi жақты.

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

Негiзгi бiрiншi екiжақтылықтың теоремасы.

Егер есептердiң бiрi оңтайлы шешiмi болса, онда оны басқа, және де оның сызықты мiндеттерi тең: Fmax (X ) = Zmin(X) F(X*)=Z(Y*).

Егер есептердiң біреуі сызықты м болса, онда басқа есептiң шарты қарама-қарсы.

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


Өзін-өзі тексеру сұрақтары

1.Қалай математикалық модельдi салады.

2.Үлгiнiң негiзгi элементтерi.


Достарыңызбен бөлісу:
1   ...   59   60   61   62   63   64   65   66   ...   95




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет