Сызықтық бағдарламалау – сызықтық теңдеулер мен теңсіздіктер жүйелерімен берілген n-өлшемді векторлық кеңістіктер жиындарына экстремалды есептерді шешудің теориясы мен әдістеріне арналған математикалық пән. Сызықтық программалау дөңес программалаудың ерекше жағдайы, ол өз кезегінде математикалық бағдарламалаудың ерекше жағдайы болып табылады. Сонымен қатар ол бүтін және сызықты емес программалау есептерін шешудің бірнеше әдістерінің негізі болып табылады. Сызықтық программалаудың жалпыламаларының бірі бөлшек сызықтық программалау болып табылады. Сызықтық бағдарламалау есептерінің көптеген қасиеттерін көп қырлылардың қасиеттері ретінде де түсіндіруге болады және осылайша геометриялық түрде тұжырымдалады және дәлелденеді.
Сызықтық программалаудың жалпы (стандартты) есебі түріндегі сызықтық мақсат функциясының (сызықтық түрі) минимумын табу мәселесі болып табылады:
Теңсіздіктер түріндегі шектеулер пайда болатын есеп негізгі сызықтық бағдарламалау мәселесі деп аталады:
Егер негізгі есепте бірінші теңсіздіктер жүйесінің орнына теңдік түріндегі шектеулері бар теңдеулер жүйесі болса, сызықтық программалау есебінің канондық түрі болады:
Негізгі мәселені қосымша айнымалыларды енгізу арқылы канондық проблемаға дейін азайтуға болады. Сызықтық программалаудың ең жалпы түрдегі есептері (аралас шектеулері бар есептер: теңдіктер мен теңсіздіктер, шектеулерден бос айнымалылардың болуы) айнымалылардың эквивалентті (шешімдер жиынтығы бірдей) өзгерістеріне және теңдіктерді жұппен ауыстыруға дейін қысқартылуы мүмкін теңсіздіктер. Максималды табу есебін қарама-қарсы таңбалы с коэффициенттерін алу арқылы минимумды табу есебімен алмастыруға болатынын байқау қиын емес.
Сызықтық программалаудың (LP) жалпы есебін шешу үшін тәжірибеде ең танымал және кеңінен қолданылатыны симплекс әдісі болып табылады. Симплекс әдісі қолданбалы LP есептерін шешуде жақсы нәтижелер көрсеткен жеткілікті тиімді алгоритм болғанына қарамастан, ол экспоненциалды күрделілігі бар алгоритм болып табылады. Мұның себебі оптималды шешімді іздестіру кезінде рұқсат етілген шешімдердің көпбұрышының төбелерін дәйекті түрде санайтын симплекс әдісінің комбинаторлық сипаты болып табылады. Алғашқы көпмүшелік алгоритм эллипсоид әдісін 1979 жылы кеңес математигі Л.Хачиян ұсынды, осылайша көптен бері шешілмей келген мәселені шешті. Эллипсоидты әдіс симплекс әдісінен мүлде басқа комбинаторлық емес сипатқа ие. Дегенмен, есептеу тұрғысынан бұл әдіс перспективасыз болып шықты. Осыған қарамастан, есептердің көпмүшелік күрделілігі фактінің өзі тиімді LP алгоритмдерінің тұтас класын – ішкі нүкте әдістерін құруға әкелді, оның біріншісі 1984 жылы ұсынылған Н.Қармарқар алгоритмі болды. Бұл түрдегі алгоритмдер LP есебінің үздіксіз интерпретациясын пайдаланады, бұл кезде LP есебінің шешімдерінің политопының төбелерін санаудың орнына есептің төбелерден өтпейтін айнымалылар кеңістігіндегі траекториялар бойымен іздеу жүргізіледі. политоптан. Симплекс әдісінен айырмашылығы, толеранттылық диапазонының ішкі бөлігінен нүктелерді айналып өтетін ішкі нүкте әдісі 1960 жылдары Фиакко мен МакКормик әзірлеген сызықты емес бағдарламалаудың логарифмдік кедергі функциясының әдістерін пайдаланады.
Сызықтық программалау есебін шешудің графикалық әдісі сызықтық программалау есебінің геометриялық интерпретациясына негізделген және негізінен екі өлшемді кеңістіктегі есептерді және тек үш өлшемді кеңістіктегі кейбір есептерді шешу үшін қолданылады, өйткені оны құру өте қиын. жартылай кеңістіктердің қиылысуы нәтижесінде пайда болатын ерітінді көпбұрышы. Үштен үлкен өлшемдер кеңістігінің тапсырмасын графикалық түрде көрсету мүлде мүмкін емес.
Сызықтық программалау мәселесі екі өлшемді кеңістікте берілсін, яғни шектеулер екі айнымалыдан тұрады.
Функцияның ең кіші мәнін табыңыз:
Шектеулері :
Және
Қолданылған әдебиеттер:
Кремер Н.Ш. Исследование операций в экономике. — Москва: Юнити, 2000. — С. 55-57. — 408 с.
Ашманов С.А. Линейное программирование. — Москва: «Наука», 1981. — 304 с.
Абрамов Л. М., Капустин В. Ф. Математическое программирование. — Учебное пособие. — Л.: ЛГУ, 1981. — 328 с.
Акоф Р., Сасиени М. Основы исследования операций. — Пер. с англ. В. Я. Алтаева., под ред. И. А. Ушакова. — М.: Мир, 1971. — 551 с.
Акулич И. Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с.
Linear Program Solver (LiPS)— Бесплатный оптимизационный пакет, предназначенный для решения задач линейного, целочисленного и целевого программирования.
Достарыңызбен бөлісу: |
