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

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

В математической оптимизации симплексный алгоритм Данцига ( или симплексный метод ) является популярным алгоритмом линейного программирования . [ ^1]

Название алгоритма происходит от концепции симплекса и было предложено Т. С. Моцкиным . ^[2] Симплексы фактически не используются в этом методе, но одна из его интерпретаций заключается в том, что он работает с симплициальными конусами , и они становятся собственными симплексами с дополнительным ограничением. ^{[3] [4] [5] [6]} Рассматриваемые симплициальные конусы являются углами (т. е. окрестностями вершин) геометрического объекта, называемого многогранником . Форма этого многогранника определяется ограничениями , применяемыми к целевой функции.

История

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

После того, как Данциг включил целевую функцию как часть своей формулировки в середине 1947 года, задача стала математически более податливой. Данциг понял, что одна из нерешенных задач, которую он ошибочно принял за домашнее задание на занятиях своего профессора Ежи Неймана (и которая впоследствии была фактически решена), была применима к поиску алгоритма для линейных программ. Эта задача включала в себя поиск существования множителей Лагранжа для общих линейных программ над континуумом переменных, каждая из которых ограничена между нулем и единицей, и удовлетворяющих линейным ограничениям, выраженным в форме интегралов Лебега . Позже Данциг опубликовал свое «домашнее задание» в качестве диссертации, чтобы получить докторскую степень. Геометрия столбцов, использованная в этой диссертации, дала Данцигу понимание, которое заставило его поверить, что метод симплекса будет очень эффективным. ^[9]

Обзор

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

Многогранник симплексного алгоритма в 3D

Симплексный алгоритм работает с линейными программами в канонической форме

максимизировать ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

при условии и ${\displaystyle A\mathbf {x} \leq \mathbf {b} }$ ${\displaystyle \mathbf {x} \geq 0}$

с коэффициентами целевой функции, — транспонированная матрица , — переменные задачи, — матрица p × n , и . Существует простой процесс преобразования любой линейной программы в стандартную форму, поэтому использование этой формы линейных программ не приводит к потере общности. ${\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}$ ${\displaystyle (\cdot )^{\mathrm {T} }}$ ${\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}$ ${\displaystyle A}$ ${\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}$

В геометрических терминах допустимая область , определяемая всеми значениями такими, что и является (возможно, неограниченным) выпуклым многогранником . Крайняя точка или вершина этого многогранника известна как базисное допустимое решение (BFS). ${\displaystyle \mathbf {x} }$ ${\textstyle A\mathbf {x} \leq \mathbf {b} }$ ${\displaystyle \forall i,x_{i}\geq 0}$

Можно показать, что для линейной программы в стандартной форме, если целевая функция имеет максимальное значение в допустимой области, то она имеет это значение в (по крайней мере) одной из крайних точек. ^[10] Это само по себе сводит задачу к конечному вычислению, поскольку существует конечное число крайних точек, но число крайних точек неуправляемо велико для всех, кроме самых маленьких линейных программ. ^[11]

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

Решение линейной программы выполняется в два этапа. На первом этапе, известном как Фаза I, находится начальная экстремальная точка. В зависимости от характера программы это может быть тривиально, но в общем случае это может быть решено путем применения симплекс-алгоритма к измененной версии исходной программы. Возможные результаты Фазы I заключаются либо в том, что найдено базовое допустимое решение, либо в том, что допустимая область пуста. В последнем случае линейная программа называется недопустимой . На втором этапе, Фазе II, симплекс-алгоритм применяется с использованием базового допустимого решения, найденного на Фазе I, в качестве отправной точки. Возможные результаты Фазы II — либо оптимальное базовое допустимое решение, либо бесконечное ребро, на котором целевая функция неограничена сверху. ^{[13] [14] [15]}

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

