Симплекс метод предназначен для решения задачи линейного программирования в каноническом виде

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

ограничениями, применяемыми к целевой функции.

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

[7] Развитие симплексного метода было эволюционным и происходило в течение примерно года.[8]

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

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

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

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

cTx{\textstyle \mathbf {c^{T}} \mathbf {x} }

при условии

Axb{\displaystyle A\mathbf {x} \leq \mathbf {b} }

и

x0{\displaystyle \mathbf {x} \geq 0}

с

c=(c1,,cn){\displaystyle \mathbf {c} =(c_{1},\,\dots ,\,c_{n})}

коэффициентами целевой функции,

()T{\displaystyle (\cdot )^{\mathrm {T} }}

является матрица транспонирования, и

x=(x1,,xn){\displaystyle \mathbf {x} =(x_{1},\,\dots ,\,x_{n})}

являются переменными задачи,

A{\displaystyle A}

является p×n матрица, и

b=(b1,,bp){\displaystyle \mathbf {b} =(b_{1},\,\dots ,\,b_{p})}

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

В геометрических терминах допустимая область, определяемая всеми значениями

x{\displaystyle \mathbf {x} }

такого. Что

Axb{\textstyle A\mathbf {x} \leq \mathbf {b} }

и

i,xi0{\displaystyle \forall i,x_{i}\geq 0}

является (возможно. Неограниченным) выпуклым многогранником. Экстремальная точка или вершина этого многогранника известна как базовое допустимое решение (BFS).

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

Это само по себе сводит задачу к конечному вычислению. Поскольку существует конечное число экстремальных точек. Но число экстремальных точек неуправляемо велико для всех. Кроме самых маленьких линейных программ.[11]

Можно также показать. Что если крайняя точка не является максимальной точкой целевой функции. То существует ребро. Содержащее точку. Так что целевая функция строго увеличивается на ребре. Удаляющемся от точки.[12] Если ребро конечно. То ребро соединяется с другой крайней точкой. Где целевая функция имеет большее значение. В противном случае целевая функция неограничена выше на ребре. И линейная программа не имеет решения.

Симплексный алгоритм применяет это понимание. Идя вдоль ребер многогранника к экстремальным точкам с все большими и большими объективными значениями. Это продолжается до тех пор. Пока не будет достигнуто максимальное значение или не будет посещено неограниченное ребро (вывод о том. Что проблема не имеет решения). Алгоритм всегда завершается. Потому что число вершин в многограннике конечно; более того. Поскольку мы прыгаем между вершинами всегда в одном и том же направлении (в направлении целевой функции). Мы надеемся. Что число посещенных вершин будет небольшим.

[12]

Решение линейной программы выполняется в два этапа. На первом этапе. Известном как фаза I. Находится начальная крайняя точка. В зависимости от природы программы эта проблема может быть тривиальной. Но в целом она может быть решена путем применения симплексного алгоритма к модифицированной версии исходной программы. Возможные результаты фазы I заключаются либо в том. Что найдено основное допустимое решение. Либо в том. Что допустимая область пуста. В последнем случае линейная программа называется неосуществимой На втором этапе, фаза II. Симплексный алгоритм применяется с использованием базового допустимого решения. Найденного в фазе I в качестве отправной точки.

Возможные результаты фазы II-это либо оптимальное базовое осуществимое решение. Либо бесконечное ребро. На котором целевая функция неограниченавыше.]

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

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

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

новая переменная,

y1{\displaystyle y_{1}}

, вводится с помощью

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

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

x1{\displaystyle x_{1}}

из линейной программы. Таким образом. Все ограничения с нижними границами могут быть изменены на ограничения без отрицательности.

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

Например, неравенство

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

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

x2+2x3+s1=3x4+3x5s2=2s1,s20{\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}}}

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

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

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

z1{\displaystyle z_{1}}

не ограничено. То напишите

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

Уравнение может быть использовано для исключения

z1{\displaystyle z_{1}}

из линейной программы.

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

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

Также полезно предположить. Что ранг

A{\displaystyle \mathbf {A} }

-это количество строк. Это не приводит к потере общности. Так как в противном случае либо система

Ax=b{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }

имеет избыточные уравнения. Которые могут быть отброшены. Либо система непоследовательна. И линейная программа не имеет решения.[17]

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

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

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

Первая строка определяет целевую функцию. А остальные строки определяют ограничения.

Ноль в первом столбце представляет нулевой вектор той же размерности. Что и вектор b (разные авторы используют разные соглашения относительно точного расположения). Если столбцы A можно переставить так. Чтобы они содержали единичную матрицу порядка p (количество строк в A). То таблица. Как говорят. Находится в канонической форме. Переменные соответствующие столбцам матрицы идентичности называются базовыми переменными в то время как остальные переменные называются

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

0{\displaystyle 0}

1{\displaystyle 1}

, либо каким-то другим числом. Каждая строка будет иметь

1{\displaystyle 1}

столбец со значением

1{\displaystyle 1}

,

p1{\displaystyle p-1}

столбцы с коэффициентами

0{\displaystyle 0}

, а остальные столбцы с некоторыми другими коэффициентами (эти другие переменные представляют наши неосновные переменные).

Устанавливая значения неосновных переменных равными нулю. Мы гарантируем в каждой строке. Что значение переменной. Представленной a

1{\displaystyle 1}

в ее столбце. Равно

b{\displaystyle b}

значению в этой строке.

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

]

Позволь

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

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

[10c¯DTzB0IDb]{\displaystyle {\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}}

где zB-значение целевой функции при соответствующем базовом допустимом решении.

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

Операции Pivot

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

В результате получается. Что если элемент pivot находится в строке r, то столбец становится r-й столбец матрицы идентичности. Переменная для этого столбца теперь является базовой переменной. Заменяющей переменную. Которая соответствовала r-му столбцу матрицы идентичности до операции. По сути, переменная . Соответствующая сводному столбцу. Входит в набор базовых переменных и называется входящей переменной, а заменяемая переменная выходит из набора базовых переменных и называется выходящей переменной. Таблица все еще находится в канонической форме. Но с набором основных переменных. Измененных одним элементом.

[13][14]

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

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

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

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

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

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

Легко видеть. Что он является оптимальным. Так как целевой ряд теперь соответствует уравнению вида

z(x)=zB+nonnegative terms corresponding to nonbasic variables{\displaystyle z(\mathbf {x} )=z_{B}+{\text{nonnegative terms corresponding to nonbasic variables}}}

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

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

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

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

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

Другими словами. Если сводный столбец равен c, то сводная строка r выбирается так. Чтобы

br/arc{\displaystyle b_{r}/a_{rc}\,}

является минимальным по всем r, так что rcЭто называется тестом минимального отношения.[20] Если существует более одной строки. Для которой достигается минимум, то для определения можно использовать правило выбора падающей переменной[22].

Пример

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

Минимизировать

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

Подлежит

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

С добавлением слабых переменных

s и tэто представлено канонической таблицей

[12340000321101002530115]{\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, а соответствующее базовое допустимое решение

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

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

Из них минимум 5, поэтому строка 3 должна быть поворотной строкой. Выполнение разворота производит

[3211004600710311502530115]{\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 и соответствующее базовое допустимое решение

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

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

Z=60+2x+11y+4t3=20+2x+11y+4t3{\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]

Пример

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

Минимизировать

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

Подлежит

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

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

[12340032110025315]{\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, дающую новую таблицу

[1000011001234000003211010002530115]{\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, добавьте третью и четвертую строки к первой строке, дающей

[10574002501234000003211010002530115]{\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, а обновленная таблица —

[3071004150321100460007103115002530115]{\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 должна быть сводной строкой. Чтобы получить

[100001100702502101300071031150001172325]{\displaystyle {\begin{bmatrix}1&0&0&0&0&-1&-1&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 и они могут быть отброшены давая каноническую таблицу эквивалентную исходной задаче:

[702501300710150011725]{\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]

Дегенерация: торможение и цикличность

Если значения всех базовых переменных строго положительны. То поворот должен привести к улучшению объективного значения. Когда это происходит всегда. Ни один набор базовых переменных не встречается дважды. И симплексный алгоритм должен завершиться после конечного числа шагов. Основные выполнимые решения. Где хотя бы одна из основных переменных равна нулю. Называются вырожденными и может привести к поворотам. Для которых нет улучшения в объективном значении. В этом случае фактическое изменение решения не происходит. А происходит только изменение набора базовых переменных. Когда несколько таких поворотов происходят последовательно. Улучшения не происходит; в крупных промышленных приложениях вырождение является обычным явлением и такое торможение— примечательно. Хуже, чем остановка. Является возможность того. Что один и тот же набор базовых переменных происходит дважды. И в этом случае детерминированные правила поворота симплексного алгоритма приведут к бесконечному циклу. Или В то время как вырождение является правилом на практике. И задержка является обычным явлением. Езда на велосипеде встречается редко. Обсуждение примера практического цикла происходит в Падберге.[24]правило Бланда предотвращает цикл и. Таким образом. Гарантирует. Что симплексный алгоритм всегда завершается.[24][29][30] Еще один поворотный алгоритм. Алгоритм крест-накрест никогда не циклирует на линейных программах.[31]

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

Эффективность

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

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

Анализ и количественная оценка наблюдения о том. Что симплексный алгоритм эффективен на практике. Несмотря на его экспоненциальную наихудшую сложность. Привели к разработке других мер сложности. Симплексный алгоритм имеет полиномиальную среднюю временную сложность при различных распределениях вероятностей, причем точная средняя производительность симплексного алгоритма зависит от выбора распределения вероятностей для случайныхматриц. Другой метод анализа производительности симплексного алгоритма изучает поведение наихудших сценариев при малых возмущениях-устойчивы ли наихудшие сценарии при небольших изменениях (в смысле структурной устойчивости) или они становятся сговорчивыми? Эта область исследований называется сглаженным анализом, был введен специально для изучения симплексного метода. Действительно. Время работы симплексного метода на входе с шумом полиномиально по числу переменных и величине возмущений.[39]

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

Другие алгоритмы решения задач линейного программирования описаны в статье линейное программирование. Другим алгоритмом поворота базисного обмена является алгоритм крест-накрест.[40][41] Существуют полиномиальные алгоритмы линейного программирования. Использующие методы внутренних точек: к ним относятся эллипсоидальный алгоритм Хачияна, проективный алгоритмКармаркара и алгоритмы следования по пути.]

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

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

См. также

  1. ^
  2. ^ Мурти (1983, Комментарий 2.2)
  3. ^ Мурти (1983, Примечание 3.9)
  4. ^ Стоун, Ричард Э.; Тови, Крейг А. (1991). Обзор СИАМА. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. МИСТЕР 1124362.
  5. ^ Стоун, Ричард Э.; Тови, Крейг А. (1991). Обзор СИАМА. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. МИСТЕР 1124362.
  6. ^ Странг, Гилберт (1 июня 1987). Математический интеллект. 9 (2): 4-10. doi:10.1007/BF03025891. ISSN 0343-6993. МИСТЕР 0883185. S2CID 123541868.
  7. ^ Данциг, Джордж Б. (апрель 1982). . Письма об исследованиях операций. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8.
  8. ^ Альберс и Рид (1986). . Математический журнал колледжа. 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 http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf.
  10. ^ Мурти (1983, Теорема 3.3)
  11. ^ Мурти (1983, стр. 143, раздел 3.13)
  12. ^ b Murty (1983, стр. 137, раздел 3.8)
  13. ^ Jump up to: a b c George B. Dantzig and Mukund N. Thapa. 1997. Линейное программирование 1: Введение. Шпрингер-Верлаг.
  14. ^ b c d Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (элементарно)
  15. ^ b Robert J. Вандербей, Линейное программирование: Основы и расширения, 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. ^ Jump up to: a b Murty (1983, p. 66)
  21. ^ Harris, Paula MJ.
  22. ^ Мурти (1983, с. 67)
  23. ^ Мурти (1983, с. 60)
  24. ^ b c d M. Падберг, Линейная оптимизация и расширения, Второе издание. Springer-Verlag, 1999.
  25. ^ Подпрыгните к: а б Джордж Б. Данциг и Мукунд Н.Тапа. 2003. Линейное программирование 2: Теория и расширения. Шпрингер-Верлаг.
  26. ^ Дмитрий Алеврас и Манфред У. Падберг, Линейная оптимизация и расширения: Проблемы и расширения, Universitext, Springer-Verlag, 2001. (Проблемы из Падберга с решениями.)
  27. ^ Maros, István; Mitra, Gautam (1996). Бизли (ред.). Достижения в области линейного и целочисленного программирования . Oxford Science. pp. 1-46. MR . 1438309.
  28. ^ Maros, István (2003). Вычислительные методы симплексного метода. Международная серия по операционным исследованиям и менеджменту. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN 978-1-4020-7332-8. МИСТЕР 1960274.
  29. ^ Блэнд, Роберт Г. (май 1977). . Математика исследования операций. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. МИСТЕР 0459599. S2CID 18493293.
  30. ^ Мурти (1983, с. 79)
  31. ^ Существуют абстрактные задачи оптимизации. Называемые ориентированными матроидными программами. В которых правило Блэнда циклически (неправильно). В то время как алгоритм крест-накрест завершается правильно.
  32. ^ Klee, Victor; Minty, George J. (1972). Неравенство III (Труды Третьего симпозиума по неравенству, проведенного в Калифорнийском университете, Лос-Анджелес, Калифорния, 1-9 сентября 1969 года. Посвященного памяти Теодора С. Моцкина) . New York-London: Academic Press. pp. 159-175. MR 0332165.
  33. ^ Hansen, Thomas; Zwick, Uri (2015), «Улучшенная версия правила поворота случайной грани для симплексного алгоритма», Труды Сорок седьмого ежегодного симпозиума ACM по теории вычислений: 209-218, CiteSeerX 10.1.1.697.2526, doi:10.1145/2746539.2746557, ISBN 9781450335362, S2CID 1980659
  34. ^ Disser, Yann; Skutella, Martin (2018-11-01). ACM Trans. Алгоритмы. 15 (1): 5:1-5:19. arXiv:1311.5935. doi:10.1145/3280847. ISSN 1549-6325. S2CID 54445546.
  35. ^ Adler, Ilan; Christos, Papadimitriou; Rubinstein, Aviad (2014), «On Simplex Pivoting Rules and Complexity Theory», International Conference on Integer Programming and Combinatorial Optimization, 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 шагов для куба. Боргвардт (1987): Borgwardt, Karl-Heinz (1987). Симплексный метод: вероятностный анализ. Алгоритмы и комбинаторика (Учебные и исследовательские тексты). 1. Берлин: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. МИСТЕР 0868467.
  39. ^ Spielman, Daniel; Teng, Shang-Hua (2001). Труды Тридцать третьего ежегодного симпозиума ACM по теории вычислений . arXiv:cs/0111050. doi:10.1145/380752.380813. ISBN 978-1-58113-349-3. S2CID 1471.
  40. ^ Терлаки, Тамаш; Чжан, Шу Чжун (1993). Анналы оперативных исследований. 46-47 (1): 203-233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. МИСТЕР 1260019. S2CID 6058077.
  41. ^ Fukuda, Komei; Terlaky, Tamás (1997). Томас М. Либлинг; Доминик де Верра (ред.). Математическое программирование. Серия В. 79 (1–3). Амстердам: Издательство Северной Голландии. С. 369-395. doi:10.1007/BF02614325. МИСТЕР 1464775.
  42. ^ Мурти (1983, глава 3.20 (стр. 160-164) и стр. 168 и 179)
  43. ^ Глава пятая: Крейвен, Б. Д. (1988). Дробное программирование. Сигма-ряды в прикладной математике. 4. Berlin: Heldermann Verlag. p. 145. ISBN 978-3-88538-404-5. МИСТЕР 0949209.
  44. ^ Kruk, Serge; Wolkowicz, Henry (1999). Сиамское обозрение. 41 (4): 795–805. Bibcode:1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355. doi:10.1137/S0036144598335259. JSTOR 2653207. МИСТЕР 1723002.
  45. ^ Mathis, Frank H.; Mathis, Lenora Jane (1995). Сиамское обозрение. 37 (2): 230–234. doi:10.1137/1037046. JSTOR 2132826. МИСТЕР 1343214.
  46. ^ Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). . Европейский журнал оперативных исследований. 114 (1): 198-214. CiteSeerX 10.1.1.36.7090. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217.

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

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

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