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

Ретроним, относящийся к телевизионному вещанию, см.

Графическое представление простой линейной программы с двумя переменными и шестью неравенствами. Множество допустимых решений изображено желтым цветом и образует многоугольник, 2-мерный многогранник. Линейная функция затрат представлена красной линией и стрелкой: Красная линия представляет собой набор уровней функции затрат. А стрелка указывает направление. В котором мы оптимизируем.

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

плоскостями (не показаны). Задача линейного программирования состоит в том. Чтобы найти точку на многограннике. Которая находится на плоскости с максимально возможным значением.

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

Более формально линейное программирование-это метод

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

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

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

Здесь компоненты x-определяемые переменные, c и b-заданные векторы

cT{\displaystyle \mathbf {c} ^{T}}

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

A-заданная матрица. Функция, значение которой должно быть максимизировано или минимизировано (

xcTx{\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }

в этом случае). Называется целевой функцией. Неравенства Axb и x0 являются ограничениями. Определяющими выпуклый многогранник, над которым должна быть оптимизирована целевая функция. В этом контексте два вектора сопоставимы когда они имеют одинаковые размеры. Если каждая запись в первой меньше или равна соответствующей записи во второй. То можно сказать. Что первый вектор меньше или равен второму вектору.

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

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

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

исключения Фурье–Моцкина.

В 1939 году советский математик и экономист Леонид Канторович сформулировал задачу линейного программирования . Эквивалентную общей задаче линейного программирования . И предложил метод ее решения[2]. Это разработанный им во время Второй мировой войныспособ планирования расходов и доходов с целью сокращения расходов армии и увеличения потерь противника. Работа Канторовича первоначально была проигнорирована в СССР. [3 ] Примерно в то же время. Что и Канторович. Голландско-американский экономист Т. К. Купманс сформулированы классические экономические задачи в виде линейных программ. Канторович и Купманс позже разделили

Нобелевскую премию по экономике 1975года .[1] В 1941 году Фрэнк Лорен Хичкок также сформулировал транспортные проблемы как линейные программы и дал решение. Очень похожее на более поздний симплексный метод.[2] Хичкок умер в 1957 году. И Нобелевская премия не присуждается посмертно.

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

Когда Данциг договорился о встрече с Джоном фон Нейманом, чтобы обсудить его симплексный метод. Нейман сразу же предположил теорию двойственности, поняв. Что проблема. Над которой он работал в теории игр, была эквивалентна.] Данциг представил формальное доказательство в неопубликованном докладе [3]. Работа Данцига была опубликована в 1951 году. В послевоенные годы многие отрасли промышленности применяли его в своем повседневном планировании.

Первоначальный пример Данцига состоял в том. Чтобы найти лучшее назначение из 70 человек на 70 рабочих мест.

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

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

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

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

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

  • Линейная функция. Которая должна быть максимизирована
напр.

f(x1,x2)=c1x1+c2x2{\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}

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

a11x1+a12x2b1a21x1+a22x2b2a31x1+a32x2b3{\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}}}

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

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

Задача обычно выражается в матричном виде, а затем становится:

max{cTxxRnAxbx0}{\displaystyle \max\{\,\mathbf {c} ^{\mathrm {T} }\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}

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

Пример

Предположим, что у фермера есть участок земли , скажем, L км2, который нужно засеять пшеницей или ячменем или какой-то их комбинацией. Фермер имеет ограниченное количество удобрений-F килограммов и пестицидов-P килограммов. Каждый квадратный километр пшеницы требует F1 килограмм удобрений и P1 килограмм пестицидов. В то время как каждый квадратный километр ячменя требует F2 килограмма удобрений и P2 килограмма пестицидов. ПустьS1 — цена продажи пшеницы за квадратный километр, аS2-цена продажи ячменя. Если мы обозначим площадь земли засеянной пшеницей и ячменем через х1 и х2 соответственно. Тогда прибыль можно максимизировать. Выбрав оптимальные значения для x1 и x2. Эта задача может быть выражена следующей задачей линейного программирования в стандартной форме:

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

максимизировать

[S1S2][x1x2]{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}

подлежит

[11F1F2P1P2][x1x2][LFP],[x1x2][00].{\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}}.}

