Реферат: Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй

Министерствообразования и науки Украины

Днепропетровский Национальный Университет

Факультет электроники, телекоммуникаций и компьютерных систем

Кафедра АСОИ

Расчётная задача №4

«Исследование операций»

г. Днепропетровск

2007г.

Задача

Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй

Прямая задача имеет вид:

Общая постановка двойственной задачи

Двойственная задача – это вспомогательная задача линейного программирования, она формулируется из прямой задачи.

Идея метода основана на связи между решениями прямой и двойственной задачи.

Двойственная задача формируется непосредственно из условий прямой задачи за следующими правилами:

Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации;

Коэффициенты целевой функции прямой задачи С1, С2, …., Сn становятся свободными членами ограничений двойственной задачи;

Свободные члены ограничений прямой задачи b1, b2, ….,bn становятся коэффициентами целевой функции двойственной задачи;

Матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

Если прямая задача является задачей максимизации, то во всех неравенствах двойственной задачи будут стоять знаки ≥, и знаки ≤, если прямая задача является задачей минимизации.

Число ограничений прямой задачи равно числу переменных двойственной задачи.

Прямая задача в канонической форме

Двойственная к ней задача будет иметь вид

Двойственная задача решается симплекс-методом до достижения оптимального решения.

Решение прямой задачи

Все ограничения прямой задачи — это равенства с неотрицательными правыми частями, когда все переменные неотрицательны.

Приведем прямую задачу к стандартному виду:

Подставим значение в целевую функцию:

Таким образом, прямая задача в стандартной форме имеет следующий вид:

Строим симплекс таблицу:

Итерация №1

Базис							Решение	Оценка
	5	-2	1	4	-
	-1	2	1	4	2
	1	1	-1	1	4	4

— ведущий столбец

— ведущая строка

Итерация №2

Базис							Решение	Оценка
	4	1	1	8	2
		1		2	-
			-1	1	2

— ведущий столбец

— ведущая строка

Итерация №3

Базис							Решение	Оценка
	1
	1					-
	1					-

— ведущий столбец

— ведущая строка

Итерация №4

Базис							Решение
				8
			1	-1	1
	1			3
	1			2

Оптимальное решение прямой задачи:

, Х = {2, 3}

Решение двойственной задачи

Двойственная задача имеет вид:

Мы получили двойственную задачу и будем решать ее М-методом. Приведем систему линейных неравенств к стандартному виду, перед этим сделав замену:

,

,

Подставим значения в функцию:

Таким образом, двойственная задача в стандартной форме имеет следующий вид:

Симплекс-таблица, итерация 1

Базис										Решение	Оценка
	-5	5	1	-1	-1	-1	1	1
	2	-2	-2	2	-1	-1	1	2	-

— ведущий столбец

— ведущая строка

Симплекс-таблица, итерация 2

Базис										Решение	Оценка
	-1	1							-
					-1		1

— ведущий столбец

— ведущая строка

Симплекс-таблица, итерация 3

Базис										Решение
	1	1	2	3			-8
	1	1
	-1	1

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

, , ,

Ответ

Оптимальное решение прямой задачи: , X = { 2, 3 }

Для двойственной задачи: , , ,