Записати задачу двоїсту до даної вирішити одну з пари завдань і відшукати оптимальне рішення

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.


Нажми чтобы узнать.
скачати

Міністерство освіти і науки України

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

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

Кафедра АСОІ

Розрахункова задача № 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


Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Завдання
73.9кб. | скачати


Схожі роботи:
Розробка технічного рішення щодо утворення пари локальних обчислювальних мереж
Рішення завдань з економічного аналізу
Методи рішення завдань на побудову
Приклади рішення економетричних завдань
Методи рішення логістичних завдань
Педагогічна діяльність Рішення педагогічних завдань
Евристичні методи рішення творчих завдань
Рішення практичних завдань в СУБД Access
Економічна статистика Росії рішення завдань
© Усі права захищені
написати до нас
Рейтинг@Mail.ru