6.1.Модель лінійного програмування.
Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(1)
при обмеженнях
,
(2)
,
(3)
,
(4)
де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні. Існують наступні методи розвязання задач лінійного програмування:
Метод потенціалів — розроблений в 1940 радянськими вченими Л.В. Канторовичем та Гавуріним М. К. в застосуванні до транспортної задачі;
Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
6.2 Модель цілочисельного програмування.
Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами.
Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами.
Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.
6.2.1Булівське програмування.
До часткового випадку задачі цілочисельного лінійного програмування відносяться задачі, де змінні X можуть приймати всього лише два значення — 0 і 1. Відповідні задачі часто називають задачами булівського програмування. Найбільш відомі із цих задач — задачі про призначення (якого працівника на яку роботу поставити), задачі вибору маршруту (задача комівояжера, задача листоноші) тощо.
Для розв'язання задач цього типу розробляються специфічні алгоритми, засновані на комбінаториці, графах тощо.
Існують наступні методи розвязання задач цілочисельного програмування:
Методи відтинання. Метод Гоморі
Комбінаторні методи. Метод гілок та меж
6.3 Динамічне програмування.
Динамічне програмування - розділ математики, який присвячено теорії і методам розв’язання багатокрокових задач оптимального управління.
У динамічному програмуванні для керованого процесу серед множини усіх допустимих управлінь шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції - деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення управління на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві "Динамічне програмування" під "програмуванням" розуміють "прийняття рішень", "планування", а слово "динамічне" вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.
Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв’язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)
Методи динамічного програмування використовуються не лише в дискретних, але і в неперервних керованих процесах, наприклад, в таких процесах, коли в кожен момент певного інтервалу часу необхідно приймати рішення. Динамічне програмування також дало новий підхід до задач варіаційного числення.
Хоча метод динамічного програмування суттєво спрощує вихідні задачі, та безпосереднє його використання, як правило, пов’язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи динамічного програмування.