Дополненная форма (slack form)

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

Максимизировать

z{\displaystyle z}

:

[1cT00AI][zxs]=[0b]{\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}}}

x0,s0{\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0}

где

s{\displaystyle \mathbf {s} }

вновь введенные переменные слабины. Переменные

x{\displaystyle \mathbf {x} }

решения и переменная,

z{\displaystyle z}

которая должна быть максимизирована.

Пример

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

где

x3,x4,x5{\displaystyle x_{3},x_{4},x_{5}}

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

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

Максимизировать

z{\displaystyle z}

:

[1S1S20000111000F1F20100P1P2001][zx1x2x3x4x5]=[0LFP],[x1x2x3x4x5]0.{\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.}

Двойственность

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

Максимизировать cTx при условии Axb, x ≥ 0;

с соответствующей симметричной двойной задачей,
Минимизировать bTy при условии ATyc, y ≥ 0.

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

Максимизация cTx при условии Axb;

с соответствующей асимметричной двойной задачей,
Минимизировать bTy при условии ATy = c, y ≥ 0.

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

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

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

Покрывающая LP-это линейная программа вида:

Минимизировать: bTy,
при условии: ATyc, y ≥ 0,

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

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

Максимизировать: cTx,
при условии: Axb, x ≥ 0,

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

Примеры

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

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

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

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

Предположим, что x = (x1, x2, … , xn) первично выполнимо и что y = (y1, y2, … , ym) двойственно выполнимо. Пусть (w1, w2, …, wm) обозначают соответствующие первичные переменные слабины, а (z1, z2, … , zn) — соответствующие двойные переменные слабины. Тогда x и y являются оптимальными для их соответствующих задач тогда и только тогда, когда

  • xjzj = 0, для j = 1, 2, … , nи
  • wiyi = 0, ибо i = 1, 2, … , m.

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

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

Существование оптимальных решений

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

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

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

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

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

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

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

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

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

Однако симплексный алгоритм имеет плохое наихудшее поведение: Клее и Минти построили семейство задач линейного программирования. Для которых симплексный метод принимает ряд шагов. Экспоненциальных по размеру задачи.[8][11][12] На самом деле в течение некоторого времени не было известно. Разрешима ли задача линейного программирования за полиномиальное время, т. е.

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

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

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

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

Эллипсоидный алгоритм. Следующий

Это первый наихудший алгоритм полиномиального времени. Когда-либо найденный для линейного программирования. Для решения задачи. Которая имеет n переменных и может быть закодирована в L входных битах. Этот алгоритм выполняется во

O(n6L){\displaystyle O(n^{6}L)}

времени.[5]Леонид Хачиян решил эту давнюю проблему сложности в 1979 году с помощью метода эллипсоидов. Анализ сходимости имеет предшественников (вещественных чисел). В частности итерационные методы, разработанные Наумом З. Шор и аппроксимационные алгоритмы Аркадия Немировского и Д. Юдина.

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

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

Однако алгоритм Хачияна вдохновил новые направления исследований в области линейного программирования. В 1984 году Н. Кармаркар предложил проективный метод линейного программирования. АлгоритмКармаркара [6] улучшен на основе наихудшей полиномиальной оценки Хачияна [5

O(n3.5L){\displaystyle O(n^{3.5}L)}

]. Кармаркар утверждал. Что его алгоритм был намного быстрее на практике. Чем симплексный метод. Что вызвало большой интерес к методам внутренних точек.Со времени открытия Кармаркара было предложено и проанализировано множество методов внутренней точки.

87

В 1987 году Вайдья предложил алгоритм. Который работает во

O(n3){\displaystyle O(n^{3})}

времени.[18]

89

В 1989 году Вайдья разработал алгоритм. Работающий во

O(n2.5){\displaystyle O(n^{2.5})}

времени.Формально говоря. Алгоритм принимает

O((n+d)1.5nL){\displaystyle O((n+d)^{1.5}nL)}

