7.10. Некоторые специальные задачи о потоках

В качестве первого примера задач, которые сводятся к задачам о потоках, рассмотрим так называемую транспортную задачу, которой посвящено много работ в литературе по исследованию операций.

Пусть множества пунктов отправления и пунктов получения соответственно, между которыми должен быть распределен некоторый однородный товар. Каждый пункт отправления имеет ограниченный склад А, и каждый пункт получения определенную потребность B (спрос). Известна стоимость перевозки единицы товара из равная В простейшем случае на объемы перевозок из не наложено никаких ограничений (конечно, они не должны нарушать ограничений, накладываемых складами и спросом Задача состоит в отыскании плана перевозок от пунктов отправления к пунктам потребления, имеющего минимальную стоимость, при условиях, что спрос должен быть удовлетворен (но избытков быть не должно) и объем перевозок от данного пункта отправления не должен превышать объемы его склада.

Эту задачу можно рассматривать как задачу нахождения максимального потока, имеющего минимальную стоимость в сети, изображенной на рис. 7.12. (Упорядоченная пара чисел приписанная каждой дуге, представляет пропускную способность дуги и единичную стоимость перевозок Если перевозки из некоторых пунктов в некоторые пункты не разрешаются, то соответствующие дуги в сети просто опускаются. Если имеются ограничения на количество товара, перевозимого из некоторых в некоторые то соответствующим дугам приписывается конечная пропускная способность. В этом случае, конечно, может оказаться, что спрос в пунктах потребления не будет удовлетворен полностью. Однако решая задачу о потоке, мы получим план, позволяющий перевезти максимально возможное количество товара при минимальной стоимости.

Если а соответствуют работникам и видам работ соответственно, то та же самая модель применима для решения задачи о назначениях, в которой требуется назначить работников для выполнения работ так, чтобы оптимально использовались их возможности. (В этом случае под следует понимать меру полезности при назначении работника на работу.) Величины и полагаются равными единице; поэтому каждый работник должен быть назначен максимум на одну работу, каждая работа должна быть

выполнена только одним работником. Если какие-то работники не могут делать некоторых работ, то соответствующие дуги опускаются. Такое ограничение может привести к тому, что не все работы будут выполняться. (В этой задаче пропускные способности дуг можно отбросить, приписывая каждый дуге большие постоянные величины, и после этого производить минимизацию.)

Для двудольных графов рассматривавшаяся в главе 6 задача о максимальном паросочетании также может быть сведена к задаче о нахождении максимального потока в сети типа изображенной на рис. 7.12.

Рис. 7.1

В этом случае все дуги имеют единичную пропускную способность, стоимости не учитываются и решается задача максимизации потока от источни а к стоку. Заметим, что задача увеличения потока с мцью нахождения пути в графе приращений на самом а совпадает с задачей нахождения чередующейся соединяющей две непокрытые вершины, которая бы. описана в разделе 6.14.

Упражнение 7.15. (см. скан)