Табличная форма симплекс – метода

Объем записей можно значительно уменьшить, если пользоваться табличным методом. Таблица состоит из частей, отвечающим отдельным итерациям.

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

Рассмотрим тот же пример:

Симплекс – таблица будет иметь вид:

Номер итерации	F и базовая переменная	Значения F и базовой переменной	Переменные	Отношения
	F		-0,5	-2
			-1				-1
		-1	2
	F		-1,5
		1,5
		0,5				-0,5
		-0,5				0,5	-8
	F						0,5

По блок – схеме:

1) Значения третьего столбца неотрицательны, значит, исходное базисное решение является допустимым

2) Решение оптимально, т. к. в первой строке имеются отрицательные коэффициенты

3) Максимальное по абсолютной величине отрицательное значение в первой строке F определяет свободную переменную, переводимую в базисные

4) Для определения базисной переменной, переводимой в свободные, вычисляем отношения свободных членов (3 – го столбца) к коэффициентам при свободной переменной, переводимой в базисные ( ). Выбирается минимальное неотрицательное отношение

5) Смена базиса (формируется часть таблицы для следующей итерации).

Назовем строку, соответствующую базисной переменной, переводимой в свободные, ведущей строкой.

Ведущий столбец– столбец, соответствующий свободной переменной, переводимой в базисные.

На их пересечении находится элемент, называемый ведущим элементом,который обозначен звездочкой.

Смена базиса состоит из двух этапов.

Напервом этапе все элементы ведущей строки делятся на ведущий элемент (нормировка ведущей строки).

Во второй столбец полученной строки ставится переменная, переводимая из свободных в базисные.

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

В результате все элементы ведущего столбца становятся равными нулю, кроме ведущего элемента.

Основное достоинствотабличной формы – удобство для реализации .

Дата добавления: 2014-08-04; просмотров: 334; Нарушение авторских прав

Мы поможем в написании ваших работ!