Двойственный симплекс-метод
Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов Pi , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными). Такую задачу и рассмотрим теперь, предварительно предположив, что единичными являются векторы т. е. рассмотрим задачу, состоящую в определении максимального значения функции
при условиях
и среди чисел имеются отрицательные.
В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) - (56), так как среди его компонент имеются отрицательные числа.
Поскольку векторы - единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа
Таким образом, можно найти:
На основе исходных данных составляют симплекс-таблицу, в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) - (56), поскольку, по предположению, все. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс-таблицы к другой до тех пор, пока из столбца вектора P0 не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)-й строки, т.е. для любого
Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора Po отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое-нибудь одно из них: пусть это число b l . Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор P l . Чтобы определить, какой вектор следует ввести в базис, находим
Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Р r . Число является разрешающим элементов. Переход к новой симплекс-таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р 0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i -й строке симплекс-таблицы в столбце вектора Р 0 стоит отрицательное число b i , а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.
Таким образом, отыскание решения задачи двойственным симплекс-методом включает следующие этапы:
- 1. Находят псевдоплан задачи.
- 2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.
- 3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р 0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m +1)-и строки к соответствующим отрицательным элементам разрешающей строки.
- 4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.
Найти максимальное значение функции
при условиях :
Решение . Запишем исходную задачу линейного программирования в форме основной задачи: найти максимум функции при условиях
Составим для последней задачи двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции
Строим симплекс таблицу:
Итерация 0:
Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент.Продолжаем наши действия
Итерация 1:
Cтраница 1
Двойственный симплекс-метод меняет только порядок нахождения разрешающего элемента, поэтому все особенности (несовместность системы, неограниченность функционала) имеют здесь те же признаки, что и в обычном симплекс-методе. Разберем только преодоление вырождения, так как оно вызывается нулем среди коэффициентов z - строки, а не среди свободных членов.
Двойственный симплекс-метод начинает с двойственно допустимого решения и сохраняет его двойственно допустимым на протяжении всех шагов. Двойственный симплекс-метод реализуется посредством таких же таблиц, что и прямой симплекс-метод. Сначала определяется, какая переменная должна быть выведена из базиса, а затем - какая должна быть введена в базис. Двойственный симплекс-метод для задачи минимизации состоит из следующих шагов.
Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов Р /, составленных из коэффициентов при неизвестных в системе уравнений, имеется т единичных.
Двойственным симплекс-методом с применением модифицированных исключений удобно решать задачи целочисленного программирования (см. гл.
Двойственным симплекс-методом он получен не тремя шагами, а двумя.
Используя двойственный симплекс-метод, находят решение задачи, получающейся в результате присоединения дополнительного ограничения.
Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (32) - (34) в результате присоединения дополнительного ограничения.
Существует еще двойственный симплекс-метод, который предназначен для решения задач с большим числом ограничений или задач, в которых число ограничений возрастает. Кроме того, существуют методы, решающие задачи с изменяющимися параметрами, когда не обязательно прибавляются только строки или только столбцы.
Применение двойственного симплекс-метода к задаче линейного программирования может натолкнуться на сложности, если задача вырождена. Геометрически это означает, что одинаковые значения целевой функции достигаются более чем в одной вершине двойственного многогранника условий.
Использование двойственного симплекс-метода для решения задачи линейного программирования эквивалентно использованию обычного симплексного метода для решения соответствующей двойственной задачп.
Воспользуемся стандартным двойственным симплекс-методом для решения задачи максимизации и получим искомую систему оптимальных цен.
В двойственном симплекс-методе решение задачи выполняется в такой последовательности: сначала добиваются неотрицательности коэффициентов z - строки, а затем-неотрицательности, свободных членов. Требуется обосновать для такого порядка правило выбора разрешающего элемента.
Если используется двойственный симплекс-метод, то нам надо, имея двойственное допустимое у, получить неравенство, которому текущее у не удовлетворяет. Таким образом, вычисления состоят из двух частей. Вторая часть - вспомогательные вычисления (порожденных) неравенств, используемых в первой части. Если воспользоваться текущим Y в графе Н (G, т), у), можно найти кратчайший путь от 0 до g0 длины yt Yo - Тогда неравенство yt То не выполняется. Это неравенство-добавляется к неравенствам первой части. Неравенство необходимо видоизменить, прежде чем записать его в конец двойственной симплексной таблицы.
11.4. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Из результатов предыдущих пунктов следует, что для получения решения исходной задачи можно перейти к двойственной и, используя оценки ее оптимального плана, определить оптимальное решение исходной задачи.
Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с единичным дополнительным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках –двойственная.
Как было показано, при решении прямой задачи на любой итерации разность , т.е. величина -коэффициента при переменной , равна разности между правой и левой частями соответствующего ограничения двойственной задачи. Если при решении прямой задачи с максимизируемой целевой функцией итерация не приводит к оптимальному решению, то по крайней мере для одной переменной и только в оптимуме для всех разность .
Рассматривая это условие с учетом двойственности, можно записать
.
Таким образом, если
,
то .
Это означает, что, когда решение прямой задачи неоптимальное, решение
двойственной задачи недопустимое. С другой стороны
при
.
Отсюда следует, что оптимальному решению прямой задачи соответствует допустимое
решение двойственной задачи.
Это позволило разработать новый метод решения задач линейного программирования, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное» решение (в обычном симплекс-методе сначала находится допустимое , но неоптимальное решение). Новый метод, получивший название двойственного симплекс-метода , обеспечивает выполнение условия оптимальности решения и систематическое «приближение» его к области допустимых решений. Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.
Двойственный симплекс-метод позволяет решать задачи линейного программирования, системы ограничений которых при положительном базисе содержат свободные члены любого знака. Этот метод позволяет уменьшить количество преобразований системы ограничений, а также размера симплексной таблицы. Рассмотрим применение двойственного симплекс-метода на примере.
Пример
. Найти минимум
функции 
при ограничениях
.
Перейдем к канонической форме:
при ограничениях
Начальная симплекс-таблица имеет вид
|
Базисные переменные |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Решение |
|
x 3 x 4 x 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Начальное базисное решение оптимальное, но не допустимое.
Как и обычный симплексный метод, рассматриваемый метод решения основан на использовании условий допустимости и оптимальности.
Условие допустимости . В качестве исключаемой переменной выбирается наибольшая по абсолютной величине отрицательная базисная переменная (при наличии альтернатив выбор делается произвольно). Если все базисные переменные неотрицательные, процесс вычислений заканчивается, так как полученное решение допустимое и оптимальное.
Условие оптимальности . Включаемая в базис переменная выбирается из числа небазисных переменных следующим образом. Вычисляются отношения коэффициентов левой части -уравнения к соответствующим коэффициентам уравнения, ассоциированного с исключаемой переменной. Отношения с положительным или нулевым значением знаменателя не учитываются. В задаче минимизации вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задаче максимизации – отношение, наименьшее по абсолютной величине (при наличии альтернатив выбор делается произвольно). Если знаменатели всех отношений равны нулю или положительные, задача не имеет допустимых решений.
После выбора включаемой в базис и исключаемой переменных для получения следующего решения осуществляется обычная операция преобразования строк симплекс-таблицы.
В рассматриваемом примере исключаемой переменной является . Отношения, вычисленные для определения новой базисной переменной, приведены в следующей таблице:
|
Переменные |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Уравнение x 4 -уравнение |
–2 –4 |
–1 –3 |
|||
|
Отношение |
В качестве включаемой переменной выбирается x 2 . Последующее преобразование строк приводит к новой симплекс-таблице:
|
Базисные переменные |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
Решение |
|
x 3 x 2 x 5 |
–1 –1 |
|||||
Новое решение также оптимальное, но все еще недопустимое. В качестве новой исключаемой переменной выберем (произвольно) x 3 . Определим включаемую переменную.
|
Переменные |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
Уравнение x 4 -уравнение |
|||||
|
отношение |
.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-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
Записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется 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 нет отрицательных чисел, то исходная задача не имеет решения.