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

Относительно ретронима, относящегося к телевизионному вещанию, см. Вещательное программирование.

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

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

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

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

Линейные программы - это проблемы, которые можно выразить в каноническая форма так как

${\displaystyle {\begin{aligned}&{\text{Maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}$

где Икс представляет собой вектор переменных (предстоит определить), c и б находятся векторов (известных) коэффициентов, А является (известным) матрица коэффициентов и ${\displaystyle (\cdot )^{\mathrm {T} }}$ это матрица транспонировать. Выражение, которое нужно максимизировать или минимизировать, называется целевая функция (c^ТИкс в таком случае). Неравенства АИкс ≤ б и Икс ≥ 0 ограничения, которые определяют выпуклый многогранник над которым должна быть оптимизирована целевая функция. В этом контексте два вектора сопоставимый когда они имеют одинаковые размеры. Если каждая запись в первом меньше или равна соответствующей записи во втором, то можно сказать, что первый вектор меньше или равен второму вектору.

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

История

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

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

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

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

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

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

Впервые было показано, что задача линейного программирования разрешима за полиномиальное время с помощью Леонид Хачиян в 1979 г.^[5] но больший теоретический и практический прорыв в этой области произошел в 1984 г., когда Нарендра Кармаркар представил новый метод внутренней точки для решения задач линейного программирования.^[6]

Использует

Линейное программирование - широко используемая область оптимизации по нескольким причинам. Многие практические проблемы в исследование операций можно выразить в виде задач линейного программирования.^[3] Некоторые частные случаи линейного программирования, такие как сетевой поток проблемы и многопродуктовый поток проблемы считаются достаточно важными, чтобы провести много исследований специализированных алгоритмов их решения. Ряд алгоритмов для других типов задач оптимизации работают, решая задачи LP как подзадачи. Исторически идеи линейного программирования вдохновляли многие из центральных концепций теории оптимизации, такие как двойственность разложение и важность выпуклость и его обобщения. Точно так же линейное программирование активно использовалось на раннем этапе формирования микроэкономика и в настоящее время он используется в управлении компанией, например, в планировании, производстве, транспортировке, технологиях и других вопросах. Хотя современные проблемы управления постоянно меняются, большинство компаний хотели бы максимизировать прибыль и минимизировать затраты с ограниченными ресурсами. Поэтому многие проблемы можно охарактеризовать как задачи линейного программирования.

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

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

• А линейная функция для максимизации

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

• Ограничения проблемы следующего вида

например

${\displaystyle {\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}}}$

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

например

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

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

${\displaystyle \max\{\mathbf {c} ^{\mathrm {T} }\mathbf {x} \;|\;A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\}}$

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

пример

Предположим, что у фермера есть участок сельскохозяйственной земли, скажем L км², для посадки пшеницы или ячменя или их комбинации. У фермера ограниченное количество удобрений, F килограммы, и пестициды, п килограммы. На каждый квадратный километр пшеницы требуется F₁ килограммы удобрений и п₁ килограммов пестицида, а на каждый квадратный километр ячменя требуется F₂ килограммы удобрений и п₂ килограммы пестицида. Давайте₁ быть продажной ценой пшеницы за квадратный километр, а S₂ цена продажи ячменя. Если обозначить площадь земель, засеянных пшеницей и ячменем, через Икс₁ и Икс₂ соответственно, то прибыль можно максимизировать, выбрав оптимальные значения для Икс₁ и Икс₂. Эта проблема может быть выражена следующей задачей линейного программирования в стандартной форме:

Максимизировать: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(максимизировать доход - доход - это "целевая функция")
При условии:	${\displaystyle x_{1}+x_{2}\leq L}$	(ограничение на общую площадь)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(ограничение на удобрения)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(ограничение по пестицидам)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(нельзя засаживать отрицательную зону).

В матричной форме это становится:

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

при условии ${\displaystyle {\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}}.}$

Расширенная форма (свободная форма)

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

Максимизировать ${\displaystyle z}$:

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{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}}}$

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

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

