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

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

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

• 1 История
• 2 Обзор
• 3 Стандартная форма
• 4 Симплексная таблица
• 5 Операции сводки
• 6 Алгоритм
  • 6.1 Ввод выбора переменной
  • 6.2 Выход из переменной selection
  • 6.3 Пример
• 7 Поиск исходной канонической таблицы
  • 7.1 Пример
• 8 Дополнительные темы
  • 8.1 Реализация
  • 8.2 Вырождение: остановка и цикличность
  • 8.3 Эффективность
• 9 Другое алгоритмы
• 10 Дробно-линейное программирование
• 11 См. также
• 12 Примечания
• 13 Ссылки
• 14 Дополнительная литература
• 15 Внешние ссылки

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

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

A система линейных неравенств определяет многогранник как возможный регион. Симплексный алгоритм начинается в начальной вершине и движется по краям многогранника, пока не достигнет вершины оптимального решения. Многогранник симплексного алгоритма в 3D

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

максимизируют $c\; T\; x\; \{\backslash \; textstyle\; \backslash \; mathbf\; \{c\; ^\; \{T\}\}\; \backslash \; mathbf\; \{x\}\}$

с учетом $A\; x\; \le \; b\; \{\backslash \; displaystyle\; A\; \backslash \; mathbf\; \{x\}\; \backslash \; leq\; \backslash \; mathbf\; \{b\}\}$и $x\; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \backslash \; geq\; 0\}$

с $c\; =\; (\; c\; 1,\dots ,\; cn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{c\}\; =\; (c\_\; \{1\},\; \backslash ,\; \backslash \; dots,\; \backslash ,\; c\_\; \{n\})\}$коэффициенты целевой функции, $(\cdot )\; T\; \{\backslash \; displaystyle\; (\backslash \; cdot)\; ^\; \{\backslash \; mathrm\; \{T\}\}\}$- это транспонированная матрица, а $x\; =\; (x\; 1,\dots ,\; xn)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; =\; (x\_\; \{1\},\; \backslash ,\; \backslash \; dots,\; \backslash ,\; x\_\; \{n\})\}$- переменные проблемы, $A\; \{\backslash \; displaystyle\; A\}$- матрица размером ap × n, а $b\; =\; (b\; 1,\dots ,\; bp)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\}\; =\; (b\_\; \{1\},\; \backslash ,\; \backslash \; dots,\; \backslash ,\; b\_\; \{p\})\}$неотрицательны ive константы ($\forall \; j,\; b\; j\; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; forall\; j,\; b\_\; \{j\}\; \backslash \; geq\; 0\; \backslash \}$). Существует простой процесс преобразования любой линейной программы в программу стандартной формы, поэтому использование этой формы линейных программ не приводит к потере общности.

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

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

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

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

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

$x\; 1\; \ge \; 5\; \{\backslash \; displaystyle\; x\_\; \{1\}\; \backslash \; geq\; 5\}$

новой переменной $y\; 1\; \{\backslash \; displaystyle\; y\_\; \{1\}\}$, вводится с помощью

$y\; 1\; =\; x\; 1\; -\; 5\; x\; 1\; =\; y\; 1\; +\; 5\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; y\_\; \{1\}\; =\; x\_\; \{1\}\; -5\; \backslash \backslash \; x\_\; \{1\}\; =\; y\_\; \{\; 1\}\; +5\; \backslash \; end\; \{align\}\}\}$

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

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

$x\; 2\; +\; 2\; x\; 3\; \le \; 3\; -\; x\; 4\; +\; 3\; x\; 5\; \ge \; 2\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\_\; \{2\}\; +\; 2x\_\; \{3\}\; \backslash \; leq\; 3\; \backslash \backslash \; -\; x\_\; \{4\}\; +\; 3x\_\; \{5\}\; \backslash \; geq\; 2\; \backslash \; end\; \{align\}\}\}$

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

$x\; 2\; +\; 2\; x\; 3\; +\; s\; 1\; =\; 3\; -\; x\; 4\; +\; 3\; x\; 5\; -\; s\; 2\; Знак\; равно\; 2\; s\; 1,\; s\; 2\; \ge \; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\_\; \{2\}\; +\; 2x\_\; \{3\}\; +\; s\_\; \{1\}\; =\; 3\; \backslash \backslash \; -\; x\_\; \{4\}\; +\; 3x\_\; \{5\}\; -s\_\; \{\; 2\}\; =\; 2\; \backslash \backslash \; s\_\; \{1\},\; \backslash ,\; s\_\; \{2\}\; \backslash \; geq\; 0\; \backslash \; end\; \{align\}\}\}$

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

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

$z\; 1\; =\; z\; 1\; +\; -\; z\; 1\; -\; z\; 1\; +,\; z\; 1\; -\; \ge \; 0\; \{\; \backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; z\_\; \{1\}\; =\; z\_\; \{1\}\; ^\; \{+\}\; -\; z\_\; \{1\}\; ^\; \{-\}\; \backslash \backslash \; z\_\; \{1\}\; ^\; \{+\},\; \backslash ,\; z\_\; \{1\}\; ^\; \{-\; \}\; \backslash \; geq\; 0\; \backslash \; end\; \{align\}\}\}$

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

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

$A\; x\; =\; b,\; \forall \; ixi\; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{A\}\; \backslash \; mathbf\; \{x\}\; =\; \backslash \; mathbf\; \{b\},\; \backslash ,\; \backslash \; forall\; i\; \backslash \; x\_\; \{i\}\; \backslash \; geq\; 0\}$

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

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

$[1\; -\; c\; T\; 0\; 0\; A\; b]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; -\; \backslash \; mathbf\; \{c\}\; ^\; \{T\}\; 0\; \backslash \backslash \; 0\; \backslash \; mathbf\; \{A\}\; \backslash \; mathbf\; \{b\}\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

Пусть

$[1\; -\; c\; BT\; -\; c\; DT\; 0\; 0\; ID\; b]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; -\; \backslash \; mathbf\; \{c\}\; \_\; \{B\}\; ^\; \{T\}\; -\; \backslash \; mathbf\; \{c\}\; \_\; \{D\}\; ^\; \{T\}\; 0\; \backslash \backslash \; 0\; I\; \backslash \; mathbf\; \{D\}\; \backslash \; mathbf\; \{b\}\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[1\; 0\; -\; c\; ¯\; DT\; z\; B\; 0\; ID\; b]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; -\; \{\backslash \; bar\; \{\backslash \; mathbf\; \{c\}\}\}\; \_\; \{D\}\; ^\; \{T\}\; z\_\; \{B\}\; \backslash \backslash \; 0\; I\; \backslash \; mathbf\; \{D\}\; \backslash \; mathbf\; \{b\}\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

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

Выбор входящей переменной

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

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

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

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

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

Оставить выбор переменной

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

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

$br\; /\; arc\; \{\backslash \; displaystyle\; b\_\; \{r\}\; /\; a\_\; \{rc\}\; \backslash ,\}$

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

Пример

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

Minimize

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

С учетом

$3\; x\; +\; 2\; y\; +\; z\; \le \; 10\; 2\; x\; +\; 5\; y\; +\; 3\; z\; \le \; 15\; x,\; y,\; z\; \ge \; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; 3x\; +\; 2y\; +\; z\; \backslash \; leq\; 10\; \backslash \backslash \; 2x\; +\; 5y\; +\; 3z\; \backslash \; leq\; 15\; \backslash \backslash \; x,\; \backslash ,\; y,\; \backslash ,\; z\; \backslash \; geq\; 0\; \backslash \; end\; \{align\}\}\}$

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

$[1-2-3-4\; 0\; 0\; 0\; 0\; 3\; 2\; 1\; 1\; 0\; 10\; 0\; 2\; 5\; 3\; 0\; 1\; 15]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; -2\; -3\; -4\; 0\; 0\; 0\; \backslash \backslash \; 0\; 3\; 2\; 1\; 1\; 0\; 10\; \backslash \; \backslash \; 0\; 2\; 5\; 3\; 0\; 1\; 15\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

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

$[3\; -\; 2\; -\; 11\; 0\; 0\; -\; 4\; -\; 60\; 0\; 7\; 1\; 0\; 3\; -\; 1\; 15\; 0\; 2\; 5\; 3\; 0\; 1\; 15]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 3\; -2\; -11\; 0\; 0\; -\; 4\; -60\; \backslash \backslash \; 0\; 7\; 1\; 0\; 3\; -1\; 15\; \backslash \backslash \; 0\; 2\; 5\; 3\; 0\; 1\; 15\; \backslash \; end\; \{bmatrix\}\}\}$

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

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

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

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

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

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

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

