Пример 1. Сетевая транспортная задача Реальные коммуникационные процессы, в частности перевозки груза, осуществляют, как правило, по транспортным (железнодорожным или автомобильным) сетям, которые представляют собой сетку, состоящую из приблизительно одинакового количества пунктов приема-отправления (станций) и участков между этими пунктами. Их количество в отдельном регионе измеряется несколькими десятками (типичные примеры: обеспечение тепловых электростанций углем, сахарных заводов – сырьем, элеваторов – зерном).
Для отдельных участков между пунктами приема-отправления устанавливаются затраты (тарифы), поэтому данные о затратах на перевозку в сетевом варианте достигают большого объема. Следовательно, актуальным становится умение решать транспортные задачи именно в сетевой постановке, где для построения математической модели используют аппарат теории графов. Сетевые транспортные модели благодаря своим универсальным свойствам могут легко выйти за границы линейных моделей, если, скажем, нужно учесть реальный порядок оплаты транспортных услуг, которые по своей природе являются нелинейными. Постановка задачи
В границах экономического региона удовлетворить спрос на определенный продукт оптимальным способом (критерий – минимум общих затрат на перевозку), используя распределенные в территориальном пространстве предложения и существующую транспортную сеть (12 пунктов + 22 участка). Экономико-математическая модель
Найти поток распределения продукта таким образом, чтобы:
Общие затраты = Поток*Затраты → min
при ограничениях:
Выход – Вход (Сума) = Спрос / Предложение;
все Потоки >= 0.
44 Таблица 6.1 – Исходные данные для сетевой транспортной задачи
Узлы
|
|
| Дуги
| Узел
| Сп/Пр
| Т-цена
| Вход
| Выход
| Сума
| Остаток
|
| Поток
| Н-стоим
| Начало
| Конец
| Зат-раты
| Всего
| Киев
| 100
|
|
|
|
|
|
|
|
| Киев
| Минск
| 4
|
| Минск
| -5
|
|
|
|
|
|
|
|
| Киев
| Варшава
| 6
|
| Варшава
| -40
|
|
|
|
|
|
|
|
| Киев
| Талин
| 3
|
| Талин
| -6
|
|
|
|
|
|
|
|
| Минск
| Париж
| 3
|
| Москва
| 21
|
|
|
|
|
|
|
|
| Варшава
| Париж
| 2
|
| Осло
| 9
|
|
|
|
|
|
|
|
| Париж
| Варшава
| 2
|
| Берлин
| 6
|
|
|
|
|
|
|
|
| Талин
| Варшава
| 3
|
| Мюнхен
| 4
|
|
|
|
|
|
|
|
| Варшава
| Талин
| 3
|
| Лондон
| -7
|
|
|
|
|
|
|
|
| Варшава
| Осло
| 6
|
| Париж
| -10
|
|
|
|
|
|
|
|
| Талин
| Москва
| 3
|
| Вена
| -25
|
|
|
|
|
|
|
|
| Москва
| Осло
| 3
|
| Даос
| -32
|
|
|
|
|
|
|
|
| Осло
| Мюнхен
| 4
|
|
|
|
|
|
|
|
|
|
|
| Осло
| Берлин
| 3
|
|
|
|
|
|
|
|
|
|
|
| Париж
| Мюнхен
| 6
|
|
|
|
|
|
|
|
|
|
|
| Париж
| Лондон
| 5
|
|
|
|
|
|
|
|
|
|
|
| Париж
| Вена
| 8
|
|
|
|
|
|
|
|
|
|
|
| Мюнхен
| Лондон
| 3
|
|
|
|
|
|
|
|
|
|
|
| Мюнхен
| Даос
| 4
|
|
|
|
|
|
|
|
|
|
|
| Берлин
| Даос
| 7
|
|
|
|
|
|
|
|
|
|
|
| Лондон
| Вена
| 3
|
|
|
|
|
|
|
|
|
|
|
| Даос
| Вена
| 3
|
|
|
|
|
|
|
|
|
|
|
| Вена
| Даос
| 3
|
|
|
|
|
|
|
|
|
|
|
|
| Об_затраты=
|
|
Реализация в Excel
Введите исходные данные согласно табл. 6.1.
Выделите диапазон I4:I25.
В ячейку N4 введите формулу:
=Поток*Затраты или =I4*M4. ОК.
С помощью маркера скопируйте формулу до конца ряда.
Вычислите значение целевой ячейки (Об_Затраты) по формуле:
=СУММ(N4:N25).
В таблице для узлов вычислите сумму входящих (Вход) и выходящих (Выход) потоков, их алгебраическую сумму (Выход-Вход), задайте колонку правых ограничений (Сп/Пр). Для вычисления потока в узлах используется функция вычисления суммы величин, координаты которых удовлетворяют определенному условию (то есть если определенная величина принадлежит соответствующему множеству).
В Excel такую процедуру исполняет функция =СУММЕСЛИ(). Например, сумма входящих потоков узла определяется по формуле:
=СУММЕСЛИ(Все концы дуг; узел; потоки),
то есть суммируются потоки по тем дугам, концы которых совпадают с поточным узлом.
В ячейку D4 введите формулу:
=СУММЕСЛИ($L$4:$L$25;A4;$I$4:$I$25). ОК.
С помощью маркера скопируйте формулу до конца ряда.
В ячейку Е4 введите формулу:
=СУММЕСЛИ($K$4:$K$25;A4;$I$4:$I$25). ОК.
С помощью маркера скопируйте формулу до конца ряда.
В ячейку F4 введите формулу: E4-D4.
С помощью маркера скопируйте формулу до конца ряда.
В ячейку G4 введите формулу: B4-F4.
С помощью маркера скопируйте формулу до конца ряда.
Результат представлен на рис. 6.2.
Запустите программу Поиск решений командой Сервис/Поиск решения (рис. 6.3).
Рис. 6.2
Рис. 6.3
В поле Установить целевую ячейку введите абсолютный адрес ячейки $N$26.
В поле Изменяя ячейки введите абсолютный адрес диапазона $I$4:$I$25.
В поле Ограничения введите $F$5:$F$15= =$B$5:$B$15 (Сумма=Спрос/Предложение).
Так как это линейная модель, то зафиксируйте в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажмите кнопку Выполнить и в появившемся окне Результаты поиска решения выведите Отчет по устойчивости.
Результат представлен на рис. 6.4.
Рис. 6.4 Анализ результата
План перевозок (рис. 6.4) имеет минимальную стоимость в размере 1064 ден. ед. Нормированные стоимости нулевых потоков (Н-стоим) указывают на увеличение затрат при принудительном включении соответствующих дуг в маршрут. Теневые цены потенциалов узлов (Т-цена) указывают на изменение величины общих затрат при соответствующем изменении потенциала узла.
|