ЭКОНОМИКАЛЫҚ ЕСЕПТЕРДІ СИМПЛЕКС ӘДІСПЕН ШЕШУ

Экономикалық есептерді симплекс әдіспен шешу

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

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

Формальды түрде бұл максималдау міндетін осылай жазуға болады :

Азайту үшін жалпы қойылым келесыдей жазуға болады

Алайда симплекс-мәселені шешу әдісі СБЕ арнайы түрлердің бірінде жазылған деп болжайды. 4 арнайы түрі бар (екі стандартты және екі канониялық түрі) . Максималдандырудың стандартты нысаны - бұл тұрақты емес теңсіздіктің (аз немесе тең) түрін шектеу кезінде және барлық айнымалылар үшін белгіге шектеулер болған кезде нысаналы функцияның максимумын табу міндеті (теріс емес жағдайлар болғанда) :

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

Максимизацияның СБЕ канониялық нысаны - теңдік түрін шектеу кезінде және барлық айнымалылар үшін белгіге шектеу болған кезде нысаналы функцияның максимумын табу міндеті:

СБЕ минимизациялаудың канониялық нысаны - бұл теңдік түрін шектеу кезінде және барлық айнымалылар үшін белгіге шектеу болған кезде нысаналы функцияның минимумын табу міндеті:

Практикада сызықтық бағдарламалаудың жалпы есебі арнайы түрлердің біріне келтірілуі тиіс. Бұл эквивалентті түрлендірулер деп аталатын қарапайым түрлендірулерді пайдалану арқылы жасалады. Сызықтық функцияның максимумын табу қарама-қарсы белгімен алынған осы функцияның минимумын табуға баламалы және керісінше жасағанда болады:

Мысалы. Стандартты және канониялық максимализация формаларында СБЕ ұсыну:

Баламалы тұжырымдарды пайдалана отырып, келесы формаларға келтіру:

Максимизацияның канондық есебі үшін симплекс-әдісінің формальды алгоритмін сипаттауға көшеміз:

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

Бұл жүйені айнымалы түрде диагональды формаға келтіреміз :

Осы диагональды форма коэффициенттерінің кестесін құрайық (симплексті кесте, қысқартылған СК) :

Бірінші ( бөлінген) СК жолы z-теңдеу коэффициенттерін қамтиды, бөлінген СК бағанасында шектеудің оң бөліктері және z - теңдеу (z0) орналасқан. Симплексті кесте-симплекс-әдісінің есептеуіш процедурасының негізгі элементі. Симплекстік кесте максималдандырудың каноникалық есебі үшін құрылған сызықтық теңдеулер жүйесінің диагоналдық формасының коэффициенттерінің кестесі болып табылады. Ол СЕ жүйесінің диагональды формасы үшін құрылғандықтан, симплексті кесте СЕ қарастырылған жүйесінің базистік шешіміне сәйкес келеді.

Тікелей симплекс-әдісінің (максимализация) алгоритмі. Есептеулерді тура-рұқсат етілген симплексті кестеден бастау. Алгоритм бойынша есептеулер келесі бір типті итерацияларды орындауда тұрады. Әрбір осындай итерация жүйелі түрде орындалатын үш қадамнан тұрады.

ИТЕРАЦИЯ1.

Оптималды тексеру немесе СК жетекші бағананы табу.

Егер бөлектелген жолдағы барлық коэффициенттер базистік емес айнымалы кезінде теріс емес болса (z-теңдеудегі коэффициенттер), онда ағымдағыбазистік шешім оңтайлы болып табылады. Кері жағдайда келесі итерацияда базистік айнымалылардың санына нөмірі ереже бойынша орналасқан бейбазистік айнымалыны Хѕ енгіземіз:

S нөмірі астындағы баған симплексті кестенің жетекші бағаны деп аталады.

2. СБЕ есебін шешудің шектелмеген шарттарын тексеру және жетекші жолды табу (жетекші элементті) СК.

- Егер s симплекс кестесінің жетекші бағанасында оң коэффициенттер болмаса, онда СБЕ мәні шексіз (оңтайлы шешім жоқ) .

- Олай болмаған жағдайда (жетекші бағанда оң элементтер бар) базистік айнымалы ретінде базистік айнымалы ретінде, ол базистік санынан алынып тасталады, ол үшін Хr айнымалы таңдалады.

r нөмірдегі жол СК жетекші жолы деп аталады, ал

элемент - СК жетекші элементі болады.

3. Симплекс кестесін түрлендіру.

- Кестенің эквивалентті түрлендірулерін (Гаусс процедурасын) қолдана отырып, кестені жаңа СК жетекші элементі 1 - ге тең, ал жетекші бағанның барлық қалған элементтері 0-ге тең болатындай етіп қайта есептейміз.

- Жаңа симплексті кестенің 1 элементтерін жоғарғы индекспен белгілейміз. Сонда коэффициенттерді қайта есептеу формулалары :

Жаңа симплексті кестені зерттеуге көшу (жаңа итерация) .

Мысалы.

Итерация 1.

Бастапқы симплекс кестесі осылай көрінеді :

Енгіземіз базис айнымалына Х1, шығарамыз S2 өндіреміз қайта есептеу кестелер бойынша

Итерация 2.

Енгіземіз базис айнымалы Х1, шығарамыз S1, таға да кестелерді есептейміз

Магистранттарға арналған тапсырма:

Жиһаз фабрикасы өнімнің үш түрін шығарады, олардың әрқайсысын шығару үшін белгілі бір уақыт қажет үш түрлі жабдық желілерінде. А өнімінің бірлігін өндіру уақыты тиісінше 60, 40 және 0 сағатты құрайды. Бұл ретте А өнімінің бірлігін сатудан түскен пайда 100 $ құрайды. Нормативтік уақытта 10, 20, 10 сағат В өнім үшін, тиісінше, 120$ пайда. Өңдеу уақыты бар С өнімдер үшін 30, 0, 0 табыс 200$. Жабдықтың әрбір желісінде уақыт қоры 600, 300, 200 сағатқа сәйкес шектелсін. Барлық өнімді сатудан түскен жалпы пайда неғұрлым көп болуы үшін қандай өнімді және қандай мөлшерде өндіру керек екенін анықтау керек.

Ұқсас жұмыстар

Алгебралық есептерді шешудің геометриялық әдістері

Конкурстық есептер

Кеңістік пен форма тақырыптарын оқытып - үйрету процесінде оқушылардың математикалық сауаттылығын қалыптастыру технологиялары

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

Оқу әдістері жәні құралжабдықтары

Үйрететін және өзі үйренетін жүйелер

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

ЭАЖ қамтамасыз етудің өзге де түрлері

Матрицалық шешім әдісі

Жоба ұйымдастыру

Пәндер