Математичне програмування

МАТЕМАТИ́ЧНЕ ПРО­ГРАМУВА́­Н­НЯ — прикладна математична дисципліна; роз­діл прикладної математики, обʼєктом теоретичного ви­вче­н­ня якого є задачі оптимізації — від їхньої по­становки до знаходже­н­ня алгоритмів роз­вʼяза­н­ня. Наявність у назві терміна «про­грамува­н­ня» можна пояснити історично тим, що перші дослідж. та за­стосува­н­ня роз­вивалися у прямому контакті з екон. дослідж. та ви­вче­н­ням операцій. Цілком природно, що термінологія від­ображає тісний звʼязок, який існує між матем. по­становкою задачі та її екон. інтер­претацією (ви­вче­н­ня оптимал. екон. про­грами). 1949 Дж.-Б. Данциґ за­пропонував термін «лінійне про­грамува­н­ня» для ви­вче­н­ня теор. і алгоритміч. задач, які повʼязані з оптимізацією ліній. функцій при за­даних ліній. обмеже­н­нях; 1951 Г. Кун і А.-В. Такер у цьому ж сенсі викори­стали назву «нелінійне про­грамува­н­ня» для ви­вче­н­ня неліній. задач оптимізації з обмеже­н­нями чи без них; 1957 Р.-Е. Бел­лман увів термін «динамічне про­грамува­н­ня» для заг. методу оптимізації динаміч. систем (тобто таких, що роз­виваються з плином часу); 1958 Р.-Е. Ґоморі (усі — амер. математики) за­стосував термін «цілочисельне про­грамува­н­ня» для задач оптимізації, в яких на змін­ні накладено обмеже­н­ня — при­ймати тільки цілі значе­н­ня. Однак, не­зважаючи на очевидну від­мін­ність цих тем, які роз­глянуто між 1945 і 1960, по­ступове зро­ста­н­ня осмисле­н­ня глибокої спорідненості між різними класами задач — як за структурою, так і за їхніми методами — досить швид-ко призвів до їхнього обʼ­єд­на­н­ня в нову, більш широку дисципліну — т. зв. М. п. Це свідчить про уніфіков. рух, який ви­глядає таким, що ще не досягнув своєї кінцевої мети. Термін «М. п.» уперше офіційно зʼявився, ймовірно, 1959 у назві між­нар. симпозіуму «The RAND symposium on Mathe-matical Programming» (м. Санта-Моніка, шт. Каліфорнія, США). Нині серед осн. видів за­стосува­н­ня М. п.: у дослідж. операцій — оп­тимізація тех.-екон. систем (планува­н­ня, економетрика), транс­­порт­ні задачі, упр. запасами; у чисел. аналізі — апроксимація, ре­гресія, роз­вʼяза­н­ня ліній. і неліній. систем, чисел. методи, по-вʼязані з включе­н­ням методів скінчен­них елементів; у автоматиці — роз­пі­знава­н­ня систем, оптимал. упр. системами, фільтрація, упр. виробництвом; у техніці — упр. роз­мірами й оптимізація структур, оптимал. планува­н­ня склад. тех. систем, зокрема й інформ. систем, мереж компʼютерів, транс­порт. і телекомунікац. мереж; у матем. економіці — роз­вʼяза­н­ня великих макроекон. моделей (типу моделі Леонтьєва), мікроекон. моделей, або моделей під­приємництва, теорії прийня­т­тя рішень та теорії ігор. Важливість М. п. повʼязана також із тим, що воно дає адекватні понятійні рамки для аналізу та ро-звʼяза­н­ня багатьох задач приклад. математики. Поня­т­тя «сідлова точка» в теорії ігор є загальнові­домим, а багаточисел. методи її роз­вʼяза­н­ня витікають із дослідж. М. п. У чисел. аналізі варіац. формулюва­н­ня багатьох задач у роз­по­всюджен­ні на випадок функціонал. просторів осн. скінчен­новимір. алгоритмів призводять до системат. викори­ста­н­ня інструментів ви­вче­н­ня рівнянь з частин. похідними або задач оптимал. упр. У комбінатор. про­грамуван­ні найважливіші базові алгоритми (в задачах про потоки на графах) виникають з дослідж. М. п. і використовують поня­т­тя дво­їстості, доповненості та унімодулярності. Множина накопичених таким чином результатів при­звела до створе­н­ня теорії складності, яка є обʼєктом інтенсив. дослідж. у звʼязку з її теор. і практ. наслідками в приклад. і теор. інформатиках. Побудова матем. моделі досліджув. задачі містить побудову цільової функції змін­них, тобто такої числ. характеристики, найбільшому чи найменшому значен­ню якої від­повід­ає найкраща ситуація з точки зору прийнятого ріше­н­ня. Часто виникає бажа­н­ня побудувати таку модель, в якій би враховувалася значна кількість вхід. даних. Однак при при­скіпливому аналізі виявляється, що вплив багатьох з них на роз­вʼяза­н­ня не­значний або просто від­сутній через невисоку точність вхід. даних. Тобто низка умов у матем. моделях вимагає їхнього аналізу ще на стадії побудови, встановле­н­ня рівнянь та нерівностей, що ви­значають змін­ні величини. Зміст М. п. полягає у теорії та методах роз­вʼяза­н­ня цих задач. У М. п. виділяють два напрями. До першого належать детерміновані задачі, у яких уся вихідна інформація повністю ви­значена; до другого — т. зв. стохастич. про­грамува­н­ня — задачі, у яких вихідна інформація містить елементи неви­значеності, або де­які параметри таких задач мають випадк. характер із ві­домими ймовірніс. характеристиками. Ви­окремлюють 3 осн. роз­діли М. п. При лінійному про­грамуван­ні цільова функція лінійна, а множину, на якій шукають екс­тремум цільової функції, задають системою ліній. рівнянь і нерівностей. Водночас у ліній. про­грамуван­ні існують класи задач, структура яких до­зволяє створити спец. методи їхнього роз­вʼяза­н­ня, які значно ефективніші, ніж методи роз­­вʼяза­н­ня задач заг. характеру (транс­порт­на задача тощо). Нелінійне про­грамува­н­ня — нелінійна цільова функція та обмеже­н­ня. Його під­роз­діли: опукле про­грамува­н­ня — опукла цільова функція (якщо роз­глядати задачу її мінімізації) та опукла множина, на якій роз­вʼязують екс­тремал. задачу; квадратичне про­грамува­н­ня — квадратична цільова функція, а обмеже­н­ня — лінійні рівня­н­ня та нерівності; багатоекс­тремальні задачі — спеціалізов. клас задач, напр., задачі про мінімізацію на опуклих множинах вгнутих функцій. При цілочисельному про­грамуван­ні на змін­ні накладають умову цілочисельності. До задач М. п. не за­стосовні, за­звичай, методи класич. аналізу для умов. екс­тремумів, оскільки навіть у най­простіших задачах — лінійних — екс­тремуму досягають у кутових (край.) точках границі допустимої області (множини умов), тобто в точках, де порушується диференці­йованість. У практ. задачах число змін­них та обмежень на­стільки велике, що якщо просто пере­бирати всі точки, пі­до­зрілі на екс­тремум, то жоден сучас. компʼютер не може здійснити обчисле­н­ня в розум. часових межах.

Завантажити статтю