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

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

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

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

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

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

${\ displaystyle {\ begin {align} & {\ text {Maximize}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {при условии}} && A \ mathbf {x} \ leq \ mathbf {b} \\ & {\ text {and}} && \ mathbf {x} \ geq \ mathbf {0} \ end {выровнено}}}$

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

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

История [ править ]

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

В 1939 г. постановка задачи линейного программирования, эквивалентная общей задаче линейного программирования, была дана советским математиком и экономистом Леонидом Канторовичем , который также предложил метод ее решения. ^[2] Это способ, который он разработал во время Второй мировой войны , чтобы планировать расходы и доходы, чтобы сократить расходы армии и увеличить потери, нанесенные противнику. ^{[ цитировать ]} Первоначально работа Канторовича в СССР игнорировалась . ^[3] Примерно в то же время, что и Канторович, голландско-американский экономист Т.К. Купманс.сформулировал классические экономические задачи в виде линейных программ. Позднее Канторович и Купманс разделили Нобелевскую премию по экономике 1975 года . ^[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\}}$

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

Пример [ править ]

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

Максимизировать: ${\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 ^T x при условии A x ≤ b , x ≥ 0;

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

Минимизировать b ^T y при условии, что A ^T y ≥ c , y ≥ 0.

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

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

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

Минимизируйте b ^T y при условии, что A ^T y = c , y ≥ 0.

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

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

Варианты [ править ]

Покрытие / упаковка дуальностей [ править ]

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

Минимизировать: b ^T y ,

при условии: A ^T y ≥ c , y ≥ 0 ,

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

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

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

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

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

Примеры [ править ]

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

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

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

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

Предположим, что 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 _i y _i  = 0 для i  = 1, 2, ...,  m .

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

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

Теория [ править ]

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

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

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

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

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

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

Алгоритмы [ править ]

Базовые алгоритмы обмена [ править ]

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

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

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

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

Перекрестный алгоритм [ править ]

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

Внутренняя точка [ править ]

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

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

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

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

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

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

Алгоритм Вайдьи 87 [ править ]

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

Алгоритм Вайдьи 89 [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Целочисленные неизвестные [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Разрешающие лицензии:

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

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

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

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме линейного программирования .

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