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

Анотація

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

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

Мета статті – показати результативність і достатню спільність такого способу розв’язання комбінаторних задач на графах.

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