Линейное программирование

Линейное программирование ( ЛП , также называемое линейной оптимизацией ) — это метод достижения наилучшего результата (например, максимальной прибыли или наименьших затрат) в математической модели , требования которой представлены линейными отношениями . Линейное программирование — это частный случай математического программирования (также известного как математическая оптимизация ).

Более формально, линейное программирование — это метод оптимизации линейной целевой функции с учетом ограничений линейного равенства и линейного неравенства . Его допустимая область представляет собой выпуклый многогранник , представляющий собой множество, определяемое как пересечение конечного числа полупространств , каждое из которых определяется линейным неравенством. Его целевая функция представляет собой вещественнозначную аффинную (линейную) функцию, определенную на этом многограннике. Алгоритм линейного программирования находит точку в многограннике где эта функция имеет наименьшее (или наибольшее) значение, если такая точка существует.

Здесь компоненты x — это определяемые переменные, c и b — заданные векторы (с указанием того, что коэффициенты при c используются как однострочная матрица с целью формирования матричного произведения), а A — заданная матрица . Функция, значение которой должно быть максимизировано или минимизировано ( в данном случае), называется целевой функцией . Неравенства A x ≤ b и x ≥ 0 являются ограничениями, задающими выпуклый многогранник ${\ Displaystyle \ mathbf {с} ^ {T}}$ ${\ Displaystyle \ mathbf {х} \ mapsto \ mathbf {с} ^ {T} \ mathbf {х}}$ по которому должна быть оптимизирована целевая функция. В этом контексте два вектора сравнимы , когда они имеют одинаковые размеры. Если каждая запись в первом меньше или равна соответствующей записи во втором, то можно сказать, что первый вектор меньше или равен второму вектору.

Линейное программирование может быть применено к различным областям исследования. Он широко используется в математике и в меньшей степени в бизнесе, экономике и для некоторых инженерных задач. Отрасли, в которых используются модели линейного программирования, включают транспорт, энергетику, телекоммуникации и производство. Он оказался полезным при моделировании различных типов проблем в планировании , маршрутизации , составлении графиков , назначении и проектировании.

Проблема решения системы линейных неравенств восходит как минимум к Фурье , опубликовавшему в 1827 г. метод их решения ^[1] и в честь которого назван метод исключения Фурье–Моцкина .

В 1939 году формулировка задачи линейного программирования, эквивалентная общей задаче линейного программирования, была дана советским математиком и экономистом Леонидом Канторовичем , который также предложил метод ее решения. ^[2] Это способ, который он разработал во время Второй мировой войны , чтобы планировать расходы и доходы, чтобы уменьшить расходы армии и увеличить потери, наносимые противнику. ^{[ править ]} Работа Канторовича была первоначально заброшена в СССР . ^[3] Примерно в то же время, что и Канторович, голландско-американский экономист Т.С.сформулировал классические экономические задачи в виде линейных программ. Канторович и Купманс позже разделили Нобелевскую премию по экономике 1975 года . ^[1] В 1941 году Фрэнк Лорен Хичкок также сформулировал транспортные задачи в виде линейных программ и дал решение, очень похожее на более поздний симплекс-метод . ^[2] Хичкок умер в 1957 году, и Нобелевская премия не присуждается посмертно.

Графическое представление простой линейной программы с двумя переменными и шестью неравенствами. Множество допустимых решений изображено желтым цветом и образует многоугольник , двумерный многогранник . Оптимум линейной функции стоимости находится там, где красная линия пересекает многоугольник. Красная линия — это набор уровней функции стоимости, а стрелка указывает направление, в котором мы оптимизируем.

Замкнутой допустимой областью задачи с тремя переменными является выпуклый многогранник . Поверхности, дающие фиксированное значение целевой функции, являются плоскостями (не показаны). Задача линейного программирования состоит в том, чтобы найти точку многогранника, лежащую на плоскости с наибольшим возможным значением.

Леонид Канторович

Джон фон Нейман

В задаче линейного программирования ряд линейных ограничений создает выпуклую допустимую область возможных значений этих переменных. В случае двух переменных эта область имеет форму выпуклого простого многоугольника .