do.unicyb.kiev.ua

  • Збільшення розміру шрифта
  • Звичайний розмір шрифта
  • Зменшити розмір шрифта

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ

Друк PDF

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