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

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

Розмір шрифту

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

Рекомендована література

Інформація про статтю