Лінійне програмування: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
Немає опису редагування |
||
Рядок 1:
{{
'''Зада́ча ліні́йного програмува́ння''' — [[задача оптимізації]] з [[Лінійна функція|лінійною]] [[цільова функція|цільовою функцією]] та [[допустима множина|допустимою множиною]] обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
: <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.
== Дивіться також ==
{{Портал математика}}
* [[Задача
* [[Задача оптимізації]]
* [[Опорний план]]
* [[Лінійне програмування]]
{{Math-stub}}
[[Категорія:Теорія оптимізації]]
[[Категорія:Лінійне програмування]]
[[af:Lineêre programmering]]
[[ca:Programació lineal]]
[[cs:Lineární programování]]
Рядок 20 ⟶ 52:
[[en:Linear programming]]
[[es:Programación lineal]]
[[fr:Programmation linéaire]]
[[he:תכנון לינארי]]
[[hu:Lineáris optimalizálás]]
[[it:Programmazione lineare]]
[[ja:線形計画問題]]
Рядок 33 ⟶ 62:
[[pt:Programação linear]]
[[ru:Линейное программирование]]
[[sl:Linearno programiranje]]
[[sr:Линеарно програмирање]]
[[ur:لکیری برمجہ]]
[[vi:Quy hoạch tuyến tính]]
|