Алгоритм перехода к новому опорному плану.

1) Выбирается разрешающий столбец из условия: оценка и хотя бы один элемент

2) Выбирается разрешающая строка из условия

для

3) Производится пересчет элементов разрешающей q-ой строки по формулам Это преобразование соответствует элементарной операции над q -ой строкой таблицы.

4) Вычисляются элементы всех остальных строк (при ) по формулам: ,

Это преобразование соответствует элементарным операциям ,

над таблицей.

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

а) для каждого определить номер разрешающей строки по правилу п.2);

б) для всех таких найти наибольшую прибавку - она и определит разрешающий столбец.

Теорема. Если после выполнения очередного шага:

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

2) найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, т.е.

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

3) все оценки окажутся неотрицательными, т.е. для всех то достигнуто оптимальное решение.

Замечание 1. Задача минимизации функции сводится к задаче максимизации функции

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

Пример 3.

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

Решение.Введем дополнительные переменные За-

пишем систему ограничений в виде

(11)

Получим систему ограничений вида (9), приведенную к единичному базису. Запишем функцию в виде (8): Задача линейного программирования представлена в виде (8)-(10), и ее можно решать симплекс-методом.

Запишем исходные данные в виде таблицы.

Базис

	-1

	-2	-3	-2

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

Шаг 1. В последней строке есть три отрицательных оценки: -2, -3, -2. выбираем произвольно одну из них, например, -2 в столбце В этом столбце есть два положительных элемента: 3, 2. Находим Выбираем строку Итак, разрешающий столбец разрешающая строка - В столбце мы должны на первом месте получить единицу, на остальных местах – нули. Выделим разрешающий элемент и выполним элементарные преобразования.

Базис
				0
	-1

=	-2	-3	-2

Базис
	10/3		1/3	1/3	1/3
		-1

=		-2	-3	-2

В столбце «базис» пишем вместо

Базис
	10/3	1/3	1/3	1/3
	37/3	16/3	7/3	1/3
	10/3	19/3	10/3	-2/3
=	20/3	-7/3	-4/3	2/3

Получили, что

Шаг 2. В последней строке есть две отрицательных оценки: Выбираем произвольно одну из них, например, Значит, - разрешающий столбец. В этом столбце есть три положительных элемента: Находим

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

Базис
	10/3	1/3	1/3	1/3
	37/3	16/3	7/3	1/3
	10/3	19/3	10/3	-2/3	1
=	20/3	-7/3	-4/3	2/3

Базис
	10/3	1/3	1/3	1/3	0
	37/3	16/3	7/3	1/3
		19/10		-1/5	3/10
=	20/3	-7/3	-4/3	2/3

В столбце «базис» пишем вместо

Базис
	-3/10	2/5	-1/10
	9/10	4/5	-7/10
	19/10	-1/5	3/10
=	1/5	2/5	2/5

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

то полученное оптимальное решение единственно.

Ответ: ■