Умк по инженерному проектированию

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

j

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

1. 
   Математикалық программалаудың жалпы тапсырмасы?
   
2. 
   Тұрман (седловая) нүкте және қос қабаттылық әдістері.
   

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ң көр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. 
   Моделдердің сезімталдығына анализ жасау. Модел түрлері.
   

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

1.Төте есеп

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

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

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

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

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

Тікелей және екіжақты тапсырмалардың айырмашылығы, тікелей тапсырмалар n белгісінің x₁,x₂,...,x_n, айнымалыларымен анықталады, ал екіжақты тапсырмалар — m айнымалысының: y_1, y_2,…, y_m белгілерімен айқындалады. Нәтижелі тапсырмада максимум ізделінеді, ал екіжақты тапсырмада –толық фнункцияның минимум ізделінеді, бұл тапсырмаларда теңсіздіктер белгілері қарам-қарсы болады, векторлардың шектеулік коэффициенті бір тапсырмада айнымалы болғанда, толық функцияда айнымалылар коэффициенті бола алады.

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

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

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

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

Сұрақтар:

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ң шарты қарама-қарсы болған, сызық міндеті тұрде шықпайды .