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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции , а именно:

На шаге 2::

На шаге 3. Целевая функция является неограниченной сверху на допустимом множестве.

На шаге 4: .

3.4. Пример

Решить задачу, записанную в виде (15).

Составим симплексную таблицу:

L	0	1	2
	3	1	1
	1		1

Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базисаL=0.

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

Выбираем ведущую строку. Для этого находим . Следовательно, ведущая строка соответствует переменной.

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

L	-2	2	-2
	2		-1
	1		1

Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальна. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисеL= -2.

Ведущий столбец здесь – столбец, соответствующий переменной . Ведущая строка – строка, соответствующая переменной. После проведения преобразований получим симплексную таблицу:

L

Еще одна итерация завершена. Переходим к новой итерации.

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