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

Автор(и)

  • S. N. Semenets Придніпровська державна академія будівництва та архітектури., Україна https://orcid.org/0000-0003-0477-8795
  • S. S. Nasonova Український державний хіміко-технологічний університет, Дніпропетровськ., Україна https://orcid.org/0000-0002-0920-7417

Ключові слова:

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

Анотація

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


 

 

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

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

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

Біографії авторів

S. N. Semenets, Придніпровська державна академія будівництва та архітектури.

Кафедра прикладної математики, к. т. н, доц.

S. S. Nasonova, Український державний хіміко-технологічний університет, Дніпропетровськ.

Кафедра вищої математики, к. т. н, доц.

Посилання

Johnson J.C., Wood D.F., Vordlou D.L. and Murphy-ml P.R. Sovremennaya logistika [Modern Logistics]. Moskow: Vil'yams, 2002, 615 p. (in Russian).

Lovas L. and Plammer M. Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, khimii [Applicated tasks of graph theory. Matchings theory in mathematics, physics, chemistry]. Moskow: Mir, 1998, 653 p. (in Russian).

Kas'yanov V.N. and Evstigneev V.A Grafy v programmirovanii: obrabotka, vizualizatsiya i primenenie [Graphs in pro- gramming: processing, visualization and application]. Sankt-Peterburg: BKHV Peterburg, 2003, 1104 p. (in Russian).

Kostyukova N.I. Grafy i ikh primenenie. Kombinatornye algoritmy dlya programmistov [Graphs and their application. Combinatorial algorithms for programmers]. Moskow, 2007, 310 p. (in Russian).

Majnika E. Algoritmy optimizatsii na setyakh i grafakh [Optimization algorithms on networks and graphs]. Moskow: Mir, 1981, 323 p. (in Russian).

Kormen T., Lejzerson Ch., Rivest R. and Shtain K. Algoritmy: postroenie i analiz [The algorithms for working with graphs]. Moskow: Vil'yams, 2006, 1296 p. (in Russian).

Zykov A.A. Osnovy teorii grafov [Fundamentals of graph theory]. Moskva: Vuzovskaya kniga, 2004, 664 p. (in Russian).

Gorbatov V.A. Fundamental'nye osnovy diskretnoy matematiki. Informatsionnaya matematika [Fundamentals of dis- crete mathematics. Information Mathematics]. Moskow: Nauka, Fizmatlit, 2000, 544 p. (in Russian).

Berzh K. Teoriya grafov i ee primenenie [Graph theory and its applications]. Moskow: Inostran. lit., 1962, 319 p. (in Russian).

Kofman A. Vvedenie v prikladnuyu kombinatoriku [Introduction to applied combinatorics]. Moskow: Nauka, 1975, 479 p. (in Russian).

Akho A., Khopkroft D. and Ul'man D. Postroenie i analiz vychislitel'nykh algoritmov [Construction and analysis of computational algorithms]. Moskow: Mir, 1979, 536 p. (in Russian).

Basaker R. and Saati T. Konechnye grafy i seti [Finishing graphs and networks]. Moskow: Nauka, 1974, 368 p. (in Rusian).

##submission.downloads##

Номер

Розділ

Наукові дослідження