По дисципліні «дослідження операцій» icon

По дисципліні «дослідження операцій»




НазваПо дисципліні «дослідження операцій»
Сторінка4/5
Дата26.06.2012
Розмір0.83 Mb.
ТипКонспект
1   2   3   4   5

^ 4. РІШЕННЯ ЗАДАЧІ ПРО КОМІВОЯЖЕРА МЕТОДОМ гілок І ГРАНИЦЬ

Постановка задачі

Є n міст (А1, А2, А3,... Аn), задана матриця відстаней між містами . Необхідно відшукати такий найкоротший замкнутий маршрут (цикл), що проходить один і тільки один раз через кожне місто, при якому мінімізується сумарна довжина шляху .

^ Математична модель задачі

У загальному випадку нехай розглядаються n пунктів, тоді вводиться n2 альтернативних змінних xij. Причому відповідна змінна буде дорівнювати 0, якщо перехід з i в j пункт не входить у розглянутий маршрут. І, мабуть, що така змінна буде дорівнювати 1, якщо зазначений перехід можливий. Тоді умова прибуття в кожен пункт і виходу з кожного пункту тільки по одному разу виражається співвідношенням виду:

(4.1)

(4.2)

Для забезпечення безперервності маршруту вводять додатково n змінних і при цьому формують n2 додаткових обмежень:

;

. (4.3)

У такому випадку сумарна довжина маршруту, який необхідно мінімізувати, буде записуватися в наступному вигляді:

. (4.4)

Для розв’язування задачі (4.1)–(4.4) існує багато різних методів. Однак, одним з найбільш, простих і зручних є метод гілок і границь.


Особливості методу гілок і границь для розв’язування задачі про комівояжера

Для методу гілок і границь існують різні підходи його реалізації. Однак загальною є ідея розбивки (розгалуження) множини припустимих значень ( на дерево підмножин (дерево розв’язків). При цьому процес розгалуження, заснований на побудові оцінок знизу (нижньої границі) для цільової функції на деякій множині розв’язків.

Для кожної задачі, з урахуванням її специфіки, розробляються наступні підходи:

1) Правило розгалуження.

2) Спосіб обчислення оцінок (функція цілі).

3) Способи знаходження розв’язків.

Отже, основною особливістю методу гілок і границь є те, що він дозволяє організувати повну процедуру перебору відповідних планів задачі.

Розглянемо зазначений підхід детально.

Нехай на деякій множині  необхідно мінімізувати функцію . Тоді цю процедуру реалізують у такий спосіб:  розбивають на ряд непересічних підмножин і потім вибирається та підмножина, наприклад 1, на якій функція  досягає свого найменшого значення. Далі розбивають 1 на ряд підмножин і вибирають ту з них, наприклад 2, на якій функція  досягає свого мінімального значення. Далі 2 розбивають на кілька непересічних частин. Такий процес розгалуження реалізують до одноелементної множини. Така одноелементна множина називається рекордом.

Практичну реалізацію методу гілок і границь для задачі про комівояжера зручніше за все проводити на тлі конкретному прикладі.

Приклад. Спекла бабка колобок і поставила його остигати на віконце. І вирішив колобок, що поки він стигне, він може оббігти ліс, подивитися на лісових жителів і знову повернутися. Сказано-зроблено. Зстрибнув він з віконця й покотився в ліс. Допоможіть колобку знайти найкоротший шлях його руху в лісі, якщо відстань між норами й будинком діда й баби дані в наступній таблиці:




Дід і баба

Заєць

Вовк

Ведмідь

Лисиця

Дід і баба

0

6

4

5

2

Заєць

6

0

3

3,5

4,5

Вовк

4

3

0

5,5

5

Ведмідь

5

3,5

5,5

0

2

Лисиця

2

4,5

5

2

0


^ Математична модель задачі: для рішення задачі привласнимо кожному пункту задачі певний номер: дід і баба = 1, заєць =2, вовк = 3, ведмідь = 4, лисиця = 5.

Отже, загальне число пунктів n = 5. Тоді, на першому етапі можна записати функцію цілі задачі



Задача вирішується в рамках наступних обмежень:

дозволяється перехід з 1 пункту в 2 або 3 або 4 або5







Розв’язування задачі комівояжера методом гілок і границь

