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

Ретроним, относящийся к телевещанию, см. в разделе « Вещательные программы» .

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

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

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

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

Линейные программы — это задачи, которые можно выразить в стандартной форме как

${\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{\mathsf {T}}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}$

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

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

История

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

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

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

В конце 1930-х годов советский математик Леонид Канторович и американский экономист Василий Леонтьев независимо друг от друга углубились в практические применения линейного программирования. Канторович сосредоточился на производственных графиках, а Леонтьев исследовал экономические приложения. Их новаторская работа оставалась незамеченной на протяжении десятилетий.

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

Несмотря на первоначальную безвестность, успехи военного времени привлекли к линейному программированию всеобщее внимание. После Второй мировой войны этот метод получил широкое признание и стал краеугольным камнем в различных областях, от исследования операций до экономики. Недооцененный вклад Канторовича и Леонтьева в конце 1930-х годов в конечном итоге стал основой для более широкого принятия и использования линейного программирования для оптимизации процессов принятия решений.

Работе Канторовича в СССР поначалу не уделяли должного внимания . Примерно в то же время, что и Канторович, американский экономист голландского происхождения Т.С. Купманс сформулировал классические экономические проблемы в виде линейных программ. Канторович и Купманс позже разделили Нобелевскую премию памяти 1975 года по экономическим наукам . В 1941 году Фрэнк Лорен Хичкок также сформулировал транспортные задачи в виде линейных программ и дал решение, очень похожее на более поздний симплексный метод . Хичкок умер в 1957 году, и Нобелевская премия памяти не присуждается посмертно.

С 1946 по 1947 год Джордж Б. Данциг независимо разработал общую формулировку линейного программирования, которую можно было использовать для решения задач планирования в ВВС США. В 1947 году Данциг также изобрел симплексный метод , который впервые эффективно решил задачу линейного программирования в большинстве случаев. Когда Данциг организовал встречу с Джоном фон Нейманом для обсуждения своего симплексного метода, Нейман сразу же выдвинул гипотезу о теории двойственности , осознав, что проблема, над которой он работал в теории игр, была эквивалентной. Данциг представил формальное доказательство в неопубликованном отчете «Теорема о линейных неравенствах» от 5 января 1948 года. Работа Данцига стала доступна публике в 1951 году. В послевоенные годы многие отрасли промышленности применяли ее в своем повседневном планировании.

Первоначальный пример Данцига состоял в том, чтобы найти наилучшее назначение 70 человек на 70 рабочих мест. Вычислительная мощность, необходимая для проверки всех перестановок и выбора лучшего задания, огромна; число возможных конфигураций превышает число частиц в наблюдаемой Вселенной . Однако поиск оптимального решения занимает всего лишь мгновение, если поставить задачу в виде линейной программы и применить симплексный алгоритм . Теория, лежащая в основе линейного программирования, резко сокращает количество возможных решений, которые необходимо проверить.

Решение задачи линейного программирования за полиномиальное время впервые было показано Леонидом Хачияном в 1979 году: но более крупный теоретический и практический прорыв в этой области произошел в 1984 году, когда Нарендра Кармаркар представил новый метод внутренней точки для решения задач линейного программирования.

Использование

Линейное программирование — широко используемая область оптимизации по нескольким причинам. Многие практические проблемы исследования операций можно выразить как задачи линейного программирования. Некоторые особые случаи линейного программирования, такие как задачи сетевых потоков и многопродуктовых потоков задачи , считаются достаточно важными, чтобы проводить обширные исследования специализированных алгоритмов. Ряд алгоритмов для других типов задач оптимизации работают путем решения задач линейного программирования как подзадач. Исторически идеи линейного программирования послужили источником вдохновения для многих центральных концепций теории оптимизации, таких как двойственность, декомпозиция и важность выпуклости и ее обобщений. Аналогичным образом, линейное программирование активно использовалось на заре формирования микроэкономики , а в настоящее время оно используется в управлении компаниями, например, в планировании, производстве, транспортировке и технологиях. Хотя современные проблемы управления постоянно меняются, большинство компаний хотели бы максимизировать прибыль и минимизировать затраты при ограниченных ресурсах. Google также использует линейное программирование для стабилизации видео на YouTube.

Стандартная форма

Стандартная форма — это обычная и наиболее интуитивно понятная форма описания задачи линейного программирования. Он состоит из следующих трех частей:

