Задача

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

Работа добавлена на сайт bukvasha.ru: 2015-10-29

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

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

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

Кафедра АСОИ

Расчётная задача №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. Реферат на тему Начальный этап Национальной революции май 1925г июнь 1926г
2. Реферат на тему Net Censorship Essay Research Paper Most of
3. Реферат на тему Educated Gentlemen And Missionaries Essay Research Paper
4. Реферат Адамс, Джон президент
5. Реферат Экономическая сущность страхования 5
6. Реферат на тему The Individual Vs Society Essay Research Paper
7. Реферат на тему The Karen Carpenter Story Essay Research Paper
8. Реферат на тему Condoms STD
9. Сочинение на тему Толстой л. н. - Смысл названия романа л. н. толстого
10. Задача Учет материалов на предприятии