Моделирование комбинаторных задач на графах в терминах задачи математического программирования

Abstract

RU: Постановка проблемы. Различают три основных подхода к решению комбинаторных задач на графах. Первый предусматривает разработку соответствующих алгоритмов на основе методов теории графов. Второй и третий подходы основаны на приведении исходной задачи, сформулированной в терминах графов, к задаче оптимизации. При этом для решения полученной задачи оптимизации в рамках второго подхода разрабатываются соответствующие алгоритмы оптимизации, а в рамках третьего – используются прикладные компьютерные технологии, инструментальная среда которых адаптирована к решению задач оптимизации. Для компьютерной реализации первого и второго подходов требуется специальное программное обеспечение, разработка которого доступна далеко не каждому пользователю. Кроме того, в случае уточнения постановки той или иной типовой задачи на графах (например, путем введения дополнительных ограничений) обычно оказывается необходимой модификация известных алгоритмов ее решения и соответствующая ревизия программного обеспечения. Все это в значительной мере затрудняет на практике проведение численных экспериментов на графовых моделях. Наиболее удобным для широкого круга пользователей является третий подход к решению комбинаторных задач на графах, поскольку он не требует для своей компьютерной реализации разработки специальных алгоритмов и соответствующего программного обеспечения. Однако вопросы согласования получаемой модели оптимизации и возможностей применяемой компьютерной технологии требуют дальнейшей научной и практической проработки. В данной статье рассматривается один из возможных способов реализации третьего подхода к решению комбинаторных задач на графах, предусматривающий приведение исходной графовой модели к задаче математического программирования и последующее решение последней в инструментальной среде надстройки MS Excel «Поиск решения». Цель статьи – показать результативность и достаточную общность такого способа решения комбинаторных задач на графах. Выводы. Полученные в статье результаты показывают, что многие комбинаторные задачи, сформулированные в терминах графов, могут быть достаточно легко переформулированы в виде задачи математического программирования. Получаемая при этом оптимизационная модель, как правило, оказывается линейной относительно неизвестных. Для численной реализации таких моделей хорошо приспособлена надстройка MS Excel «Поиск решения», что делает табличный процессор Excel эффективной компьютерной технологией решения комбинаторных задач на графах даже в случае их достаточно большой размерности

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

EN: Raising of problem. To the decision of combinatorics tasks on columns distinguish three basic approaches. The first envisages development of corresponding algorithms on the basis of methods of theory of the graphs. Second and third approaches are based on bringing the initial task over, set forth in terms of counts, to the task of optimization. Thus for the decision of the got task of optimization within the framework of the second approach the proper algorithms of optimization are developed, and within the framework of the third – the applied computer technologies the instrumental environment of which is adapted to the decision of tasks of optimization are used. For computer realization of the first and second approaches the special software development of which is accessible to far not every user is required. In addition, in the case of clarification of raising of one or another model task on columns (for example, by introduction of additional limitations) usually modification of the known algorithms of its decision and proper revision of software appears necessary. All this makes it very difficult in practice, the implementation of numerical experiments on a graph model. The most convenient for a wide range of users is a third approach to the solution of combinatorial problems on graphs, since it does not require for its computer implementation, the development of specific algorithms and software. However, issues of harmonization and optimization of the resulting model the ability to apply computer technology require further research and practical study. In this article one of possible methods of realization of the third going is examined near the decision of combinatorics tasks on columns, envisaging bringing an initial count model over to the task of the mathematical programming and subsequent decision of the last in an instrumental environment building on of Excel "Solver".

Purpose of the article – to show effectiveness and sufficient community of such method of decision of combinatorics tasks on columns.

Conclusion. The results got in the article show that many combinatorics tasks set forth in terms of counts, it is undifficult reformulate as a task of the mathematical programming. The optimization model got here, as a rule, appears linear relatively unknown. For numeral realization of such models building on of MS Excel is well adjusted "Solver", that does the tabular processor of Excel effective computer technology of decision of combinatorics tasks on columns even in case of their large enough dimension