Контрольные работы по методам оптимизации (стр. 3 )

Решение задачи ЛП симплекс - методом искусственного базиса

В каноническом виде задача выглядит так:

Так как нет единичной базисной матрицы , то применяем симплекс - метод искусственного базиса. В первом равенстве и во втором равенстве нет переменной, которую можно взять за базисную, поэтому вводим переменную , а во втором равенстве вводим переменную .

Получим задачу:

1.  Составим симплекс – таблицу:

	4	2	1	1	1	0	0
	2	1	-1	-1	0	-1	1

2. Высчитываем вектор по формулам:

	4	2	1	1	1	0	0
	2	1	-1	-1	0	-1	1
	0	0	0	0	0	0	-1
	-2	-1	1	1	0	1	0

3.  Определяем минимальную из оценок . Так как минимальное значение оценка . . В этом случае переменная входит в базис.

	4	2	1	1	1	0	0	2
	2	1	-1	-1	0	-1	1	2
	-2	-1	1	1	0	1	0

4.  Для всех положительных , определяем отношение . Минимальное значение . Возьмем - номер минимального отношения . В этом случае, переменная выходит из базиса.

	4	2	1	1	1	0	0
	2	1	-1	-1	0	-1	1
	-2	-1	1	1	0	1	0

5. Выполняем преобразования симплекс – таблицы: в ведущем столбце на месте ведущего элемента должна быть 1, а на остальных местах ведущего столбца 0. Используем формулы:

	0	0	3	3	1	2	-2
	2	1	-1	-1	0	-1	1
	0	0	0	0	0	0	1

6. Т. к. все , а значение функционала равно 0, то используя получившийся базис приступим у решению исходной задачи.

Составим симплекс – таблицу для исходной задачи:

	0	0	3	3	1	2
	2	1	-1	-1	0	-1
	0	1	-4	5	0	0
	2	0	3	-6	0	-1

Далее определяем ведущий столбец и ведущую строку, и работаем по алгоритму, как описано выше.

	0	0	3	3	1	2	3
	2	1	-1	-1	0	-1
	2	0	3	-6	0	-1
	0	0	1	1	1/3	2/3
	2	1	0	0	1/3	-1/3
	2	0	9	0	2	3

Т. к. все , то получено оптимальное решение.

; ; .

Значение функционала равно .