Пример

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

Свернуть

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

С учетом

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

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

$[1\; 2\; 3\; 4\; 0\; 0\; 3\; 2\; 1\; 10\; 0\; 2\; 5\; 3\; 15]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 2\; 3\; 4\; 0\; \backslash \backslash \; 0\; 3\; 2\; 1\; 10\; \backslash \backslash \; 0\; 2\; 5\; 3\; 15\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[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]\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; 0\; 0\; 0\; -1\; -1\; 0\; \backslash \backslash \; 0\; 1\; 2\; 3\; 4\; 0\; 0\; 0\; \backslash \backslash \; 0\; 0\; 3\; 2\; 1\; 1\; 1\; 0\; 10\; \backslash \backslash \; 0\; 0\; 2\; 5\; 3\; end\}$Уравнение, определяющее исходную целевую функцию, сохраняется в ожидании Фазы II.

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

$[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]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; 5\; 7\; 4\; 0\; 0\; 25\; \backslash \backslash \; 0\; 1\; 2\; 3\; 4\; 0\; 0\; 0\; \backslash \backslash \; 0\; 0\; 3\; 2\; 1\; 1\; 0\; 10\; \backslash \backslash \; 0\; 0\; 2\; 5\; 3\; 0\; 1\; 15\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[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]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 3\; 0\; 7\; 1\; 0\; 0\; -4\; 15\; \backslash \backslash \; 0\; 3\; -2\; -11\; 0\; 0\; -4\; -60\; \backslash \backslash \; 0\; 0\; 7\; 1\; 0\; 3\; -1\; 15\; \backslash \backslash \; 0\; 0\; 2\; 5\; 3\; 0\; 1\; 15\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[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]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 1\; 0\; 0\; 0\; 0\; 0\; -1\; -1\; 0\; \backslash \; \backslash \; 0\; 7\; 0\; -25\; 0\; 2\; -10\; -130\; \backslash \backslash \; 0\; 0\; 7\; 1\; 0\; 3\; -1\; 15\; \backslash \backslash \; 0\; 0\; 0\; 11\; 7\; -2\; 3\; 25\; \backslash \; end\; \{bmatrix\}\}\}$

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

$[7\; 0\; -\; 25\; 0\; -\; 130\; 0\; 7\; 1\; 0\; 15\; 0\; 0\; 11\; 7\; 25]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{bmatrix\}\; 7\; 0\; -25\; 0\; -130\; \backslash \backslash \; 0\; 7\; 1\; 0\; 15\; \backslash \backslash \; 0\; 0\; 11\; 7\; 25\; \backslash \; end\; \{bmatrix\}\}\}$

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

Дополнительные темы

Реализация

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

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

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

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

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

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

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

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

В 2018 году было доказано, что конкретный вариант симплекс-метода является, т.е. его можно использовать для решения с полиномиальными накладными расходами любой проблемы в NP неявно во время выполнения алгоритма. Более того, решение, входит ли данная переменная когда-либо в базис во время выполнения алгоритма на данном входе, и определение количества итераций, необходимых для решения данной проблемы, являются NP-трудными проблемами. Вычисление результатов некоторых других сводных правил было уже известно как PSPACE-complete.

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

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

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

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

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

См. Также

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

Примечания

Ссылки

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

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

Эти введения написаны для студентов информатики и исследование операций :

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

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

В Wikibook Operations Research есть страница по теме: Симплексный метод

• Введение в линейное программирование и симплексный алгоритм Спайроса Ревелиотиса из Технологического института Джорджии.
• Гринберг, Харви Дж., Политоп Клее – Минти показывает экспоненциальное время Complexity of Simplex Method University of Colorado at Denver (1997) PDF download
• Simplex Method A tutorial for Simplex Method with examples (also two-phase and M-method).
• Mathstools Simplex Calculator from www.mathstools.com
• Example of Simplex Procedure for a Standard Linear Programming Problem by Thomas McFarland of the University of Wisconsin-Whitewater.
• PHPSimplex: online tool to solve Linear Programming Problems by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)
• simplex-m Online Simplex Solver