2.2 Алгоритм симплекс-метода для задачи на минимум

Ш0: Приводим задачу ЛП к специальной форме.

Ш1: Составляем симплекс-таблицу, соответствующую специальной форме:

	b		…		…
L			…		…
			…		…
.	.	…
			…		…
.	.	…
			…		…

Этой таблице соответствует допустимое базисное решение задачи. Значение целевой функции на этом решении

Ш2: Проверка на оптимальность. Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то , оптимальное решение задачи ЛП найдено: . Алгоритм завершает работу.

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

Ш4: Выбор ведущего столбца q. Среди элементов выбираем максимальный положительный элемент .Этот столбец объявляем ведущим.

Ш5: Выбор ведущей строки p. Среди положительных элементов столбца находим элемент , для которого выполняется равенство: . Строку p объявляем ведущей. Элемент объявляем ведущим.

Ш6: Преобразование симплексной таблицы. Составляем новую симплекс-таблицу, в которой:

а) вместо базисной переменной записываем , вместо небазисной переменной записываем ;

б) ведущий элемент заменяем на обратную величину ;

в) все элементы ведущего столбца (кроме ) умножаем на ;

г) все элементы ведущей строки (кроме ) умножаем на ;

д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».

Из элемента вычитается произведение трех сомножителей:

первый - соответствующий элемент ведущего столбца;

второй - соответствующий элемент ведущей строки;

третий - обратная величина ведущего элемента .

Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».

Ш7: Переход к следующей итерации (на Ш2).

2.3 Алгоритм метода Гомори

Ш1: Симплекс-методом находим оптимальное решение задачи без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В случае алгоритм завершает работу.

Ш2: Пусть оптимальная таблица имеет вид:

	b		…
L			…
	.		…
.	.	…
			…

Если элементы – целые, то оптимальное решение является целочисленным. В этом случае вычисления заканчиваем. Иначе, переходим к следующему шагу.

Ш3: Среди дробных компонент таблицы выбираем элемент с максимальной дробной частью и по строке i составляем дополнительное ограничение:

Здесь - целая часть числа (наибольшее целое число, не превышающее число ).

Ш4: Добавляем построенное ограничение к последней симплекс-таблице и, применяя двойственный симплекс-метод, находим оптимальное решение. Переходим к Ш2.

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

2. На Ш4 двойственный симплекс-метод применяется до тех пор, пока не будет получена оптимальная симплексная таблица (возможно потребуется несколько итераций).

Если на Ш4 в базис вводится переменная дополнительного ограничения , то эта строка вычеркивается из симплексной таблицы (соответствующее ограничение является избыточным).