Организация маршрутов перевозок грузов и построение эпюр

     Заполним  матрицу транспортной задачи и с  помощью метода минимального элемента определим первоначальный план перевозок.

     Таблица 1.4. План перевозок грузов

     Суммарный холостой пробег составит:

     I_x = 6*500+4*1000+24*750+750*10+500*19+10*500+14*500 =

     = 54000 км

     При нахождении опорного плана методом  минимального элемента, выбираем клетку с минимальным   – это . Далее выбираем наименьший из объемов груза:

     Т.к. потребность грузополучателя Б₂ и грузоотправителя А₃ полностью удовлетворена, то остальные клетки по строке и столбцу не принимаются во внимание. Далее выбираем следующий минимальный элемент - :

     Т.к. потребность грузополучателя Б₁ удовлетворена полностью, а у грузоотправителя А₅ еще осталось 500 ед. ресурсов, которые он отвезет грузополучателю Б_4, т.к. у него наименьший тариф в строке.

     Т.к. ресурсы грузоотправителя А₅ исчерпаны, а потребность грузополучателя Б₄ полностью не удовлетворена, то продолжим ее удовлетворение за счет грузоотправителя А₁. Далее расчет производится аналогично.

     Проверим  полученный план на оптимальность. Результат  отразим в таблице 1.5.

     Вычислим  потенциалы грузоотправителей (U_i) и грузополучателей (V_j). Затем вычисляем оценки для свободных клеток. Т.к. некоторые оценки отрицательны, то план не является оптимальным.

     Из  всех отрицательных оценок имеет  смысл выбрать наибольшую по модулю (выделена цветом), так как ее воздействие  на общие затраты является максимальным. В соответствующую ячейку транспортной таблицы мы должны переместить некоторое количество груза т.е. загрузить ее. Отметим в транспортной таблице ячейку А₄Б₄ знаком +. Кроме нее мы пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и - .То есть помеченные знаками клетки должны образовывать цикл. Т.к. задача вырожденная, чтобы избежать этого, нарушаем баланс запасов и заявок на e (бесконечно малое число) в 3 и 4 строках, не нарушая общего баланса. 
 

     Таблица 1.5. Уточненный план перевозок грузов

     Получился замкнутый цикл. Он содержит клетки А₄Б_4, А₄Б_3, А₅Б_3, А₅Б_4. Т.к. для клеток А₄Б₃ и А₅Б₄ минимальный объем перевозок равен 500 тонн, то отнимать и прибавлять будем его. В результате клетка А₄Б₄ становится загруженной, а клетка А₅Б₄ пустой. Получаем матрицу с новым планом перевозок.

     Таблица 1.6. Матрица с планом перевозок  грузов

     Суммарный холостой пробег составит:

     I_x = 6*500+4*1000+24*250+500*21+10*750+500*16+10*500+14*500 =

     = 51000 км

     Аналогично  предыдущим расчетам проверим полученный план на оптимальность. Полученный план не является оптимальным, т.к. оценки некоторых свободных клеток отрицательные. Выбираем клетку с наибольшим по модулю отрицательным значением – А₂Б₄. Тогда клетки А₁Б₄, А₁Б₅, А₂Б₃, А₂Б₄ образуют замкнутый цикл. Получим матрицу с планом перевозок.

     Таблица 1.7. Оптимальный план перевозок грузов