Преобразование линейной программы в программу стандартной формы может быть выполнено следующим образом. ^[16] Во-первых, для каждой переменной с нижней границей, отличной от 0, вводится новая переменная, представляющая разницу между переменной и границей. Затем исходная переменная может быть исключена путем подстановки. Например, учитывая ограничение

${\displaystyle x_{1}\geq 5}$

новая переменная, , вводится с ${\displaystyle y_{1}}$

${\displaystyle {\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}}$

Второе уравнение может быть использовано для исключения из линейной программы. Таким образом, все ограничения нижней границы могут быть изменены на ограничения неотрицательности. ${\displaystyle x_{1}}$

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

${\displaystyle {\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}}$

заменяются на

${\displaystyle {\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}}$

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

В-третьих, каждая неограниченная переменная исключается из линейной программы. Это можно сделать двумя способами: один — решить для переменной одно из уравнений, в котором она появляется, а затем исключить переменную путем подстановки. Другой — заменить переменную разностью двух ограниченных переменных. Например, если неограниченно, то запишите ${\displaystyle z_{1}}$

${\displaystyle {\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}}$

Уравнение можно использовать для исключения из линейной программы. ${\displaystyle z_{1}}$

Когда этот процесс будет завершен, допустимая область будет иметь вид

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall \ x_{i}\geq 0}$

Также полезно предположить, что ранг равен числу строк. Это не приводит к потере общности, поскольку в противном случае либо система имеет избыточные уравнения, которые можно отбросить, либо система несогласованна и линейное программирование не имеет решения. ^[17] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$

Симплексная таблица

Линейную программу в стандартной форме можно представить в виде таблицы вида

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {A} &\mathbf {b} \end{bmatrix}}}$

Первая строка определяет целевую функцию, а остальные строки указывают ограничения. Ноль в первом столбце представляет собой нулевой вектор той же размерности, что и вектор (разные авторы используют разные соглашения относительно точной компоновки). Если столбцы из можно переставить так, чтобы они содержали единичную матрицу порядка (количество строк в ), то говорят, что таблица находится в канонической форме . ^[18] Переменные, соответствующие столбцам единичной матрицы, называются базовыми переменными, а остальные переменные называются небазовыми или свободными переменными . Если значения небазовых переменных установлены в 0, то значения базовых переменных легко получить как записи в , и это решение является базовым допустимым решением. Алгебраическая интерпретация здесь заключается в том, что коэффициенты линейного уравнения, представленного каждой строкой, являются либо , , либо некоторым другим числом. Каждая строка будет иметь столбец со значением , столбцы с коэффициентами , а оставшиеся столбцы с некоторыми другими коэффициентами (эти другие переменные представляют наши небазовые переменные). Устанавливая значения небазовых переменных равными нулю, мы гарантируем, что в каждой строке значение переменной, представленной a в ее столбце, равно значению в этой строке. ${\displaystyle \mathbf {b} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle p}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {b} }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle b}$

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

Позволять

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}}$

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

${\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}}$

где z _B — значение целевой функции при соответствующем базовом допустимом решении. Обновленные коэффициенты, также известные как коэффициенты относительной стоимости , представляют собой скорости изменения целевой функции по отношению к небазисным переменным. ^[14]

Операции по развороту

Геометрическая операция перехода от базового допустимого решения к смежному базовому допустимому решению реализуется как операция поворота . Сначала в небазовом столбце выбирается ненулевой опорный элемент . Строка, содержащая этот элемент, умножается на его обратную величину, чтобы изменить этот элемент на 1, а затем кратные этой строки добавляются к другим строкам, чтобы изменить другие записи в столбце на 0. Результатом является то, что если опорный элемент находится в строке r , то столбец становится r -ым столбцом матрицы тождества. Переменная для этого столбца теперь является базовой переменной, заменяя переменную, которая соответствовала r -ому столбцу матрицы тождества до операции. По сути, переменная, соответствующая опорному столбцу, входит в набор базовых переменных и называется входящей переменной , а заменяемая переменная покидает набор базовых переменных и называется выходящей переменной . Таблица по-прежнему находится в канонической форме, но с набором базовых переменных, измененным на один элемент. ^{[13] [14]}

