Вікіпедія

Лінійне програмування: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Немає опису редагування
Немає опису редагування
Рядок 1:
{{Об'єднатиПриєднати з|ЛінійнеЗадача лінійного програмування|дата=січень 2010}}
[[File:Linear optimization in a 2-dimensional polytope.svg|thumb|Графічне представлення простої лінійної програми з двома змінними і шістьма нерівностями. Множина допустимих розв'язків зображена світло червоним і утворює багатогранник, 2-вимірний політоп. Цільова функція представлена червоною лінією і стрілкою. Червона лінія це [[множина рівня]] цільової функції і стрілка позначає в якому напрямку ми оптимізуємо]]
'''Лінійне програмування''' або '''лінійна оптимізація''' ('''LP''', {{lang-en|Linear Programming}}) — метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у [[математична модель|математичній моделі]] чиї вимоги представлені через лінійні відношення. Лінійне програмування є особливим випадком математичного програмування ([[оптимізація (математика)|математичної оптимізації]]).
 
Більш формально, лінійне програмування є технікою для [[математика (оптимізація)|оптимізації]] [[лінійна функція|лінійної]] [[цільова функція|цільової функції]], що [[Обмеження (математика)|обмежена]] [[Лінійне рівняння|лінійними рівняннями]] і лінійними нерівностями. Її [[Допустимий розв'язок|допустима множина]] є [[Опуклий політоп|опуклим політопом]], який є множиною визначеною як перетин скінченної кількості [[півпростір]]ів, кожен з яких визначає лінійна нерівність. Її цільова функція є [[дійсне число|дійсно]]-значима [[Афінне перетворення|афінна функція]] визначена на цьому багатограннику. [[Алгоритм]] лінійного програмування знаходить точку на багатограннику де ця функція набуває найбільшого чи найменшого значення якщо така точка існує.
'''Зада́ча ліні́йного програмува́ння''' — [[задача оптимізації]] з [[Лінійна функція|лінійною]] [[цільова функція|цільовою функцією]] та [[допустима множина|допустимою множиною]] обмеженою лінійними рівностями або нерівностями.
 
Лінійну програму можна виразити в [[канонічна форма|канонічній формі]]:
Тобто, необхідно мінімізувати
:{|
: <math> \sum_{j=1}^n c_j x_j \to \min </math> (1)
|-
при обмеженнях
| '''максимізувати''' || <math>\mathbf{c}^\mathrm{T} \mathbf{x}</math>
: <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_jA \geq 0,mathbf{x} \; j = 1,leq \dots, n_1mathbf{b}</math>, (4)
|-
де ''c''<sub>j</sub> (''j'' = 1, …, ''n''), ''a''<sub>ij</sub>(''i'' = 1, …, ''m'')&nbsp;— задані числа.
| '''і також''' || <math>\mathbf{x} \ge \mathbf{0}</math>
|}
де '''x''' представляє вектор змінних (треба визначити), '''c''' і '''b''' це [[Векторний простір|вектори]] (відомих) коефіцієнтів, ''A'' це (відома) [[Матриця (математика)|матриця]] коефіцієнтів і <math>(\cdot)^\mathrm{T}</math> це [[транспонована матриця]]. Вираз, який необхідно максимізувати або мінімізувати називають ''цільова функція'' (тут '''c'''<sup>T</sup>'''x'''). Нерівності ''A'''''x'''&nbsp;≤&nbsp;'''b''' і '''x''' ≥ '''0''' є обмеженнями, які визначають опуклий політоп над яким оптимізують цільову функцію.
 
Лінійне програмування можна застосувати у різноманітних галузях науки. Його використовують в економіці і бізнесі, але можна використати і в інженерних задачах. Серед галузей які використовують лінійне програмування можна згадати перевезення, енергетику, телекомунікації і виробництво. Воно довело свою корисність у моделюванні різних типів проблем у плануванні, [[Маршрутизація|маршрутизації]], [[Задача про призначення|призначенні задач]] і дизайні.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів ''c''<sub>j</sub> на протилежні.
 
== Загальні відомості ==
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей [[Програмування математичне|математичного програмування]] та [[Теорія оптимізації|теорії оптимізації]]. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого [[Канторович Леонід Віталійович|Канторовича Л. В.]] в [[1939]]. В цій же роботі намічено один із методів розв'язання задачі &mdash; метод послідовного зменшення нев'язок.
 
== Методи розв'язання ==
* [[Метод потенціалів]] &mdash; розроблений в [[1940]] радянськими вченими [[Канторович Леонід Віталійович|Канторовичем]] та [[Гавурін М. К.|Гавуріним Л. В.]] в застосуванні до [[Транспортна задача|транспортної задачі]];
* [[Симплекс-метод]] &mdash; цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим [[Данциґ Дж.-Б.|Данциґом Дж.-Б.]] в [[1949]] році.
* [[Двоїстий симплекс-метод]] розроблений згодом після прямого [[симплекс-метод]]у, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
 
Близький зв'язок між лінійним програмуванням та [[Ігор теорія|теорією ігор]] дає змогу використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.
 
Інша група ітеративних методів характеризується заміною вихідної задачі на еквівалентну їй [[Опукла задача оптимізації|задачу опуклої оптимізації]] без обмежень, для розв'язання якої використовуються різноманітні [[градієнтні методи]].
 
Для розв'язання задач лінійного програмування з великою кількістю змінних та обмежень використовують [[Декомпозиції методи|методи декомпозиції]], які дають змогу замість вихідної задачі розв'язувати послідовність задач меншого обсягу.
 
Методів лінійного програмування недостатньо при накладанні додаткових обмежень на цілочисельність значень змінних. Вивченням таких задач займається [[Програмування цілочисельне|цілочисельне програмування]].
 
Поряд з основною задачею лінійного програмування, розглядають різноманітні окремі задачі лінійного програмування, такі як транспортні, задачі розподілу, задачі теорії розкладів, вибору тощо.
 
== Джерела інформації ==
* [[Енциклопедія кібернетики]], [[Трубін В. А.]], т. '''2''', с. 232-234.
 
== Див. також ==
{{Портал|Математика}}
* [[Задача математичноголінійного програмування]]
* [[Цілочислові задачі лінійного програмування]]
* [[Задача оптимізації]]
* [[Опорний план]]
* [[Лінійне програмування]]
 
== Посилання ==
* [http://sourceforge.net/projects/lipside/ Linear Program Solver (LiPS)]&nbsp;— [[розв'язувач]] задач лінійного цілочисельного программирования.
* [http://www.mdtvm.rv.ua/matem/matprog.html Динамічні математичні моделі]
 
{{Math-stub}}
{{Без джерел|дата=травень 2009}}
 
[[Категорія:Теорія оптимізації]]
[[Категорія:Лінійне програмування]]
 
[[fr:Programmation linéaire]]
Отримано з https://uk.wikipedia.org/wiki/Лінійне_програмування