Двойственный симплекс. Пример решения прямой и двойственной задачи симплекс методом
.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x 1 + x 2 при следующих условиях-ограничений.
- 5x 1 - 6x 2 ≤-1
- 15x 1 ≤-1
- 7x 1 - 12x 2 ≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме
).
В 1-м неравенстве смысла (≤) вводим базисную переменную x 3 . В 2-м неравенстве смысла (≤) вводим базисную переменную x 4 . В 3-м неравенстве смысла (≤) вводим базисную переменную x 5 .
-5x 1 -6x 2 + 1x 3 + 0x 4 + 0x 5 = -1
-15x 1 + 0x 2 + 0x 3 + 1x 4 + 0x 5 = -1
-7x 1 -12x 2 + 0x 3 + 0x 4 + 1x 5 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| A= | -5 | -6 | 1 | 0 | 0 |
| -15 | 0 | 0 | 1 | 0 | |
| -7 | -12 | 0 | 0 | 1 |
Решим систему уравнений относительно базисных переменных:
x 3 , x 4 , x 5 ,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,-1,-1,-1)
Базисное решение называется допустимым, если оно неотрицательно.
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| -1 | -5 | -6 | 1 | 0 | 0 | |
| -1 | -15 | 0 | 0 | 1 | 0 | |
| -1 | -7 | -12 | 0 | 0 | 1 | |
| 0 | -1 | -1 | 0 | 0 | 0 |
.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
.
Ведущей будет 1-ая строка, а переменную x 3 следует вывести из базиса.
.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-6).
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| -1 | -5 | -6 | 1 | 0 | 0 | |
| -1 | -15 | 0 | 0 | 1 | 0 | |
| -1 | -7 | -12 | 0 | 0 | 1 | |
| 0 | -1 | -1 | 0 | 0 | 0 | |
| 0 | -1: (-5) = 1 / 5 | -1: (-6) = 1 / 6 | - | - | - |
4. Пересчет симплекс-таблицы .
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| 1 / 6 | 5 / 6 | 1 | -1 / 6 | 0 | 0 | |
| -1 | -15 | 0 | 0 | 1 | 0 | |
| 1 | 3 | 0 | -2 | 0 | 1 | |
| 1 / 6 | -1 / 6 | 0 | -1 / 6 | 0 | 0 |
| x 1 | x 2 | x 3 | x 4 | x 5 | |
| 5 / 6: 1 | 1: 1 | -1 / 6: 1 | 0: 1 | 0: 1 | |
| 1-(1 / 6 0):1 | -15-(5 / 6 0):1 | 0-(1 0):1 | 0-(-1 / 6 0):1 | 1-(0 0):1 | 0-(0 0):1 |
| 3-(5 / 6 0):1 | 0-(1 0):1 | -2-(-1 / 6 0):1 | 0-(0 0):1 | 1-(0 0):1 | |
| 1 / 6 -(1 / 6 0):1 | -1 / 6 -(5 / 6 0):1 | 0-(1 0):1 | -1 / 6 -(-1 / 6 0):1 | 0-(0 0):1 | 0-(0 0):1 |
1. Проверка критерия оптимальности .
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной .
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 2-ая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной .
Минимальное значение θ соответствует 1-му столбцу, т.е. переменную x 1 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-15).
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| 1 / 6 | 5 / 6 | 1 | -1 / 6 | 0 | 0 | |
| -1 | -15 | 0 | 0 | 1 | 0 | |
| 1 | 3 | 0 | -2 | 0 | 1 | |
| 1 / 6 | -1 / 6 | 0 | -1 / 6 | 0 | 0 | |
| 0 | -1 / 6: (-15) = 1 / 90 | - | - | - | - |
4. Пересчет симплекс-таблицы .
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| 1 / 9 | 0 | 1 | -1 / 6 | 1 / 18 | 0 | |
| 1 / 15 | 1 | 0 | 0 | -1 / 15 | 0 | |
| 4 / 5 | 0 | 0 | -2 | 1 / 5 | 1 | |
| 8 / 45 | 0 | 0 | -1 / 6 | -1 / 90 | 0 |
Представим расчет каждого элемента в виде таблицы:
| x 1 | x 2 | x 3 | x 4 | x 5 | |
| 1 / 9 -(1 / 15 0):1 | 0-(1 0):1 | 1-(0 0):1 | -1 / 6 -(0 0):1 | 1 / 18 -(-1 / 15 0):1 | 0-(0 0):1 |
| 1: 1 | 0: 1 | 0: 1 | -1 / 15: 1 | 0: 1 | |
| 4 / 5 -(1 / 15 0):1 | 0-(1 0):1 | 0-(0 0):1 | -2-(0 0):1 | 1 / 5 -(-1 / 15 0):1 | 1-(0 0):1 |
| 8 / 45 -(1 / 15 0):1 | 0-(1 0):1 | 0-(0 0):1 | -1 / 6 -(0 0):1 | -1 / 90 -(-1 / 15 0):1 | 0-(0 0):1 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности .
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| B | x 1 | x 2 | x 3 | x 4 | x 5 | |
| 1 / 9 | 0 | 1 | -1 / 6 | 1 / 18 | 0 | |
| 1 / 15 | 1 | 0 | 0 | -1 / 15 | 0 | |
| 4 / 5 | 0 | 0 | -2 | 1 / 5 | 1 | |
| 8 / 45 | 0 | 0 | -1 / 6 | -1 / 90 | 0 |
x 1 = 1 / 15
x 2 = 1 / 9
F(X) = 1 1 / 9 + 1 1 / 15 = 8 / 45
Рассмотрим симплекс -метод
для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
- Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0 , т.к. целевая функция не должна при этом менять свой экономический смысл.
- Выписываются вектора P i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
- После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение . Коэффициенты целевой функции записывают с противоположным знаком.
- Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р 0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
- Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0 . Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
- Так поступают до тех пор, пока в f – строке все элементы не станут положительными.
Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:
Приводим задачу к каноническому виду:
Составляем вектора:
Заполняем симплекс – таблицу:
:
Пересчитаем первый элемент вектора Р 0
, для чего составляем прямоугольник из чисел: и получаем: 
.
Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:
В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:
Отсутствие отрицательных элементов в f
– строке означает, что найден оптимальный план
:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
- Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
- Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
- Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.
Решение линейного программирования на заказ
Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на
Записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс–метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы т. е. рассмотрим задачу, состоящую в определении максимального значения функции
(54)
при условиях
(55)
(56)
где
и среди чисел имеются отрицательные .
В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа.
Поскольку векторы –
единичные,
каждый из векторов можно представить в виде
линейной комбинации данных векторов, причем коэффициентами разложения
векторов по векторам служат числа
Т
аким образом, можно найти
Определение 14.
Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого
Теорема 11.
Если в псевдоплане , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) – (56) вообще не имеет планов.
Теорема 12.
Если в псевдоплане , определяемом базисом , имеются отрицательные числа такие, что для любого из них существуют числа a ij <0, то можно перейти к новому псевдоплану , при котором значение целевой функции задачи (54) – (56) не уменьшится.
Сформулированные теоремы дают основание для построения алгоритма двойственного симплекс-метода.
Итак, продолжим рассмотрение задачи (54) – (56). Пусть – псевдоплан этой задачи. На основе исходных данных составляют симплекс-таблицу (табл. 15), в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) – (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого
Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число b l . Выбор этого числа определяет , исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P l . Чтобы определить, какой вектор следует ввести в базис, находим , где
Пусть это минимальное значение принимается при тогда в базис вводят вектор Р r . Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i –й строке симплекс–таблицы (табл. 15) в столбце вектора Р 0 стоит отрицательное число b i , а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.
Таким образом, отыскание решения задачи (54) – (56) двойственным симплекс-методом включает следующие этапы:
1. Находят псевдоплан задачи.
2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален , то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану .
3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р 0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m +1)–и строки к соответствующим отрицательным элементам разрешающей строки.
4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.
Таблица 15
Пример 17.
Найти максимальное значение функции при условиях
Решение. Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях
Умножим второе и третье уравнения системы ограничений последней задачи на –1 и перейдем к следующей задаче: найти максимум функции
(57)
при условиях
(58)
(59)
Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции
(60)
при условиях
(61)
(62)
Выбрав в качестве базиса векторы и , составим симплексную таблицу (табл. 16) для исходной задачи (57) – (59).
Таблица 16
|
i |
Базис |
С б |
Р 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 5 |
–4 –6 |
–1 –1 |
–2 |
Из этой таблицы видим, что планом двойственной задачи (57) – (59) является . При этом плане Т ак как в столбце вектора Р 0 таблица 16 имеются два отрицательных числа (–4 и –6), а в 4–й строке отрицательных чисел нет, то в соответствии с алгоритмом двойственного симплекс–метода переходим к новой симплекс–таблице. (В данном случае это можно сделать, так как в строках векторов Р 4 и Р 5 имеются отрицательные числа. Если бы они отсутствовали, то задача была бы неразрешима. Вектор, исключаемый из базиса, определяется наибольшим по абсолютной величине отрицательным числом, стоящим в столбце вектора Р 0 . В данном случае это число –6. Следовательно, из базиса исключаем вектор Р 5 . Чтобы определить, какой вектор необходимо ввести в базис, находим где Имеем
Значит, в базис вводим вектор P 2 . Переходим к новой симп екс–таблице (табл. 17).
Таблица 17
|
i |
Базис |
С б |
Р 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 2 |
–7 |
–3/2 |
–1/2 |
Из этой таблицы видно, что получен новый план двойственной задачи П ри этом плане значение ее линейной формы равно Таким образом, с помощью алгоритма двойственного симплекс–метода произведен упорядоченный переход от одного плана двойственной задачи к другому.
Так как в столбце вектора Р 0 таблицы 17 стоит отрицательное число –7, то рассмотрим элементы 2–й строки. Среди этих чисел есть одно отрицательное –3/2. Если бы такое число отсутствовало, то исходная задача была бы неразрешима. В данном случае переходим к новой симплекс-таблице (табл. 18).
Таблица 18
|
i |
Базис |
С б |
Р 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 1 p 2 |
14/3 32/3 |
–2/3 |
–1/3 –1/3 |
Как видно из таблицы 18, найдены
оптимальные планы исходной и двойственной задач. Ими
являются 
и . При этих планах значения
линейных форм исходной и двойственной задач равны между собой: 
Пример 18.
Найти максимальное значение функции 
при
условиях
Решение. Умножая первое и третье уравнения системы ограничений задачи на –1, в результате приходим к задаче нахождения максимального значения функции при условиях
Взяв в качестве базиса векторы Р 3 , Р 4 и Р 5 , составляем симплекс-таблицу (табл. 19).
Таблица 19
|
i |
Базис |
С б |
Р 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 5 |
–12 –18 |
–3 |
–1 |
В 4-й строке таблице 19 нет отрицательных чисел. Следовательно, если бы в столбце вектора Р 0 не было отрицательных чисел, то в таблице 19 был бы записан оптимальный план. Поскольку в указанном столбце отрицательные числа имеются и такие же числа содержатся в соответствующих строках, переходим к новой симплекс–таблице (таблица 20). Для этого исключим из базиса вектор Р 5 и введем в базис вектор Р 1 . В результате получим псевдоплан X=(6;0;-24;4)
Таблица 20
|
i |
Базис |
С б |
Р 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 1 |
–24 |
–2/3 |
–1/3 |
Так как в строке вектора Р 3 нет отрицательных чисел, то исходная задача не имеет решения.
Cтраница 1
Двойственный симплекс-метод меняет только порядок нахождения разрешающего элемента, поэтому все особенности (несовместность системы, неограниченность функционала) имеют здесь те же признаки, что и в обычном симплекс-методе. Разберем только преодоление вырождения, так как оно вызывается нулем среди коэффициентов z - строки, а не среди свободных членов.
Двойственный симплекс-метод начинает с двойственно допустимого решения и сохраняет его двойственно допустимым на протяжении всех шагов. Двойственный симплекс-метод реализуется посредством таких же таблиц, что и прямой симплекс-метод. Сначала определяется, какая переменная должна быть выведена из базиса, а затем - какая должна быть введена в базис. Двойственный симплекс-метод для задачи минимизации состоит из следующих шагов.
Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов Р /, составленных из коэффициентов при неизвестных в системе уравнений, имеется т единичных.
Двойственным симплекс-методом с применением модифицированных исключений удобно решать задачи целочисленного программирования (см. гл.
Двойственным симплекс-методом он получен не тремя шагами, а двумя.
Используя двойственный симплекс-метод, находят решение задачи, получающейся в результате присоединения дополнительного ограничения.
Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (32) - (34) в результате присоединения дополнительного ограничения.
Существует еще двойственный симплекс-метод, который предназначен для решения задач с большим числом ограничений или задач, в которых число ограничений возрастает. Кроме того, существуют методы, решающие задачи с изменяющимися параметрами, когда не обязательно прибавляются только строки или только столбцы.
Применение двойственного симплекс-метода к задаче линейного программирования может натолкнуться на сложности, если задача вырождена. Геометрически это означает, что одинаковые значения целевой функции достигаются более чем в одной вершине двойственного многогранника условий.
Использование двойственного симплекс-метода для решения задачи линейного программирования эквивалентно использованию обычного симплексного метода для решения соответствующей двойственной задачп.
Воспользуемся стандартным двойственным симплекс-методом для решения задачи максимизации и получим искомую систему оптимальных цен.
В двойственном симплекс-методе решение задачи выполняется в такой последовательности: сначала добиваются неотрицательности коэффициентов z - строки, а затем-неотрицательности, свободных членов. Требуется обосновать для такого порядка правило выбора разрешающего элемента.
Если используется двойственный симплекс-метод, то нам надо, имея двойственное допустимое у, получить неравенство, которому текущее у не удовлетворяет. Таким образом, вычисления состоят из двух частей. Вторая часть - вспомогательные вычисления (порожденных) неравенств, используемых в первой части. Если воспользоваться текущим Y в графе Н (G, т), у), можно найти кратчайший путь от 0 до g0 длины yt Yo - Тогда неравенство yt То не выполняется. Это неравенство-добавляется к неравенствам первой части. Неравенство необходимо видоизменить, прежде чем записать его в конец двойственной симплексной таблицы.
Заключается в построении оптимального недопустимого плана с последующим преобразованием его в допустимый, не нарушая оптимальности.
Алгоритм двойственного симплекс-метода
1) выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;
2) выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;
3) пересчитывают симплексную таблицу по правилам обычного симплекс-метода;
4) решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.
Замечания
1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.
2. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.
Пример . Решить задачу, используя алгоритм двойственного симплекс-метода
L = x 1 + 4x 2 → min
Составляем исходную симплексную таблицу.
| Баз. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Св. |
| x 4 | -2 | -3 | 1 | 0 | 0 | 0 | -20 | |
| x 5 | -5 | 1 | -2 | 0 | 1 | 0 | 0 | -12 |
| x 6 | 1 | 2 | -1 | 0 | 0 | 1 | 0 | 2 |
| x 7 | -1 | 4 | -2 | 0 | 0 | 0 | 1 | 1 |
| L | -1 | -4 | -1 | 0 | 0 | 0 | 0 | 0 |
Отсутствие в L строке положительных оценок свидетельствует об оптимальности исходного решения, а наличие в столбце свободных членов отрицательных элементов – о его недопустимости. Согласно алгоритму двойственного симплекс-метода выбираем разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных элементов. В нашем примере разрешающая строка – первая. Разрешающий столбец выбирается в соответствии с правилом, изложенным в пункте 2 схемы алгоритма. Разрешающий элемент равен (-4). После пересчета получаем следующую таблицу
| Баз. | х 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 | Св. |
| х 3 | 1 | 0 | 0 | 0 | 5 | |||
| х 5 | 0 | 1 | 0 | 0 | -2 | |||
| х 6 | 0 | 0 | 1 | 0 | 7 | |||
| х 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 | 5 |
Аналогично рассуждая, получим еще одну таблицу
| Баз. | х 1 | х 2 | х 3 | х 4 | х 5 | х 6 | х 7 | Св. |
| х 3 | 0 | 1 | 0 | 0 | ||||
| х 1 | 1 | 0 | 0 | 0 | ||||
| х 6 | 0 | 0 | 1 | 0 | ||||
| х 7 | 0 | 0 | 0 | 0 | 1 | 11 | ||
| L | 0 | 0 | 0 | 0 |
Отсутствие в столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение , 
.
Замечание
. Если решение ЗЛП и недопустимо и неоптимально, то сначала получаем допустимое решение, используя алгоритм двойственного симплекс-метода, а затем по правилам обычного симплекс-метода получаем оптимальное решение.
Пример
.
L = 5x 1 – x 2 – x 3 → max
или 
Составляем исходную симплекс-таблицу
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Св. | |
| x 4 | 0 | -2 | 1 | 0 | 0 | 0 | -9 | |
| x 5 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | -1 |
| x 6 | -1 | -1 | 3 | 0 | 0 | 1 | 0 | -8 |
| x 7 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | -5 | 1 | 4 | 0 | 0 | 0 | 0 | 0 |
Решение недопустимо, так как в столбце свободных членов есть отрицательные элементы и неоптимально, так как в строке L есть отрицательная оценка (-5). Получаем сначала допустимое решение, используя алгоритм двойственного симплекс-метода. После пересчета получаем следующую симплексную таблицу
| Баз. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Св. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| x 5 | 1 | 0 | 2 | -1 | 1 | 0 | 0 | 8 |
| x 6 | -1 | 0 | 5 | -1 | 0 | 1 | 0 | 1 |
| x 7 | 0 | -1 | 0 | 0 | 0 | 1 | 4 | |
| L | -5 | 0 | 2 | 1 | 0 | 0 | 0 | -9 |
В столбце свободных членов нет отрицательных элементов, но в строке L есть отрицательная оценка (-5), значит решение допустимо, неоптимально.
Используем обычный симплекс-метод и получаем следующие таблицы
| Баз. | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | Св. |
| x 2 | 0 | 1 | 2 | -1 | 0 | 0 | 0 | 9 |
| х 5 | 0 | 0 | 3 | -1 | 1 | 0 | -1 | 4 |
| х 6 | 0 | 0 | -1 | 0 | 1 | 1 | 5 | |
| x 1 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 4 |
| L | 0 | 0 | -3 | 1 | 0 | 0 | 5 | 11 |