Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent
Актуальність і масовий характер проблематики оптимізаційного моделювання привели до розробки та широкомасштабного впровадження доступних, потужних й ефективних засобів математичної оптимізації. Вважається, що цей процес має привести до суттєвого підвищення якості управлінських рішень, що приймаються...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50524 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2011. — Т. 13, № 3. — С. 3-16. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50524 |
|---|---|
| record_format |
dspace |
| spelling |
Додонов, О.Г. Кузьмичов, А.І. 2013-10-22T23:38:28Z 2013-10-22T23:38:28Z 2011 Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2011. — Т. 13, № 3. — С. 3-16. — Бібліогр.: 8 назв. — укр. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50524 338.45(078.5) Актуальність і масовий характер проблематики оптимізаційного моделювання привели до розробки та широкомасштабного впровадження доступних, потужних й ефективних засобів математичної оптимізації. Вважається, що цей процес має привести до суттєвого підвищення якості управлінських рішень, що приймаються на різних рівнях відповідальності. Важливо, що ці засоби орієнтовані на розв’язання задач оптимізації, реалізація математичних моделей яких до сьогодні була недосяжна для звичайних управлінців та аналітиків. Розглянуто новітні програмні засоби еволюційного програмування, які дозволяють на звичайному робочому місці професійного користувача без будь-яких додаткових витрат розв’язувати оптимізаційну задачу комівояжера, яка має безліч варіантів і модифікацій. Актуальность и массовый характер проблематики оптимизационного моделирования привели к разработке и широкомасштабному внедрению доступных, мощных и эффективных средств математической оптимизации. Считается, что этот процесс должен привести к существенному повышению качества управленческих решений, принимаемых на разных уровнях ответственности. Важно, что эти средства ориентированы на решение задач оптимизации, реализация математических моделей которых доныне была недостижима для обычных управленцев и аналитиков. Рассмотрены новейшие программные средства эволюционного программирования, позволяющие на обычном рабочем месте профессионального пользователя, без каких-либо дополнительных затрат, решать оптимизационную задачу коммивояжера, которая имеет множество вариантов и модификаций. The relevance and mass character of optimization modeling problems led to the development and large-scale implementation of accessible, powerful and effective tools of mathematical optimization. It is believed that this process should lead to a significant increase in the quality of management decisions being made at different levels of responsibility. It is important that these tools are aimed at solving optimization problems. Mathematical models implementation of these problems has been inaccessible to ordinary managers and analysts up to date. The latest evolutionary programming tools are considered. They allow to solve to real professional users at its workplace without any additional cost the well-known optimization traveling salesman problem, which has many variations and modifications. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Математичні методи обробки даних Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent Оптимизационные модели эволюционного программирования в Excel: решение задачи коммивояжера с ограничениями alldifferent Optimization Models of Evolutionary Programming in Excel: Solving the Traveling Salesman Problem with Alldifferent Constraint Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| spellingShingle |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent Додонов, О.Г. Кузьмичов, А.І. Математичні методи обробки даних |
| title_short |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| title_full |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| title_fullStr |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| title_full_unstemmed |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| title_sort |
оптимізаційні моделі еволюційного програмування в excel: розв’язання задачі комівояжера з обмеженнями alldifferent |
| author |
Додонов, О.Г. Кузьмичов, А.І. |
| author_facet |
Додонов, О.Г. Кузьмичов, А.І. |
| topic |
Математичні методи обробки даних |
| topic_facet |
Математичні методи обробки даних |
| publishDate |
2011 |
| language |
Ukrainian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
Оптимизационные модели эволюционного программирования в Excel: решение задачи коммивояжера с ограничениями alldifferent Optimization Models of Evolutionary Programming in Excel: Solving the Traveling Salesman Problem with Alldifferent Constraint |
| description |
Актуальність і масовий характер проблематики оптимізаційного моделювання привели до розробки та широкомасштабного впровадження доступних, потужних й ефективних засобів математичної оптимізації. Вважається, що цей процес має привести до суттєвого підвищення якості управлінських рішень, що приймаються на різних рівнях відповідальності. Важливо, що ці засоби орієнтовані на розв’язання задач оптимізації, реалізація математичних моделей яких до сьогодні була недосяжна для звичайних управлінців та аналітиків. Розглянуто новітні програмні засоби еволюційного програмування, які дозволяють на звичайному робочому місці професійного користувача без будь-яких додаткових витрат розв’язувати оптимізаційну задачу комівояжера, яка має безліч варіантів і модифікацій.
Актуальность и массовый характер проблематики оптимизационного моделирования привели к разработке и широкомасштабному внедрению доступных, мощных и эффективных средств математической оптимизации. Считается, что этот процесс должен привести к существенному повышению качества управленческих решений, принимаемых на разных уровнях ответственности. Важно, что эти средства ориентированы на решение задач оптимизации, реализация математических моделей которых доныне была недостижима для обычных управленцев и аналитиков. Рассмотрены новейшие программные средства эволюционного программирования, позволяющие на обычном рабочем месте профессионального пользователя, без каких-либо дополнительных затрат, решать оптимизационную задачу коммивояжера, которая имеет множество вариантов и модификаций.
The relevance and mass character of optimization modeling problems led to the development and large-scale implementation of accessible, powerful and effective tools of mathematical optimization. It is believed that this process should lead to a significant increase in the quality of management decisions being made at different levels of responsibility. It is important that these tools are aimed at solving optimization problems. Mathematical models implementation of these problems has been inaccessible to ordinary managers and analysts up to date. The latest evolutionary programming tools are considered. They allow to solve to real professional users at its workplace without any additional cost the well-known optimization traveling salesman problem, which has many variations and modifications.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50524 |
| citation_txt |
Оптимізаційні моделі еволюційного програмування в Excel: розв’язання задачі комівояжера з обмеженнями alldifferent / О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2011. — Т. 13, № 3. — С. 3-16. — Бібліогр.: 8 назв. — укр. |
| work_keys_str_mv |
AT dodonovog optimízacíinímodelíevolûcíinogoprogramuvannâvexcelrozvâzannâzadačíkomívoâžerazobmežennâmialldifferent AT kuzʹmičovaí optimízacíinímodelíevolûcíinogoprogramuvannâvexcelrozvâzannâzadačíkomívoâžerazobmežennâmialldifferent AT dodonovog optimizacionnyemodeliévolûcionnogoprogrammirovaniâvexcelrešeniezadačikommivoâžerasograničeniâmialldifferent AT kuzʹmičovaí optimizacionnyemodeliévolûcionnogoprogrammirovaniâvexcelrešeniezadačikommivoâžerasograničeniâmialldifferent AT dodonovog optimizationmodelsofevolutionaryprogramminginexcelsolvingthetravelingsalesmanproblemwithalldifferentconstraint AT kuzʹmičovaí optimizationmodelsofevolutionaryprogramminginexcelsolvingthetravelingsalesmanproblemwithalldifferentconstraint |
| first_indexed |
2025-11-26T00:09:37Z |
| last_indexed |
2025-11-26T00:09:37Z |
| _version_ |
1850593933944422400 |
| fulltext |
Математичні методи обробки даних
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 3
УДК 338.45(078.5)
О. Г. Додонов1, А. І. Кузьмичов2
1Інститут проблем реєстрації інформації НАН України
вул. М. Шпака, 2, 03113 Київ, Україна
e-mail: dssd@ipri.kiev.ua
2Академія муніципального управління МОН України
вул. І. Кудрі, 33, 01601 Київ, Україна
e-mail: akuzmychov@gmail.com
Оптимізаційні моделі еволюційного програмування
в Excel: розв’язання задачі комівояжера
з обмеженнями alldifferent
Актуальність і масовий характер проблематики оптимізаційного мо-
делювання привели до розробки та широкомасштабного впроваджен-
ня доступних, потужних й ефективних засобів математичної оптимі-
зації. Вважається, що цей процес має привести до суттєвого підви-
щення якості управлінських рішень, що приймаються на різних рівнях
відповідальності. Важливо, що ці засоби орієнтовані на розв’язання
задач оптимізації, реалізація математичних моделей яких до сьогодні
була недосяжна для звичайних управлінців та аналітиків. Розглянуто
новітні програмні засоби еволюційного програмування, які дозволяють
на звичайному робочому місці професійного користувача без будь-яких
додаткових витрат розв’язувати оптимізаційну задачу комівояжера,
яка має безліч варіантів і модифікацій.
Ключові слова: математична оптимізація, MS Excel, еволюційне про-
грамування, генетичний алгоритм, задача комівояжера, прийняття
рішень, spreadsheet modeling and optimization.
Вступ
Переважну більшість практичних задач оптимізації відносять до «важких»
для комп’ютерної реалізації задач з-за явної нелінійності цільової функції й об-
межень і необхідності врахування спеціальних граничних значень для шуканих
невідомих. Тож вимушений й тому найбільш популярний шлях до пошуку глоба-
льного оптимуму — зведення цих задач до класичних моделей лінійного, цілочи-
слового або хоча б опуклого програмування, зрозуміло, із втратою певних харак-
терних властивостей об’єкта дослідження. Цей шлях фактично досяг вершин
своїх теоретичних і прикладних можливостей, відповідно, залишається актуальною
© О. Г. Додонов, А. І. Кузьмичов
mailto:dssd@ipri.kiev.ua
mailto:akuzmychov@gmail.com
О. Г. Додонов, А. І. Кузьмичов
4
проблема безпосереднього математичного моделювання реальних задач оптиміза-
ції без будь-яких принципових спрощень. І у цьому напрямку йде пошук оригіна-
льних обчислювальних алгоритмів, за допомогою яких із застосуванням потуж-
них комп’ютерних засобів вдається знайти оптимальні чи близькі до них
розв’язки важливих і «важких» задач солідних розмірів із явним практичним
спрямуванням. Цей напрямок орієнтується на комбіновану технологію імітаційної
оптимізації (математичне програмування + імітаційне моделювання, simulation
optimization), де спільно застосовується апарат обробки невідомих детермінованої
й випадкової природи.
Однією з таких «важких» задач, яка має безліч застосувань, зокрема, як тест
(benchmark) для дослідження нових алгоритмів, є класична задача про комівояже-
ра (який має відвідати n міст з мінімальною довжиною контуру обходу), де кінце-
вий результат критично й експоненційно залежить від розміру задачі (значення n)
— кількість можливих контурів обходу складає фантастичну величину n! У про-
цесі її розв’язання типовими й паралельними алгоритмами переборного типу про-
тягом останніх майже 60 років сформувався навіть стимул спортивного типу у ви-
гляді досягнення рекордів — час від часу дослідники публікують кращі показники
щодо досягнутих максимальних розмірів (значень n), витрат машинного часу спе-
ціально побудованих багатомашинних комп’ютерних систем і поведінки відповід-
них алгоритмів. Найперший рекорд, який було досягнуто ще на ЕОМ ранніх по-
колінь, це найкоротший контур, що з’єднує 49 міст-столиць штатів США. Останні
рекорди 2000-х років, що отримані на багатомашинних комплексах за спеціально
розробленою програмою, досить вражаючі: 2005 р. — 33810 міст, 2006 р. — 85900
міст1. Але ці рекорди, на жаль, не мають серйозного впливу на реальну масову
практику, де сотні тисяч аналітиків мають, як правило, стандартні комп’ютерні та
програмні засоби для моделювання практичних задач оптимізації й прийняття
управлінських рішень на цій основі.
Тож саме для цієї найпоширенішої категорії користувачів-оптимізаторів зі
стандартною математичною й програмістською підготовкою вже 20 років у попу-
лярне обчислювальне середовище Excel вбудовують доступні й ефективні про-
грамні продукти масового використання у вигляді готових до використання опти-
мізаційних програм-надбудов (solvers). Відповідно, у сфері оптимізаційного мо-
делювання та прийняття управлінських рішень, яка найбільш поширена у бізнес-
середовищі, в операційному менеджменті та бізнес-освіті, сформувалася й актив-
но розвивається сучасна технологія аналізу, моделювання та прийняття рішень на
платформі електронних таблиць (spreadsheets) — електронно-табличне моделю-
вання та оптимізація (spreadsheet-based modeling and optimization) [4–5].
Стандартний комплект надбудови під назвою Excel Solver (в російськомовній
версії — Поиск решения) до версії Excel 2003 складається з трьох програм-
оптимізаторів для розв’язання найпоширеніших задач математичного програму-
вання: лінійної, цілочислової та гладкої нелінійної оптимізації, де реалізовано три
1 Слід згадати піонерні дослідження київських кібернетиків 70–80 років, коли в умовах обмежених машинних
ресурсів цифрових ЕОМ (швидкодія, пам’ять) розроблялися спеціалізовані електронні моделі потокових за-
дач, у тому числі, задачі комівояжера, де процес паралельних обчислень здійснюється зі швидкістю руху
електричного струму, тобто, миттєво [2].
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 5
обчислювальні алгоритми: симплекс-метод, метод гілок і границь та методи Нью-
тона й спряжених градієнтів для нелінійних задач.
За узгодженням з компанією Microsoft до середовищ Excel 2007/2010 вбудо-
вано вдосконалену надбудову Premium Solver, де для гладкої нелінійної оптиміза-
ції застосовується потужний метод узагальненого приведеного градієнта2 (Gene-
ralized Reduced Gradient, GRG).
У прикладній математиці «важкі» задачі оптимізації відносять до класу нелі-
нійних задач із негладкою цільовою функцією й обмеженнями на невідомі різного
типу, для яких безсилі класичні моделі й методи нелінійного програмування гра-
дієнтного типу щодо пошуку глобального оптимуму. Тож прогресивна й багато-
обіцяюча надбудова Premium Solver має у своєму складі модуль негладкої нелі-
нійної оптимізації під назвою Evolutionary Solver (у російськомовній версії Excel
2010 — Эволюционный поиск решения), що відповідає новітньому класу матема-
тичних моделей еволюційного програмування. В основі цього потужного, але ма-
ло ще відомого масовому користувачу модулю реалізація специфічного алгорит-
му направленого перебору під назвою «генетичний алгоритм» (ГА), де спільно
застосовується генератор випадкових чисел й оригінальний обчислювальний ме-
ханізм пошуку оптимуму, що відтворює еволюційні процеси живої природи. На
відміну від стихійних методів спроб і помилок чи випадкового пошуку із накопи-
ченням статистики, в ГА на кожному кроці-спробі здійснюється певне перекомбі-
нування значень шуканих невідомих (мовою біології — мутація та схрещення) й
розв’язується набір проміжних підзадач, щоб сформувати оновлений набір зна-
чень шуканих невідомих, який визначає краще за попереднє значення цільової
функції. За цим алгоритмом можна знайти досить близький до оптимального
розв’язок поставленої негладкої нелінійної задачі оптимізації солідного розміру
[7, 8].
Цей же модуль має ще одну цікаву й ефективну властивість, що детально роз-
глядається у цій роботі, яка дозволяє застосувати для шуканих невідомих оригіна-
льний вид обмежень під назвою alldifferent (в Excel 2010 — «все разные»).
Для задачі про комівояжера цей вид обмежень є надзвичайно корисним, бо
приводить до суттєвого збільшення допустимого розміру задачі, що розв’язується
в Excel, — замість задачі з n2 + n невідомими за цим обмеженням розв’язується
задача лише з n невідомими. Скажімо, за допомогою методу «гілок і границь» в
Excel можна точно розв’язати задачу комівояжера за моделлю булевого програ-
мування з n £ 13 [6, с. 192], зате еволюційним методом з обмеженням «все раз-
ные» наближено, з відхиленням від оптимуму на 2–3 %, що для практики цілком
прийнятно, розв’язується задача комівояжера з n £ 2003.
Появу надбудови Premium Solver слід вважати революційною подією у сфері
прикладного оптимізаційного моделювання завдяки наявності доступних, потуж-
них, ефективних й надзвичайно корисних засобів. На прикладі розв’язання кла-
сичної й «непідйомної» задачі комівояжера рядовий користувач (менеджер-аналі-
тик, дослідник-практик, викладач, аспірант, студент і навіть учень старших кла-
2 В Excel 2010 буквальний переклад — «Нелинейный метод обобщенного понижающего градиента (ОПГ)».
3 Число 200 — максимальне граничне значення числа невідомих у стандартних версіях Excel у складі пакета
MS Office, у комерційних версіях — кілька тисяч.
О. Г. Додонов, А. І. Кузьмичов
6
сів) фактично вперше на звичайному ПК із встановленим процесором електрон-
них таблиць Excel 2007/2010 отримав реальну можливість перейти від «іграшко-
вих» задач про комівояжера з приблизно 10–12 містами для обходу й тривалістю
пошуку до 15–20 хв. до розв’язання цієї ж задачі на порядок більших розмірів із
такою ж тривалістю, яка зазвичай покриває реальні задачі, що виникають у прак-
тиці моделювання матеріальних чи фінансових потоків у мережах та в прикладній
логістиці.
Задача комівояжера
Задача комівояжера (в теорії графів — задача пошуку найкоротшого гаміль-
тонова контуру) дуже близька за своєю постановкою до типових потокових задач
на графах: про найкоротший шлях, про призначення та про мінімальне покриття.
Але ці задачі розв’язуються значно простіше, ніж задача комівояжера, тому й
розв’язок задачі комівояжера базується на алгоритмах цих дещо простіших задач.
Уперше математична модель задачі про комівояжера (TSP, travelling salesmam
problem) була визначена в 1930 р. (К. Менгер) у класі моделей комбінаторного
програмування; для її комп’ютерної реалізації у 1950-ті роки (Дж. Данциг) була
поставлена відповідна задача лінійного програмування4 (ЛП) із-за її схожості з
транспортною задачею та задачею про призначення матричного типу. Правда,
зразу ж виявилася непередбачувана проблема — при використанні лінійної моделі
для задачі про призначення шуканий гамільтонів контур розривається на сукуп-
ність часткових підконтурів, що з’єднують певні групи точок. Ця постановка для
повного графа з n вершинами містить n2 + n змінних і не менше половини цієї ве-
личини — це явні обмеження на невідомі, наступні неявні обмеження в процесі
обчислень ставлять за мету ліквідацію часткових контурів. Тож хоча принципово
симплекс-методом можна користуватися, але на практиці від нього відмовляються
з-за його громіздкості й неефективності моделі ЛП. В Excel застосовується вбудо-
ваний в «Поиск решения» точний симплекс-метод (див. нижче).
Наступний етап розробки алгоритмів для розв’язання задачі про комівояжера
— більш продуктивний дискретний підхід з використанням розгалужень, алго-
ритмів направленого й скороченого перебору варіантів (адже повний перебір аст-
рономічної n! кількості варіантів відпадає одразу) за допомогою дерева пошуку та
моделі булевого програмування. У цьому напрямку розробляються точні й на-
ближені методи і алгоритми пошуку оптимуму. В Excel для цього застосовується
вбудований в «Поиск решения» точний метод «гілок і границь»5 (модель булевого
програмування) і наближений еволюційний метод (модель еволюційного програ-
мування).
Постановка задачі.
Комівояжер (агент роздрібної торгівлі) має обійти n клієнтів (замовників, пев-
них об’єктів, традиційно — міст) найкоротшим шляхом (якнайшвидше, з мініма-
льними витратами ресурсів) і повернутися у початковий пункт, побувавши у кож-
4Dantzig G. Solution of a Large-Scale Traveling Salesman Problem / G. Dantzig, D. Fulkerson, S. Jonson. — OR,
1954. — Р. 393–410.
5 An Algorithm for Traveling Salesman Problem / [Little J., Murty K., Swenney D., Karel C.]. — OR, 1963. —
Р. 972–989.
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 7
ного клієнта лише раз. У ролі комівояжера може бути транспортний засіб з дос-
тавки товарів у заклади роздрібної торгівлі чи в певні пункти для поповнення за-
пасів ресурсів (харчів, питної води, палива, ліків, джерел електроенергії) чи замі-
ни персоналу, сміттєзбиральна техніка, кандидат в депутати, персонал контроль-
но-ревізійної служби, бригада обслуговування банкоматів, автобус з групою ту-
ристів тощо — усі вони мають на меті визначити оптимальний контур обходу від-
повідних об’єктів, щоб мінімізувати довжину, час чи інші витрати.
Аналогічну постановку має виробнича задача про переналагодження універ-
сального обладнання для послідовного виконання на ньому n різних операцій із
мінімальною загальною тривалістю усього процесу, задача про найкоротше
з’єднання n електронних елементів на мікросхемі та багато інших.
Класична постановка задачі комівояжера доповнюється рядом специфічних
чи узагальнених задач, коли, скажімо, комівояжер має відвідувати певні групи
міст у межах певних регіонів чи коли треба визначити «вузьке місце» в контурі
обходу — ці умови ще додатково ускладнюють й без цього непросту задачу в кла-
сичній постановці, але ж досягнення оптимального чи хоча би близького до нього
варіанта забезпечує явну економічну чи іншу ефективність.
Ця математична задача припускає просту наочну інтерпретацію, з чого й роз-
починається її постановка: на площині задано n точок із відповідними координа-
тами, де кожна точка з’єднана із усіма іншими n точками. Це — набір даних (V, D,
А, X, S), де
V = {1, …, n} — задана множина n вузлів (номери, назви, коди);
D ={(i, j)} — задана множина n2 дуг: (1, 1), (1, 2), …, (n, n), кожна (i, j)-та дуга
(i ¹ j) графа з’єднує певну пару вузлів i, j Î V, це — повний граф, для якого існує
розв’язок; для неповного графа існування розв’язку не гарантується;
А = {аij} — задана множина вагових коефіцієнтів чи параметрів дуг, це: відс-
тань, тривалість, витрати палива, коштів чи будь-яких ресурсів, для i = j aij = ¥;
при aij = aji задача симетрична, інакше, у загальному випадку, несиметрична;
X ={xij} — шуканий результат у матричній формі, множина шуканих невідо-
мих, де: xij = 1, якщо (i, j)-та дуга належить шуканому контуру, xij = 0 — в іншому
випадку, або X = {xi} — шуканий результат у векторній формі, множина шуканих
невідомих у вигляді комбінації n номерів вузлів;
S — схема контуру на площині.
Відповідно, для постановки та розв’язання задачі про комівояжера маємо зва-
жений граф (або неорієнтовану мережу), де треба знайти найкоротший замкнений
контур, який складається точно з n дуг і проходить через кожен вузол один лише
раз (це задача про мінімальний гамільтонів контур, що визначена ірландським ма-
тематиком Гамільтоном у 1800-ті роки, яка довгі роки сприймалася як звичайна
головоломка).
Задача оптимізації.
І. Знайти план { }ijX x= та { }iU u= , такі, щоб
ІІ. ЦФ
1 1
min
n n
ij ij
i j
K a x
= =
= ®åå
ІІІ. за обмежень:
О. Г. Додонов, А. І. Кузьмичов
8
а)
1
1
n
ij
i
x
=
=å , з кожного вузла можна вийти 1 раз;
б)
1
= 1
n
ij
j
x
=
å , у кожен вузол можна увійти 1 раз;
ці два обмеження забезпечують умову 1-разового відвіду-
вання кожного міста;
в) 1, , = 2,3,..., ,i j iju u nx n i j n i j- + £ - ¹ , ui, uj — довіль-
ні значення, при i = j i j iju u nx n i j n i j- + £ - = ¹= 0; це обмеження забезпе-
чує неможливість розриву контуру на окремі підконтури та
граничних умов: усі { }0,1ijx Î .
Таким чином, для задачі обходу n міст треба знайти: n2 значень матриці Х,
n – 1 значень вектора U, разом: n2 + n – 1 невідомих із загальним числом обмежень
n2 + 1 (див. табл.). Отже, з допустимим числом невідомих (200) і обмежень (100) в
Excel можна розв’язати задачу комівояжера з числом міст до 13.
Розв’язання задачі комівояжера в Excel
Приклад 1. Симплекс-метод лінійного програмування.
Постановка задачі.
На площині задано координати 6 пунктів, розв’язати задачу комівояжера як
закриту задачу про призначення (кількість претендентів = кількості вакансій).
Математична модель:
І. Знайти план { }ijX x= такий, щоб
ІІ. ЦФ
1 1
min
n n
ij ij
i j
K a x
= =
= ®åå
ІІІ. за обмежень:
а)
1
1
n
ij
i
x
=
=å , з кожного вузла можна вийти 1 раз;
б)
1
1
n
ij
j
x
=
=å , у кожен вузол можна увійти 1 раз;
ці два обмеження забезпечують умову 1-разового відвідування кожного міста та
граничних умов: усі { }0,1ijx Î .
Порядок роботи.
1. Увести назви міст і їхні координа-
ти.
2. Побудувати діаграму Точечная:
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 9
3. Сформувати матрицю відстаней A(6,6) обчисленнями значень aij за фор-
мулою: 2 2( ) ( )ij i j i ja x x y y= - + - , усі діагональні елементи (аіі) = 100 (аналог ¥):
4. Сформувати матрицю Х, знайти суми елементів за рядками та стовпцями й
обчислити значення цільової функції (ЦФ):
5. Сформувати табличну модель задачі про призначення й знайти її розв’язок.
Як і передбачалося, шуканий контур розпався на три підконтури: (1-6-1), (2-3-2),
(4-5-4), які побудовано на діаграмі, значення плану: (х16, х23, х32, х45, х54, х61) = 1,
інші — нулі, ЦФ = 17,34:
6. Вирішуємо розірвати підконтур (1-6-1), для цього формуємо додаткове об-
меження: х16 + х61 £ 1 й уводимо в модель; отримано новий результат, за яким є
два підконтури: (1-3-2-6-1) та (4-5-4), значення ЦФ збільшилося на 0,33:
О. Г. Додонов, А. І. Кузьмичов
10
7. Вирішуємо розірвати підконтур (4-5-4), для цього формуємо друге додат-
кове обмеження: х45 + х54 £ 1 і вводимо в модель; отримано новий результат, за
яким є два підконтури: (1-5-4-1) та (2-3-6-2), значення ЦФ збільшилося на 1,05:
8. Вирішуємо розірвати підконтур (1-5-4-1), для цього формуємо третє додат-
кове обмеження: х15 + х51 + х54 + х45 + х41 + х14 £ 2 і вводимо його в модель; отри-
мано новий результат, за яким знайдено оптимальний контур (1-4-5-3-2-6-1), його
мінімальна довжина (значення ЦФ) дорівнює 19,47:
Висновок: модель лінійного програмування вимагає виконувати багато допо-
міжної роботи щодо визначення підконтурів для розірвання та уведення відповід-
них обмежень.
Приклад 2. Метод «гілок і границь» булевого програмування.
Постановка задачі (див. Приклад 1).
Використовується наведена вище математична модель.
Порядок роботи.
Виконати пункти 1¸5.
6. Сформувати допоміжну матрицю з метою реалізації обмеження (в), вико-
риставши шаблон матриці Х.
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 11
7. Визначити стовпець із 5 клітинок для елементів ui шуканого вектора U,
транспонуванням визначити рядок з 5 клітинок для елементів uj.
8. Сформувати матрицю лівих частин обмежень, на її діагоналі нулі:
9. У табличну модель увести обмеження (в), для цього у вікні Поиск решения:
— у поле Изменяя ячейки додати адреси елементів ui;
— у полі Ограничения: додати обмеження на двійковий тип матриці Х та об-
меження (в);
— у вікні Параметры поиска решения зняти галочку з позиції Неотрицате-
льные значения, оскільки змінна ui може приймати довільні значення.
Результат:
О. Г. Додонов, А. І. Кузьмичов
12
Висновок: цим методом можна знайти зразу
шуканий контур обходу, але за цю можливість ми
«розплачуємося» додатковими обмеженнями, тож
область роботи цього методу суттєво обмежується
граничними значеннями кількості невідомих та об-
межень Excel: до 200 змінних і до 100 обмежень.
Зауваження. В середовищі Excel 2010 у вікно
Параметры поиска решения треба внести такі змі-
ни: для шуканих змінних ui рекомендується внести
певне обмеження, наприклад, не менше 10, далі у
полі Выберите метод решения вибрати Поиск ре-
шения линейных задач симплекс-методом.
Приклад 3. Еволюційний метод.
Цю ж задачу комівояжера для найкоротшого обходу 6 пунктів розв’яжемо за
допомогою методу Эволюционный поиск решения в Excel 2010.
Позначення:
і — поточний номер шуканої змінної (співпадає із номером міста в контурі),
і = 1, …, 6;
Х = {хі} — шуканий вектор невідомих, Х ={x1, x2, x3, x4, x5, x6};
D = {d(i, j)} — вектор відстаней між парами сусідніх вузлів у контурі обходу
розміром з 6 елементів, де )( jпередуєiji p .
Задача оптимізації:
І. Знайти план обходу Х = {хі}, такий, щоб
ІІ. ЦФ: довжина контуру K = min
6
1,
®å
=ji
ijd
ІІІ. За обмежень: хі Î{все разные}.
Порядок роботи.
Повторити пункти 1÷3.
4. Сформувати рядок Х і за-
повнити його порядковими но-
мерами, у наступній (n + 1)-й
клітинці зробити посилання на
1-й елемент цього рядка (щоб
замкнути контур або цикл). Об-
числити відстані між сусідніми
клітинками за допомогою функ-
ції ИНДЕКС й обчислити їхню
суму за допомогою функції
СУММ.
5. Командою Данные ® Поиск решения викликати вікно Параметры поиска
решения і заповнити його поля вказаним чином.
6. Натиснути на Параметры, визначити у цьому вікні режим роботи програ-
ми, ОK і в попередньому вікні натиснути на Найти решение.
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 13
Починається процес обчислень — у рядку стану внизу вікна поступово виво-
диться повідомлення такого вигляду
де видно: нове значення ЦФ, номер підзадачі і попереднє значення ЦФ.
Процес припиняється, коли значення ЦФ не змінюється в межах заданої точ-
ності або вичерпані граничні значення заданих параметрів і пропонується альтер-
натива: Продолжить/Остановить.
Процес оптимізаційного моделювання завершується за командою Остано-
вить.
Результат.
Знайдено оптимальний контур обходу Х = {4, 5, 3, 2, 6, 1, 4} із мінімальною
довжиною 19,47. Результат співпав з усіма попередніми результатами, але отри-
мано його значно швидше з мінімальними витратами часу та розміру документа:
Усі наступні приклади реалізовані за допомогою еволюційного методу, бо з
урахуванням розмірів цих задач альтернативи цьому методу нема. Початковими
даними є координати географічних об’єктів чи тестові дані, що отримані за допо-
могою генератора випадкових чисел.
О. Г. Додонов, А. І. Кузьмичов
14
Приклад 4 (n = 13).
Приклад 5 (n = 22).
Оптимізаційні моделі еволюційного програмування в Excel:
розв’язання задачі комівояжера з обмеженнями alldifferent
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2011, Т. 13, № 3 15
Приклад 6 (n = 100).
Корегування результату.
Доведено [1], що найкоротший замкнений контур, що зв’язує n точок на пло-
щині, є замкненою ламаною зі сторонами, що не перетинаються. Наближений
розв’язок задачі великого розміру може утворити перетини у вигляді петель, тож
їхня заміна ламаними — шлях до покращення шуканого результату.
Приклад 7.
За допомогою еволюційного методу розв’язана задача комівояжера розміром
50×50, значення ЦФ склало величину 289,4, побудована схема контуру (зліва).
На діаграмі визначена петля, яка вручну замінена ламаною, що привело до
зменшеного значення ЦФ величиною 281,3. Відповідний фрагмент оновленої
О. Г. Додонов, А. І. Кузьмичов
16
комбінації номерів уведений у модель, і повторний її запуск підтвердив оновле-
ний результат. Таким чином, для задач великого розміру з’являється можливість
дещо покращити отриманий наближений результат шляхом корекції певних фра-
гментів діаграми у вигляді перетинань.
Приклад 8. Манхетенська метрика.
Задача: обійти 23 пункти на карті Києва, рухаючись вулицями.
Результат.
1. Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати. — М.: Наука, 1974. — 366 с.
2. Васильев В.В. Гибридные модели задач оптимизации / В.В. Васильев, А.Г. Додонов. — К.:
Наук. думка, 1974. — 215 с.
3. Кристофидес Н. Теория графов: Алгоритмический подход / Н. Кристофидес / Пер. с англ.
— М.: Мир, 1978. — 432 с.
4. Fylstra D. Design and Use of the Microsoft Excel Solver / D. Fylstra, L. Lasdon. —
INTERFACES. — 1998. — Vol. 28, N 5. — Р. 29–55.
5. Powell S. The Art of Modeling with Spreadsheets: Management Science, Spreadsheet Engineer-
ing and Modeling Craft / S. Powell, K. Baker. — John Wiley & Sons, 2004. — 400 p.
6. Кузьмичов А.І. Математичне програмування в Excel / А.І. Кузьмичов, М.Г. Медведєв. —
К.: Вид-во Європ. ун-ту, 2005. — 320 с.
7. Кузьмичов А.І. Таблична реалізація генетичного алгоритму пошуку рішень для нелінійних
задач оптимізації / А.І. Кузьмичов // Наук. вісник АМУ. Серія «Техніка». Автоматизація та
комп’ютерно-інтегровані технології управління. — К.: АМУ, 2008. — С. 125–135.
8.Кузьмичов А.І. Таблична реалізація генетичного алгоритму пошуку рішень для «важких»
задач оптимізації / А.І. Кузьмичов // Тр. межд. конф. «Моделирование-2008», ИПМЭ НАНУ. —
2008. — Т. 1. — С. 94–108.
Надійшла до редакції 19.07.2011
|