Задача 2

Решить транспортную задачу методом потенциалов.

Решение

Как видно из таблицы, запасы груза 4+7+15=26 больше суммарных потребностей в данном грузе 9+3+3+2=17. Следовательно, математическая модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт потребления B5 с объемом потребности, равным 26-17=9. Тарифы перевозки груза от всех поставщиков в пункт B5 считаем равными нулю. В результате получаем закрытую модель транспортной задачи.

Сведем данные задачи в стандартную таблицу:

Последовательность дальнейших действий такова:

1.составим распределительную (транспортную) таблицу для закрытой задачи;

2.строим начальный опорный план;

3.вычисляем потенциалы (для занятых поставками клеток);

4.вычисляем оценки (для незанятых клеток).

Если получится хотя бы одна отрицательная оценка, то план неоптимален,

идля клетки с наибольшей (по абсолютной величине) отрицательной оценкой построим цикл пересчета, тем самым улучшив план. Для нового опорного плана повторяем все вычисления, начиная с пункта 3.

Если же все оценки неотрицательны, то план перевозок оптимален, вычислим его стоимость и выпишем матрицу перевозок, не включая в нее фиктивного потребителя.

Составляем распределительную (транспортную) таблицу:

Определим начальный план. Начальный опорный план перевозок будем строить методом минимальной стоимости затрат на перевозку.

Клетки таблицы,в которых записаны поставки – базисные, а остальные клетки – свободные. Полученный план является невырожденным (m+n-1=3+5-1=7). Оценим полученный план перевозок методом потенциалов. К строкам и столбцам матрицы затрат (cij) , оформленной в виде распределительной таблицы подберем числа ui и vj так, чтобы ui+vj=cij для каждой занятой клетки (i,j). Числа ui и vj называются потенциалами.

∆11=15-0-13=2 ∆12=8-0-6=2 ∆15=0-0+3=3 ∆23=12+1-11=2

∆24=14+1-5=10 ∆25=0+1+3=4

∆32=7-3-6=-2 < 0 ∆33=24-3-11=10

План неоптимален, будем его улучшать.

Для клетки (3,2), имеющей отрицательную оценку ∆32=-2, построим цикл. Он будет включать в себя клетки +(3,2), -(2,2), +(2,1), -(3,1). Величина груза, перемещаемого по клеткам цикла λ=min{5,3}=3. Найденную величину прибавим в положительных клетках цикла и вычтем в отрицательных клетках цикла.

L(X)=11*3+5*1+12*7+16*2+7*3+8*1+0*9=183. Произведем перерасчет оценок ∆ij:

∆11=15-0-13=2 ∆12=8-0-4=4 ∆15=0-0+3=3 ∆22=5+1-4=2

∆23=12+1-11=2 ∆24=14+1-5=10 ∆25=0+1+3=4 ∆33=24-3-11=10

Отрицательных оценок нет, следовательно, найден оптимальный план перевозок груза с матрицей объемов перевозок

при этом L(X)=183 ден. ед.