УПРАЖНЕНИЯ 6.5.3
1. Решите задачу из упражнения 6.5.1.1 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью. Покажите также, что эту задачу можно решить как транспортную.
2. Решите задачу из упражнения 6.5.1.2 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью. Покажите также, что эту задачу можно решить как транспортную.
3. Решите задачу из упражнения 6.5.1.3 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.
4. Решите задачу из упражнения 6.5.1.4 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.
5. Решите задачу из упражнения 6.5.1.5 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.
6. Решите задачу из примера 6.5.3 с помощью симплексного алгоритма для сетей с ограниченной пропускной способностью.
7. Электрическая компания Вайоминга транспортирует по трубопроводам угольную пульпу от трех шахт (1, 2 и 3) к трем электростанциям (4, 5 и 6). Каждый трубопровод может транспортировать не более 10 тонн пульпы в час. Стоимость транспортировки одной тонны пульпы (в долл.), а также предложение шахт и спрос электростанций представлены в следующей таблице.
4 5 6 Предложение
Спрос 16 6 14
Найдите оптимальную схему транспортировки угля к электростанциям.
8. На рис. 6.48 показана сеть из семи городов и расстояния между ними. С помощью симплексного алгоритма для сетей с ограниченной пропускной способностью найдите кратчайший маршрут между городами 1 и 7. (Совет. Пусть узлы 1 и 7 имеют результирующие потоки [+1] и [-1] соответственно, а все остальные - нулевые результирующие потоки.)
Рис. 6.48. Сеть для задачи из упражнения 8
9. Покажите, что симплексный алгоритм вычисления потока минимальной стоимости для сетей с ограниченной пропускной способностью можно применить, чтобы найти максимальный поток в сети (см. раздел 6.4). С его помощью решите задачу из примера 6.4.2. Для определенности положите стоимость прохождения потока от узла 4 к узлу 3 нулевой, остальные данные остаются без изменений.
6.5.4. Решение задачи вычисления потока наименьшей стоимости в Excel
Шаблон Excel, предназначенный для решения общей транспортной задачи (см. раздел 5.3.3), можно применить, чтобы найти поток наименьшей стоимости. На рис. 6.49 показан рабочий лист, на котором решается задача из примера 6.5.4 (файл
2 Входны» дайны»
В С Е F G Н
нахождение потока наименьшей стоимости
Матрица пропускных <
N1 N2 N3 N4 N5
10 35 60 0
17 Оптимальное решение
18 Сщая стоимост,
19 От-в Ш N1-N2
N1 - N3 N1 - N4 N1 -N5 N2-N1 N2-N3 N2-N4 N2- N5 N3-N1 N3-N2 N3- N4 N3-N5 N4- N1 N4-M?
Поток
Пр спос
35 0 0
25 О
30 0 0 О
25 0
9999Э9 10 35 0 0 60 0 30 0 0 0
999999 0
Промежуточные вычисления
Имя Узел
м N2 N3
N4 N5
Поток
40 50 0 -30 -60
Спрос От В Уд стоимость
40 50
-30 60
поиск решения
установить целевую ячейку: равной: С максимальному значению
р минимальному значению изменяя ячейки:
$В$1в
$В$20:$В$39 Ограничения:
$В$20:$В$Э9 <= $С$20:$С$39
значению:
31 Гдпопожить ~~3 Добавить I
Выполнить
Закрыть
Параметры
Изменить ]
Удалить
Восс1ановить 1 Справка I
Рис. 6.49. Поиск потока минимальной стоимости в Excel
ch6SolverMinCostCapacitatedNetwork.xls). Матрица пропускных способностей записана в диапазоне N6:W15.6 Незаполненные ячейки матрицы пропускных способностей показывают, что соответствующие дуги имеют бесконечную пропускную способность. Нулевые значения пропускных способностей вводятся для несуществующих дуг. Матрица удельных стоимостей записана в диапазоне В6:К15. Здесь также нулевые значения вводятся для несуществующих дуг.
После того как будут введены значения пропускных способностей и удельных стоимостей, рабочий лист пересчитывается автоматически.
В диалоговом окне средства Поиск решения целевая ячейки, изменяемые ячейки и ограничения уже заданы. На рис. 6.49 видно, что изменяемые ячейки составляют диапазон В20:В39, а ограничения задаются как F19:F23=G19:G23 (баланс потоков для всех узлов) и В20:В39<=С20:С39 (ограничения пропускных способностей дуг).
Решение N1-N2 = 5, N1-N4 = 35, N2-N3 = 25, N2-N5 = 30, N3-N5 = 25 и N4-N5 = 5, показанное на рис. 6.49, дает общую стоимость потока, равную 490 долл.
УПРАЖНЕНИЯ 6.5.4
1. Решите следующие задачи с помощью средства Поиск решения.
a) Задача из упражнения 6.5.3.3.
b) Задача из упражнения 6.5.3.4.
c) Задача из упражнения 6.5.3.7.
d) Задача из упражнения 6.5.3.8.
На основе сетевых моделей разработано множество методов планирования, составления временных расписаний и управления проектами. Наиболее известные - метод критического пути (Critical Path Method - СРМ), а также система планирования и руководства программами разработок (Program Evaluation and Review Technique - PERT). В этих методах проекты рассматриваются как совокупность некоторых взаимосвязанных процессов (видов деятельности, этапов или фаз выполнения проекта), каждый из которых требует определенных временных и других ресурсов. В методах JCPM и PERT проводится анализ проектов для составления временных графиков распределения фаз проектов. На рис. 6.50 в обобщенной форме показаны основные этапы реализации этих методов. На первом этапе определяются отдельные процессы, составляющие проект, их отношения последовательности (т.е. какой процесс должен предшествовать другому) и длительность. Далее проект представляется в виде сети, показывающей последовательность процессов, составляющих проект. На третьем этапе на основе построенной сети выполняются вычисления, в результате которых составляется временной график реализации проекта.
6.6. МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ
Сеть
Временной график
]-»п Вычисления
Время
н, I-I
Рис. 6.50. Основные этапы выполнения методов СРМ и PERT
На рис. 6.49 строки от 11 до 15 и столбец К скрыты для экономии места.