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

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

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

Кафедра АСОИ

Расчётная задача №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. Реферат на тему Don Quixote The Misadventures Essay Research Paper 3. Реферат Изучение возрастных и межполовых особенностей самооценки трех школьных возрастов 4. Контрольная работа Виды балансовых изменений 5. Реферат на тему Against The Privacy Of Aids Essay Research 6. Реферат на тему Women In The House Of Commons Essay 7. Лекция на тему Теория и технология холодной листовой штамповки 8. Курсовая Сравнительный анализ основных типологий темперамента 9. Курсовая Корь 3 10. Реферат Футуризм в українському мистецтві Bukvasha Правила Контакты copyright bukvasha.net