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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

например ${\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 и 2 килограмма пестицидов. Пусть 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 при условии AT 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 ^* .

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

Вариации

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

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

Минимизировать: 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 неотрицательны.

Примеры

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

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

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

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

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

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

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

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

Теория

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Джерард Сиерксма; Йори Зволс (2015). Линейная и целочисленная оптимизация: теория и практика (3-е изд.). ЦРК Пресс. п. 1. ISBN 978-1498710169.
2. «Линейное программирование | Определение и факты | Британника» . www.britanica.com . Проверено 20 ноября 2023 г.
3. Джордж Б. Данциг (апрель 1982 г.). «Воспоминания об истоках линейного программирования» (PDF) . Письма об исследованиях операций . 1 (2): 43–48. дои : 10.1016/0167-6377(82)90043-8. Архивировано из оригинала 20 мая 2015 года.
4. Александр Шрийвер (1998). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. стр. 221–222. ISBN 978-0-471-98232-6.
5. Данциг, Джордж Б.; Тапа, Мукунд Нараин (1997). Линейное программирование . Нью-Йорк: Спрингер. п. xxvii. ISBN 0387948333. ОСЛК  35318475.
6. Леонид Хачиян (1979). «Полиномиальный алгоритм линейного программирования». Доклады Академии наук СССР . 224 (5): 1093–1096.
7. Нарендра Кармаркар (1984). «Новый алгоритм полиномиального времени для линейного программирования». Комбинаторика . 4 (4): 373–395. дои : 10.1007/BF02579150. S2CID  7257867.
8. М. Грундманн; В. Кватра; И. Эсса (2011). «Автоматическая стабилизация видео с надежным оптимальным траекторией камеры L1». ЦВПР 2011 (PDF) . стр. 225–232. дои : 10.1109/CVPR.2011.5995525. ISBN 978-1-4577-0394-2. S2CID  17707171.
9. Вазирани (2001, стр. 112)
10. Данциг и Тапа (2003)
11. Падберг (1999)
12. Фукуда, Комей ; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373 . дои : 10.1007/BF02614325. MR  1464775. S2CID  2794181. 
13. Боргвардт (1987)
14. Тодд (2002)
15. Мурти (1983)
16. Пападимитриу и Стейглиц
17. Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование . Серия А. 46 (1): 79–84. дои : 10.1007/BF01585729. MR  1045573. S2CID  33463483.
18. Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». Математический интеллект . 9 (2): 4–10. дои : 10.1007/BF03025891. ISSN  0343-6993. MR  0883185. S2CID  123541868.
19. Вайдья, Правин М. (1987). Алгоритм линейного программирования, требующий арифметических операций . 28-й ежегодный симпозиум IEEE по основам информатики. ФОКС. ${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$
20. Вайдья, Правин М. (1989). «Ускорение линейного программирования с помощью быстрого умножения матриц». 30-й ежегодный симпозиум по основам информатики . 30-й ежегодный симпозиум по основам информатики. ФОКС. стр. 332–337. дои : 10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.
21. Ли, Инь-Тат; Сидфорд, Аарон (2015). Эффективное обратное обслуживание и более быстрые алгоритмы линейного программирования . FOCS '15 Основы информатики. arXiv : 1503.01752 .
22. Коэн, Майкл Б.; Ли, Инь-Тат; Сун, Чжао (2018). Решение линейных программ за время умножения текущей матрицы . 51-й ежегодный симпозиум ACM по теории вычислений. СТОК'19. arXiv : 1810.07896 .
23. Ли, Инь-Тат; Сун, Чжао; Чжан, Цюи (2019). Решение задачи минимизации эмпирического риска за время умножения текущей матрицы . Конференция по теории обучения. КОЛЬТ'19. arXiv : 1905.04447 .
24. Цзян, Шуньхуа; Сун, Чжао; Вайнштейн, Омри; Чжан, Хэнцзе (2020). Более быстрая обратная динамическая матрица для более быстрых LP . arXiv : 2004.07470 .
25. Иллес, Тибор; Терлаки, Тамаш (2002). «Методы поворота и внутренней точки: плюсы и минусы». Европейский журнал операционных исследований . 140 (2): 170. CiteSeerX 10.1.1.646.3539 . дои : 10.1016/S0377-2217(02)00061-9. 
26. Анстрайхер, Курт М.; Терлаки, Тамаш (1994). «Монотонный симплексный алгоритм построения для линейного программирования». Исследование операций . 42 (3): 556–561. дои : 10.1287/opre.42.3.556 . ISSN  0030-364X. JSTOR  171894.
27. «Справочное руководство lp_solve (5.5.2.5)» . mit.edu . Проверено 10 августа 2023 г.
28. «Внешние языковые интерфейсы» . Проверено 3 декабря 2021 г.
29. "Команда lp_solve" . Проверено 3 декабря 2021 г.
30. «COR@L - Исследования по оптимизации вычислений в Лихае» . lehigh.edu .
31. http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ используется в модели оптимизации для сборочных линий смешанной модели, Мюнстерский университет
32. 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.
• ГБ Данциг: Максимизация линейной функции переменных с учетом линейных неравенств , 1947. Опубликовано стр. 339–347 в TC Koopmans (ред.): Анализ деятельности производства и распределения , Нью-Йорк-Лондон, 1951 (Wiley & Chapman-Hall).
• Дж. Э. Бисли, редактор. Достижения в области линейного и целочисленного программирования . Oxford Science, 1996. (Сборник опросов).
• Бланд, Роберт Г. (1977). «Новые правила конечного поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. дои : 10.1287/moor.2.2.103. JSTOR  3689647.
• Боргвардт, Карл-Хайнц (1987). Симплексный алгоритм: вероятностный анализ . Алгоритмы и комбинаторика. Том. 1. Шпрингер-Верлаг.(Среднее поведение при решении случайных задач)
• Ричард В. Коттл, изд. Базовый Джордж Б. Данциг . Stanford Business Books, Stanford University Press, Стэнфорд, Калифорния, 2003 г. (Избранные статьи Джорджа Б. Данцига )
• Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Спрингер-Верлаг.
• Данциг, Джордж Б.; Тапа, Мукунд Н. (2003). Линейное программирование 2: Теория и расширения . Спрингер-Верлаг.(Всеобъемлющий, охватывающий, например, алгоритмы поворота и внутренней точки, крупномасштабные проблемы, декомпозицию по Данцигу – Вольфу и Бендерсу , а также введение в стохастическое программирование .)
• Эдмондс, Джек; Джайлз, Рик (1977). «Соотношение Мин-Макс для субмодулярных функций на графах». Исследования по целочисленному программированию . Анналы дискретной математики. Том. 1. С. 185–204. дои : 10.1016/S0167-5060(08)70734-9. ISBN 978-0-7204-0765-5.
• Фукуда, Комей; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. 79 (1–3): 369–395. CiteSeerX  10.1.1.36.9373 . дои : 10.1007/BF02614325. MR  1464775. S2CID  2794181.
• Гондзио, Яцек; Терлаки, Тамаш (1996). «3 Вычислительный взгляд на методы внутренней точки». В Дж. Э. Бизли (ред.). Достижения в области линейного и целочисленного программирования . Оксфордская серия лекций по математике и ее приложениям. Том. 4. Нью-Йорк: Издательство Оксфордского университета. стр. 103–144. MR  1438311. Постскриптум-файл на веб-сайте Гондзио и на веб-сайте Университета Макмастера в Терлаки.
• Мурти, Катта Г. (1983). Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc., стр. xix+482. ISBN 978-0-471-09725-9. МР  0720547. (комплексная ссылка на классические подходы).
• Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и связанные с ними проблемы , Academic Press. (элементарный)
• Падберг, М. (1999). Линейная оптимизация и расширения, второе издание . Спрингер-Верлаг.(тщательно написанный отчет о простых и двойственных симплексных алгоритмах и проективных алгоритмах с введением в целочисленное линейное программирование, включающим задачу коммивояжера для Одиссея .)
• Пападимитриу, Христос Х .; Стейглиц, Кеннет. Комбинаторная оптимизация: алгоритмы и сложность (исправленная перепубликация с новым предисловием). Дувр.(Информатика)
• Тодд, Майкл Дж. (февраль 2002 г.). «Многогранность линейного программирования». Математическое программирование . 91 (3): 417–436. дои : 10.1007/s101070100261. S2CID  6464735.(Приглашенный опрос с Международного симпозиума по математическому программированию.)
• Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения . Спрингер Верлаг.
• Вазирани, Виджай В. (2001). Алгоритмы аппроксимации . Спрингер-Верлаг. ISBN 978-3-540-65367-7.(Информатика)

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

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

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

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