• Линейная (или аффинная) функция, которую необходимо максимизировать.

например $f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}$

• Ограничения задачи следующего вида

например

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}$

• Неотрицательные переменные

например

${\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}$

Проблема обычно выражается в матричной форме , а затем становится:

$\max\{\,\mathbf {c} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}$

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

Пример

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

Предположим, что у фермера есть участок сельскохозяйственной земли, скажем, L км. ² , который будет засеян пшеницей или ячменем, или их комбинацией. Фермер имеет ограниченное количество удобрений ( F килограммов) и пестицидов ( P килограммов). каждый квадратный километр пшеницы требуется F ₁ килограмм удобрений и 1 _На килограмм пестицидов, а на каждый квадратный километр ячменя требуется F _{килограмма} удобрений и 2 ₂ килограмма пестицидов. Пусть S ₁ — цена продажи пшеницы за квадратный километр, а S ₂ — цена продажи ячменя. Если обозначить площадь земель, засеянных пшеницей и ячменем, через x ₁ и x ₂ соответственно, то прибыль можно максимизировать, выбрав оптимальные значения x ₁ и x ₂ . Эту проблему можно выразить с помощью следующей задачи линейного программирования в стандартной форме:

Максимизировать: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(максимизировать доход (общий объем продаж пшеницы плюс общий объем продаж ячменя) – доход является «целевой функцией»)
С учетом:	$x_{1}+x_{2}\leq L$	(ограничение по общей площади)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(ограничение на удобрения)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(ограничение на пестициды)
	$x_{1}\geq 0,x_{2}\geq 0$	(невозможно посадить отрицательную область).

В матричной форме это выглядит так:

максимизировать ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

при условии ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.$

Дополненная форма (расслабленная форма)

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

Максимизировать $z$:

