Двухкритериальные задачи потокового программирования

Abstract

Рассматривается три типа двухкритериальных задач: нахождение кратчайшего пути во множестве путей максимальной ширины, путей максимальной ширины среди множества кратчайших путей и задача о максимальном потоке минимальной стоимости. Построены специальные графы, необходимые для доказательства основных свойств исследуемых моделей. Приведены конструктивные доказательства теорем об оптимальных решениях задач с учетом двух критериев оптимизации. Построены структурные и алгоритмические решения двухкритериальных задач потокового программирования. Three types of two-criteria problems are considered: finding the shortest path in the set of paths of maximum width, the paths of maximum width among the set of shortest paths and the problem of the maximum flow of minimum cost. The special graphs are constructed that are necessary to prove the basic properties of the models under study. Constructive proofs of theorems on optimal solutions to problems are given taking into account two optimization criteria. Structural and algorithmic solutions of twocriteria flow programming problems are constructed.