Алгоритм

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

Ввод выбора переменной

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

Если имеется более одного столбца, так что запись в целевой строке положительна, то выбор того, какую из них добавить к набору базовых переменных, является несколько произвольным, и было разработано несколько правил выбора входящих переменных ^[20], таких как алгоритм Devex ^{[21] .}

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

$${\displaystyle z(\mathbf {x} )=z_{B}+{\text{non-positive terms corresponding to non-basic variables}}}$$

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

Оставляем выбор переменной

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

Далее, опорная строка должна быть выбрана так, чтобы все остальные базовые переменные оставались положительными. Расчет показывает, что это происходит, когда результирующее значение входящей переменной минимально. Другими словами, если опорная колонка — c , то опорная строка r выбирается так, чтобы

${\displaystyle b_{r}/a_{rc}\,}$

является минимумом по всем r, таким образом, что a _rc > 0. Это называется тестом минимального отношения . ^[20] Если есть более одной строки, для которой достигается минимум, то для определения можно использовать правило выбора отбрасываемой переменной ^{[22] .}

Пример

Рассмотрим линейную программу

Свернуть

${\displaystyle Z=-2x-3y-4z\,}$

При условии соблюдения

${\displaystyle {\begin{aligned}3x+2y+z&\leq 10\\2x+5y+3z&\leq 15\\x,\,y,\,z&\geq 0\end{aligned}}}$

С добавлением дополнительных переменных s и t это представляется канонической таблицей

${\displaystyle {\begin{bmatrix}1&2&3&4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}}$

где столбцы 5 и 6 представляют собой основные переменные s и t , а соответствующее основное допустимое решение —

${\displaystyle x=y=z=0,\,s=10,\,t=15.}$

Столбцы 2, 3 и 4 могут быть выбраны в качестве опорных столбцов, для этого примера выбран столбец 4. Значения z , полученные в результате выбора строк 2 и 3 в качестве опорных, составляют 10/1 = 10 и 15/3 = 5 соответственно. Из них минимум равен 5, поэтому строка 3 должна быть опорной. Выполнение опорного столбца дает

${\displaystyle {\begin{bmatrix}3&-2&-11&0&0&-4&-60\\0&7&1&0&3&-1&15\\0&2&5&3&0&1&15\end{bmatrix}}}$

Теперь столбцы 4 и 5 представляют основные переменные z и s , а соответствующее основное допустимое решение —

${\displaystyle x=y=t=0,\,z=5,\,s=5.}$

Для следующего шага в строке цели нет положительных записей и фактически

$${\displaystyle Z={\frac {-60+2x+11y+4t}{3}}=-20+{\frac {2x+11y+4t}{3}}}$$

поэтому минимальное значение Z равно −20.

Нахождение начальной канонической таблицы

В общем случае линейная программа не будет задана в канонической форме, и эквивалентная каноническая таблица должна быть найдена до того, как симплексный алгоритм сможет начать работу. Это можно сделать путем введения искусственных переменных . Столбцы матрицы тождества добавляются как векторы столбцов для этих переменных. Если значение b для уравнения ограничений отрицательно, уравнение отрицается перед добавлением столбцов матрицы тождества. Это не меняет набор допустимых решений или оптимальное решение и гарантирует, что резервные переменные будут составлять начальное допустимое решение. Новая таблица находится в канонической форме, но она не эквивалентна исходной задаче. Поэтому вводится новая целевая функция, равная сумме искусственных переменных, и симплексный алгоритм применяется для поиска минимума; модифицированная линейная программа называется задачей фазы I. ^[23]

