Самая известная и наиболее широко используемая специальная сетевая структура - это «двудольная» структура, изображенная на рисунке:
Узлы делятся на две группы: одна служит источником потока, а другая - местом назначения. Каждая дуга соединяет источник с пунктом назначения.
Модель перевалки с минимальной стоимостью в этой сети известна как транспортная модель. Каждый путь от источника до пункта назначения в двухсторонней сети состоит из одной дуги. Или, говоря то же самое по-другому, оптимальный поток вдоль дуги транспортной модели дает фактическую сумму, отправленную из некоторого источника в определенный пункт назначения. Это свойство позволяет альтернативно рассматривать транспортную модель, как так называемую модель назначения, в которой оптимальный поток по дуге представляет собой количество чего-либо от начала координат, которое назначено месту назначения. Одним из наиболее распространенных применений модели назначения является сопоставление людей с соответствующими целями, такими как рабочие места, офисы или даже другие люди. Каждый исходный узел связан с одним человеком, а каждый целевой узел - с одной из целей - например, с одним проектом. Наборы могут быть определены следующим образом:
set PEOPLE; set PROJECTS; set ABILITIES within (PEOPLE cross PROJECTS);
Набор ABILITIES играет роль LINKS в наших более ранних моделях. Пара (i,j) помещается в этот набор тогда и только тогда, когда человек i может работать над проектом j.
В качестве одной из возможностей продолжения модели, предложение в узле i может быть количеством часов, которое человек i может работать, а спрос в узле j может быть количеством часов, необходимых для проекта j. Переменные Assign [i,j] будут представлять количество часов времени человека i, выделенного на проект j. Также, с каждой парой (i,j) будет связана стоимость часа и максимальное количество часов, которое человек i может потратить на работу j. Полученная модель показана на рисунке:
set PEOPLE;
set PROJECTS;
set ABILITIES within (PEOPLE cross PROJECTS);
param supply {PEOPLE} >= 0; # hours each person is available
param demand {PROJECTS} >= 0; # hours each project requires
check: sum {i in PEOPLE} supply[i] = sum {j in PROJECTS} demand[j];
param cost {ABILITIES} >= 0; # cost per hour of work
param limit {ABILITIES} >= 0; # maximum contributions to projects
var Assign {(i,j) in ABILITIES} >= 0, <= limit[i,j];
minimize Total_Cost:
sum {(i,j) in ABILITIES} cost[i,j] * Assign[i,j];
subject to Supply {i in PEOPLE}:
sum {(i,j) in ABILITIES} Assign[i,j] = supply[i];
subject to Demand {j in PROJECTS}:
sum {(i,j) in ABILITIES} Assign[i,j] = demand[j];
Другая возможность состоит в том, чтобы сделать назначение людей, а не часов.
Предложение в каждом узле i равно 1 (человек), а спрос в узле j - это количество людей, необходимое для проекта j. Ограничения предложения гарантируют, что Assign [i,j] не больше 1. Оно будет равно 1 в оптимальном решении тогда и только тогда, когда человек i назначен для проекта j. Стоимость коэффициента [i,j] может быть своего рода затратами на назначение человека i на проект j, и в этом случае цель все равно будет заключаться в минимизации общей стоимости. Или коэффициент может быть рейтингом человека i для проекта j, возможно, по шкале от 1 (высший) до 10 (низший). Целью такой модели может стать, наилучшая сумма рейтингов из возможных.
Наконец, мы можем представить себе модель назначения, в которой спрос каждого узла j также равен 1. Тогда задача состоит в том, чтобы подобрать людей для проектов. Для таких задач, cost[i,j] может быть количеством часов, которое понадобится для завершения проекта j, и в этом случае модель найдет задание, которое минимизирует общее количество часов работы, необходимое для завершения всех проектов. Можно создать такую модель, заменив все ссылки на supply [i] и demand [j] на 1 в модели выше. Целевые коэффициенты, представляющие рейтинги, являются вариантом для этой модели, такая формулировка приводит к модели назначения.
