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

Анотація. В даний час різні графові моделі широко використовуються для формалізації багатьох прикладних задач як технічного, так і економічного характеру, а розробка ефективних методів чисельної реалізації таких моделей являє теоретичний та практичний інтерес. Традиційно для розв’язання комбінаторних задач на графах розробляються спеціальні алгоритми і відповідне програмне забезпечення. Однак, у випадках, коли в постановку задачі вносяться деякі уточнення або доповнення, це, як правило, призводить до необхідності перегляду алгоритмів її розв’язання та програмного забезпечення. Іншим підходом до розв’язання таких задач є застосування офісних інформаційних технологій, інструментальне середовище яких адаптовано для розв’язання оптимізаційних задач. Такий підхід не вимагає розробки спеціальних алгоритмів і програмного забезпечення. Він менш трудомісткий в реалізації, і, тому популярний в широкому колі користувачів. Мета статті – показати результативність та ефективність MS Excel для розв’язання комбінаторних задач на графах. В даній статті на прикладах трьох класичних графових моделей, що застосовуються для формалізації багатьох прикладних економічних задач, розглядаються особливості розв’язання комбінаторних задач на графах в інструментальному середовищі табличного процесора MS Excel. Розглянуті класичні графові моделі, а саме: задача про комівояжера (задача про мінімальний цикл Гамільтона), задача про вартових (задача про найменшу домінуючу множину вершин графу) та задача про максимальний потік в транспортній мережі. Отриманні в статті результати показують, що багато комбінаторних задач на графах можуть бути достатньо легко переформульовані у вигляді задачі лінійного програмування. Доведено, що MS Excel є ефективною офісною інформаційною технологією розв’язання економічних оптимізаційних задач, що сформульовані на графах. Ключові слова: офісні інформаційні технології, граф, модель, алгоритм, оптимізація.