Симплексный алгоритм, примененный к задаче Фазы I, должен завершиться минимальным значением для новой целевой функции, поскольку, будучи суммой неотрицательных переменных, ее значение ограничено снизу 0. Если минимум равен 0, то искусственные переменные могут быть исключены из результирующей канонической таблицы, создавая каноническую таблицу, эквивалентную исходной задаче. Затем симплексный алгоритм может быть применен для поиска решения; этот шаг называется Фаза II . Если минимум положителен, то нет допустимого решения для задачи Фазы I, где все искусственные переменные равны нулю. Это означает, что допустимая область для исходной задачи пуста, и поэтому исходная задача не имеет решения. ^{[13] [14] [24]}

Пример

Рассмотрим линейную программу

Свернуть

${\displaystyle Z=-2x-3y-4z\,}$

При условии соблюдения

${\displaystyle {\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}}$

Это представлено (неканонической) таблицей

${\displaystyle {\begin{bmatrix}1&2&3&4&0\\0&3&2&1&10\\0&2&5&3&15\end{bmatrix}}}$

Введем искусственные переменные u и v и целевую функцию W  =  u  +  v , что даст новую таблицу

${\displaystyle {\begin{bmatrix}1&0&0&0&0&-1&-1&0\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

Уравнение, определяющее исходную целевую функцию, сохраняется в ожидании Фазы II.

По построению, u и v являются базовыми переменными, поскольку они являются частью исходной матрицы идентичности. Однако целевая функция W в настоящее время предполагает, что u и v оба равны 0. Чтобы настроить целевую функцию так, чтобы она имела правильное значение, где u  = 10 и v  = 15, добавьте третью и четвертую строки к первой строке, что даст

${\displaystyle {\begin{bmatrix}1&0&5&7&4&0&0&25\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

Выберите столбец 5 в качестве опорного столбца, поэтому опорной строкой должна быть строка 4, а обновленная таблица будет иметь вид

${\displaystyle {\begin{bmatrix}3&0&7&1&0&0&-4&15\\0&3&-2&-11&0&0&-4&-60\\0&0&7&1&0&3&-1&15\\0&0&2&5&3&0&1&15\end{bmatrix}}}$

Теперь выберите столбец 3 в качестве опорного столбца, для которого строка 3 должна быть опорной строкой, чтобы получить

${\displaystyle {\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&-25&0&2&-10&-130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}}$

Искусственные переменные теперь равны 0 и их можно отбросить, получив каноническую таблицу, эквивалентную исходной задаче:

${\displaystyle {\begin{bmatrix}7&0&-25&0&-130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}}$

К счастью, это уже оптимально, а оптимальное значение для исходной линейной программы составляет −130/7.

Продвинутые темы

Выполнение

Форма таблицы, использованная выше для описания алгоритма, допускает непосредственную реализацию, в которой таблица поддерживается как прямоугольный массив ( m  + 1) на ( m  +  n  + 1). Легко избежать хранения m явных столбцов матрицы тождественности, которые будут встречаться в таблице, в силу того, что B является подмножеством столбцов [ A ,  I ]. Такая реализация называется « стандартным симплексным алгоритмом». Накладные расходы на хранение и вычисления таковы, что стандартный симплексный метод является непомерно дорогим подходом к решению больших задач линейного программирования.

В каждой симплексной итерации требуются только данные первой строки таблицы, (основного) столбца таблицы, соответствующего входящей переменной, и правой стороны. Последняя может быть обновлена ​​с использованием опорного столбца, а первая строка таблицы может быть обновлена ​​с использованием (основной) строки, соответствующей выходящей переменной. Как опорный столбец, так и опорная строка могут быть вычислены напрямую с использованием решений линейных систем уравнений, включающих матрицу B и произведение матрицы и вектора с использованием A. Эти наблюдения мотивируют « пересмотренный симплексный алгоритм », для которого реализации отличаются обратимым представлением  B. ^[25 ]

В больших задачах линейного программирования A обычно является разреженной матрицей , и когда полученная разреженность B используется при сохранении ее обратимого представления, пересмотренный симплексный алгоритм гораздо эффективнее стандартного симплексного метода. Коммерческие симплексные решатели основаны на пересмотренном симплексном алгоритме. ^{[24] [25] [26] [27] [28]}

Вырождение: остановка и цикличность

Если значения всех базовых переменных строго положительны, то поворот должен привести к улучшению целевого значения. Когда это всегда так, ни один набор базовых переменных не встречается дважды, и симплексный алгоритм должен завершиться после конечного числа шагов. Базовые допустимые решения, где хотя бы одна из базовых переменных равна нулю, называются вырожденными и могут приводить к поворотам, для которых нет улучшения целевого значения. В этом случае нет фактического изменения решения, а есть только изменение набора базовых переменных. Когда несколько таких поворотов происходят подряд, улучшения нет; в крупных промышленных приложениях вырождение является обычным явлением, и такое « застревание » заметно. Хуже застревания — возможность того, что один и тот же набор базовых переменных встречается дважды, и в этом случае детерминированные правила поворота симплексного алгоритма приведут к бесконечному циклу или «циклу». Хотя вырождение является правилом на практике, а застревание — обычным явлением, цикличность на практике встречается редко. Обсуждение примера практической цикличности приводится в Padberg . ^[24] Правило Бланда предотвращает цикличность и, таким образом, гарантирует, что симплексный алгоритм всегда завершается. ^{[24] [29] [30]} Другой поворотный алгоритм, алгоритм крест-накрест, никогда не зацикливается на линейных программах. ^[31]

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

Эффективность в худшем случае

Симплексный метод на практике оказался исключительно эффективным и стал большим улучшением по сравнению с более ранними методами, такими как исключение Фурье–Моцкина . Однако в 1972 году Клее и Минти ^[32] привели пример, куб Клее–Минти , показывающий, что наихудшая сложность симплексного метода, сформулированная Данцигом, составляет экспоненциальное время . С тех пор для почти каждой вариации метода было показано, что существует семейство линейных программ, для которых он работает плохо. Остается открытым вопрос, существует ли вариация с полиномиальным временем , хотя известны субэкспоненциальные правила поворота. ^[33]

В 2014 году было доказано ^{[ требуется ссылка ]} , что конкретный вариант симплексного метода является NP-мощным, т. е. его можно использовать для решения с полиномиальными накладными расходами любой проблемы в NP неявно во время выполнения алгоритма. Более того, решение о том, входит ли заданная переменная в базис во время выполнения алгоритма на заданном входе, и определение количества итераций, необходимых для решения заданной задачи, являются NP-трудными задачами. ^[34] Примерно в то же время было показано, что существует искусственное правило поворота, для которого вычисление его выходных данных является PSPACE-полным . ^[35] В 2015 году это было усилено, чтобы показать, что вычисление выходных данных правила поворота Данцига является PSPACE-полным . ^[36]

Эффективность на практике

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

Другой метод анализа производительности симплексного алгоритма изучает поведение наихудших сценариев при малых возмущениях — являются ли наихудшие сценарии стабильными при малых изменениях (в смысле структурной устойчивости ) или они становятся управляемыми? Эта область исследований, называемая сглаженным анализом , была введена специально для изучения симплексного метода. Действительно, время выполнения симплексного метода на входе с шумом является полиномиальным по числу переменных и величине возмущений. ^{[39] [40]}

Другие алгоритмы

Другие алгоритмы для решения задач линейного программирования описаны в статье о линейном программировании . Другой алгоритм поворота с заменой базиса — это алгоритм крест-накрест . ^{[41] [42]} Существуют алгоритмы с полиномиальным временем для линейного программирования, которые используют методы внутренних точек: к ним относятся эллипсоидальный алгоритм Хачияна , проективный алгоритм Кармаркара и алгоритмы следования по пути . ^[15] Метод Big-M — это альтернативная стратегия для решения линейной программы с использованием однофазного симплекса.

Дробно-линейное программирование

Дробно-линейное программирование (ДЛП) является обобщением линейного программирования (ЛП). В ДЛП целевая функция является линейной функцией , в то время как целевая функция дробно-линейной программы является отношением двух линейных функций. Другими словами, линейная программа является дробно-линейной программой, в которой знаменатель является постоянной функцией, имеющей значение один везде. Дробно-линейное программирование может быть решено с помощью варианта симплексного алгоритма ^{[43] [44] [45] [46]} или с помощью алгоритма крест-накрест . ^[47]

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

• Правило поворота Бланда , которое позволяет избежать цикличности
• Алгоритм крест-накрест
• Метод секущей плоскости
• Алгоритм Девекса
• Исключение Фурье-Моцкина
• Градиентный спуск
• Алгоритм Кармаркара
• Симплициальная эвристика Нелдера-Мида
• Функции потерь — тип целевой функции

Примечания

1. Мурти, Катта Г. (2000). Линейное программирование. John Wiley & Sons.
2. Мурти (1983, Комментарий 2.2)
3. Мурти (1983, Примечание 3.9)
4. Стоун, Ричард Э.; Тови, Крейг А. (1991). «Симплексные и проективные алгоритмы масштабирования как итеративно перевзвешенные методы наименьших квадратов». Обзор SIAM . 33 (2): 220–237. doi :10.1137/1033049. JSTOR  2031142. MR  1124362.
5. Стоун, Ричард Э.; Тови, Крейг А. (1991). «Исправление: алгоритмы симплексного и проективного масштабирования как методы наименьших квадратов с итеративным повторным взвешиванием». Обзор SIAM . 33 (3): 461. doi :10.1137/1033100. JSTOR  2031443. MR  1124362.
6. Стрэнг, Гилберт (1 июня 1987 г.). «Алгоритм Кармаркара и его место в прикладной математике». The Mathematical Intelligencer . 9 (2): 4–10. doi :10.1007/BF03025891. ISSN  0343-6993. MR  0883185. S2CID  123541868.
7. Данциг, Джордж Б. (апрель 1982 г.). «Воспоминания об истоках линейного программирования» (PDF) . Operations Research Letters . 1 (2): 43–48. doi :10.1016/0167-6377(82)90043-8. Архивировано из оригинала 20 мая 2015 г.
8. Альберс и Рид (1986). «Интервью с Джорджем Б. Данцигом: отцом линейного программирования». College Mathematics Journal . 17 (4): 292–314. doi :10.1080/07468342.1986.11972971.
9. Данциг, Джордж (май 1987). "Истоки симплексного метода" (PDF) . В Нэш, Стивен Г. (ред.). История научных вычислений . Ассоциация вычислительной техники. стр. 141–151. doi :10.1145/87252.88081. ISBN 978-0-201-50814-7. Архивировано (PDF) из оригинала 29 мая 2015 г.
10. Мёрти (1983, Теорема 3.3)
11. Мурти (1983, стр. 143, раздел 3.13)
12. Murty (1983, стр. 137, раздел 3.8)
13. Джордж Б. Данциг и Мукунд Н. Тапа. 1997. Линейное программирование 1: Введение . Springer-Verlag.
14. Эвар Д. Неринг и Альберт В. Такер , 1993, Линейные программы и смежные проблемы , Academic Press. (элементарный)
15. Роберт Дж. Вандербей, Линейное программирование: основы и расширения, 3-е изд., Международная серия по исследованию операций и науке управления, т. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5 . 
16. Мурти (1983, Раздел 2.2)
17. Мурти (1983, стр. 173)
18. Мурти (1983, раздел 2.3.2)
19. Мурти (1983, раздел 3.12)
20. Murty (1983, стр. 66)
21. Харрис, Паула М.Дж. «Методы выбора опорного элемента кода Devex LP». Математическое программирование 5.1 (1973): 1–28
22. Мурти (1983, стр. 67)
23. Мурти (1983, стр. 60)
24. Падберг, М. (1999). Линейная оптимизация и расширения (второе изд.). Спрингер-Верлаг. ISBN 3-540-65833-5.
25. Dantzig, George B. ; Thapa, Mukund N. (2003). Линейное программирование 2: Теория и расширения . Springer-Verlag.
26. Алеврас, Дмитрий; Падберг, Манфред В. (2001). Линейная оптимизация и расширения: проблемы и решения . Университетский текст. Спрингер-Верлаг. ISBN 3-540-41744-3.(Задачи от Padberg с решениями.)
27. Марош, Иштван; Митра, Гаутам (1996). «Симплексные алгоритмы». В JE Beasley (ред.). Достижения в линейном и целочисленном программировании . Oxford Science. стр. 1–46. MR  1438309.
28. Марош, Иштван (2003). Вычислительные методы симплексного метода . Международная серия по исследованию операций и науке управления. Том 61. Бостон, Массачусетс: Kluwer Academic Publishers. С. xx+325. ISBN 978-1-4020-7332-8. МР  1960274.
29. Бланд, Роберт Г. (май 1977 г.). «Новые правила конечного поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. doi :10.1287/moor.2.2.103. JSTOR  3689647. MR  0459599. S2CID  18493293.
30. Мурти (1983, стр. 79)
31. Существуют абстрактные задачи оптимизации, называемые ориентированными матроидными программами, в которых правило Бланда зацикливается (неправильно), в то время как алгоритм «крест-накрест» завершается правильно.
32. Клее, Виктор ; Минти, Джордж Дж. (1972). «Насколько хорош симплексный алгоритм?». В Шиша, Овед (ред.). Неравенства III (Труды третьего симпозиума по неравенствам, состоявшегося в Калифорнийском университете, Лос-Анджелес, Калифорния, 1–9 сентября 1969 г., посвященного памяти Теодора С. Моцкина) . Нью-Йорк-Лондон: Academic Press. стр. 159–175. MR  0332165.
33. Хансен, Томас; Цвик, Ури (2015), «Улучшенная версия правила поворота случайных граней для симплексного алгоритма», Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений , стр. 209–218, CiteSeerX 10.1.1.697.2526 , doi :10.1145/2746539.2746557, ISBN  9781450335362, S2CID  1980659
34. Диссер, Янн; Скутелла, Мартин (01 ноября 2018 г.). «Симплексный алгоритм NP-могуч». АКМ Транс. Алгоритмы . 15 (1): 5:1–5:19. arXiv : 1311.5935 . дои : 10.1145/3280847. ISSN  1549-6325. S2CID  54445546.
35. Адлер, Илан; Христос, Пападимитриу ; Рубинштейн, Авиад (2014), «О правилах симплексного поворота и теории сложности», Целочисленное программирование и комбинаторная оптимизация , Lecture Notes in Computer Science, т. 17, стр. 13–24, arXiv : 1404.3320 , doi : 10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, S2CID  891022
36. Fearnly, John; Savani, Rahul (2015), «Сложность симплексного метода», Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений , стр. 201–208, arXiv : 1404.0605 , doi : 10.1145/2746539.2746558, ISBN 9781450335362, S2CID  2116116
37. Александр Шрайвер , Теория линейного и целочисленного программирования . John Wiley & sons, 1998, ISBN 0-471-98232-6 (математический) 
38. Симплексный алгоритм занимает в среднем D шагов для куба. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). Симплексный метод: вероятностный анализ . Алгоритмы и комбинаторика (Учебные и исследовательские тексты). Том 1. Берлин: Springer-Verlag. С. xii+268. ISBN 978-3-540-17096-9. МР  0868467.
39. Шпильман, Дэниел; Тенг, Шан-Хуа (2001). «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время». Труды Тридцать третьего ежегодного симпозиума ACM по теории вычислений . ACM. С. 296–305. arXiv : cs/0111050 . doi :10.1145/380752.380813. ISBN 978-1-58113-349-3. S2CID  1471.
40. Дадуш, Даниэль; Хьюбертс, Софи (01.01.2020). «Дружественный сглаженный анализ симплексного метода». SIAM Journal on Computing . 49 (5): STOC18–449. arXiv : 1711.05667 . doi : 10.1137/18M1197205. ISSN  0097-5397. S2CID  226351624.
41. Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила осевого положения для линейного программирования: обзор последних теоретических разработок». Annals of Operations Research . 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658 . doi :10.1007/BF02096264. ISSN  0254-5330. MR  1260019. S2CID  6058077. 
42. Фукуда, Комей ; Терлаки, Тамас (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Методы крест-накрест: свежий взгляд на алгоритмы поворота». Математическое программирование, серия B. 79 ( 1–3). Амстердам: North-Holland Publishing: 369–395. doi :10.1007/BF02614325. MR  1464775. S2CID  2794181.
43. Мурти (1983, Глава 3.20 (стр. 160–164) и стр. 168 и 179)
44. Глава пятая: Craven, BD (1988). Дробное программирование . Серия Sigma в прикладной математике. Том 4. Берлин: Heldermann Verlag. С. 145. ISBN 978-3-88538-404-5. МР  0949209.
45. Крук, Серж; Волкович, Генри (1999). «Псевдолинейное программирование». SIAM Review . 41 (4): 795–805. Bibcode :1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355 . doi :10.1137/S0036144598335259. JSTOR  2653207. MR  1723002. 
46. Матис, Фрэнк Х.; Матис, Ленора Джейн (1995). «Алгоритм нелинейного программирования для управления больницей». Обзор SIAM . 37 (2): 230–234. doi :10.1137/1037046. JSTOR  2132826. MR  1343214. S2CID  120626738.
47. Иллес, Тибор; Сирмаи, Акос; Терлаки, Тамаш (1999). «Метод конечного креста для гиперболического программирования». Европейский журнал операционных исследований . 114 (1): 198–214. CiteSeerX 10.1.1.36.7090 . дои : 10.1016/S0377-2217(98)00049-6. ISSN  0377-2217. 

Ссылки

• Murty, Katta G. (1983). Линейное программирование . Нью-Йорк: John Wiley & Sons, Inc. стр. xix+482. ISBN 978-0-471-09725-9. МР  0720547.

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

Эти введения написаны для студентов, изучающих информатику и исследование операций :

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest и Clifford Stein . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 29.3: Симплексный алгоритм, стр. 790–804. 
• Фредерик С. Хиллер и Джеральд Дж. Либерман: Введение в исследование операций , 8-е издание. McGraw-Hill. ISBN 0-07-123828-X 
• Рардин, Рональд Л. (1997). Оптимизация в исследовании операций . Prentice Hall. стр. 919. ISBN 978-0-02-398415-0.

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

• Введение в линейное программирование и симплекс-алгоритм, Спирос Ревелиотис из Технологического института Джорджии.
• Гринберг, Харви Дж., Политоп Клее–Минти демонстрирует экспоненциальную временную сложность симплекс-метода, Университет Колорадо в Денвере (1997) скачать PDF
• Симплекс-метод Учебное пособие по симплекс-методу с примерами (также двухфазный и М-метод).
• Калькулятор Mathstools Simplex от www.mathstools.com
• Пример симплексной процедуры для стандартной задачи линейного программирования Томаса Макфарланда из Университета Висконсин-Уайтуотер.
• PHPSimplex: онлайн-инструмент для решения задач линейного программирования от Даниэля Искьердо и Хуана Хосе Руиса из Университета Малаги (UMA, Испания)
• simplex-m Онлайн-решение симплекса