В рассматриваемом расчетном задании представлена транспортная сеть с конечным числом коммуникаций, состоящая из 11 вершин и 18 дуг, на кожной из которых представлено число, характеризующее расстояние между соседними вершинами, соединенными дугами (рисунок 4.1).
В таблице 4.1 представлены данные, характеризующие мощность пунктов отправления и потребность в товаре в пунктах назначения, которые являются основой для решения поставленной транспортной задачи.
Таблица 4.1 Исходные данные для проведения расчетов.
|
Показатели. | Значения показателей. |
Мощность пунктов отправления. |
П 1. | |
П 6. | |
П 10. | |
Потребность в товаре в пунктах назначения. |
П 2. | |
П 3. | |
П 4. | |
П 5. | |
П 7. | |
П 8. | |
П 9. | |
П 11. | |
Задание: распределить грузопотоки таким образом, чтобы минимизировать расстояние перевозок продукции.
Решение Составим исходный вариант, при котором ресурсы поставщиков должны быть отправлены и спрос потребителей удовлетворен (стрелками на рисунке обозначим направления грузопотоков, а цифрами — количество перевозимой продукции).
Далее вершинам присваиваются потенциалы. Вершине 1 присвоим потенциал 100, назначаем потенциалы остальным вершинам, придерживаясь следующего правила: при продвижении по дугам сети в направлении следования грузопотока к потенциалу предыдущей вершины прибавляем длину дуги, а при движении по дугам против потока эту длину из потенциала предыдущей вершины вычитаем.
Следующим шагом осуществляем проверку выполнение условия оптимальности для всех дуг сети, на которых нет грузопотоков, т. е. соблюдение выражения.
Vj — Ui Cij, (4.1).
где Vj — потенциал, устанавливаемый в пункте потребления,.
Ui — потенциал, устанавливаемый в пункте отправления товара;
Cij расстояние между соседними вершинами.
- 1−10: 110−100 = 10<75 Выполняется;
- 6−10: 110−50 = 60<120 Выполняется;
- 3−11: 210−180 = 30<50 Выполняется;
- 9−10: 150−110 = 40<110 Выполняется.
Все дуги сети выполняют условия оптимальности, значит исходный вариант и является оптимальным вариантом.