арифметические операции в наихудшем случае. Где

d{\displaystyle d}

— число ограничений,

n{\displaystyle n}

— число переменных и

L{\displaystyle L}

-число битов.

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

В 2015 году Ли и Сидфорд показали. Что она может быть решена во

O~((nnz(A)+d2)dL){\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}

времени[20], где

nnz(A){\displaystyle nnz(A)}

представляет собой число ненулевых элементов. И она остается взятой

O(n2.5L){\displaystyle O(n^{2.5}L)}

в худшем случае.

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

В 2019 году Коэн. Ли и Сонг улучшили время выполнения

O~((nω+n2.5α/2+n2+1/6)L){\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}

,

ω{\displaystyle \omega }

это показатель умножения матриц и

α{\displaystyle \alpha }

двойной показатель умножения матриц.[21]

α{\displaystyle \alpha }

(грубо) определяется как наибольшее число, такое. Что можно умножить

n×n{\displaystyle n\times n}

матрицу на

n×nα{\displaystyle n\times n^{\alpha }}

матрицу во

O(n2){\displaystyle O(n^{2})}

времени. В последующей работе Ли. Сун и Чжан они воспроизводят тот же результат с помощью другого метода.[22] Эти два алгоритма остаются

O~(n2+1/6L){\displaystyle {\tilde {O}}(n^{2+1/6}L)}

, когда

ω=2{\displaystyle \omega =2}

и

α=1{\displaystyle \alpha =1}

. Результат благодаря Цзяну, Сун. Вайнштейну и Чжану улучшился

O~(n2+1/6L){\displaystyle {\tilde {O}}(n^{2+1/6}L)}

до

O~(n2+1/18L){\displaystyle {\tilde {O}}(n^{2+1/18}L)}

[23]

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

В настоящее время существует мнение. Что эффективность хороших реализаций симплексных методов и методов внутренних точек аналогична для рутинных приложений линейного программирования. Однако для конкретных типов задач LP может быть так. Что один тип решателя лучше другого (иногда намного лучше). И что структура решений. Генерируемых внутренними точечными методами. По сравнению с симплексными методами. Значительно отличается. Причем набор активных переменных поддержки обычно меньше для последнего.]

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

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

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

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

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

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

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

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

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

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

Симплексные методы разворота сохраняют первичную (или двойственную) осуществимость. С другой стороны. Методы перекрестного поворота не сохраняют (первичную или двойственную) осуществимость – они могут посещать первичные выполнимые. Двойные выполнимые или первичные и двойные неосуществимые базы в любом порядке. Методы разворота этого типа изучались с 1970-х годов. По существу. Эти методы пытаются найти кратчайший путь разворота на многограннике расположения под задачей линейного программирования. В отличие от многогранных графов. Графы многогранников расположения. Как известно. Имеют малый диаметр. Что позволяет использовать сильно полиномиальный алгоритм перекрестного поворота без решения вопросов о диаметре общих многогранников.]

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

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

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

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

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

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

Интеграл линейного программирования

Линейная программа в вещественных переменных называется интегральной, если она имеет хотя бы одно оптимальное решение. Которое является интегральным. Аналогично, многогранник

P={xAx0}{\displaystyle P=\{x\mid Ax\geq 0\}}

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

{maxcxxP}{\displaystyle \{\max cx\mid x\in P\}}

имеет оптимум

x{\displaystyle x^{*}}

с целочисленными координатами. Как наблюдали Эдмондс и Джайлс в 1977 году. Можно эквивалентно сказать . Что многогранник

P{\displaystyle P}

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

{maxcxxP}{\displaystyle \{\max cx\mid x\in P\}}

является целым числом.

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

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

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

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

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

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

Имя Лицензия Краткая информация
Пемо BSD Язык моделирования с открытым исходным кодом для крупномасштабной линейной. Смешанной целочисленной и нелинейной оптимизации

Лицензии авторского лева (взаимные) :

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

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

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

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

