Симплекс метод пример в excel: Симплекс-метод решения задачи линейного программирования в Excel – Задача линейного программирования. Симплекс-метод. Применение надстройки «Поиск решения» в MS Excel

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.

Очистить все ячейки?

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

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

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные , а свободные переменные :

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x₃. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x₄. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F(X)=.

Пример 2. Найти максимум функции

при условиях

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1:

Базисные векторы x₄, x₃, следовательно, все элементы в столбцах x₄, x₃, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x₃, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

при условиях

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x₂. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x₃. Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₃, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

.

Значение целевой функции в данной точке:

.

Пример 2. Найти оптимальный план задачи линейного программирования:

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы x₄, x₅, x₆, следовательно, все элементы в столбцах x₄, x₅, x₆, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x₅, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x₆, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

В строке 5 элементы, соответствующие переменным x₁, x₂, x₃, x₄, x₅, x₆ неотрицательны, а число находящийся в пересечении данной строки и столбца x₀ отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Пример — Табличный симплекс метод

Необходимо решить задачу линейного программирования.

Целевая функция:

2x ₁+5x₂+3x₃+8x₄ →min

Ограничивающие условия:

3x₁+6x₂-4x₃+x₄≤12
4x₁-13x₂+10x₃+5x₄≥6
3x₁+7x₂+x₃≥1

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

Так как наша задача — задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x₅ и изменив знак «≤» на «=». Т. к. второе и третье неравенства имеют знаки «≥» необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x₆ и x₇ соответственно. В результате получем эквивалентную задачу:

3x₁+6x₂-4x₃+x₄+x₅=12
-4x₁+13x₂-10x₃-5x₄+x₆=-6
-3x₁-7x₂-x₃+x₇=-1

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -6, он задает ведущую строку — X6. В этой строке так же находим максимальный по модулю отрицательный элемент: -10 он находится в столбце X3 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю — это элемент: -0.4, он задает ведущую строку — X7. В этой строке так же находим максимальный по модулю отрицательный элемент: -8.3 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент — это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.

Так как в строке F нет отрицательных элементов, то
найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x₃=0.539, x₁=0.153. Переменные x₂ и x₄ не входят в базис, поэтому x₂=0 x₄=0.

Симплекс-метод — Википедия

Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида

Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.

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

В работе Л. В. Канторовича «Математические методы организации и планирования производства» (1939) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.^[1]

Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе 1952 года^[2].

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый выпуклый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

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

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

Усиленная постановка задачи[править | править код]

Рассмотрим следующую задачу линейного программирования:

cTx→max,Ax⩽b,x⩾0,b⩾0.{\displaystyle c^{T}x\to \max ,Ax\leqslant b,x\geqslant 0,b\geqslant 0.}

Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z, где:

[1−cT00AE][Zxxs]=[0b],x,xs⩾0{\displaystyle {\begin{bmatrix}1&-c^{T}&0\\0&A&E\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}0\\b\end{bmatrix}},x,x_{s}\geqslant 0}

Здесь x — переменные из исходного линейного функционала, x_s — новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство, c — коэффициенты исходного линейного функционала, Z — переменная, которую необходимо максимизировать. Полупространства x⩾0{\displaystyle x\geqslant 0} и xs⩾0{\displaystyle x_{s}\geqslant 0} в пересечении образуют многогранник, представляющий множество допустимых решений. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Тогда мы можем присвоить этому числу переменных значение 0 и назвать их «небазисными». Остальные переменные при этом будут вычисляться однозначно и называться «базисными». Сам же набор этих переменных называется базисом. Полученная точка будет вершиной в пересечении соответствующих небазисным переменным гиперплоскостей. Для того, чтобы найти т. н. начальное допустимое решение (вершину, из которой мы начнём движение), присвоим всем изначальным переменным x значение 0 и будем их считать небазисными, а все новые будем считать базисными. При этом начальное допустимое решение вычисляется однозначно : xsi=bi{\displaystyle \mathbf {x} _{si}=\mathbf {b} _{i}}.

Алгоритм[править | править код]

Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества базисных и небазисных векторов (двигаться по рёбрам), и матрица будет иметь следующий вид:

[1cBTB−1A−cTcBTB−10B−1AB−1][Zxxs]=[cBTB−1bB−1b],{\displaystyle {\begin{bmatrix}1&c_{B}^{T}B^{-1}A-c^{T}&c_{B}^{T}B^{-1}\\0&B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}c_{B}^{T}B^{-1}b\\B^{-1}b\end{bmatrix}},}

