Применение метода искусственного базиса

Применение метода искусственного базиса рассмотрим на следующем примере[20]:

при ограничениях:

Решение. Составим вспомогательную задачу:

при ограничениях:

Решим вспомогательную задачу симплексным методом:

сi	БП				-1	-1
х1	х2	х3	х4	х5	bi
-1 -1	х4 х5		-1
Dj	-4		-3			-3
-1	х1 х5		½ -2	½	½ -1		½
Dj			-1			-1
	х1 х3		3/2 -2		-1	½
Dj

Решение вспомогательной задачи:

= (0, 0, 1, 0, 0), = 0,

Исходное опорное решение данной задачи:

= (0, 0, 1).

Проверим это решение на оптимальность:

сi	БП		-4
х1	х2	х3	bi
	х1 х3		3/2 -2
Dj

Ответ: = (0, 0, 1), = 2.

Лекция 7. Двойственные задачи линейного программирования

План.

7.1. Двойственная задача для стандартной задачи.

7.2. Основные теоремы двойственности.

7.3. Метод одновременного решения пары двойственных задач.