Двойной симплекс метод пример решения. Прямая и двойственная задачи и их решение симплекс-методом

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

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

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

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

Описание алгоритма . Задача ЛП должна быть задана в канонической форме (1.1), (1.2) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его . Разложим А 0 по векторам базиса А і1 ,.,А іm в соответствии с (1.9) и найдем псевдоплан прямой задачи.

Исследуем знаки {х i0 } . Если имеет место случай , то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {х i0 } вычисляем коэффициенты разложения векторов A j по векторами сопряженного базиса {х ij } в соответствии с (1.8).

Если для некоторого r такого, что х r0 <0 , все то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.

Если имеет место третий случай (то есть для каждого r такого, что х r0 <0 , по крайней мере одна из компонент х rj <0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную симплекс-таблице ), которая состоит (m+2) строк и (n+1) -го столбца (табл. 6.1).

Столбец В x таблицы, как обычно, содержит векторы {A i } базиса псевдоплана хk , а столбец А 0 - базисные компоненти псевдоплана {х i0 (k)} . Строка (m+1) -индексная, ее заполняют параметрами , являющимися оценками векторов А j :

величина - значение целевой функции при псевдоплане

Итерацию k завершают заполнением главной части таблицы (от первой до (m+1) -й строк).

Таблица 6.1.

C			C 1	C 2	.	C j	.	C n
	B x	A 0	A 1	A 2	.	A j	.	A n
C 1	X 1	X 10	X 11	X 12	.	X 1j	.	X 1n
C 2	X 2	X 20	X 21	X 22	.	X 2j	.	X 2n
.	.	.	.	.	.	.	.	.
C i	X i	X i0	X i1	X i2	.	X ij	.	X in
.	.	.	.	.	.	.	.	.
C m	X m	X m0	X m1	X m2	.	X mj	.	X mn
					.		.
					.		.

На первом этапе (k+1) -и итерации выясняют, имеет ли место первый, второй или третий случай.

В третьем случае переходим ко второму этапу. Сначала определяют вектор А r , который необходимо вывести из базиса. Его индекс r определяют из условия

В строке заполняют лишь те позиции, для которых x rj <0 . Вектор А l , который должен быть введен в базис, находят из условия

Определив направляющую строку r и столбец l , вычисляют элементы главной части таблицы (k+1) -й итерации по рекуррентным соотношениям

(1.15)

Где x ri - направляющий элемент преобразования.

Вычислительная схема алгоритма двойственного симплекс-метода похожа на вычислительную схему симплекс-метода . Аналогичны и формы таблиц.

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

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

Отметим некоторые важные свойства двойственного симплекс-метода .

В отличие от прямого