Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
1. Визначення мети автоматизації процедури
Автоматизація виконується з метою мінімізації часу необхідного на визначення маршруту мінімальної вартості між усіма вузлами, за допомогою знаходження найоптимальнішої процедури.
2. Визначення функцій процедури
При розв’язанні широкого кола прикладних задач нерідко виникає необхідність знайти маршрут, що зв’язує усі вершини в графі G. Наведемо алгоритм розв’язання такої задачі. В ньому задача зводиться до пошуку маршруту в зв’язаному графі G = (V, E), V – вершини, Е – ребра, який з’єднує задані вершини v, u Î V, де v≠u.
3. Генерація варіантів побудови процедури
Кожен концептуальний варіант характеризується критеріями перспективності (мінімальне собівартість, максимальна швидкодія, максимальний час напрацювання на відмову).
Для формування набору критеріїв перспективності концептуального варіанту доцільно використовувати, можливо з модифікацією набір показників Q до S.
Існують два основних способи подолання проблеми багатокритеріальності:
Згортка
Конструюємо гіпотетичний показник, шляхом об’єднання (+,* тощо) всіх наявних показників, критеріїв.
При цьому кожна складова цього показника аранжується коефіцієнтом приведення розмірності,і можливо ваговим коефіцієнтом.
Виділення головного критерію
Виділяють головне, а інші записуються, як обмеження.
Визначені критерії:
5. Впорядкування варіантів за ознакою зменшення перспективності (з використанням методу аналітичної ієрархії)
Вибір кінцевого єдиного компромісного рішення з урахуванням різноманітних критеріїв є достатньо складним завданням при плануванні та прийнятті рішень.
Метод аналізу ієрархії (MAI), розроблений відомим американським математиком Томасом Сааті, з успіхом використовується для розв'язання багатьох практичних задач на різних рівнях планування. Цей метод набув широкого розповсюдження в останнє десятиріччя. Згідно з цим методом вибір пріоритетних рішень здійснюється за допомогою парних порівнянь. Припустимо, що ми маємо три камені. Спробуємо оцінити їх вагу. Скажімо, А важчий за Б, а Б важчий за С. Аналогічно можна порівняти відносну важливість будь-яких кількісно невизначених факторів.
Для представлення результатів оцінок у кількісному виразі Т.Сааті вводить шкалу парних порівнянь (таблиця 1). Згідно з цією шкалою нас не цікавитиме відсутність фізичних чи об'єктивних одиниць виміру. Основною перевагою цього методу є те, що він є безрозмірним і не виникає проблем при приведенні до однакових одиниць виміру.
Правомірність цієї шкали доведена теоретично і практично при порівнянні з багатьма іншими відомими даними. Досвід показав, що при проведенні парних порівнянь, в основному, ставляться запитання: "Який з елементів є важливішим? Який най вірогідніший? Який з них найпривабливіший?".
MAI є систематичною процедурою ієрархічного представлення елементів, що визначають суть будь-якої проблеми.
Існує кілька видів ієрархій:
Таблиця 1
|
Відносна важливість (бали) |
Визначення |
Пояснення |
|
1 |
однакова вжливість |
Обидва елементи вносять однаковий вклад |
|
3 |
один елемент трохи важливіший за другий |
досвід дозволяє поставити один елемент трохи вище за другий |
|
5 |
суттєва перевага |
Досвід дозволяє встановити безумовну перевагу одного над другим |
|
7 |
значна перевага |
один елемент настільки важливіший за другий, що є практично значимим |
|
9 |
абсолютна перевага одного над другим |
Очевидність переваги пдтверджується більшістю |
|
2,4,6,8 |
проміжні оцінки між сусідніми твердженнями |
компромісне рішення |
|
Обернені величини чисел, наведених вище |
Якщо при порівнянні одного елемента з другим, отримане одне з вищевказаних чисел (1-9), то при порівнянні другого з першим, матиме обернену величену |
Визначення вагу критеріїв, користуючись шкалою порівняння (Табл. 1):
Матриця бінарного порівняння критеріїв
|
|
П |
Е |
Ш |
Σ |
|
П |
0 |
1/7 |
1/3 |
0,03037667 |
|
Е |
7 |
0 |
5 |
0,7654921 |
|
Ш |
3 |
1/5 |
0 |
0,20413123 |
Простота в 1/7 разів (значна перевага ефективності) важливіша за ефективність та в 1/3 разів (швидкодія трохи вашливіша) важливіша за швидкодію.
Ефективність в 7 разів (значна перевага) важливіша за простоту та в 5 разів (суттєва перевага) важливіша за швидкодію.
Швидкодія в 3 рази (один елемент трохи важливіший за другий) важливіша за простоту та в 1/5 разів (суттєва перевага ефективності) важливіший за ефективність.
Знаходження суми у кожному рядку матриці бінарного порівняння критеріїв:
Σ1 = 1/7 + 1/3 + 0 = 0,47619047
Σ2 = 7 + 5 + 0 = 12
Σ3 = 3 + 1/5 + 0 = 3,2
Знаходження суми у всіх рядку матриці бінарного порівняння критеріїв:
Σ1-3 = 0,47619047 + 12 + 3,2 = 15,6761905
Знаходження інтегральної оцінки для кожного з критеріїв:
ΣП = 0,47619047 / 15,6761905 = 0,03037667
ΣЕ = 12 / 15,6761905 = 0,7654921
ΣШ = 3,2 / 15,6761905 = 0,20413123
Перевірка:
ΣП + ΣЕ + ΣШ = 1
Отже, вагові коефіцієнти критеріїв:
αП = 0,03037667
αЕ = 0,7654921
αШ = 0,20413123
Визначення ваги кожного з трьох варіантів по кожному критерію окремо:
Матриця бінарного порівняння варіантів для першого критерію
(простота алгоритму)
|
|
Л |
М.г.м. |
Σ |
|
Л |
0 |
7 |
0,98 |
|
М.г.м. |
1/7 |
0 |
0,20 |
Знаходження суми у кожному рядку матриці бінарного порівняння:
Σ1 = 7
Σ2 = 1/7 = 0,14285714
Знаходження суми у всіх рядку матриці бінарного порівняння:
Σ1-2 = 7 + 0,14285714 = 7,14285714
Знаходження інтегральної оцінки для кожного з варіантів:
ΣЛ = 7 / 7,14285714 = 0,98
ΣМ.г.м. = 0,14285714 / 7,14285714 = 0,02
Перевірка:
ΣЛ + ΣМ.г.м. = 1
Матриця бінарного порівняння варіантів для другого критерію
(ефективність алгоритму)
|
|
Л |
М.г.м |
Σ |
|
Л |
0 |
1 |
0,50 |
|
М.г.м. |
1 |
0 |
0,50 |
Знаходження суми у кожному рядку матриці бінарного порівняння:
Σ1 = 1
Σ2 = 1
Знаходження суми у всіх рядку матриці бінарного порівняння:
Σ1-2 = 1 + 1 = 2
Знаходження інтегральної оцінки для кожного з варіантів:
ΣД = 1 / 2 = 0,5
ΣФ-У = 1 / 2 = 0,5
Перевірка:
ΣД + ΣФ-У = 1
Матриця бінарного порівняння варіантів для третього критерію
(швидкодія алгоритму)
|
|
Л |
М.г.м. |
Σ |
|
Л |
0 |
3 |
0,90 |
|
М.г.м. |
1/3 |
0 |
0,10 |
Знаходження суми у кожному рядку матриці бінарного порівняння:
Σ1 = 3
Σ2 = 1/3 ≈ 0,33
Знаходження суми у всіх рядку матриці бінарного порівняння:
Σ1-2 = 3 + 0,33 ≈ 3,33
Знаходження інтегральної оцінки для кожного з варіантів:
ΣЛ = 3 / 3,33 = 0,9009009 ≈ 0,9
ΣМ.г.м. = 0,33 / 3,33 = 0,0990991 ≈ 0,1
Перевірка:
ΣЛ + ΣМ.г.м. = 1
Знаходження інтегральних оцінок для кожного з варіантів з урахуванням ваги кожного критерію
|
|
П |
Е |
Ш |
Σ |
|
α |
0,03 |
0,77 |
0,20 |
- |
|
Л |
0,98 |
0,50 |
0,90 |
0,59 |
|
М.г.м. |
0,02 |
0,50 |
0,1 |
0,40 |
ΣЛ = 0,03 * 0,98 + 0,77 * 0,5 + 0,2 * 0,9 = 0,5944
ΣМ.г.м. = 0,03 * 0,02 + 0,77 * 0,5 + 0,2 * 0,1 = 0,4056
Отже, судячи з отриманих інтегральних оцінок, можна прийти до висновку, що за даних умов слід використовувати алгоритм Літтла для вирішення поставленої задачі.
6. Розробка алгоритму автоматизованої проектної процедури на основі вибраного методу (варіанту) із представленням схеми алгоритму
Алгоритм Літтла
У кожному рядку матриці вартості знайдемо мінімальний елемент і віднімемо його з усіх елементів рядка. Зробимо це і для стовпців , що не містять нуля . Отримаємо матрицю вартості , кожен рядок і кожен стовпець якої містять хоча б один нульовий елемент .
Для кожного нульового елемента матриці cij розрахуємо коефіцієнт Гi , j , що дорівнює сумі найменшого елемента i рядки (виключаючи елемент Сi , j = 0 ) і найменшого елемента j шпальти. З усіх коефіцієнтів Гi , j виберемо такий , який є максимальним ГK , l = max { Гi , j } . У гамильтонов контур вноситься відповідна дуга ( k , l ) .
Видаляємо k -ту рядок і стовпець l , поміняємо на нескінченність значення елемента Сl , k (оскільки дуга ( k , l ) включена в контур , то зворотний шлях з l в k неприпустимий ) .
Повторюємо алгоритм кроку 1 , поки порядок матриці не стане рівним двом.
Потім в поточний орієнтований граф вносимо дві відсутні дуги , що визначаються однозначно матрицею прядка 2 . Отримуємо гамильтонов контур.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
- |
69 |
34 |
8 |
- |
45 |
- |
|
2 |
69 |
- |
- |
12 |
8 |
- |
|
|
3 |
34 |
- |
- |
- |
- |
7 |
- |
|
4 |
8 |
12 |
- |
- |
12 |
- |
- |
|
5 |
- |
8 |
- |
12 |
- |
- |
7 |
|
6 |
45 |
- |
7 |
- |
- |
- |
55 |
|
7 |
- |
- |
- |
- |
7 |
55 |
- |
Крок 1 (Ініціалізація)
У матриці D0 присутні елементи мають значення ∞, що не допустимо. Замінимо нескінченні дуги на довжини найкоротших шляхів між відповідними вершинами (за винятком діагональних елементів яким присвоїмо значення нескінченності). В результаті отримаємо таку матрицю вартості:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
- |
20 |
34 |
8 |
20 |
41 |
27 |
|
2 |
20 |
- |
54 |
12 |
8 |
61 |
15 |
|
3 |
34 |
54 |
- |
42 |
54 |
7 |
61 |
|
4 |
8 |
12 |
42 |
- |
12 |
53 |
19 |
|
5 |
20 |
8 |
54 |
12 |
- |
61 |
7 |
|
6 |
41 |
61 |
7 |
53 |
61 |
- |
55 |
|
7 |
27 |
15 |
61 |
19 |
7 |
55 |
- |
Крок 2
Знайдемо мінімальні елементи в кожному рядку і потім віднімемо його з решти елементів рядка (мінімальні елементи записані навпроти відповідних рядків). Отримаємо матрицю представлену нижче.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
1 |
- |
11 |
26 |
0 |
12 |
33 |
19 |
|
2 |
12 |
- |
46 |
4 |
0 |
53 |
7 |
|
3 |
27 |
46 |
- |
35 |
47 |
0 |
54 |
|
4 |
0 |
3 |
34 |
- |
4 |
45 |
11 |
|
5 |
13 |
0 |
47 |
5 |
- |
54 |
0 |
|
6 |
34 |
53 |
0 |
46 |
54 |
- |
48 |
|
7 |
20 |
7 |
54 |
12 |
0 |
48 |
- |
Крок 3
Для кожного нульового елемента розрахуємо значення Гij, рівне сумі найменшого елемента i рядки (виключаючи елемент Сij = 0) і найменшого елемента j шпальти.
Г1,4=11+4=15
Г2,5=4+0=4
Г3,6=27+33=60
Г4,1=3+12=15
Г5,2=0+7=7
Г5,7=0+7=7
Г6,3=34+26=60
Г7,5=7+0=7
Видалимо з матриці вартості рядок 3 і стовпець 6. Внесемо в поточний орієнтований граф дугу (3,6)
У рядку 6 і стовпці 3 відсутній елемент рівний ∞. Привласнимо елементу (6,3) значення нескінченності щоб уникнути передчасного замикання контуру.
|
1 |
2 |
3 |
4 |
5 |
7 |
|
|
1 |
- |
11 |
26 |
0 |
12 |
19 |
|
2 |
12 |
- |
46 |
4 |
0 |
7 |
|
4 |
0 |
3 |
34 |
- |
4 |
11 |
|
5 |
13 |
0 |
47 |
5 |
- |
0 |
|
6 |
34 |
53 |
- |
46 |
54 |
48 |
|
7 |
20 |
7 |
54 |
12 |
0 |
- |
Крок 4
Знайдемо мінімальні елементи в кожному рядку і потім віднімемо його з решти елементів рядка (мінімальні елементи записані навпроти відповідних рядків). Отримаємо матрицю представлену нижче.
|
1 |
2 |
3 |
4 |
5 |
7 |
|
|
1 |
- |
0 |
0 |
0 |
1 |
8 |
|
2 |
8 |
- |
27 |
0 |
0 |
3 |
|
4 |
0 |
0 |
16 |
- |
1 |
8 |
|
5 |
8 |
0 |
27 |
0 |
- |
0 |
|
6 |
0 |
19 |
- |
12 |
20 |
14 |
|
7 |
13 |
0 |
32 |
5 |
0 |
- |
Крок 5
Для кожного нульового елемента розрахуємо значення Гij, рівне сумі найменшого елемента i рядки (виключаючи елемент Сij = 0) і найменшого елемента j шпальти.
Г1,2=0
Г1,3=16
Г1,4=0
Г2,4=0
Г2,5=0
Г4,1=0
Г4,2=0
Г5,2=0
Г5,4=0
Г5,7=3
Г6,1=12
Г7,2=0
Г7,5=0
Видалимо з матриці вартості рядок 1 і стовпець 3. Внесемо в поточний орієнтований граф дугу (1,3)
У рядку 3 і стовпці 1 відсутній елемент рівний ∞. Привласнимо елементу (3,1) значення нескінченності щоб уникнути передчасного замикання контуру.
|
1 |
2 |
4 |
5 |
7 |
|
|
2 |
5 |
- |
0 |
0 |
0 |
|
4 |
0 |
0 |
- |
0 |
7 |
|
5 |
0 |
0 |
0 |
- |
0 |
|
6 |
- |
7 |
0 |
8 |
2 |
|
7 |
8 |
0 |
0 |
0 |
- |
Крок 6
Для кожного нульового елемента розрахуємо значення Гij, рівне сумі найменшого елемента i рядки (виключаючи елемент Сij = 0) і найменшого елемента j шпальти.
Г6,4=2
Видалимо з матриці вартості рядок 6 і стовпець 4. Внесемо в поточний орієнтований граф дугу (6,4)
У рядку 4 і стовпці 6 відсутній елемент рівний ∞. Привласнимо елементу (4,6) значення нескінченності щоб уникнути передчасного замикання контуру.
|
1 |
2 |
5 |
7 |
|
|
2 |
0 |
- |
0 |
0 |
|
4 |
- |
0 |
0 |
0 |
|
5 |
0 |
0 |
- |
0 |
|
7 |
0 |
0 |
0 |
- |
Крок 7
Для кожного нульового елемента розрахуємо значення Гij, рівне сумі найменшого елемента i рядки (виключаючи елемент Сij = 0) і найменшого елемента j шпальти.
Г4,2=0
Видалимо з матриці вартості рядок 4 і стовпець 2. Внесемо в поточний орієнтований граф дугу (4,2)
У рядку 2 і стовпці 4 відсутній елемент рівний ∞. Привласнимо елементу (2,4) значення нескінченності щоб уникнути передчасного замикання контуру.
|
1 |
5 |
7 |
|
|
2 |
- |
0 |
0 |
|
5 |
0 |
- |
0 |
|
7 |
0 |
0 |
- |
Крок 7
Для кожного нульового елемента розрахуємо значення Гij, рівне сумі найменшого елемента i рядки (виключаючи елемент Сij = 0) і найменшого елемента j шпальти.
Г2,5=0
Видалимо з матриці вартості рядок 2 і стовпець 5. Внесемо в поточний орієнтований граф дугу (2,5)
У рядку 5 і стовпці 2 відсутній елемент рівний ∞. Привласнимо елементу (5,2) значення нескінченності щоб уникнути передчасного замикання контуру.
|
1 |
7 |
|
|
5 |
- |
0 |
|
7 |
0 |
- |
Крок 8 (Завершення виконання алгоритму)
В даному випадку, алгоритм закінчує роботу, коли знайдений найкоротший шлях. Результат його роботи: точки 3,6 - 1,3 – 6,4 – 4,2 – 2,5 – 5,7 – 7,1
Мінімальна вартість маршруту дорівнює:
1 – 3 – 6 – 3 – 1 – 4 – 2 – 5 – 7 – 5 – 4 – 1 = > 144.
7. Програмування алгоритму
Для реалізації данної задачі використовується программа TSPbyGA.
8. Тестування автоматизованої процедури з аналізом впливу розмірності задачі на ефективність автоматизованої процедури
Запустивши програму, користувач побачить головне вікно програми, що зображене на рис. 2.
Рис. 2. Головне вікно програми
Для того, щоб обчислити маршрут треба натиснути на кнопку «Start». Результат натиснення на кнопку «Start» зображений на рис. 3.
Рис. 3. Результат встановлення графу
9. Висновки із зазначенням напрямку подальших досліджень
При виконанні курсової роботи було розраховано замкнений мінімальний маршрут для пропайки друкованої плати роботом.
Завдяки використанню алгоритму Літтла був обчислений маршрут мінімальної вартості, а саме 1 – 3 – 6 – 3 – 1 – 4 – 2 – 5 – 7 – 5 – 4 – 1. Довжина маршруту дорівнює 144.
За допомогою методу аналітичної ієрархії був обраний оптимальний варіант (алгоритм Літтла) рішення індивідуального завдання.
Такой для вирішення такого типу задач було протестована програма TSPbyGA.
В подальшому життєвому циклі необхідно реалізувати, тобто розповсюдити дану процедуру, здійснити її моніторинги і вразі потреби вдосконалити чи усунути недоліки, для цього має бути присутній зворотній зв'язок.
10. Перелік використаних інформаційних джерел