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

В математической оптимизации , Данциг «s симплексный алгоритм (или симплекс - метод ) является популярным алгоритмом для линейного программирования .

Название алгоритма происходит от концепции симплекса и было предложено Т. С. Моцкиным . Симплексы фактически не используются в методе, но одна его интерпретация состоит в том, что он работает на симплициальных конусах , и они становятся собственными симплексами с дополнительным ограничением. Рассматриваемые симплициальные конусы - это углы (т. Е. Окрестности вершин) геометрического объекта, называемого многогранником . Форма этого многогранника определяется ограничениями, применяемыми к целевой функции.

История

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

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

Обзор

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

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

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

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

при условии и${\ Displaystyle А \ mathbf {х} \ leq \ mathbf {b}}$${\ Displaystyle \ mathbf {х} \ geq 0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

заменены на

${\ displaystyle {\ begin {align} x_ {2} + 2x_ {3} + s_ {1} & = 3 \\ - x_ {4} + 3x_ {5} -s_ {2} & = 2 \\ s_ { 1}, \, s_ {2} & \ geq 0 \ конец {выровнено}}}$

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

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

${\ displaystyle {\ begin {align} & z_ {1} = z_ {1} ^ {+} - z_ {1} ^ {-} \\ & z_ {1} ^ {+}, \, z_ {1} ^ { -} \ geq 0 \ end {выровнено}}}$

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

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

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

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

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

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

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

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

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

Позволять

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

Сводные операции

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

Алгоритм

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

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

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

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

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

${\ displaystyle z (\ mathbf {x}) = z_ {B} + {\ text {неотрицательные термины, соответствующие небазовым переменным}}}$

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

Выход из выбора переменных

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

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

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

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

Пример

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

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

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

При условии

${\ displaystyle {\ begin {align} 3x + 2y + z & \ leq 10 \\ 2x + 5y + 3z & \ leq 15 \\ x, \, y, \, z & \ geq 0 \ end {выравнивается}}}$

С добавлением резервных переменных 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.

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

Пример

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

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

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

При условии

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

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

${\ 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) -by- ( m  +  n  + 1) массив. Несложно избежать сохранения m явных столбцов единичной матрицы, которые будут встречаться в таблице, поскольку B является подмножеством столбцов [ A ,  I ]. Эта реализация называется « стандартным симплексным алгоритмом». Накладные расходы на хранение и вычисления таковы, что стандартный симплексный метод является чрезмерно дорогим подходом к решению больших задач линейного программирования.

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

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

Вырождение: срыв и езда на велосипеде

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

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

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

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

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

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

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

Другие алгоритмы решения задач линейного программирования описаны в статье о линейном программировании . Другой алгоритм поворота базисного обмена - это алгоритм перекрестного пересечения . Существует алгоритмы полиномиального времени для линейного программирования , которые используют методы внутренней точки: они включают Хачиян «s эллипсоидной алгоритм , Кармаркар » s проективного алгоритм и алгоритмы пути следования .

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

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

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

Примечания

использованная литература

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

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

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

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7 . Раздел 29.3: Симплексный алгоритм, стр. 790–804.
• Фредерик С. Хиллер и Джеральд Дж. Либерман: Введение в исследование операций , 8-е издание. Макгроу-Хилл. ISBN  0-07-123828-X
• Рардин, Рональд Л. (1997). Оптимизация исследования операций . Прентис Холл. п. 919. ISBN 978-0-02-398415-0.

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

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