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

Метод решения задач оптимизации

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

Использует

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

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

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

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

например ${\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} ^{\mathsf {T}}\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

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

Пример

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

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

В матричной форме это принимает вид:

максимизировать ${\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} ^{\mathsf {T}}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$

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

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

Пример

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

где — (неотрицательные) резервные переменные, представляющие в этом примере неиспользованную площадь, количество неиспользованных удобрений и количество неиспользованных пестицидов. ${\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.

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

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

Вариации

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

Покрывающая 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 обычно возникают как релаксация линейного программирования комбинаторной задачи и важны при изучении алгоритмов приближения . ^[12] Например, релаксации LP задачи упаковки множеств , задачи независимого множества и задачи сопоставления являются упаковочными LP. Релаксации LP задачи покрытия множеств , задачи покрытия вершин и задачи доминирующего множества также являются покрывающими LP.

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

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

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

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

Алгоритмы

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

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

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

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

На практике симплексный алгоритм довольно эффективен и может гарантированно найти глобальный оптимум, если принять определенные меры предосторожности против цикличности . Было доказано, что симплексный алгоритм эффективно решает «случайные» задачи, т. е. за кубическое число шагов, ^[16], что похоже на его поведение на практических задачах. ^{[13] [17]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 2019 году Коэн, Ли и Сонг улучшили время выполнения по времени, является показателем умножения матриц и является двойным показателем умножения матриц . ^[25] (приблизительно) определяется как наибольшее число, такое, что можно умножить матрицу на матрицу за время. В последующей работе Ли, Сонга и Чжана они воспроизводят тот же результат другим методом. ^[26] Эти два алгоритма остаются , когда и . Результат, полученный Цзяном, Сонгом, Вайнштейном и Чжаном, улучшился до . ^[27] ${\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 может оказаться, что один тип решателя лучше другого (иногда намного лучше), и что структура решений, генерируемых методами внутренних точек по сравнению с симплексными методами, существенно отличается, при этом набор поддержки активных переменных обычно меньше для последнего. ^[28]

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

Нерешенная проблема в информатике :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. фон Нейман, Дж. (1945). «Модель общего экономического равновесия». Обзор экономических исследований . 13 : 1–9.
2. Кемени, Дж. Г.; Моргенштерн, О.; Томпсон, Г. Л. (1956). «Обобщение модели фон Неймана для расширяющейся экономики». Эконометрика . 24 : 115–135.
3. Ли, У (2019). Общее равновесие и структурная динамика: перспективы новой структурной экономики (на китайском языке). Пекин: Economic Science Press. С. 122–125. ISBN 978-7-5218-0422-5.
4. Джерард Сиерксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика (3-е изд.). ЦРК Пресс. п. 1. ISBN 978-1498710169.
5. "Линейное программирование | Определение и факты | Britannica". www.britannica.com . Получено 20.11.2023 .
6. Джордж Б. Данциг (апрель 1982 г.). «Воспоминания об истоках линейного программирования» (PDF) . Operations Research Letters . 1 (2): 43–48. doi :10.1016/0167-6377(82)90043-8. Архивировано из оригинала 20 мая 2015 г.
7. Александр Шрийвер (1998). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. стр. 221–222. ISBN 978-0-471-98232-6.
8. Данциг, Джордж Б.; Тапа, Мукунд Нараин (1997). Линейное программирование . Нью-Йорк: Springer. стр. xxvii. ISBN 0387948333. OCLC  35318475.
9. Леонид Хачиян (1979). «Полиномиальный алгоритм линейного программирования». Доклады Академии наук СССР . 224 (5): 1093–1096.
10. Narendra Karmarkar (1984). «Новый алгоритм полиномиального времени для линейного программирования». Combinatorica . 4 (4): 373–395. doi :10.1007/BF02579150. S2CID  7257867.
11. M. Grundmann; V. Kwatra; I. Essa (2011). «Автоматически направленная стабилизация видео с надежными оптимальными путями камеры L1». CVPR 2011 (PDF) . стр. 225–232. doi :10.1109/CVPR.2011.5995525. ISBN 978-1-4577-0394-2. S2CID  17707171.
12. Вазирани (2001, стр. 112)
13. Данциг и Тапа (2003)
14. Padberg (1999)
15. Fukuda, Komei ; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия B . 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181. 
16. Боргвардт (1987)
17. Тодд (2002)
18. Мёрти (1983)
19. Пападимитриу и Стейглиц
20. Roos, C. (1990). "Экспоненциальный пример правила поворота Терлаки для метода симплекса крест-накрест". Математическое программирование . Серия A. 46 (1): 79–84. doi :10.1007/BF01585729. MR  1045573. S2CID  33463483.
21. Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». The Mathematical Intelligencer . 9 (2): 4–10. doi :10.1007/BF03025891. ISSN  0343-6993. MR  0883185. S2CID  123541868.
22. Вайдья, Правин М. (1987). Алгоритм линейного программирования, требующий арифметических операций . 28-й ежегодный симпозиум IEEE по основам компьютерной науки. FOCS. ${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$
23. Вайдья, Правин М. (1989). «Ускорение линейного программирования с помощью быстрого умножения матриц». 30-й ежегодный симпозиум по основам компьютерной науки . 30-й ежегодный симпозиум по основам компьютерной науки. FOCS. стр. 332–337. doi :10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.
24. Ли, Инь-Тат; Сидфорд, Аарон (2015). Эффективное обратное обслуживание и более быстрые алгоритмы для линейного программирования . FOCS '15 Основы компьютерной науки. arXiv : 1503.01752 .
25. Коэн, Майкл Б.; Ли, Инь-Тат; Сонг, Чжао (2018). Решение линейных программ за текущее время умножения матриц . 51-й ежегодный симпозиум ACM по теории вычислений. STOC'19. arXiv : 1810.07896 .
26. Ли, Инь-Тат; Сун, Чжао; Чжан, Цюи (2019). Решение задачи минимизации эмпирического риска в текущем времени умножения матриц . Конференция по теории обучения. COLT'19. arXiv : 1905.04447 .
27. Цзян, Шуньхуа; Сун, Чжао; Вайнштейн, Омри; Чжан, Хэнцзе (2020). Более быстрая обратная динамическая матрица для более быстрых LP . arXiv : 2004.07470 .
28. Иллес, Тибор; Терлаки, Тамаш (2002). «Методы поворота и внутренней точки: плюсы и минусы». Европейский журнал операционных исследований . 140 (2): 170. CiteSeerX 10.1.1.646.3539 . дои : 10.1016/S0377-2217(02)00061-9. 
29. Анстрейхер, Курт М.; Терлаки, Тамаш (1994). «Алгоритм монотонного наращивания симплекса для линейного программирования». Исследование операций . 42 (3): 556–561. doi : 10.1287/opre.42.3.556 . ISSN  0030-364X. JSTOR  171894.
30. "Справочное руководство lp_solve (5.5.2.5)". mit.edu . Получено 2023-08-10 .
31. "Внешние языковые интерфейсы" . Получено 3 декабря 2021 г.
32. "lp_solve command" . Получено 3 декабря 2021 г. .
33. "COR@L – Исследования по вычислительной оптимизации в Лихай". lehigh.edu .
34. http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ используется в модели оптимизации для сборочных линий смешанной модели, Университет Мюнстера
35. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 Архивировано 29 июня 2011 г. на Wayback Machine OptimJ используется в методе вычисления приблизительного идеального равновесия для повторяющихся игр

Ссылки

• Канторович, Л. В. (1940). «Об одном эффективном методе решения некоторых классов экстремальных задач». Доклады АН СССР . 28 : 211–214.
• Ф. Л. Хичкок: Распространение продукта из нескольких источников в многочисленные местности , Журнал математики и физики, 20, 1941, 224–230.
• GB Dantzig: Максимизация линейной функции переменных, подчиненных линейным неравенствам , 1947. Опубликовано на стр. 339–347 в TC Koopmans (ред.): Activity Analysis of Production and Allocation , Нью-Йорк-Лондон, 1951 (Wiley & Chapman-Hall)
• JE Beasley, редактор. Advances in Linear and Integer Programming . Oxford Science, 1996. (Сборник обзоров)
• Бланд, Роберт Г. (1977). «Новые правила конечного поворота для симплекс-метода». Математика исследования операций . 2 (2): 103–107. doi :10.1287/moor.2.2.103. JSTOR  3689647.
• Боргвардт, Карл-Хайнц (1987). Симплексный алгоритм: вероятностный анализ . Алгоритмы и комбинаторика. Т. 1. Springer-Verlag.(Среднее поведение при решении случайных задач)
• Ричард В. Коттл, ред. The Basic Джордж Б. Данциг . Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния, 2003. (Избранные статьи Джорджа Б. Данцига )
• Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Springer-Verlag.
• Данциг, Джордж Б.; Тапа, Мукунд Н. (2003). Линейное программирование 2: Теория и расширения . Springer-Verlag.(Всеобъемлющий, охватывающий, например, алгоритмы поворота и внутренней точки, крупномасштабные задачи, декомпозицию по Данцигу–Вульфу и Бендерсу , а также введение в стохастическое программирование .)
• Эдмондс, Джек; Джайлс, Рик (1977). "Отношение минимума-максимума для субмодулярных функций на графах". Исследования по целочисленному программированию . Анналы дискретной математики. Том 1. С. 185–204. doi :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 . doi :10.1007/BF02614325. MR  1464775. S2CID  2794181.
• Gondzio, Jacek; Terlaky, Tamás (1996). "3 Вычислительный взгляд на методы внутренней точки". В JE Beasley (ред.). Достижения в линейном и целочисленном программировании . Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. MR  1438311. Файл Postscript на веб-сайте Gondzio и на веб-сайте McMaster University Terlaky.
• Murty, Katta G. (1983). Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc. стр. xix+482. ISBN 978-0-471-09725-9. MR  0720547. (полный справочник по классическим подходам).
• Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и смежные проблемы , Academic Press. (элементарный)
• Падберг, М. (1999). Линейная оптимизация и расширения, второе издание . Springer-Verlag.(тщательно написанный отчет о простых и двойственных симплексных алгоритмах и проективных алгоритмах с введением в целочисленное линейное программирование — с участием задачи коммивояжера для Одиссея .)
• Пападимитриу, Христос Х .; Стейглиц, Кеннет. Комбинаторная оптимизация: алгоритмы и сложность (исправленное переиздание с новым предисловием). Дувр.(Информатика)
• Тодд, Майкл Дж. (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование . 91 (3): 417–436. doi :10.1007/s101070100261. S2CID  6464735.(Приглашенный опрос с Международного симпозиума по математическому программированию.)
• Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Springer Verlag.
• Вазирани, Виджай В. (2001). Алгоритмы аппроксимации . Спрингер-Верлаг. ISBN 978-3-540-65367-7.(Информатика)

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

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

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

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