Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах
n
{\displaystyle n}
-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование (ЛП) является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Содержание 1 История
2 Задачи
3 Примеры задач 3.1 Максимальное паросочетание
3.2 Максимальный поток
3.3 Транспортная задача
3.4 Игра с нулевой суммой 4 Алгоритмы решения
5 Двойственные задачи линейного программирования
6 Программное обеспечение
7 См. также
8 Примечания
9 Литература
10 Ссылки
Применение методов линейного программирования в военном деле. Симплекс-метод