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

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

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

Кафедра АСОИ

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

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

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

2007г.

Задача

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итерация №1

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

-

-1

2

0

1

0

0

4

2

1

1

0

0

-1

1

4

4

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

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

Итерация №2

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

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

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

Итерация №3

Базис							Решение	Оценка
	0	0	0
	0	0	1
	0	1	0 - 1 0 0 - - ведущий столбец - ведущая строка Итерация №4 Базис Решение 0 0 0 8 0 0 1 -1 1 0 1 0 0 3 1 0 0 0 2 Оптимальное решение прямой задачи: , Х = {2 , 3} Решение двойственной задачи Двойственная задача имеет вид: Мы получили двойственную задачу и будем решать ее М-методом. Приведем систему линейных неравенств к стандартному виду, перед этим сделав замену: , , Подставим значения в функцию: Таким образом, двойственная задача в стандартной форме имеет следующий вид: Симплекс-таблица, итерация 1 Базис Решение Оценка 0 0 -5 5 1 -1 -1 -1 0 1 0 1 2 -2 -2 2 -1 0 -1 0 1 2 - - ведущий столбец - ведущая строка Симплекс-таблица, итерация 2 Базис Решение Оценка 0 0 0 -1 1 0 0 - 0 0 -1 1 - ведущий столбец - ведущая строка Симплекс-таблица, итерация 3 Базис Решение 0 0 1 0 1 2 3 -8 1 1 0 0 0 0 -1 1 Оптимальное решение двойственной задачи: , , , Ответ Оптимальное решение прямой задачи: , X = { 2 , 3 } Для двойственной задачи: , , , 10 1. Реферат Таиланд во Второй мировой войне 2. Реферат Секреты долголетия 3. Реферат Разработка проблемной ситуации гламурная литература как социальное и культурное явление сов 4. Реферат на тему Gulliver Essay Research Paper Houyhnhnms and YahoosAnimal 5. Курсовая Підприємництво суть, субєкти, форми 6. Реферат на тему Jonathan SwiftS A Modest Proposal Essay Research 7. Реферат на тему Holocaust Paper Essay Research Paper HolocaustPrejudices We 8. Реферат Автоматизированные технологические комплексы 9. Реферат на тему Computer Essay Research Paper DEVELOPMENT OF COMPUTERS 10. Курсовая Характеристика основных выгод и проблем связанных с развитием туризма Туристский продукт Алтайского Bukvasha Правила Контакты