где cB{\displaystyle c_{B}} — коэффициенты вектора c{\displaystyle c}, соответствующие базисным переменным (переменным xs{\displaystyle x_{s}} соответствуют 0), B{\displaystyle B} — столбцы [AE]{\displaystyle [\mathbf {A} \mathbf {E} ]}, соответствующие базисным переменным. Матрицу, образованную оставшимися столбцами обозначим D{\displaystyle D}. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма.

Первый шаг.

Выбираем начальное допустимое значение, как указано выше. На первом шаге B{\displaystyle B} — единичная матрица, так как базисными переменными являются xs{\displaystyle x_{s}}. cB{\displaystyle c_{B}} — нулевой вектор по тем же причинам.

Второй шаг

Покажем, что в выражении (cBTB−1A−cT)x+(cBTB−1)xs{\displaystyle (c_{B}^{T}B^{-1}A-c^{T})x+(c_{B}^{T}B^{-1})x_{s}} только небазисные переменные имеют ненулевой коэффициент. Заметим, что из выражения Ax+xs=b{\displaystyle Ax+x_{s}=b} базисные переменные однозначно выражаются через небазисные, так как число базисных переменных равно числу уравнений. Пусть x′{\displaystyle x’} — базисные, а x″{\displaystyle x»} — небазисные переменные на данной итерации. Уравнение Ax+xs=b{\displaystyle Ax+x_{s}=b} можно переписать, как Bx′+Dx″=b{\displaystyle Bx’+Dx»=b}. Умножим его на B−1{\displaystyle B^{-1}} слева: x′+B−1Dx″=B−1b{\displaystyle x’+B^{-1}Dx»=B^{-1}b}. Таким образом мы выразили базисные переменные через небазисные, и в выражении B−1Ax+B−1xs{\displaystyle B^{-1}Ax+B^{-1}x_{s}}, эквивалентному левой части равенства, все базисные переменные имеют единичные коэффициенты. Поэтому, если прибавить к равенству Z−cTx=0{\displaystyle Z-c^{T}x=0} равенство cBTB−1Ax+cBTB−1xs{\displaystyle c_{B}^{T}B^{-1}Ax+c_{B}^{T}B^{-1}x_{s}}, то в полученном равенстве все базисные переменные будут иметь нулевой коэффициент — все базисные переменные вида x сократятся, а базисные переменные вида x_s не войдут в выражение cBTB−1xs{\displaystyle c_{B}^{T}B^{-1}x_{s}}.

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z, то необходимо выбрать переменную, которая будет более всех уменьшать выражение

(cBTB−1A−cT)x+(cBTB−1)xs{\displaystyle (c_{B}^{T}B^{-1}A-c^{T})x+(c_{B}^{T}B^{-1})x_{s}}.

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

Третий шаг

Теперь необходимо понять, какая базисная переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

[B−1AB−1][xxs]=B−1b{\displaystyle {\begin{bmatrix}B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}x\\x_{s}\end{bmatrix}}=B^{-1}b}

При фиксированных значениях небазисных переменных система однозначно разрешима относительно базисных, поэтому мы можем определить, какая из базисных переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в базисную, а выходящая из них «выйдет» в небазисные. Теперь перепишем матрицу B и вектор c_B в соответствии с новыми наборами базисных и небазисных переменных, после чего вернёмся ко второму шагу. x»

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

Причины использования[править | править код]

Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «≤», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат.

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

Модификация ограничений[править | править код]

Все ограничения задачи модифицируются согласно следующим правилам:

• ограничения типа «≤» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.
• ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».
• ограничения типа «=» дополняются одной вспомогательной переменной.

Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные. Осторожно: решение, которому соответствует этот базис, не является допустимым.

Различия между дополнительными и вспомогательными переменными[править | править код]

Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:

• дополнительные переменные сообщают, насколько соответствующее им ограничение «недоиспользовано». Значение дополнительной переменной, равное нулю, соответствует равенству значений правых и левых частей ограничения.
• вспомогательные переменные сообщают, насколько данное условие далеко от допустимого (относительно конкретного ограничения). Если значение вспомогательной переменной больше нуля, то данное решение не выполняет определённое ограничение, а значит не является допустимым.

То есть ненулевое значение дополнительной переменной может (но не должно) сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения.

Фазы решения[править | править код]

После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как yi{\displaystyle y_{i}}, i∈{1,…,k}{\displaystyle i\in \left\{1,\dots ,k\right\}}, то вспомогательную функцию определим, как

После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Поскольку все вспомогательные переменные увеличивают значение z′{\displaystyle z’}, в ходе алгоритма они будут поочерёдно выводится из базиса, при этом после каждого перехода новое решение будет всё ближе к множеству допустимых решений.

Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:

