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

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

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

Здесь компонентами являются переменные, которые необходимо определить, и являются заданными векторами , и является заданной матрицей . Функция, значение которой необходимо максимизировать ( в данном случае), называется целевой функцией . Ограничения и определяют выпуклый многогранник , по которому должна быть оптимизирована целевая функция. $\mathbf {x}$ $\mathbf {c}$ $\mathbf {b}$ $А$ $\mathbf {x} \mapsto \mathbf {c} ^{\mathsf {T}} \mathbf {x}$ $A\mathbf {x} \leq \mathbf {b}$ $\mathbf {x} \geq \mathbf {0}$

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

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

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