|
там картинки, они сюда не закачиваются....
Пример решения ТЗ на сети
Найдем оптимальный поток для сети, изображенной на
рис. 16.1.
Построим начальный допустимый невырожденный поток . В данном простом случае мы можем не прибегать к решению вспомогательной задачи, а построить поток исходя из требований допустимости и невырожденности.
Рис. 16.1
Необходимо каким-либо способом развезти весь объем произведенного продукта из пунктов производства в пункты потребления (это возможно, так как сеть сбалансирована и суммарный объем производства равен суммарному объему потребления). При этом по требованию допустимости объем производства в каждом пункте должен быть равен разнице между количеством вывозимого и ввозимого в него продукта, а по требованию невырожденности количество перевозок должно быть на одну меньше количества пунктов в сети, и в каждый пункт должна входить (или из каждого пункта должна выходить) хотя бы одна перевозка.
Выберем любой исходный пункт, например, пункт 2 с объемом производства равным 3 (крайний слева) (см. рис. 16.1). Вывезем весь произведенный в нем продукт в пункты 3 и 7 в количестве 2 и 1 единицы соответственно (выбор пунктов назначения произволен: можно было бы, например, вывезти все 3 единицы в пункт 1. Перевозки будем обозначать жирными линиями, их величины подписывать рядом в квадратных рамках. Условие баланса для пункта 2 выполнено: объем производства в нем равен количеству вывезенного из него продукта: 3 = 2 + 1 (при этом в него ничего не ввозится). В пункте 7 существовала потребность в продукте в количестве 1 (объем производства –1). Теперь в него ввезена 1 единица продукта из пункта 2. Потребность полностью удовлетворена, продукт полностью потреблен. Условие баланса в пункте 7 вы-полнено: объем производства в нем равен количеству ввезенного в него продукта со знаком минус –1 = –1 (при этом из него уже нечего вывозить). В пункте 3 производится 2 единицы продукта; кроме того, в него ввозится 2 единицы из пункта 2. Таким образом, в пункте 3 скапливается 2 + 2 = 4 единицы продукта, которые необходимо из него вывезти для соблюдения условия баланса. Вывозить мы можем в пункты 7 и 4. В пункте 7 потребность в продукте полностью удов-летворена: нет смысла туда его везти (все равно придется потом его оттуда вывозить). Поэтому мы везем все 4 единицы из пункта 3 в пункт 4. Условие баланса в пункте 3 выполнено: 2 (произведено) = 4 (вывезено) – 2 (ввезено). В пункте 4 потребляется только 2 единицы продукта из 4, остальные ве-зем дальше в пункт 5. В пункте 4 условие баланса соблюдено: –2 =
=2 – 4. В пункте 5 потребность в 4 единицы продукта удовлетворяется 2 единицами продукта лишь частично, остается потребность еще в 2 единицах. Их необходимо откуда-нибудь ввезти, например из пункта 6. Уравнение баланса для пункта 5: –4 = –(2 + 2) (из пункта ничего не вывозится). В пункте 6 имеется потребность в 5 единицах продукта; кроме того, из него вывозится 2 единицы в пункт 5. Значит, в него необходимо ввезти 7 = 5 + 2 единицы продукта, например из пункта 1. Тогда условие баланса для пункта 6: –5 = 2 – 7. В пункте 1 производится 7 единиц продукции, и все 7 единиц вывозятся из него в пункт 6. Таким образом, и для пункта 1 условие баланса выполнено: 7 = 7 (в пункт ничего не ввозится). Итак, весь продукт развезен теперь из пунктов производства в пункты потребления. На рис. 16.2 построен допустимый поток.
Рис. 16.2
Проверим, является ли построенный поток невырожденным. Очевидно, нет, так как количество введенных перевозок (2,3), (2,7), (3,4), (4,5), (6,5) и (1,6) равно шести (а перевозок должно быть на единицу меньше, чем пунктов в сети, т.е. семь), и не все пункты соединены перевозками (пункт 8). Необходимо ввести фиктивную перевозку нулевой величины. Она не сможет изменить условия баланса для пунктов сети. Так как у нас только пункт 8 не соединен с другими пунктами перевозками, новая фиктивная перевозка должна либо входить в него, либо выходить из него. Это может быть перевозка (1,8), (7,8), (8,4), (8,5) или (8,6). Выбор
совершенно произволен. Введем, например, перевозку (7,8)
(рис. 16.3).
Рис. 16.3
Теперь начальный допустимый невырожденный поток построен. Переходим к последовательным итерациям.
Итерация 1:
1. Вычислим потенциалы пунктов сети. Потенциал приравниваем к нулю ( ). Остальные потенциалы вычисляются по правилу (см. рис. 16.3).
Пункт 1 соединен перевозкой только с пунктом 6. Потенциал в пункте 6: .
В н и м а н и е! Прибавляем к потенциалам не величины перевозок (заключенные в квадратные рамки), а стоимости перевозок единицы продукции по коммуникациям.
Далее:
,
,
,
,
,
.
2. Проверим, является ли поток через сеть оптимальным.
Для каждой коммуникации должно выполняться усло-
вие . В противном случае вычисляем невязки . Не будем рассматривать коммуникации, по которым введены перевозки: потенциалы пунктов, которые они соединяют, вычислялись по формулам, предполагающим автоматическое соблюдение условий оптимальности.
(2,1): . Критерий оптимальности для коммуникации (2,1) выполняется. Поставим на рис. 16.3 «плюс» в кружочке рядом с коммуникацией;
(1,7): . Критерий оптимальности не выполняется. Вычислим невязку и проставим ее в кружочке рядом с коммуникацией;
(1,8): . Критерий не выполняется. Невязка ;
(8,6): . Критерий выполняется;
(8,5): . Критерий выполняется;
(8,4): . Критерий выполняется;
(7,4): . Критерий выполняется;
(3,7): . Критерий выполняется.
3. Построим новый поток по сети. У нас только две коммуникации (1,7) и (1,8) имеют невязки. Обе невязки равны 2. Вводим нулевую перевозку по любой из этих коммуникаций, например (1,7). Возникает контур, изображенный на рис. 16.4 (в кружках проставлены номера пунктов). Помечаем «+» вновь вводимую перевозку (1,7), а также перевозки (2,3), (3,4) и (4,5), направленные в ту же сторону. Оставшиеся перевозки (2,7), (6,5) и (1,6) помечаем «–». Среди них перевозка (2,7) имеет минимальную величину 1. Прибавляем её к величине перевозок «+», и вычитаем из величины перевозок «–». Зачеркиваем старые значения величин перевозок на рисунке и записываем новые. Перевозка (2,7) стала теперь нулевой. Ее мы исключаем из контура. Сеть с получившимся новым потоком изображена на рис. 16.5.
Рис. 16.4
Рис. 16.5
Итерация 2:
1. Вычислим потенциалы пунктов сети:
,
,
,
,
,
,
,
.
2. Проверим, является ли поток через сеть оптимальным:
(2,1): . Критерий выполняется;
(2,7): . Критерий выполняется;
(1,8): . Критерий выполняется;
(8,6): . Критерий выполняется;
(8,5): . Критерий не выполняется. Невязка ;
(8,4): . Критерий выполняется;
(7,4): . Критерий выполняется;
(3,7): . Критерий выполняется.
3. Строим новый поток по сети. Только коммуникация (8,5) имеет невязку величиной 1. Вводим нулевую перевозку по этой коммуникации. Возникает контур, изображенный на рис. 16.6. Помечаем «+» вновь вводимую перевозку (8,5), а также перевозки (1,7) и (7,8), направленные в ту же сторону. Оставшиеся перевозки (6,5) и (1,6) помечаем «–». Среди них перевозка (6,5) имеет минимальную величину 1. Прибавляем эту величину к величине перевозок «+», и вычитаем из величины перевозок «–». Исключаем перевозку (6,5), ставшую нулевой, из контура. Сеть с новым потоком изображена на рис. 16.7.
Рис. 16.6
Рис. 16.7
Итерация 3:
1. Вычислим потенциалы пунктов сети:
,
,
,
,
,
,
,
.
2. Проверим, является ли поток через сеть оптимальным:
(2,1): . Критерий выполняется;
(2,7): . Критерий выполняется;
(1,8): . Критерий выполняется;
(8,6): . Критерий выполняется;
(6,5): . Критерий выполняется;
(8,4): . Критерий выполняется;
(7,4): . Критерий выполняется;
(3,7): . Критерий выполняется.
Поток через сеть оптимален (выполнены все критерии оптимальности). Переходим к завершающему шагу 4.
4. Вычислим величину транспортных расходов при оптимальном потоке
|
Приведите текст здесь.