Камешкова. камешкова_TZS_merged (1)_removed. Баланс Запас
 Скачать 0.75 Mb.
|
|
Баланс: Запас Пришло Ушло Разница B1 60 0 60 0 50 B2 -50 50 0 0 B3 -10 10 0 0 B4 -20 20 0 0 10 B5 -20 20 0 0 10 28 32 27 10 25 45 B6 100 0 100 0 B7 -30 30 0 0 B8 50 0 50 0 10 30 B9 -30 30 0 0 B10 -50 50 0 0 10 15 17 20 28 11 35 10 50 30 i j V i V j c ij |V i -V j |-C ij (*) 1 5 100 130 32 -2 4 5 128 130 15 -13 5 9 130 141 20 -9 6 9 88 141 28 25 9 10 141 99 23 19 2 6 140 88 10 42 2 5 140 130 27 -17 2 3 140 113 20 7 3 7 113 118 45 -40 0 42 2 - 6 10 Баланс: Запас Пришло Ушло Разница B1 60 0 60 0 40 B2 -50 50 0 0 B3 -10 10 0 0 B4 -20 20 0 0 10 10 B5 -20 20 0 0 10 28 32 10 27 10 25 45 B6 100 0 100 0 B7 -30 30 0 0 B8 50 0 50 0 30 B9 -30 30 0 0 B10 -50 50 0 0 10 15 17 20 28 11 35 10 50 30 i j V i V j c ij |V i -V j |-C ij (*) 4 5 128 132 15 -11 5 2 132 140 27 -19 5 6 132 130 42 -40 5 9 132 141 20 -11 2 3 140 155 20 -5 3 7 155 160 45 -40 9 10 141 141 23 -23 7 10 160 141 35 -16 0 0 - - - ( ) -10 -20 -20 100 B1 100 B2 140 B3 113 40 20 60 -50 ( ) ( ) ( ) ( ) 50 -30 ( ) ( ) B4 B5 130 15 42 128 Суммарная стоимость плана: F= 5560 ( ) -30 B7 ( ) -50 ( ) 118 30 B6 88 Нарушения условия оптимальности плана Данный план перевозок является не оптимальным оптимальным/ не оптимальным Максимальное нарушение Величина сдвига по циклу 113 141 99 на дуге B8 B9 B10 28 23 ) ( -10 ) B1 B2 B3 40 20 100 140 155 ( 60 ) ( -50 -30 ) B4 B5 B6 B7 15 42 30 128 132 130 160 ) ( 100 ) ( ( -20 ) ( -20 Суммарная стоимость плана: ( 50 ) ( -30 ) ( -50 ) F= 5160 оптимальным/ не оптимальным Максимальное нарушение на дуге Данный план перевозок является Величина сдвига по циклу оптимальным B8 B9 B10 Нарушения условия оптимальности плана 28 23 113 141 141 ЭД-319 ЭД-329 ЭД-339 ЭД-349 ЭД-359 ЭДм-319 ЭДм-329 Задание к работе Найти оптимальный план перевозки груза без ограничения пропускной способности сети. Сеть и стоимости перевозки единицы груза приведены на графе. Данные о запасах и потребностях в грузе приведены в таблице вариантов. 1. Заполните граф сети в соответствии с вариантом группы: между красными скобками внести запасы и потребности узлов, учитывая знак. 2. Составьте опорный план перевозок, начиная с самой левой вершины, на которой имеется запас груза (+). Перевозки следует вносить в зеленые ячейки рядом с дугами. Для обозначения направления перевозок копируйте шаблоны волнистых стрелок, расположенных под графом. Проверьте баланс перевозок для каждой вершины в таблице: заполните колонки «Пришло» и «Ушло» в соответствии с направлениями расставленных стрелок. Колонка «Разница» для правильного плана должна содержать только нулевые значения. При нарушениях баланса исправьте план. Вычислите суммарную стоимость плана F. 3. Проверьте составленный план на оптимальность методом потенциалов. Потенциалы следует внести в зеленые области на вершинах графа. Примите потенциал вершины, с которой начато планирование в п.2, за 100. Вычислите потенциалы оставшихся вершин, двигаясь по загруженным дугам, по правилам: o j i ij V V c , o если вычисление идет в направлении перевозки от известного потенциала к неизвестному, то неизвестный потенциал вычисляется как известный+стоимость, o если вычисление идет в направлении, противоположном перевозке, от известного потенциала к неизвестному, то неизвестный потенциал вычисляется как известный -стоимость. Проверьте правило j i ij V V c для незагруженных дуг. o Если выполняется, то план оптимальный, дальнейшие действия не требуются o Если не выполняется, поставьте символ «*» в зеленую ячейку с отсутствующей перевозкой в направлении с нарушением. Если таких направлений несколько, отметьте «*» наибольшую разницу. Для выявления наибольшего нарушения воспользуйтесь таблицей. Скопируйте область в синей рамке после описания заданий 4, 5. 4. Выполните (при необходимости) цикл перерасчета плана. На дуге, отмеченной «*», будет введена перевозка , с направлением от вершины с меньшим потенциалом к вершине с большим (необходимо добавить синюю стрелку из шаблонов под графом) Образовать замкнутый цикл загруженных дуг, включая отмеченную. Двигаясь по циклу, отметить все перевозки в противопотоках и выберем из них минимальную. Это будет величина сдвига по циклу . Внести ее в ячейку под графом. Вычитая из всех противопотоков и, прибавляя ко всем попутным потокам груза величину , получить новый опорный план задачи. Необходимо удалить стрелку и оставить пустой ячейку исчезнувшей перевозки. Проверить баланс нового плана. Вычислить стоимость нового плана. 5. Повторить пункт 3 для нового плана. |