• оптимальное значение z′{\displaystyle z’} больше нуля. Это значит, что как минимум одна из вспомогательных переменных осталась в базисе. В таком случае можно сделать вывод, что допустимых решений данной задачи линейного программирования не существует.
• оптимальное значение z′{\displaystyle z’} равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым.

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

В модифицированном методе матрица

[1cBTB−1A−cTcBTB−10B−1AB−1]{\displaystyle {\begin{bmatrix}1&c_{B}^{T}B^{-1}A-c^{T}&c_{B}^{T}B^{-1}\\0&B^{-1}A&B^{-1}\end{bmatrix}}}

не пересчитывается, хранится и пересчитывается только матрица B−1{\displaystyle B^{-1}}. В остальном алгоритм похож на вышеописанный.

1. Вычисляем двойственные переменные d=cBTB−1{\displaystyle d=c_{B}^{T}B^{-1}}

2. Проверка оптимальности. cBTB−1A−cT{\displaystyle c_{B}^{T}B^{-1}A-c^{T}} преобразуется в dTA−cT{\displaystyle d^{T}A-c^{T}}.

Проверка заключается в вычислении dTAn−cn{\displaystyle d^{T}A_{n}-c_{n}} для всех столбцов n∈N{\displaystyle n\in N}. Столбец со значением < 0 можно вводить в базис.

Часто выбирают минимальное значение, но для этого нужно перебрать все столбцы.

Чаще выбирают значение, меньшее некоторого заданного значения −ε{\displaystyle -\varepsilon }

Если такого столбца не обнаружится, за ε{\displaystyle \varepsilon } принимается максимальное найденное абсолютное значение и соответствующий столбец AJ{\displaystyle A_{J}} вводится в базис.

3. Определение выводимого.

Пусть AJ{\displaystyle A_{J}} — вводимый столбец, соответствующий переменной xJ{\displaystyle x_{J}} Базисный план — это решение системы ABp=b{\displaystyle A_{B}p=b} Увеличиваем ABp+ϑAJ=b{\displaystyle A_{B}p+\vartheta A_{J}=b}.

Умножим слева на B−1{\displaystyle B^{-1}}, то есть B−1ABp+ϑB−1AJ=B−1b{\displaystyle B^{-1}A_{B}p+\vartheta B^{-1}A_{J}=B^{-1}b}.

Здесь B−1b{\displaystyle B^{-1}b} — базисный план, q=B−1AJ{\displaystyle q=B^{-1}A_{J}} — разложение вводимого столбца по базису.

Находим максимальное значение ϑ{\displaystyle \vartheta }, при котором все значения не отрицательны. Если ϑ{\displaystyle \vartheta } может быть взято как угодно велико, решение не ограничено. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса.

4. Пересчет опорного(базисного) плана.

Вычисляем новый опорный план по уже приведенной формуле x=p+ϑB−1AJ{\displaystyle x=p+\vartheta B^{-1}A_{J}} с найденным значением ϑ{\displaystyle \vartheta }.

5. Пересчитываем обратную к базисной B−1{\displaystyle B^{-1}}.

Пусть B−1AF{\displaystyle B^{-1}A_{F}} — выводимый столбец.

Матрица B представима в виде [BGAF]{\displaystyle [B_{G}A_{F}]}

где BG{\displaystyle B_{G}} — базисная матрица без выводимого столбца.

После замены столбца базисная матрица будет иметь вид [BGAJ]{\displaystyle [B_{G}A_{J}]}

Нам нужно найти матрицу B1{\displaystyle B_{1}}, такую что

[BG,AJ]B1−1=E{\displaystyle [B_{G},A_{J}]B_{1}^{-1}=E} => [B−1BGB1−1,B−1AJ]=B−1{\displaystyle [B^{-1}B_{G}B_{1}^{-1},B^{-1}A_{J}]=B^{-1}} => [B−1BG,q]B1−1=B−1{\displaystyle [B^{-1}B_{G},q]B_{1}^{-1}=B^{-1}} =>

[Eq′0qf]B1−1=B−1{\displaystyle {\begin{bmatrix}E&q’\\0&q_{f}\end{bmatrix}}B_{1}^{-1}=B^{-1}}

Откуда B1−1=[E−q′/qf01/qf]B−1{\displaystyle B_{1}^{-1}={\begin{bmatrix}E&-q’/q_{f}\\0&1/q_{f}\end{bmatrix}}B^{-1}}

Замечание.

