На этом шаге мы рассмотрим пример сетевой модели.
Рассмотрим сеть G = (N, A) с ограниченной пропускной способностью, где N - множество узлов, A - множество дуг. Обозначим:
- xij - величина потока, протекающего от узла i к узлу j,
- uij (lij) - верхняя (нижняя) граница пропускной способности дуги (i, j),
- cij - стоимость прохождения единицы потока по дуге (i, j),
- fi - величина "чистого" результирующего потока, протекающего через узел i.
На рисунке 1 показано, как на схемах сетей будем отображать определенные параметры дуг. Метка [fi] указывает положительное (отрицательное) значение предложения (спроса), соответствующего узлу i:
Рис.1. Отображение параметров дуг
Рассмотрим пример построения сетевой модели.
Пример. Компания GrainCo снабжает зерном из трех зернохранилищ три птицеводческие фермы. Предложение зернохранилищ составляет 100, 200 и 50 тысяч тонн зерна, а спрос ферм - 150, 80 и 120 тысяч тонн соответственно. Компания может транспортировать зерно по железной дороге, за исключением трех маршрутов, где используется автомобильный транспорт.
Рис.2. Схема маршрутов
На рисунке 2 показаны возможные маршруты между зернохранилищами и птицеводческими фермами. Зернохранилища представлены узлами 1, 2 и 3; их предложения указаны метками [100], [200] и [50] соответственно. Фермы обозначены узлами 4, 5 и 6 с величинами спроса [-150], [-80] и [-120]. Маршруты транспортировки зерна показаны на рисунке 2 дугами, соединяющими узлы сети. Дуги (1, 4), (3, 4) и (4, 6) соответствуют автомобильным маршрутам. Эти маршруты имеют верхние и нижние границы пропускных способностей. Например, по маршруту (1, 4) можно провести от 50 до 80 тысяч тонн зерна. Другие маршруты соответствуют железнодорожному транспорту, пропускная способность которого практически не ограничена. Стоимость транспортировки одной тонны зерна показана возле каждой дуги.
На следующем шаге мы рассмотрим сетевую модель как задачу линейного программирования.