Примечания

  1. ^ b
  2. ^ b Alexander Schrijver (1998). Теория линейного и целочисленного программирования. John Wiley & Sons. pp. 221-222. ISBN 978-0-471-98232-6.
  3. ^ Перейти вверх к: a b c Джордж Б. Данциг (апрель 1982). . Письма об исследованиях операций. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8.
  4. ^ b c Dantzig, George B.; Thapa, Mukund Narain (1997). Линейное программирование. Нью-Йорк: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475.
  5. ^ Перейти вверх к: a b c Леонид Хачиян (1979). Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.
  6. ^ b Нарендра Кармаркар (1984). Комбинаторика. 4 (4): 373–395. doi:10.1007/BF02579150. S2CID 7257867.
  7. ^ Вазирани (2001, с. 112)
  8. ^ Jump up to: a b c d Dantzig & Thapa (2003) harvtxt error: no target: CITEREFDantzigThapa2003 (help)
  9. ^ Jump up to: a b c Padberg (1999) harvtxt error: no target: CITEREFPadberg1999 (help)
  10. ^ Блэнд (1977)
  11. ^ Jump up to: a b Murty (1983)
  12. ^ Jump up to: a b Papadimitriou & Steiglitz harvtxt error: no target: CITEREFPapadimitriouSteiglitz (help)
  13. ^ Перейти вверх к: a b c Fukuda, Komei; Terlaky, Tamás (1997). Томас М. Либлинг; Доминик де Верра (ред.). Математическое программирование. Серия Б. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. МИСТЕР 1464775. S2CID 2794181.
  14. ^ Borgwardt (1987) harvtxt ошибка: нет цели: CITEREFBorgwardt1987 (справка)
  15. ^ Todd (2002) harvtxt error: no target: CITEREFTodd2002 (help)
  16. ^ Roos, C. (1990). Математическое программирование. Серия A. 46 (1): 79-84. doi:10.1007/BF01585729. МИСТЕР 1045573. S2CID 33463483.
  17. ^ Странг, Гилберт (1 июня 1987). Математический интеллект. 9 (2): 4-10. doi:10.1007/BF03025891. ISSN 0343-6993. МИСТЕР 0883185. S2CID 123541868.
  18. ^ Вайдья, Правин М. (1987). Алгоритм линейного программирования. Требующий

    O(((m+n)n2+(m+n)1.5n)L){\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}

    арифметических операций. 28-й ежегодный симпозиум IEEE по основам информатики. ФОКС.

  19. ^ Вайдья, Правин М. (1989). Ускорение линейного программирования с использованием быстрого умножения матриц. 30-й ежегодный симпозиум по основам информатики. ФОКС. doi:10.1109/SFC.1989.63499.
  20. ^ Ли, Инь-Тат; Сидфорд, Аарон (2015). Эффективное обратное обслуживание и более быстрые алгоритмы линейного программирования. FOCS ’15 Основы информатики. arXiv:1503.01752.
  21. ^ Коэн, Майкл Б.; Ли, Инь-Тат; Сон, Чжао (2018). Решение линейных программ в текущем времени умножения матрицы. 51-й ежегодный симпозиум ACM по теории вычислений. СТОК’19. arXiv:1810.07896.
  22. ^ Ли, Инь-Тат; Сун, Чжао; Чжан, Цюйи (2019). Решение задачи эмпирической минимизации риска в текущем времени умножения матрицы. Конференция по теории обучения. КОЛЬТ 19-го года. arXiv:1905.04447.
  23. ^ Цзян, Шуньхуа; Сун, Чжао; Вайнштейн, Омри; Чжан, Хэнцзе (2020). Более быстрая динамическая матрица Обратная для более быстрых LPs. arXiv:2004.07470.
  24. ^ Illés, Tibor; Terlaky, Tamás (2002). . Европейский журнал оперативных исследований. 140 (2): 170. CiteSeerX 10.1.1.646.3539. doi:10.1016/S0377-2217(02)00061-9.
  25. ^ . lehigh.edu.
  26. ^ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ используется в оптимизационной модели для сборочных линий смешанной модели Мюнстерского университета
  27. ^ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ используется в приближенной методике вычисления идеального равновесия подигры для повторяющихся игр

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

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