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

Шаг 0Подготовительный этап.Приводим задачу ЛП к специальной форме (9).

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

	B		…		…
L			…		…
			…		…
..	..	…………
			…		…
..	..	…………
			…		…

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

Шаг 2 Проверка на оптимальность.

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

Шаг 3 Проверка на неразрешимость.

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

Шаг 4 Выбор ведущего столбца q.

Среди элементов выбираем максимальный положительный элемент .Этот столбец объявляем ведущим (разрешающим).

Шаг 5 Выбор ведущей строки p.

Среди положительных элементов столбца находим элемент , для которого выполняется равенство:

Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 7Переход к следующей итерации осуществляется возвратом к шагу 2.

Дата добавления: 2015-07-26; просмотров: 156; Нарушение авторских прав

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