Графический метод решения задач комбинаторной оптимизации

Предлагается графический метод решения задач комбинаторной оптимизации, которые допускают декомпозицию и использование принципа оптимальности Беллмана при их решении. В отличие от алгоритмов динамического программирования, использующих тот же принцип, в графическом алгоритме все возможные состояния системы рассматриваются не отдельно, а группами. Это становится возможным, если принимать во внимание аналитический вид целевой функции, т.е. работать с “графиком” функции, преобразовывая его на каждой стадии аналитически. Графический метод позволяет значительно сократить трудоемкость решения некоторых задач и строить эффективные аппроксимационные схемы. Результаты численных экспериментов свидетельствуют об эффективности графического метода.

Статья представлена к публикации членом редколлегии: А. А. Лазарев