${\begin{bmatrix}1&-\mathbf {c} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$

$\mathbf {x} \geq 0,\mathbf {s} \geq 0$

где $\mathbf {s}$ — это недавно введенные слабые переменные, $\mathbf {x}$ являются переменными решения, и $z$ – это переменная, которую необходимо максимизировать.

Пример

Приведенный выше пример преобразуется в следующую расширенную форму:

Максимизировать: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(целевая функция)
подлежит:	$x_{1}+x_{2}+x_{3}=L$	(дополненное ограничение)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	(дополненное ограничение)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P$	(дополненное ограничение)
	$x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.$

где $x_{3},x_{4},x_{5}$ являются (неотрицательными) резервными переменными, представляющими в этом примере неиспользованную площадь, количество неиспользованных удобрений и количество неиспользованных пестицидов.

В матричной форме это выглядит так:

Максимизировать $z$:

$${\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.$$

Двойственность

Основная статья: Двойная линейная программа

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

Максимизировать c ^Т x при условии A x ≤ b , x ≥ 0;

с соответствующей симметричной двойственной задачей,

Минимизировать б ^Т y подлежит А ^Т у ≥ с , у ≥ 0.

Альтернативная основная формулировка:

Максимизировать c ^Т x при условии A x ≤ b ;

с соответствующей асимметричной двойственной задачей,

Минимизировать б ^Т y подлежит А ^Т у знак равно с , у ≥ 0.

Есть две фундаментальные идеи теории дуальности. Одним из них является тот факт, что (для симметричной двойственной программы) двойственной к двойственной линейной программе является исходная первичная линейная программа. Кроме того, каждое допустимое решение для линейной программы дает границу оптимального значения целевой функции ее двойственной программы. Теорема о слабой двойственности утверждает, что значение целевой функции двойственного решения при любом допустимом решении всегда больше или равно значению целевой функции простого решения при любом допустимом решении. Теорема сильной двойственности утверждает, что если простое число имеет оптимальное решение, x ^* , то двойственное решение также имеет оптимальное решение, y ^* , и с ^Т х ^* = б ^Т и ^* .

Линейная программа также может быть неограниченной или неосуществимой. Теория двойственности говорит нам, что если простое число неограничено, то двойственное невозможно в соответствии с теоремой слабой двойственности. Аналогично, если двойственное неограниченно, то первичное должно быть неосуществимо. Однако возможно, что и двойственное, и первичное могут оказаться невозможными. см. в разделе «Двойная линейная программа» Подробности и несколько примеров .

Вариации

Двойственности покрытия/упаковки

Покрывающая ЛП представляет собой линейную программу вида:

Минимизировать: б ^Т и ,

предмет: А ^Т у ≥ с , у ≥ 0 ,

такие, что матрица A и векторы b и c неотрицательны.

Двойственной накрывающей LP является упаковка LP — линейная программа вида:

Максимизировать: c ^Т х ,

при условии: A x ≤ b , x ≥ 0 ,

такие, что матрица A и векторы b и c неотрицательны.

Примеры

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

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

Дополнительная расслабленность

Можно получить оптимальное решение двойственной задачи, когда известно только оптимальное решение прямой задачи, используя теорему о дополнительной нежесткости. Теорема гласит:

Предположим, что x = ( x ₁ , x ₂ , ... , x _n ) является простым допустимым и что y = ( y ₁ , y ₂ , ... , y _m ) является двойственно допустимым. Пусть ( w ₁ , w ₂ , ..., w _m ) обозначают соответствующие основные резервные переменные, и пусть ( z ₁ , z ₂ , ... , z _n ) обозначают соответствующие двойственные резервные переменные. Тогда x и y оптимальны для своих задач тогда и только тогда, когда

• x _j z _j = 0, для j = 1, 2, ..., n и
• w _я y _я знак равно 0, для я знак равно 1, 2, ... , м .

Таким образом, если i -я слабая переменная простого числа не равна нулю, то i -я переменная двойственного равна нулю. Аналогично, если j -я слабая переменная двойственного не равна нулю, то j -я переменная простого равна нулю.

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

Теория

Наличие оптимальных решений

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

Оптимальное решение не обязательно должно существовать по двум причинам. Во-первых, если ограничения противоречивы, то допустимого решения не существует: например, ограничения x ≥ 2 и x ≤ 1 не могут быть удовлетворены совместно; в этом случае мы говорим, что ЛП невозможна . Во-вторых, когда многогранник неограничен в направлении градиента целевой функции (где градиент целевой функции представляет собой вектор коэффициентов целевой функции), то оптимальное значение не достигается, поскольку всегда можно сделать лучше, чем любое конечное значение целевой функции.

Оптимальные вершины (и лучи) многогранников

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

Вершины многогранника также называются основными допустимыми решениями . Причина такого выбора названия следующая. Пусть d обозначает количество переменных. Тогда из фундаментальной теоремы линейных неравенств следует (для допустимых задач), что для каждой вершины x ^* допустимой области LP, существует набор из d (или меньшего количества) ограничений-неравенств из LP, такой, что, когда мы рассматриваем эти d ограничения как равенства, единственным решением является x ^* . Таким образом, мы можем изучать эти вершины, рассматривая определенные подмножества набора всех ограничений (дискретный набор), а не континуум решений ЛП. Этот принцип лежит в основе симплексного алгоритма решения линейных программ.

Алгоритмы

См. Также: Список тем численного анализа § Линейное программирование.

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

Алгоритмы обмена базой

Симплексный алгоритм Данцига

Симплексный алгоритм , разработанный Джорджем Данцигом в 1947 году, решает задачи ЛП путем построения допустимого решения в вершине многогранника и последующего обхода пути по ребрам многогранника к вершинам с неубывающими значениями целевой функции до тех пор, пока не будет найдено оптимум будет достигнут наверняка. Во многих практических задачах происходит « срыв »: многие повороты выполняются без увеличения целевой функции. В редких практических задачах обычные версии симплексного алгоритма могут фактически «зацикливаться». Чтобы избежать циклов, исследователи разработали новые правила поворота.

На практике симплексный алгоритм весьма эффективен и может гарантированно найти глобальный оптимум, если будут приняты определенные меры предосторожности против цикличности . Доказано, что симплексный алгоритм эффективно решает «случайные» задачи, т.е. за кубическое число шагов: что похоже на его поведение в практических задачах.

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

Алгоритм крест-накрест

Как и симплексный алгоритм Данцига, алгоритм крест-накрест представляет собой алгоритм обмена базисами, который вращается между базисами. Однако алгоритм перекрещивания не обязательно должен поддерживать выполнимость, а может скорее переходить от осуществимой основы к неосуществимой. Алгоритм крест-накрест не имеет полиномиальной временной сложности для линейного программирования. Оба алгоритма посещают все 2 ^Д углы (возмущенного) куба в размерности D , куба Кли-Минти в худшем случае .

Внутренняя точка

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

Эллипсоидный алгоритм по Хачияну

Это первый наихудшего случая, алгоритм с полиномиальным временем когда-либо найденный для линейного программирования. Чтобы решить задачу, которая имеет n переменных и может быть закодирована L входными битами, этот алгоритм выполняется в $O(n^{6}L)$ время. Леонид Хачиян решил эту давнюю проблему сложности в 1979 году, представив метод эллипсоидов . Анализ сходимости имеет предшественников (действительных чисел), в частности, итерационные методы, разработанные Наумом З. Шором , и аппроксимационные алгоритмы Аркадия Немировского и Д. Юдина.

Проективный алгоритм Кармаркара

Основная статья: алгоритм Кармаркара

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

Однако алгоритм Хачияна вдохновил на новые направления исследований в области линейного программирования. В 1984 году Н. Кармаркар предложил проективный метод линейного программирования. Алгоритм Кармаркара улучшился по сравнению с Хачияном полиномиальная оценка наихудшего случая (давая $O(n^{3.5}L)$). Кармаркар утверждал, что его алгоритм на практике работает намного быстрее, чем симплексный метод, и это утверждение вызвало большой интерес к методам внутренней точки. Со времени открытия Кармаркара было предложено и проанализировано множество методов внутренних точек.

Алгоритм Вайдьи 87

В 1987 году Вайдья предложил алгоритм, работающий в $O(n^{3})$ время.

Алгоритм Вайдьи 89

В 1989 году Вайдья разработал алгоритм, работающий в $O(n^{2.5})$ время. Формально говоря, алгоритм принимает $O((n+d)^{1.5}nL)$ арифметические операции в худшем случае, где $d$ количество ограничений, $n$ количество переменных, а $L$ это количество битов.

Алгоритмы входного времени разреженности

В 2015 году Ли и Сидфорд показали, что линейное программирование можно решить за ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ время, где ${\tilde {O}}$ обозначает мягкое обозначение O , а $nnz(A)$ представляет количество ненулевых элементов и продолжает принимать $O(n^{2.5}L)$ в худшем случае.

Алгоритм времени умножения текущей матрицы

В 2019 году Коэн, Ли и Сон улучшили время бега до ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ время, $\omega$ является показателем матричного умножения и $\alpha$ — двойной показатель матричного умножения . $\alpha$ (примерно) определяется как наибольшее число, на которое можно умножить $n\times n$ матрица по $n\times n^{\alpha }$ матрица в $O(n^{2})$ время. В последующей работе Ли, Сун и Чжана они воспроизвели тот же результат другим методом. Эти два алгоритма остаются ${\tilde {O}}(n^{2+1/6}L)$ когда $\omega =2$ и $\alpha =1$. Результат благодаря Цзяну, Сун, Вайнштейну и Чжану улучшился. ${\tilde {O}}(n^{2+1/6}L)$ к ${\tilde {O}}(n^{2+1/18}L)$.

Сравнение методов внутренней точки и симплексных алгоритмов

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

Открытые проблемы и недавние работы

Нерешенная задача в информатике :

Допускает ли линейное программирование алгоритм со строго полиномиальным временем?

(еще нерешенные проблемы по информатике)

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

• Допускает ли LP строго полиномиальный алгоритм?
• Допускает ли LP алгоритм со строго полиномиальным временем для поиска строго дополнительного решения?
• Допускает ли LP алгоритм с полиномиальным временем в модели вычислений с действительным числом (единичная стоимость)?

Этот тесно связанный набор проблем был назван Стивеном Смейлом среди 18 величайших нерешенных проблем 21 века. По словам Смейла, третий вариант задачи «является основной нерешенной проблемой теории линейного программирования». Хотя существуют алгоритмы для решения линейного программирования за слабо полиномиальное время , такие как методы эллипсоида и методы внутренней точки , еще не найдено алгоритмов, которые обеспечивают производительность в строго полиномиальном времени по количеству ограничений и количеству переменных. Разработка таких алгоритмов представляла бы большой теоретический интерес и, возможно, позволила бы получить практические результаты и при решении больших ЛП.

Хотя гипотеза Хирша для высших размерностей недавно была опровергнута, она все еще оставляет открытыми следующие вопросы.

• Существуют ли правила поворота, которые приводят к симплексным вариантам с полиномиальным временем?
• Все ли многогранные графы имеют полиномиально ограниченный диаметр?

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

Симплексный алгоритм и его варианты относятся к семейству алгоритмов следования по ребрам, названных так потому, что они решают задачи линейного программирования, перемещаясь от вершины к вершине вдоль ребер многогранника. Это означает, что их теоретическая производительность ограничена максимальным количеством ребер между любыми двумя вершинами многогранника LP. В результате нас интересует максимальный теоретико-графовый диаметр многогранных графов . Доказано, что все многогранники имеют субэкспоненциальный диаметр. Недавнее опровержение гипотезы Хирша является первым шагом к доказательству того, что какой-либо многогранник имеет суперполиномиальный диаметр. Если такие многогранники существуют, то ни один вариант с следованием по ребру не может работать за полиномиальное время. Вопросы о диаметре многогранника представляют самостоятельный математический интерес.

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

Целочисленные неизвестные

Если все неизвестные переменные должны быть целыми числами, то проблема называется проблемой целочисленного программирования (IP) или целочисленного линейного программирования (ILP). В отличие от линейного программирования, которое можно эффективно решить в худшем случае, задачи целочисленного программирования во многих практических ситуациях (с ограниченными переменными) являются NP-трудными . Целочисленное программирование 0–1 или двоично-целое программирование (BIP) — это особый случай целочисленного программирования, когда переменные должны быть равны 0 или 1 (а не произвольным целым числам). Эта задача также классифицируется как NP-трудная, и фактически вариант решения был одной из 21 NP-полной задачи Карпа .

Если только некоторые из неизвестных переменных должны быть целыми числами, то проблема называется задачей смешанного целочисленного (линейного) программирования (MIP или MILP). Как правило, они также являются NP-сложными, поскольку они даже более общие, чем программы ПДОДИ.

Однако существуют некоторые важные подклассы проблем IP и MIP, которые эффективно разрешимы, в первую очередь проблемы, в которых матрица ограничений полностью унимодулярна , а правые части ограничений являются целыми числами или, в более общем смысле, когда система имеет полную двойственную целочисленность. (ТДИ) собственность.

Расширенные алгоритмы решения целочисленных линейных программ включают в себя:

• метод секущей плоскости
• Ветвь и граница
• Ветка и разрез
• Филиал и цена
• если проблема имеет дополнительную структуру, можно применить отложенную генерацию столбцов .

Такие алгоритмы целочисленного программирования обсуждаются Падбергом и Бисли.

Интегральные линейные программы

Дополнительная информация: Целочисленный многогранник.

Линейная программа с действительными переменными называется целой , если она имеет хотя бы одно оптимальное решение, которое является целым, т. е. состоит только из целочисленных значений. Аналогично многогранник $P=\{x\mid Ax\geq 0\}$ называется целой, если для всех ограниченных допустимых целевых функций c линейная программа $\{\max cx\mid x\in P\}$ имеет оптимум $x^{*}$ с целочисленными координатами. Как заметили Эдмондс и Джайлз в 1977 году, можно аналогичным образом сказать, что многогранник $P$ является целым, если для каждой ограниченной допустимой интегральной целевой функции c оптимальное значение линейной программы $\{\max cx\mid x\in P\}$ является целым числом.

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

Терминология не является единообразной во всей литературе, поэтому следует внимательно различать следующие два понятия:

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

Один из распространенных способов доказать целочисленность многогранника — показать, что он полностью унимодулярен . Существуют и другие общие методы, включая свойство целочисленной декомпозиции и полную двойственную целостность . Другие конкретные, хорошо известные целочисленные ЛП включают совпадающий многогранник, решетчатые многогранники, субмодульные многогранники потока и пересечение двух обобщенных полиматроидов/ g -полиматроидов – например, см. Schrijver 2003.

Решатели и языки сценариев (программирования)

Разрешительные лицензии:

Имя	Лицензия	Краткая информация
Гекко	МОЯ лицензия	Библиотека с открытым исходным кодом для решения крупномасштабных задач LP, QP , QCQP , NLP и MIP. оптимизации
ЩЕЛЧОК	Апач v2	Решатель линейного программирования Google с открытым исходным кодом
ЮМП	Лицензия МПЛ	Язык моделирования с открытым исходным кодом и решателями для крупномасштабной LP, QP , QCQP , SDP , SOCP , NLP и MIP оптимизации .
Пёмо	БСД	Язык моделирования с открытым исходным кодом для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации.
SCIP	Апач v2	Решатель целочисленного программирования с ограничениями общего назначения с упором на MIP. Совместим с языком моделирования Zimpl.
Суан Шу	Апач v2	Набор алгоритмов оптимизации с открытым исходным кодом для решения LP, QP , SOCP , SDP , SQP на Java.

Копилефт (взаимные) лицензии:

Имя	Лицензия	Краткая информация
АЛГЛИБ	Лицензионная лицензия 2+	Решатель LP из проекта ALGLIB (C++, C#, Python)
Решатель казуарных ограничений	LGPL	Инструментарий для постепенного решения ограничений, который эффективно решает системы линейных равенств и неравенств.
CLP	CPL	Решатель LP от COIN-OR
глпк	лицензия GPL	GNU Linear Programming Kit, решатель LP/MILP с собственным API C и многочисленными (15) сторонними оболочками для других языков. Специализированная поддержка потоковых сетей . Содержит AMPL -подобный язык моделирования GNU MathProg и транслятор.
лп решить	LGPL v2.1	Решающая программа LP и MIP с поддержкой формата MPS и собственного формата «lp», а также пользовательских форматов через «внешний языковой интерфейс» (XLI). Также возможен перевод между форматами моделей.
Старик	лицензия GPL	Библиотека для пошагового решения систем линейных уравнений с различными целевыми функциями.
Р-Проект	лицензия GPL	Язык программирования и программная среда для статистических вычислений и графики.

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

Собственные лицензии:

Имя	Краткая информация
АИММС	Язык моделирования, позволяющий моделировать линейные, смешанные целочисленные и нелинейные модели оптимизации. Он также предлагает инструмент для программирования в ограничениях. Алгоритм также может быть реализован в форме эвристики или точных методов, таких как метод ветвей и разрезов или генерация столбцов. Инструмент вызывает соответствующий решатель, такой как CPLEX или аналогичный, для решения рассматриваемой задачи оптимизации. Академические лицензии предоставляются бесплатно.
АЛГЛИБ	Коммерческое издание лицензионной библиотеки с авторским левом. С++, С#, Питон.
AMPL	Популярный язык моделирования для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации. Доступна бесплатная версия, ограниченная для студентов (500 переменных и 500 ограничений).
Аналитика	Общий язык моделирования и интерактивная среда разработки. Его диаграммы влияния позволяют пользователям формулировать проблемы в виде графиков с узлами для переменных решения, целей и ограничений. Analytica Optimizer Edition включает в себя линейные, смешанные целочисленные и нелинейные решатели и выбирает решатель, соответствующий задаче. Он также принимает в качестве плагинов другие движки, включая XPRESS , Gurobi, Artelys Knitro и MOSEK .
APMonitor	API для MATLAB и Python. Решите примеры задач линейного программирования (LP) с помощью MATLAB, Python или веб-интерфейса.
Комплексный комплекс	Популярный решатель с API для нескольких языков программирования, а также имеет язык моделирования и работает с AIMMS, AMPL, GAMS , MPL, OpenOpt, OPL Development Studio и TOMLAB . Бесплатно для академического использования.
Excel Функция решения	Нелинейный решатель, адаптированный к электронным таблицам, в которых оценки функций основаны на пересчете ячеек. Базовая версия доступна как стандартное дополнение к Excel.
ФортМП
ГАМС
Оптимизатор Гуроби
Числовые библиотеки IMSL	Коллекции математических и статистических алгоритмов доступны на C/C++, Fortran, Java и C#/.NET. Процедуры оптимизации в библиотеках IMSL включают в себя неограниченную, линейно и нелинейно ограниченную минимизацию, а также алгоритмы линейного программирования.
КРАСИВЫЙ	Решатель с API для крупномасштабной оптимизации линейных, целочисленных, квадратичных, конических и общих нелинейных программ с расширениями стохастического программирования. Он предлагает процедуру глобальной оптимизации для поиска гарантированного глобально оптимального решения общих нелинейных программ с непрерывными и дискретными переменными. Он также имеет API статистической выборки для интеграции моделирования Монте-Карло в структуру оптимизации. Он имеет язык алгебраического моделирования ( LINGO ) и позволяет моделировать в электронной таблице ( What'sBest ).
Клен	Язык программирования общего назначения для символьных и числовых вычислений.
МАТЛАБ	Универсальный матрично-ориентированный язык программирования для численных вычислений. Для линейного программирования в MATLAB требуется Optimization Toolbox в дополнение к базовому продукту MATLAB ; доступные процедуры включают INTLINPROG и LINPROG.
Маткад	Математический редактор WYSIWYG. Он имеет функции для решения как линейных, так и нелинейных задач оптимизации.
Математика	Язык программирования общего назначения для математики, включая символьные и числовые возможности.
МОИСЕЙ	Решатель для крупномасштабной оптимизации с API для нескольких языков (C++, Java, .net, Matlab и Python).
Цифровая библиотека НАГ	Коллекция математических и статистических процедур, разработанных группой числовых алгоритмов для нескольких языков программирования (C, C++, Fortran, Visual Basic, Java и C#) и пакетов (MATLAB, Excel, R, LabVIEW). Глава «Оптимизация» библиотеки NAG включает процедуры для решения задач линейного программирования как с разреженными, так и с неразреженными матрицами линейных ограничений, а также процедуры для оптимизации квадратичных, нелинейных сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными ограничениями или без них. . В библиотеке NAG есть процедуры как для локальной, так и для глобальной оптимизации, а также для решения непрерывных или целочисленных задач.
ОптимДж	Язык моделирования на основе Java для оптимизации, доступна бесплатная версия.
САС /ИЛИ	Набор решателей для линейной, целочисленной, нелинейной, без производной, сетевой, комбинаторной оптимизации и оптимизации с ограничениями; язык алгебраического моделирования OPTMODEL; и множество вертикальных решений, направленных на конкретные проблемы/рынки, все из которых полностью интегрированы с системой SAS .
XPRESS	Решатель для крупномасштабных линейных программ, квадратичных программ, общих нелинейных и смешанно-целочисленных программ. Имеет API для нескольких языков программирования, также имеет язык моделирования Mosel и работает с AMPL, GAMS . Бесплатно для академического использования.
ВисСим	Язык визуальных блок-схем для моделирования динамических систем .

См. также

• Выпуклое программирование
• Динамическое программирование
• Ожидаемый дефицит § Оптимизация ожидаемого дефицита
• Модель ввода-вывода
• График работы цеха
• Наименьшие абсолютные отклонения
• Спектральный анализ методом наименьших квадратов
• Линейная алгебра
• Линейная производственная игра
• Дробно-линейное программирование (ДЛП)
• Проблема типа LP
• Математическое программирование
• Нелинейное программирование
• Алгоритм шансов, используемый для решения задач оптимальной остановки
• Ориентированный матроид
• Квадратичное программирование — надмножество линейного программирования.
• Полуопределенное программирование
• Теневая цена
• Симплексный алгоритм , используемый для решения задач ЛП.

Ссылки

• Kantorovich, L. V. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [A new method of solving some classes of extremal problems]. Doklady Akad Sci SSSR . 28 : 211–214.
• Ф. Л. Хичкок: Распространение продукта из нескольких источников в многочисленные места , Журнал математики и физики, 20, 1941, 224–230.
• ГБ Данциг: Максимизация линейной функции переменных с учетом линейных неравенств , 1947. Опубликовано стр. 339–347 в журнале TC Koopmans (ред.): Анализ деятельности производства и распределения , Нью-Йорк-Лондон, 1951 (Wiley & Chapman-Hall).
• Дж. Э. Бизли, редактор. Достижения в области линейного и целочисленного программирования . Oxford Science, 1996. (Сборник опросов).
• Бланд, Роберт Г. (1977). «Новые правила конечного поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. дои : 10.1287/moor.2.2.103 . JSTOR   3689647 .
• Боргвардт, Карл-Хайнц (1987). Симплексный алгоритм: вероятностный анализ . Алгоритмы и комбинаторика. Том. 1. Шпрингер-Верлаг. (Среднее поведение при решении случайных задач)
• Ричард В. Коттл, изд. Базовый Джордж Б. Данциг . Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния, 2003 г. (Избранные статьи Джорджа Б. Данцига )
• Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Спрингер-Верлаг.
• Данциг, Джордж Б.; Тапа, Мукунд Н. (2003). Линейное программирование 2: Теория и расширения . Спрингер-Верлаг. (Всеобъемлющий, охватывающий, например, алгоритмы поворота и внутренней точки, крупномасштабные проблемы, декомпозицию по Данцигу – Вольфу и Бендерсу , а также введение в стохастическое программирование .)
• Эдмондс, Джек; Джайлз, Рик (1977). «Соотношение Мин-Макс для субмодулярных функций на графах». Исследования по целочисленному программированию . Анналы дискретной математики. Том. 1. С. 185–204. дои : 10.1016/S0167-5060(08)70734-9 . ISBN  978-0-7204-0765-5 .
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. 79 (1–3): 369–395. CiteSeerX   10.1.1.36.9373 . дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 .
• Гондзио, Яцек; Терлаки, Тамаш (1996). «3 Вычислительный взгляд на методы внутренней точки» . В Дж. Э. Бисли (ред.). Достижения в области линейного и целочисленного программирования . Оксфордская серия лекций по математике и ее приложениям. Том. 4. Нью-Йорк: Издательство Оксфордского университета. стр. 103–144. МР   1438311 . Постскриптум-файл на веб-сайте Гондзио и на веб-сайте Университета Макмастера в Терлаки .
• Мурти, Катта Г. (1983). Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc., стр. xix+482. ISBN  978-0-471-09725-9 . МР   0720547 . (комплексная ссылка на классические подходы).
• Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и связанные с ними проблемы , Academic Press. (элементарный)
• Падберг, М. (1999). Линейная оптимизация и расширения, второе издание . Спрингер-Верлаг. (тщательно написанный отчет о простых и двойственных симплекс-алгоритмах и проективных алгоритмах с введением в целочисленное линейное программирование, включая задачу коммивояжера для Одиссея .)
• Пападимитриу, Христос Х .; Стейглиц, Кеннет. Комбинаторная оптимизация: алгоритмы и сложность (исправленная публикация с новым предисловием). Дувр. (Информатика)
• Тодд, Майкл Дж. (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование . 91 (3): 417–436. дои : 10.1007/s101070100261 . S2CID   6464735 . (Приглашенный опрос с Международного симпозиума по математическому программированию.)
• Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Спрингер Верлаг.
• Vazirani, Vijay V. (2001). Approximation Algorithms . Springer-Verlag. ISBN  978-3-540-65367-7 . (Информатика)

Дальнейшее чтение

• Дмитрис Алеврас и Манфред В. Падберг, Линейная оптимизация и расширения: проблемы и решения , Universitext, Springer-Verlag, 2001. (Задачи Падберга с решениями.)
• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000). Вычислительная геометрия (2-е исправленное изд.). Издательство Спрингер . ISBN  978-3-540-65620-3 . Глава 4: Линейное программирование: стр. 63–94. Описывает рандомизированный алгоритм пересечения полуплоскостей для линейного программирования.
• Майкл Р. Гари и Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  978-0-7167-1045-5 . A6: MP1: ЦЕЛОЕ ПРОГРАММИРОВАНИЕ, стр. 245. (информатика, теория сложности)
• Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN  3-540-30697-8 . (элементарное введение для математиков и информатиков)
• Корнелис Роос, Тамаш Терлаки, Жан-Филипп Виал, Методы внутренних точек для линейной оптимизации , второе издание, Springer-Verlag, 2006 г. (выпускной уровень)
• Александр Шрийвер (2003). Комбинаторная оптимизация: многогранники и эффективность . Спрингер.
• Александр Шрийвер, Теория линейного и целочисленного программирования . Джон Уайли и сыновья, 1998 г. ISBN   0-471-98232-6 (математический)
• Жерар Сиерксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика . ЦРК Пресс. ISBN  978-1-498-71016-9 .
• Жерар Сиерксма; Диптеш Гош (2010). Сети в действии; Текстовые и компьютерные упражнения по оптимизации сети . Спрингер. ISBN  978-1-4419-5512-8 . (линейное оптимизационное моделирование)
• HP Williams, Построение моделей в математическом программировании , пятое издание, 2013 г. (Моделирование)
• Стивен Дж. Райт, 1997, Методы первично-двойственной внутренней точки , SIAM. (высший уровень)
• Инью Е , 1997, Алгоритмы внутренних точек: теория и анализ , Wiley. (Продвинутый уровень магистратуры)
• Циглер, Гюнтер М. , главы 1–3 и 6–7 в книге «Лекции по многогранникам» , Springer-Verlag, Нью-Йорк, 1994. (Геометрия)

Внешние ссылки

• Руководство по формулировке задач ЛП
• Глоссарий по математическому программированию
• Часто задаваемые вопросы по линейному программированию
• Тесты для программного обеспечения для оптимизации