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

Эта статья об алгоритме линейного программирования. Информацию об эвристике нелинейной оптимизации см. в разделе « Метод Нелдера – Мида» .

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

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

История

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

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

Обзор

Дополнительная информация: Линейное программирование.

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

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

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

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

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

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

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

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

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

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

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

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

$x_{1}\geq 5$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять

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

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

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

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

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

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

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

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

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

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

Пример

См. Также: Пересмотренный симплексный алгоритм § Численный пример.

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

Свернуть

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

С учетом

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

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

${\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.$

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

${\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.$

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

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

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

исходной

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

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

Пример

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

Свернуть

$Z=-2a-3b-4c\,$

С учетом

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

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

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

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

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

${\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, а обновленная таблица будет иметь вид

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

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

${\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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Дробно-линейное программирование

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

См. также

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

Ссылки

• Мурти, Катта Г. (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. ИСБН  978-0-02-398415-0 .

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

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