Пример. Перейти к исследованию новой симплексной таблицы (новая итерация)

Перейти к исследованию новой симплексной таблицы (новая итерация).

Преобразование симплексной таблицы.

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

Проверка оптимальности или нахождение ведущего столбца.

§ Если все коэффициенты в строке z-уравнения при небазисных переменных неотрицательны (коэффициенты в z-уравнении), то текущее базисное решение является оптимальным (условие оптимальности).

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

.

Столбец под номером s называется ведущим столбцом симплексной таблицы.

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

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

.

Строка под номером r называется ведущей строкой, а элемент a_rs>0 –ведущим элементом (условие допустимости).

§ Используя эквивалентные преобразования таблицы (процедуру Гаусса) пересчитываем таблицу так, чтобы ведущий элемент новой симплекс-таблицы стал равным 1, а все остальные элементы ведущего столбца – равными 0.

Обозначим верхним индексом 1 элементы новой симплексной таблицы. Тогда формулы пересчета коэффициентов примут вид:

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

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

Таким образом, последовательность вычислений (итераций) следующая:

Шаг 0. Находится начальное допустимое решение.

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

Шаг 2. На основе условия допустимости выбирается исключаемая переменная.

Шаг 3. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 1.

Итерации симплекс-метода для задачи Reddy Mikks (ведущие строки и столбцы выделены цветом)

Базис	z	x1	x2	S1	S2	S3	S4	Решение
z		-5	-4
s1
S2
S3		-1
S4

Базис	z	x1	x2	S1	S2	S3	S4	Решение
z			-2/3	5/6
X1			2/3	1/6
S2			4/3	-1/6
S3			5/3	1/6
S4

Базис	z	x1	x2	S1	S2	S3	S4	Решение
z				3/4	1/2
X1				1/4	-1/2
x2				-1/8	3/4			3/2
S3				3/8	-5/4			5/2
S4				1/8	-3/4			1/2

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

Обратите внимание, что последовательность базисных решений состоит в том, что итерационный процесс симплекс-метода начался в угловой точке А, затем, пройдя через точку В, закончился в крайней точке С — точке оптимума. Итерации соответствуют смежным крайним точкам границы области допустимых решений.

	z	x1	x2	s1	s2
z		-5	-3
s1
s2

	z	x1	x2	s1	s2
z			-1
s1			3/5		-1/5
x1			2/5		1/5

	z	x1	x2	s1	s2
z	40/3			5/3	2/3
x2	10/3			5/3	-1/3
x1	2/3			-2/3	1/3

Ответ:

ТЕМА 4. Двойственность в задачах линейного программирования

Дата добавления: 2014-12-29