1. ћетод последовательного уточнени¤ оценок

»ногда называют еще двойственным симплекс-методом. –анее говорилось, что одновременно с решением пр¤мой задачи, решаетс¤ и двойственна¤ задача. ≈сли проследить за получающимис¤ преобразовани¤ми двойственной таблицы и переменных и , записав таблицу дл¤ двойственной задачи в обычном виде, то получим описание нового метода Ц метода последовательного уточнени¤ оценок.

ѕусть дана задача:

—имплексна¤ таблица, построенна¤ дл¤ данной задачи, будет иметь вид:

		Е.		Е.		1
=		Е.		Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.
=		Е.		Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.
=		Е.		Е.
=		Е.		Е.		0

¬ методе последовательного уточнени¤ оценок сначала избавл¤ютс¤ от отрицательности в -строке (получают псевдоплан), а затем, перебира¤ псевдопланы, ищут оптимальный план (первый найденный опорный).

ѕравило выбора разрешающего элемента дл¤ избавлени¤ от отрица­тельности в -строке.

1. ≈сли все коэффициенты -строки неотрицательны, то 0 ¤вл¤етс¤ оценкой снизу дл¤ целевой функции и можно переходить к отысканию оптимального решени¤. »наче выбираем некоторый и рассматриваем -й столбец.

2. Ќаходим в -м столбце какой-нибудь из отрицательных элементов, например, . “огда строку с номером , содержащую ,  выбираем в качестве разрешающей строки. ≈сли все коэффициенты -го столбца неотрицательны, то либо неограничена снизу (), либо система ограничений противоречива. (»з противоречивости двойственной не следует неограниченность пр¤мой задачи).

3. Ќаходим неотрицательные отношени¤ коэффициентов -строки к коэффициентам разрешающей (-й) строки. ¬ качестве разрешающего берем тот элемент разрешающей -й строки, дл¤ которого это отношение положительно и минимально, т.е. выбираем некоторый коэффициент , дл¤ которого  

.

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

		Е.			Е.		1
=		Е.			Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.
=		Е.			Е.
=		Е.			Е.
Е.	Е.	Е.	Е.	Е.	Е.	Е.	Е.
=		Е.			Е.
=		Е.			Е.

≈сли все Ц неотрицательны, то таблица соответствует оптималь­ному решению и , иначе, Ц оценка снизу дл¤ .

ѕравило выбора разрешающего элемента при поиске оптимального решени¤.

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

2. ¬ качестве разрешающего выбираем тот положительный коэффициент строки , дл¤ которого

.

≈сли в строке с номером нет положительных коэффициентов, то ограничени¤ задачи противоречивы.

ѕосле выбора разрешающего элемента делаем шаг обыкновенного жорданова исключени¤.

ѕосле конечного числа шагов либо найдем оптимальное решение, либо можно убедимс¤ в противоречивости ограничений задачи.

«амечание: ≈сли в симплекс-методе мы приближаемс¤ к оптимальному решению при поиске минимума сверху, передвига¤сь по опорным планам, то в методе последовательного уточнени¤ оценок при поиске минимума к оптимальному решению приближаемс¤ снизу, причем промежуточные планы (псевдопланы) не ¤вл¤ютс¤ опорными (лежат вне многогранника решений). ѕервое же допустимое решение (опорный план) будет оптимальным.