пример

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

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

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

В матричной форме это становится:

Максимизировать ${\displaystyle z}$:

${\displaystyle {\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^ТИкс при условии АИкс ≤ б, Икс ≥ 0;

с соответствующими симметричный двойная проблема,

Свести к минимуму б^Ту при условии А^Ту ≥ c, у ≥ 0.

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

Максимизировать c^ТИкс при условии АИкс ≤ б;

с соответствующими асимметричный двойная проблема,

Свести к минимуму б^Ту при условии А^Ту = c, у ≥ 0.

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

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

Вариации

Дуальности покрытия / упаковки

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

Свести к минимуму: б^Ту,

при условии: А^Ту ≥ c, у ≥ 0,

такая, что матрица А и векторы б и c неотрицательны.

Двойник покрытия LP - это упаковка LP, линейная программа вида:

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

при условии: АИкс ≤ б, Икс ≥ 0,

такая, что матрица А и векторы б и c неотрицательны.

Примеры

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

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

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

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

Предположим, что Икс = (Икс₁, Икс₂, ... , Икс_п) является примитивно допустимым и что у = (у₁, у₂, ... , у_м) двойственно допустима. Позволять (ш₁, ш₂, ..., ш_м) обозначают соответствующие переменные прямого запаса, и пусть (z₁, z₂, ... , z_п) обозначают соответствующие двойственные переменные запаса. потом Икс и у оптимальны для соответствующих задач тогда и только тогда, когда

• Икс_j z_j = 0, для j = 1, 2, ... , п, и
• ш_я у_я = 0, для я = 1, 2, ... , м.

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

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

Теория

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

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

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

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

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

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

Алгоритмы

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

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

Базовые алгоритмы обмена

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

В симплексный алгоритм, разработан Джордж Данциг в 1947 г. решает задачи ЛП путем построения допустимого решения в вершине многогранник и затем идти по пути по краям многогранника к вершинам с неубывающими значениями целевой функции, пока не будет точно достигнут оптимум. Во многих практических задачах "торможение "происходит: многие повороты выполняются без увеличения целевой функции.^[8][9] В редких практических задачах обычные версии симплексного алгоритма могут фактически «зацикливаться».^[9] Чтобы избежать циклов, исследователи разработали новые правила поворота.^{[10][11][8][9][12][13]}

На практике симплекс алгоритм довольно эффективен и может гарантировать достижение глобального оптимума, если принять определенные меры против кататься на велосипеде принимаются. Доказано, что симплексный алгоритм эффективно решает "случайные" задачи, т.е. за кубическое число шагов,^[14] что похоже на его поведение при решении практических задач.^[8][15]

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

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

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

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

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

Алгоритм эллипсоида по Хачияну

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нерешенная проблема в информатике: Допускает ли линейное программирование алгоритм с сильно полиномиальным временем? (больше нерешенных проблем в информатике)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Интегральный многогранник

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

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

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

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

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

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

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

имя	Лицензия	Краткая информация
Pyomo	BSD	Язык моделирования с открытым исходным кодом для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации
HiGHS	Массачусетский технологический институт	Последовательный и параллельный решатель с открытым исходным кодом для крупномасштабных моделей разреженного линейного программирования (LP)

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

имя	Лицензия	Краткая информация
Решатель ограничений казуара	LGPL	набор инструментов для постепенного решения ограничений, который эффективно решает системы линейных равенств и неравенств
CLP	CPL	решатель LP от COIN-OR
glpk	GPL	GNU Linear Programming Kit, решатель LP / MILP с родным C API и многочисленные (15) сторонние оболочки для других языков. Специализированная поддержка проточные сети. Связывает AMPL -любить GNU MathProg язык моделирования и переводчик.
Qoca	GPL	библиотека для пошагового решения систем линейных уравнений с различными целевыми функциями
R-Project	GPL	язык программирования и программная среда для статистических вычислений и графики

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

Проприетарный лицензии:

имя	Краткая информация
ЦЕЛИ	Язык моделирования, позволяющий моделировать линейные, смешанные целочисленные и нелинейные модели оптимизации. Он также предлагает инструмент для программирования ограничений. Также может быть реализован алгоритм в виде эвристики или точных методов, таких как Branch-and-Cut или Column Generation. Инструмент вызывает соответствующий решатель, такой как CPLEX, Gurobi или аналогичный, для решения поставленной задачи оптимизации. Академические лицензии выдаются бесплатно.
AMPL	Популярный язык моделирования для крупномасштабной линейной, смешанной целочисленной и нелинейной оптимизации с доступной бесплатной ограниченной версией для студентов (500 переменных и 500 ограничений).
APMonitor	API к MATLAB и Python. Пример решения Проблемы линейного программирования (LP) через MATLAB, Python или веб-интерфейс.
CPLEX	Популярный решатель с API для нескольких языков программирования, а также имеет язык моделирования и работает с AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio и ТОМЛАБ. Бесплатно для академического использования.
Excel Функция решателя	Нелинейный решатель, адаптированный к электронным таблицам, в которых оценки функций основаны на пересчете ячеек. Базовая версия доступна как стандартное дополнение для Excel.
FortMP
GAMS
Гуроби	Решатель с параллельными алгоритмами для крупномасштабных линейных программ, квадратичных программ и смешано-целочисленных программ. Бесплатно для академического использования.
Цифровые библиотеки IMSL	Коллекции математических и статистических алгоритмов доступны на C / C ++, Fortran, Java и C # /. NET. Процедуры оптимизации в библиотеках IMSL включают неограниченные, линейно и нелинейно ограниченные минимизации, а также алгоритмы линейного программирования.
LINDO	Решатель с API для крупномасштабной оптимизации линейных, целочисленных, квадратичных, конических и общих нелинейных программ с расширениями стохастического программирования. Он предлагает процедуру глобальной оптимизации для поиска гарантированного глобально оптимального решения общих нелинейных программ с непрерывными и дискретными переменными. Он также имеет API статистической выборки для интеграции моделирования Монте-Карло в структуру оптимизации. Имеет язык алгебраического моделирования (ЛИНГО ) и позволяет моделировать в электронной таблице (Что лучше ).
Клен	Универсальный язык программирования для символьных и числовых вычислений.
MATLAB	Универсальный матрично-ориентированный язык программирования для числовых вычислений. Для линейного программирования в MATLAB требуется Панель инструментов оптимизации в дополнение к базовому продукту MATLAB; доступные процедуры включают INTLINPROG и LINPROG
Mathcad	Математический редактор WYSIWYG. В нем есть функции для решения как линейных, так и нелинейных задач оптимизации.
Mathematica	Универсальный язык программирования для математики, включая символьные и числовые возможности.
МОСЕК	Решатель для крупномасштабной оптимизации с API для нескольких языков (C ++, java, .net, Matlab и python).
Цифровая библиотека NAG	Набор математических и статистических процедур, разработанных Группа численных алгоритмов для нескольких языков программирования (C, C ++, Fortran, Visual Basic, Java и C #) и пакетов (MATLAB, Excel, R, LabVIEW). Глава Оптимизация библиотеки NAG включает процедуры для задач линейного программирования как с разреженными, так и с неразреженными матрицами линейных ограничений, а также процедуры для оптимизации квадратичных, нелинейных сумм квадратов линейных или нелинейных функций с нелинейными, ограниченными или отсутствующими ограничениями. . В библиотеке NAG есть процедуры как для локальной, так и для глобальной оптимизации, а также для непрерывных или целочисленных задач.
Статистика NMath	Универсальный .СЕТЬ статистическая библиотека, содержащая симплексный решатель.[26]
OptimJ	Язык моделирования на основе Java для оптимизации, доступна бесплатная версия.[27][28]
SAS /ИЛИ	Набор решателей для линейной, целочисленной, нелинейной, без производной, сетевой, комбинаторной оптимизации и оптимизации ограничений; то Язык алгебраического моделирования ОПТМОДЕЛЬ; и различные вертикальные решения, направленные на конкретные проблемы / рынки, все из которых полностью интегрированы с Система SAS.
SCIP	Решатель целочисленного программирования с ограничениями общего назначения с упором на MIP. Совместим с Zimpl язык моделирования. Бесплатно для академического использования и доступно в исходном коде.
XPRESS	Решатель для крупномасштабных линейных программ, квадратичных программ, общих нелинейных и смешанно-целочисленных программ. Имеет API для нескольких языков программирования, также имеет язык моделирования Mosel и работает с AMPL, GAMS. Бесплатно для академического использования.
VisSim	Визуальный блок-схема язык для моделирования динамические системы.

Смотрите также

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

Заметки

1. Жерар Сирксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика (3-е изд.). CRC Press. п. 1. ISBN  978-1498710169.
2. Александр Шрайвер (1998). Теория линейного и целочисленного программирования. Джон Вили и сыновья. С. 221–222. ISBN  978-0-471-98232-6.
3. Джордж Б. Данциг (апрель 1982 г.). «Воспоминания об истоках линейного программирования». Письма об исследованиях операций. 1 (2): 43–48. Дои:10.1016/0167-6377(82)90043-8.
4. Данциг, Джордж Б .; Тапа, Мукунд Нараин (1997). Линейное программирование. Нью-Йорк: Спрингер. п. xxvii. ISBN  0387948333. OCLC  35318475.
5. Леонид Хачиян (1979). «Полиномиальный алгоритм линейного программирования». Доклады Академии Наук СССР. 224 (5): 1093–1096.
6. Нарендра Кармаркар (1984). «Новый алгоритм полиномиального времени для линейного программирования». Комбинаторика. 4 (4): 373–395. Дои:10.1007 / BF02579150. S2CID  7257867.
7. Вазирани (2001), п. 112)
8. Данциг и Тапа (2003) Ошибка harvtxt: нет цели: CITEREFDantzigThapa2003 (Помогите)
9. Падберг (1999) Ошибка harvtxt: цель отсутствует: CITEREFPadberg1999 (Помогите)
10. Блэнд (1977)
11. Мерти (1983)
12. Пападимитриу и Штайглиц Ошибка harvtxt: нет цели: CITEREFPapadimitriouSteiglitz (Помогите)
13. Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373. Дои:10.1007 / BF02614325. Г-Н  1464775. S2CID  2794181.
14. Боргвардт (1987) Ошибка harvtxt: цель отсутствует: CITEREFBorgwardt1987 (Помогите)
15. Тодд (2002) Ошибка harvtxt: нет цели: CITEREFTodd2002 (Помогите)
16. Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование. Серия А. 46 (1): 79–84. Дои:10.1007 / BF01585729. Г-Н  1045573. S2CID  33463483.
17. Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». Математический интеллект. 9 (2): 4–10. Дои:10.1007 / BF03025891. ISSN  0343-6993. Г-Н  0883185. S2CID  123541868.
18. Вайдья, Правин М. (1987). Алгоритм линейного программирования, требующий ${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$ арифметические операции. 28-й ежегодный симпозиум IEEE по основам компьютерных наук. FOCS.
19. Вайдья, Правин М. (1989). Ускоренное линейное программирование с помощью быстрого умножения матриц. 30-й ежегодный симпозиум по основам информатики. FOCS. Дои:10.1109 / SFCS.1989.63499.
20. Ли, Инь-Тат; Сидфорд, Аарон (2015). Эффективное обратное обслуживание и более быстрые алгоритмы линейного программирования. FOCS '15 Основы компьютерных наук. arXiv:1503.01752.
21. Коэн, Майкл Б .; Ли, Инь-Тат; Песня, Чжао (2018). Решение линейных программ в текущем времени умножения матрицы. 51-й ежегодный симпозиум ACM по теории вычислений. STOC'19. arXiv:1810.07896.
22. Ли, Инь-Тат; Песня, Чжао; Чжан, Цюи (2019). Решение минимизации эмпирического риска при умножении текущей матрицы. Конференция по теории обучения. COLT'19. arXiv:1905.04447.
23. Цзян, Шуньхуа; Песня, Чжао; Вайнштейн, Омри; Чжан, Хэнцзе (2020). Более быстрая инверсия динамической матрицы для более быстрых пластинок. arXiv:2004.07470.
24. Иллеш, Тибор; Терлаки, Тамаш (2002). «Методы поворота и внутренней точки: плюсы и минусы». Европейский журнал операционных исследований. 140 (2): 170. CiteSeerX  10.1.1.646.3539. Дои:10.1016 / S0377-2217 (02) 00061-9.
25. "COR @ L - Исследование вычислительной оптимизации в Lehigh". lehigh.edu.
26. «Линейное программирование на C #». centerpace.net.^{[постоянная мертвая ссылка ]}
27. http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ используется в модели оптимизации для сборочных линий смешанных моделей, Университет Мюнстера
28. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ используется в методике приближенного вычисления идеального равновесия для повторяющихся игр

использованная литература

• Канторович, Л. В. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [Новый метод решения некоторых классов экстремальных задач]. Доклады АН СССР. 28: 211–214.
• Ф. Л. Хичкок: Распространение продукта из нескольких источников во множество населенных пунктов, Журнал математики и физики, 20, 1941, 224–230.
• Дж. Б. Данциг: Максимизация линейной функции переменных с учетом линейных неравенств, 1947. Опубликовано с. 339–347 в T.C. Купманс (ред.):Анализ деятельности производства и распределения, Нью-Йорк-Лондон 1951 (Wiley & Chapman-Hall)
• Дж. Э. Бизли, редактор. Достижения в линейном и целочисленном программировании. Oxford Science, 1996. (Сборник обзоров)
• Блэнд, Роберт Г. (1977). «Новые правила конечного поворота для симплекс-метода». Математика исследования операций. 2 (2): 103–107. Дои:10.1287 / moor.2.2.103. JSTOR  3689647.
• Карл-Хайнц Боргвардт, Симплексный алгоритм: вероятностный анализ, Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987. (Среднее поведение для случайных задач)
• Ричард В. Коттл, изд. The Basic Джордж Б. Данциг. Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния, 2003 г. (Избранные статьи Джордж Б. Данциг )
• Джордж Б. Данциг и Мукунд Н. Тапа. 1997 г. Линейное программирование 1: Введение. Springer-Verlag.
• Джордж Б. Данциг и Мукунд Н. Тапа. 2003 г. Линейное программирование 2: теория и расширения. Springer-Verlag. (Комплексный, охватывающий, например, поворот и алгоритмы внутренней точки, крупномасштабные задачи, разложение по Данцигу – Вульфу и Бендеры, и представляя стохастическое программирование.)
• Эдмондс, Джек; Джайлз, Рик (1977). «Отношение минимум-максимум для субмодульных функций на графах». Исследования в области целочисленного программирования. Анналы дискретной математики. 1. С. 185–204. Дои:10.1016 / S0167-5060 (08) 70734-9. ISBN  978-0-7204-0765-5.
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B. 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. (элементарно)
• М. Падберг, Линейная оптимизация и расширения, Second Edition, Springer-Verlag, 1999. (тщательно написанный отчет о первичных и двойственных симплексных алгоритмах и проективных алгоритмах, с введением в целочисленное линейное программирование - с задача коммивояжера для Одиссей.)
• Христос Х. Пападимитриу и Кеннет Стейглиц, Комбинаторная оптимизация: алгоритмы и сложность, Исправленное переиздание с новым предисловием, Dover. (Информатика)
• Майкл Дж. Тодд (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование. 91 (3): 417–436. Дои:10.1007 / с101070100261. S2CID  6464735. (Приглашенный опрос с Международного симпозиума по математическому программированию.)
• Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения. Springer Verlag.
• Вазирани, Виджай В. (2001). Алгоритмы аппроксимации. Springer-Verlag. ISBN  978-3-540-65367-7. (Информатика)

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

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

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

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