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

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

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

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

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

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

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

Алгоритм завершает работу.

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

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

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

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

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

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

Строку p объявляем ведущей. Элемент объявляем ведущим.

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Метод искусственного базиса

Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:

(1)

Характерная особенность задачи (1) – известное базисное допустимое решение

Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (1), т.е. выделить начальное допустимое базисное решение.

Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем.

Вычислительная схема метода искусственного базиса.

Шаг 1.Приводим задачу ЛП к канонической форме

(2)

с неотрицательными правыми частями .

Шаг 2. В каждуюi-ю строку ограничений (2) вводимискусственнуюнеотрицательную переменнуюx_iи строимвспомогательную задачу ЛПвида:

(3)

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

Шаг 3.Для построенной вспомогательной задачи строим симплексную таблицу

	b		…
			…
			…
…	…	…………..
			…

и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.

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

(4)

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

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

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

В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс – метода) искусственная переменнаявыведется из базиса.

В результате получим симплексную таблицу, соответствующую шагу 4.

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