Составьте оптимальный план перевозок - такой

Для решения задачи необходимо выполнение следующего условия: суммарные запасы пунктов отправления должны равняться суммарной потребности пунктов назначения.
i=13ai=30+90+80=200 i=13bi=45+50+105=200
Уравнение баланса выполнено, следовательно, это транспортная задача закрытого типа
Определим начальный план перевозок. Используем для этого метод минимальной стоимости:
Для каждого шага выбираем наименьшую стоимость перевозки в таблице с ненулевыми потребностями потребителей и запасами поставщиков.
Шаг 1
a13=1 min30,105=30 A1=30-30=0 B3=105-30=75
Поставщики Потребители Запасы
B1
B2
B3
A1
3 7 1[30] 0
A2
3 4 1 90
A3
7 1 2 80
Потребности 45 50 75 200
Шаг 2
a23=1 min75,90=75 A2=90-75=15 B3=75-75=0
Поставщики Потребители Запасы
B1
B2
B3
A1
3 7 1[30] 0
A2
3 4 1[75] 15
A3
7 1 2 80
Потребности 45 50 0 200
Шаг 3
a32=1 min50,80=50 A3=80-50=30 B2=50-50=0
Поставщики Потребители Запасы
B1
B2
B3
A1
3 7 1[30] 0
A2
3 4 1[75] 15
A3
7 1[50] 2 30
Потребности 45 0 0 200
Шаг 4
a21=3 min15,45=15 A2=15-15=0 B1=45-15=30
Поставщики Потребители Запасы
B1
B2
B3
A1
3 7 1[30] 0
A2
3[15] 4 1[75] 0
A3
7 1[50] 2 30
Потребности 30 0 0 200
Шаг 4
a21=3 min15,45=15 A2=15-15=0 B1=45-15=30
Поставщики Потребители Запасы
B1
B2
B3
A1
3 7 1[30] 0
A2
3[15] 4 1[75] 0
A3
7[30] 1[50] 2 0
Потребности 0 0 0 200
Весь груз распределен, все потребители обеспечены . Получено решение задачи методом минимальной стоимости.
Стоимость доставки для полученного решения составит:
Z=30∙1+15∙3+75∙1+30∙7+50∙1=410
Количество занятых клеток равно 5, что говорит о невырожденности плана.
Проверим оптимальность полученного решения.
Проведем оценку каждой свободной клетки, составив для нее цикл, начало которого находится в свободной клетке, а все вершины в занятых клетках, а по нему - знакочередующуюся сумму тарифов клеток, входящих в этот цикл; если эта оценка окажется для какой-то клетки неотрицательной, ее невыгодно включать в новый план, если же она окажется отрицательной, то рассматриваемый план не оптимален и эту клетку целесообразно включить в новый, более выгодный план.
3 7 1[30]
3[15] 4 1[75]
7[30] 1[50] 2
α11=a11-a13+a23-a21=3-1+1-3=0
α12=a12-a13+a23-a21+a31-a32=7-1+1-3+7-1=10
α22=a22-a32+a31-a21=4-1+7-3=7
α33=a33-a23+a21-a31=2-1+3-7=-3
Так как оценка α33 отрицательна, то план неоптимальный.
Произведем улучшение плана