Лінійне програмування: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м +перекласти, ВП:ВФ |
Bunyk (обговорення | внесок) Немає опису редагування |
||
Рядок 31:
[[Категорія:Теорія оптимізації]]
'''Зада́ча ліні́йного програмува́ння''' — [[задача оптимізації]] з [[Лінійна функція|лінійною]] [[цільова функція|цільовою функцією]] та [[допустима множина|допустимою множиною]] обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
: <math> \sum_{j=1}^n c_j x_j \to \min </math> (1)
при обмеженнях
: <math> \sum_{j=1}^n a_{ij} x_j \leq b_i,\; i = 1, \dots, m_1</math>, (2)
: <math> \sum_{j=1}^n a_{ij} x_j = b_i, \; i = m_1+1, \dots, m</math>, (3)
: <math> x_j \geq 0, \; j = 1, \dots, n_1</math>, (4)
де ''c''<sub>j</sub> (''j'' = 1, …, ''n''), ''a''<sub>ij</sub>(''i'' = 1, …, ''m'') — задані числа.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів ''c''<sub>j</sub> на протилежні.
== Загальні відомості ==
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей [[Програмування математичне|математичного програмування]] та [[Теорія оптимізації|теорії оптимізації]]. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого [[Канторович Леонід Віталійович|Канторовича Л. В.]] в [[1939]]. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення нев'язок.
== Методи розв'язання ==
* [[Метод потенціалів]] — розроблений в [[1940]] радянськими вченими [[Канторович Леонід Віталійович|Канторовичем]] та [[Гавурін М. К.|Гавуріним Л. В.]] в застосуванні до [[Транспортна задача|транспортної задачі]];
* [[Симплекс-метод]] — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим [[Данциґ Дж.-Б.|Данциґом Дж.-Б.]] в [[1949]] році.
* [[Двоїстий симплекс-метод]] розроблений згодом після прямого [[симплекс-метод]]у, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
Близький зв'язок між лінійним програмуванням та [[Ігор теорія|теорією ігор]] дає змогу використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.
Інша група ітеративних методів характеризується заміною вихідної задачі на еквівалентну їй [[Опукла задача оптимізації|задачу опуклої оптимізації]] без обмежень, для розв'язання якої використовуються різноманітні [[градієнтні методи]].
Для розв'язання задач лінійного програмування з великою кількістю змінних та обмежень використовують [[Декомпозиції методи|методи декомпозиції]], які дають змогу замість вихідної задачі розв'язувати послідовність задач меншого обсягу.
Методів лінійного програмування недостатньо при накладанні додаткових обмежень на цілочисельність значень змінних. Вивченням таких задач займається [[Програмування цілочисельне|цілочисельне програмування]].
Поряд з основною задачею лінійного програмування, розглядають різноманітні окремі задачі лінійного програмування, такі як транспортні, задачі розподілу, задачі теорії розкладів, вибору тощо.
== Джерела інформації ==
* [[Енциклопедія кібернетики]], [[Трубін В. А.]], т. '''2''', с. 232-234.
== Див. також ==
{{Портал|Математика}}
* [[Задача математичного програмування]]
* [[Задача оптимізації]]
* [[Опорний план]]
* [[Лінійне програмування]]
== Посилання ==
* [http://www.mdtvm.rv.ua/matem/matprog.html Динамічні математичні моделі]
{{Math-stub}}
[[Категорія:Теорія оптимізації]]
[[Категорія:Лінійне програмування]]
[[fr:Programmation linéaire]]
| |||