1. Аналіз вихідної множини ( (омега)

Знайдемо оцінку знизу функції якості. Для цієї мети на першому етапі визначимо матрицю мінімальних відстаней по рядках



Далі знаходимо значення функції цілі

.

Аналогічно визначається матриця мінімальних відстаней по стовпцях

.

Тоді .

У такому випадку оцінка функції якості Н буде визначатися на основі співвідношення

– вибираємо максимальне число.

Далі оцінимо верхнє значення функції якості. Для цієї мети виберемо початковий план

.

У такому випадку верхнє значення функції якості .

Очевидно, що вихідна множина планів ( буде містити в собі наступні підмножини:

.

Тут ij означає перехід з i-того пункту (у цьому випадку 1) в j-ий.

2. Аналіз підмножини 12



.

У такому випадку на першому етапі матрицю вихідних маршрутів можна представити у вигляді



Для визначення нижньої границі функції якості на підмножині 12 знову визначають мінімальне значення функції якості по рядках і стовпцях







3. Аналіз підмножини 13



Верхня оцінка функції якості на цій підмножині











4. Аналіз підмножини 14



Далі визначаємо верхню границю функції якості на цій підмножині









.

5. Аналіз підмножини 15





Визначимо нижнє значення функції якості на множині 15

. – можливий варіант відвідування





.

6. Відсівання безперспективних підмножин

.

Підмножини V12 й V14 мають найкращу верхню оцінку функції якості, однак перспективним є підмножина 14, в силу того, що нижня границя функції якості є ближче до оптимальної.

Отже, надалі необхідно розглядати підмножину 14.

Розглядається підмножина 14, що містить у собі наступні підмножини .

7. Аналіз підмножини 142

.

Далі обчислюють верхню границю функції якості

.

Визначення нижньої границі функції якості

. – можливі шляхи пересування комівояжера





.

8. Аналіз підмножини 143



Визначення верхньої границі функції якості



Визначення нижньої границі функції якості





.

9. Аналіз підмножини 145



Визначення верхньої границі функції якості



Визначення нижньої границі функції якості







.

10. Відсівання безперспективних підмножин

.

Підмножина ^ V143 є безперспективною.В силу того, що верхня границя функції якості на підмножинах V142 й V145 збігаються між собою, то далі порівнюють між собою нижні границі функції якості і тому що Н142 > Н145, то рекордом є підмножина 145. При цьому 145 буде містити в собі 2 непересічні підмножини .

11. Аналіз підмножини 1452



Визначення верхньої границі функції якості



Визначення нижньої границі функції якості







.

12. Аналіз підмножини 1453



Визначення верхньої границі функції якості



Визначення нижньої границі функції якості







.

13. Відсівання безперспективних підмножин

.

14. У такому випадку

.

Оптимальна матриця переміщень буде представлена в такий спосіб



Таким чином, оптимальний маршрут колобка буде представлений наступними відвідуваннями: дід і баба  ведмідь  лисиця  заєць  вовк  дід і баба. При цьому .


Дерево розв’язків


0 крок































12

13

14

15



















1 крок
















2 крок





142



143



145




















3 крок








1452



1453




























14523










^ МЕТОДИЧНІ ВКАЗІВКИ ДЛЯ ВИКОНАННЯ

КОНТРОЛЬНОЇ РОБОТИ


Навчальним планом по|с| дисципліні "Дослідження операцій" передбачене виконання контрольної роботи. Кількість задач контрольної роботи визначається викладачем. Перед рішенням задач необхідно освоїти відповідний розділ теоретичного матеріалу.

При виконанні контрольної роботи студент повинен дотримувати наступних правил:

  1. Кількість завдань|задач| контрольної роботи визначається викладачем.

  2. Титульна сторінка роботи оформляється за зразком, зазначеним деканатом|нижеследующим|.

  3. Контрольна робота виконується|исполняется| в зошиті, в якому|какой| необхідно залишити поля для зауважень рецензента й кілька чистих аркушів для доповнень і відповідей на ці зауваження.

  4. Рішення кожної задачі потрібно починати із приведення її повної умови.

  5. Розв’язування задач необхідно супроводжувати поясненнями, графіками й посиланнями на відповідні теоретичні поняття й формули.

  6. Якщо контрольна робота після перевірки не зарахована, потрібно виправити помилки, зазначені викладачем. Це необхідно робити наприкінці роботи (або в окремому зошиті), написавши спочатку титул “Робота над помилками”. Вносити зміни|смены| в текст уже перевіреної роботи категорично|категорично| забороняється. Дороблена контрольна робота посилається для повторного огляду разом з першим варіантом.

  7. Студент, що не виконав|исполнил,проделал| контрольну роботу, до|до| заліку (іспиту) не допускається.



ЛІТЕРАТУРА


6. ЛІТЕРАТУРА


6.1. Основна

    1. Кремер Н.Ш. Исследование операций в экономике. - М.: Банки и биржи, 1997.

    2. Вагнер Г. Исследование операций.- В 3 - х томах. - М.: Мир, 1973.

    3. Вентцель Е.С. Исследование операций. Задачи, принципы, методология.– М. Наука, 1980.

    4. Горелик В.А., Ушаков В.А. Исследование операций. - М.: Машиностроение, 1996.

    5. Зайченко Ю.П. Исследование операций. - К.: Высшая школа, 1985.

    6. Зайченко Ю.П., Шумилова С.А. Исследование операций (сборник задач). – К.: Высшая школа, 1984.


6.2. Додаткова

  1. Горчаков А.А., Орлова И.В. Компьютерные экономико-математические модели. М.: Компьютер, ЮНИТИ, 1995.

  2. Хедли Дж. Нелинейное и динамическое программирование. - М.:Мир, 1967.

  3. Щедрин Н.И., Кархов А.Н. Математические методы программирования в экономике. - М.: Статистика, 1974.

  4. Швачич Г.Г. Лінійна алгебра в розрахунках середовища МАТНСАD: Підручник. - Дніпропетровськ: ДАУБП, 2000.



Додаток 1


^ ТАБЛИЦЯ ВАРІАНТІВ ЗАВДАНЬ


Для визначення Вашого номера варіанта контрольної роботи необхідно число, що утворюється двома останніми цифрами номера залікової книжки, поділити на 30. Залишок від ділення відповідає потрібному номеру варіанта. Наприклад,

- номер Вашої залікової книжки 0012^ 71, тоді 71 : 30 = 2х30 +11 (залишок), номер варіанта 11.

- номер Вашої залікової книжки 001208, тоді 08 : 30 = 0х30 + 8 (залишок), номер варіанта 8.



№ варіанта

Номера задач

0

1.6

2.10

3.4

4.1

5.6

6.6

7.1

8.7

9.3

10.6

11.7

12.10

13.2

1

1.3

2.2

3.9

4.2

5.4

6.2

7.2

8.9

9.1

10.3

11.4

12.9

13.5

2

1.10

2.8

3.4

4.4

5.3

6.4

7.6

8.8

9.6

10.1

11.1

12.5

13.2

3

1.2

2.4

3.3

4.5

5.1

6.8

7.1

8.4

9.2

10.4

11.8

12.1

13.7

4

1.4

2.6

3.10

4.7

5.9

6.9

7.4

8.6

9.5

10.7

11.5

12.6

13.9

5

1.9

2.5

3.5

4.8

5.7

6.3

7.7

8.5

9.4

10.8

11.2

12.2

13.4

6

1.2

2.3

3.9

4.9

5.8

6.1

7.5

8.1

9.9

10.6

11.9

12.8

13.6

7

1.5

2.1

3.4

4.6

5.2

6.7

7.8

8.3

9.8

10.5

11.6

12.4

13.1

8

1.4

2.9

3.8

4.3

5.5

6.5

7.6

8.2

9.7

10.1

11.3

12.3

13.3

9

1.10

2.7

3.3

4.10

5.4

6.10

7.3

8.10

9.5

10.9

11.1

12.7

13.2

10

1.8

2.10

3.4

4.2

5.6

6.5

7.10

8.9

9.3

10.2

11.5

12.7

13.4

11

1.6

2.1

3.9

4.5

5.10

6.4

7.4

8.5

9.2

10.4

11.9

12.5

13.6

12

1.1

2.5

3.2

4.8

5.2

6.6

7.2

8.1

9.1

10.8

11.4

12.3

13.8

15

1.8

2.9

3.7

4.3

5.4

6.1

7.5

8.7

9.4

10.6

11.8

12.8

13.5

14

1.3

2.7

3.6

4.6

5.9

6.3

7.8

8.5

9.8

10.1

11.7

12.6

13.9

15

1.4

2.5

3.1

4.9

5.6

6.7

7.4

8.3

9.6

10.5

11.2

12.10

13.1

16

1.6

2.3

3.8

4.1

5.7

6.9

7.6

8.4

9.10

10.3

11.6

12.4

13.10

17

1.7

2.2

3.10

4.4

5.3

6.8

7.7

8.8

9.10

10.7

11.3

12.2

13.9

18

1.10

2.8

3.1

4.7

5.1

6.5

7.9

8.6

9.4

10.2

11.1

12.1

13.7

19

1.4

2.4

3.6

4.8

5.5

6.2

7.2

8.2

9.5

10.6

11.10

12.9

13.10

20

1.9

2.6

3.7

4.9

5.3

6.10

7.1

8.10

9.9

10.4

11.2

12.5

13.5

21

1.4

2.5

3.9

4.6

5.1

6.6

7.6

8.4

9.3

10.8

11.1

12.10

13.6

22

1.7

2.2

3.5

4.3

5.6

6.1

7.6

8.9

9.2

10.10

11.3

12.4

13.4

23

1.3

2.8

3.4

4.2

5.4

6.7

7.3

8.3

9.1

10.2

11.4

12.5

13.2

24

1.1

2.10

3.9

4.1

5.5

6.2

7.4

8.2

9.6

10.1

11.6

12.6

13.3

25

1.6

2.1

3.3

4.4

5.4

6.9

7.8

8.4

9.8

10.4

11.5

12.2

13.8

26

1.5

2.3

3.1

4.7

5.9

6.4

7.6

8.6

9.7

10.5

11.10

12.7

13.10

27

1.10

2.4

3.5

4.10

5.7

6.3

7.4

8.7

9.10

10.3

11.9

12.8

13.4

28

1.1

2.9

3.2

4.2

5.8

6.10

7.1

8.5

9.5

10.6

11.1

12.4

13.5

29

1.8

2.7

3.6

4.5

5.5

6.9

7.2

8.1

9.7

10.7

11.4

12.1

13.6



ЗАДАЧА 1

Із листів металу розміру mxn необхідно виготовити N заготовок розміру m1xn1 та М заготовок розміру m2xn2. Скласти модель оптимізації розкроювання металу за мінімумом загальних відходів.


№ зад.

m

n

N

m1

n1

M

m2

n2

1.1.

7

14

900

5

6

500

3

4

1.2.

6

14

800

3

5

400

2

4

1.3.

5

15

700

2

4

300

3

3

1.4.

6

15

600

3

4

400

3

5

1.5.

7

16

500

3

5

300

2

4

1.6.

8

17

400

4

6

400

3

5

1.7.

9

18

300

5

7

400

2

4

1.8.

8

19

350

6

8

370

5

7

1.9.

9

20

500

5

7

400

4

6

1.10.

10

20

500

5

6

450

3

5


ЗАДАЧА 2

В столярній майстерні мають в достатній кількості колод довжиною l метрів. Колоди необхідно розпиляти на заготовки двох видів: довжиною l1 та довжиною l2 метрів відповідно. Кожної подоби необхідно заготовити не менше m та n штук відповідно.

Скласти модель оптимізації розпилювання колод за:

  • мінімумом загальних відходів;

  • мінімумом числа використаних колод.




№ зад.

l

l1

l2

m

n

2.1

4

2

1,5

50

80

2.2

5

3

2

40

70

2.3

6

2,4

1,2

3

50

2.4

6

3

1,8

40

30

2.5

6

2,5

3,2

50

40

2.6

6

3

1,5

40

80

2.7

6

3,4

1,2

50

80

2.8

5

1,2

0,8

40

60

2.9

5

1,4

0,7

30

20

2.10

5

1,6

0,5

40

50



ЗАДАЧА 3

Знайти оптимальний розв’язок задачі цілочисельного лінійного програмування:

  • використовуючи алгоритм Гоморі;

  • знявши умови цілочисельності, ЗЛП розв’язати графічним методом та використовуючи нерівність Гоморі показати, яким чином проходить правильне відтинання.

3.1. 3.2.



3.3. 3.4.



3.5. 3.6.



3.7. 3.8.




3.9. 3.10.




ЗАДАЧА 4

Розв’язати задачу дробово-лінійного програмування


4.1. 4.2.




4.3. 4.4.



4.5. 4.6.




4.7. 4.8.



4.9. 4.10.




ЗАДАЧА 5

За методом Лагранжа знайти точку умовного екстремуму функції


5.1. 5.2.




5.3. 5.4.




5.5. 5.6.




5.7. 5.8.



5.9. 5.10.




ЗАДАЧА 6


Розв’язати задачу нелінійного програмування графічним методом


6.1. 6.2.



6.3. 6.4.




6.5. 6.6.




6.7. 6.8.


1   2   3   4   5

Схожі:

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconI. Предмет І задачі дослідження операцій
Навчальний посібник являє собою конспект лекцій для студентів економічних фахів по однойменній дисципліні. У кожній главі розглядаються...
По дисципліні «дослідження операцій» iconПо дисципліні «дослідження операцій»
У ній найбільше чітко реалізуються основні ідеї вивчення математичних дисциплін на економічних спеціальностях|экономичном| – ідеї...
По дисципліні «дослідження операцій» iconТематичнийпла н по видах занять з курсу "Дослідження операцій"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconПара 6/18/2013
Дослідження операцій в транспортних системах, корп. 4, ауд. 1-7А, Пристінський М. Г., Екзамен
По дисципліні «дослідження операцій» iconМетодичні вказівки щодо виконання контрольної роботи з навчальної дисципліни " дослідження операцій" для студентів заочної форми навчання
Методичні вказівки щодо виконання контрольної роботи з навчальної дисципліни „Дослідження операцій” для студентів заочної форми навчання...
По дисципліні «дослідження операцій» iconПитання з дисциплини «дослідження операцій»
Розподіл капіталовкладень між підприємствами; постановка задачі, функціональні рівняння
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи