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

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

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

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

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

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

${\ displaystyle {\ begin {align} & {\ text {Найдите вектор}} && \ mathbf {x} \\ & {\ text {, который максимизирует}} && \ mathbf {c} ^ {T} \ mathbf {x } \\ & {\ text {subject to}} && A \ mathbf {x} \ leq \ mathbf {b} \\ & {\ text {and}} && \ mathbf {x} \ geq \ mathbf {0}. \ конец {выровнен}}}$

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

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

История

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

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

Проблема решения системы линейных неравенств восходит, по крайней мере, к Фурье , который в 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} \ mid \ mathbf {x} \ in \ mathbb {R} ^ {n} \ land A \ mathbf {х} \ 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 х_ {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 {х} \ 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 & 1 & 0 & 0 \\ 0 & F_ {1} & F_ {2} & 0 & 1 & 0 \\ 0 & P_ {1} & P_ {2} & 0 & 0 & 1 \\\ конец {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 неотрицательны.

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

Максимизировать: 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 входных битов, этот алгоритм работает в${\ Displaystyle О (п ^ {6} L)}$время. ^[5] Леонид Хачиян решил эту давнюю проблему сложности в 1979 году, введя метод эллипсоидов . У анализа сходимости есть предшественники (действительные числа), в частности итерационные методы, разработанные Наумом З. Шором, и алгоритмы аппроксимации, разработанные Аркадием Немировским и Д. Юдиным.

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

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

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

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

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

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

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

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

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

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

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

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

В настоящее время считается, что эффективность хороших реализаций симплекс-методов и методов внутренней точки одинакова для рутинных приложений линейного программирования. Однако для определенных типов задач 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) свойство.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

Примечания

Ссылки

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

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

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