Постановка сетевых задач коммерческой деятельности

Задача о максимальном потоке

Коммерческая деятельность заполнена движением товарных и финансовых потоков, образующих сети взаимодействий организаций и предприятий и являющихся жизненно необходимой составляющей торгово-экономической сферы. Причем чем выше сложность этих потоков, тем больше прибыль участников операций. В этом случае задачу о максимальном потоке можно представить в виде двухполюсной сети S=(N, IP) с одним входом (источником) s е N и выходом (стоком) t е Ny дуги сети (i,j) е f/имеют ограниченную пропускную способность Су. Задача о максимальном потоке заключается в поиске таких потоков (р(/ по дугам (i,j) сети, чтобы результирующий поток из источника в сток являлся максимальным.

Математическая модель задачи о максимальном потоке выглядит следующим образом:

найти такие значения еру, при которых

при ограничениях

Для решения этой задачи может быть использован метод построения увеличивающих цепей.

Задача о потоке минимальной стоимости

В коммерческой деятельности существует большое число ограничений на каждом этапе операции — по объемам поставки товаров, но размерам пересылки платежей и др. Вполне естественно стремление к минимальным затратам в сети товарно-денежных потоков. Поэтому задачу о потоке минимальной стоимости выполнения операций можно представить в виде двухполюсной сети S = (N, U) с источником s и стоком t.

Для каждой дуги (i,j) е Uзаданы пропускная способность Су и стоимость доставки по ней единицы потока г. Необходимо найти поток от источников в сток заданной величины V, имеющей минимальную стоимость доставки. Очевидно, при этом поток V не должен превышать максимальной вели- чины VW

Математическая модель задачи имеет следующий вид:

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >