Вікіпедія

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

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
DixonDBot (обговорення | внесок)
Боти
220 373 редагування
м Додавання/виправлення дати для: Шаблон:Об'єднати; косметичні зміни
DixonDBot (обговорення | внесок)
Боти
220 373 редагування
м Додавання/виправлення дати для: Шаблон:Приєднати з
Рядок 1:
{{Об'єднатиПриєднати з|ЛінійнеЗадача лінійного програмування|дата=січень 2010}}
 
'''Лінíйне програмувáння''' ('''LP''', {{lang-en|'''L'''inear '''P'''rogramming}}) — один з важливих розділів дослідження операцій, що зводиться до оптимізації лінійної [[цільова функція|цільової функції]] на [[множина|множині]], яка описується [[лінійне рівняння|лінійними рівняннями]] і [[нерівність|нерівностями]]. Лінійне програмування є окремими випадками [[математичне програмування|математичного]] [[програмування]].
'''Зада́ча ліні́йного програмува́ння''' — [[задача оптимізації]] з [[Лінійна функція|лінійною]] [[цільова функція|цільовою функцією]] та [[допустима множина|допустимою множиною]] обмеженою лінійними рівностями або нерівностями.
Одночасно воно — основа декількох методів вирішення задач [[цілочисельне програмування|цілочисельного]] і [[нелінійне програмування|нелінійного програмування]]. Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості многогранників і таким чином геометрично формулювати і доводити їх. Термін «програмування» треба тут розуміти в значенні «планування». Він був запропонований в середині [[1940-ві|1940-х]] років [[Джордж Данціг|Джорджем Данціґом]], одним із засновників лінійного програмування, ще до того, як [[комп'ютер]]и були використані для вирішення лінійних задач [[оптимізація|оптимізації]].
 
Тобто, необхідно мінімізувати
: <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'')&nbsp;— задані числа.
 
Задача максимізації функції (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}}
 
[[Категорія:Теорія оптимізації]]
[[Категорія:Лінійне програмування]]
 
[[af:Lineêre programmering]]
[[fr:Programmation linéaire]]▼
[[ar:برمجة خطية]]
[[bs:Linearno programiranje]]
[[ca:Programació lineal]]
[[cs:Lineární programování]]
[[de:Lineare Optimierung]]
[[en:Linear programming]]
[[es:Programación lineal]]
[[eu:Programazio lineal]]
[[fa:برنامه‌ریزی خطی]]
▲[[fr:ProgrammationOptimisation linéaire]]
[[he:תכנון לינארי]]
[[hi:रैखिक प्रोग्रामन]]
[[hu:Lineáris optimalizálás]]
[[id:Pemrograman linier]]
[[it:Programmazione lineare]]
[[ja:線型計画問題]]
[[ko:선형 계획법]]
[[nl:Lineair programmeren]]
[[nn:Lineær programmering]]
[[pl:Programowanie liniowe]]
[[pt:Programação linear]]
[[ro:Programare liniară]]
[[ru:Линейное программирование]]
[[scn:Prugrammazzioni liniàri]]
[[sh:Linearno programiranje]]
[[simple:Linear programming]]
[[sl:Linearno programiranje]]
[[sr:Линеарно програмирање]]
[[sv:Linjärprogrammering]]
[[th:กำหนดการเชิงเส้น]]
[[tr:Doğrusal programlama]]
[[ur:لکیری برمجہ]]
[[vi:Quy hoạch tuyến tính]]
[[zh:线性规划]]
Отримано з https://uk.wikipedia.org/wiki/Лінійне_програмування