При пересчете матрицы B−1{\displaystyle B^{-1}} накапливаются ошибки округления. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется «повторением».

Мультипликативный вариант симплекс-метода[править | править код]

В мультипликативном варианте матрица B−1{\displaystyle B^{-1}} не хранится, хранятся лишь множители [E−q′/qf01/qf]{\displaystyle {\begin{bmatrix}E&-q’/q_{f}\\0&1/q_{f}\end{bmatrix}}}

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

Во избежание накопления ошибок округления может использоваться LU-разложение матрицы.

При подавляющем числе ограничений типа «неравенство» может быть использован метод переменного базиса. ^[4]

Метод основан на том, что базисная матрица может быть представлена в виде

[AB0AEE]{\displaystyle {\begin{bmatrix}A_{B}&0\\A_{E}&E\end{bmatrix}}}

Обратная к ней имеет вид

[AB−10−AB−1AEE]{\displaystyle {\begin{bmatrix}A_{B}^{-1}&0\\-A_{B}^{-1}A_{E}&E\end{bmatrix}}}

При относительно небольших размерах матрицы AB−1{\displaystyle A_{B}^{-1}} остальная часть матрицы может не храниться.

Таким подходом удается решить задачи с десятками миллионов строк ограничений (например, из теории игр).

Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум (или наоборот) путём транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:

g=∑i=1nbiyi→max{\displaystyle g=\sum _{i=1}^{n}b_{i}y_{i}\to max}

при ограничениях

∑i=1naijyi≤cj{\displaystyle \sum _{i=1}^{n}a_{ij}y_{i}\leq c_{j}}.

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

Если линейная функция одной из задач не ограничена, то другая не имеет решения.

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

Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности.

Симплекс-метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах.^[6][7]

Вычислительная эффективность оценивается обычно при помощи двух параметров:

1) Числа итераций, необходимого для получения решения;

2) Затрат машинного времени.

В результате численных экспериментов получены результаты:

1) Число итераций при решении задач линейного программирования в стандартной форме с M{\displaystyle M} ограничениями и N{\displaystyle N} переменными заключено между M{\displaystyle M} и 3M{\displaystyle 3M}. Среднее число итераций 2M{\displaystyle 2M}. Верхняя граница числа итераций равна 2M+N{\displaystyle 2M+N}.

2) Требуемое машинное время пропорционально M3{\displaystyle M^{3}}.

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

Одной из наиболее трудоёмких процедур в симплекс-методе является поиск вводимого в базис столбца Для лучшей сходимости, казалось бы, нужно выбирать переменную с наилучшей невязкой, но для этого нужен полный просмотр, то есть нужно умножить столбец двойственных переменных (которые иногда называются теневыми ценами) на все столбцы матрицы^[8]. Такой подход хорошо работает для небольших задач, которые решаются вручную. Более того, строгое соблюдение правила выбора максимальной по модулю невязки может оказаться неоптимальным с точки зрения общего количества итераций, необходимых для получения экстремума. Максимальный выигрыш на одной итерации может привести к медленному убыванию значения целевой функции на последующих шагах и, следовательно, замедлить процесс решения задачи^[9].

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

Барьер. Как только невязка переменной будет достаточно сильно отличаться от нуля (превосходит некоторой величины, называемой барьером), переменную вводят в базис. Если все невязки оказались меньше барьера, в качестве вводимой выбирается переменная с наименьшей невязкой, сам же барьер уменьшается по некоторому правилу (например, половина наименьшей невязки). Барьер часто используется со следующим приёмом. Близкий подход описан в книге Муртафа, см. раздел 3.6.2. Частичное оценивание книги^[10].

Циклический просмотр. Поиск вводимой переменной начинается с позиции, следующей за введённой на предыдущей итерации переменной.

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

Назначение весов. Переменным назначаются веса. См. раздел 3.6.4 Метод оценивания в системе DEVEX Муртафа^[12].

Поиск наиболее крутого ребра Гольдфарба и Рида. См. раздел 3.6.5 Метод оценивания с поиском наиболее крутого ребра в книге Муртафа^[13].

Возможны и другие приёмы, такие как правило Заде.

1. ↑ Канторович Л. В. Математические методы организации планирования производства // Издание Ленинградского государственного университета. — Ленинград, 1939.
2. ↑ С. Гасс. Линейное программирование (методы и приложения). — Москва: Государственное издательство физико-математической литературы, 1961. — (Физико-математическая библиотека инженера).
3. ↑ Такая рекомендация часто встречается в учебниках, но не всегда верна. См. раздел #Методы повышения эффективности