Задача лінійного програмування
Матеріал з Вікіпедії — вільної енциклопедії.
Задача лінійного програмування — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(1)
при обмеженнях
, (2)
, (3)
, (4)
де cj (j = 1, ..., n), aij(i = 1, ..., m) — задані числа.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні.
Зміст |
[ред.] Загальні відомості
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовіча Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення невязок.
[ред.] Методи розв'язання
- Метод потенціалів — розроблений в 1940 радянськими вченими Канторовічем Л. В. та Гавуріним Л. В. в застосуванні до транспортної задачі;
- Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
- двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, по суті, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінчені. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
Близький зв'язок між лінійним програмуванням та теорією ігор дозволяє використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.
Інша група ітеративних методів характеризується заміною вихідної задачі на еквівалентну їй задачу опуклої оптимізації без обмежень, для розв'язання якої використовуються різноманітні градієнтні методи.
Для розв'язання задач лінійного програмування з великою кількістю змінних та обмежень використовують методи декомпозиції, які дозволяють замість вихідної задачі розв'язувати послідовність задач меншого об'єму.
Методів лінійного програмування недостатньо при накладанні додаткових обмежень на цілочисельність значень змінних. Вивченням таких задач займається цілочисельне програмування.
Поруч із основною задачею лінійного програмування, вивчаються різноманітні частні задачі лінійного програмування, такі як транспортні, задачі розподілу, задачі теорії розкладів, вибору і так далі.
[ред.] Джерела інформації
- Енциклопедія кібернетики, Трубін В. А., т. 2, с. 232-234.
[ред.] Дивіться також
![]() |
Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її. |