Ai Bj B1 B2 B3 B4 Потребность/наличие 10 55 20 55 A1 30 1 2 5 3 А1=20 0 А2=30 А3=50 В1=10 В2=20 В3=40 В4=30 417 A2 60 1 6 5 2 A3 50 6 3 7 4 (Решение → 8551)

заказ №38669

Ai Bj B1 B2 B3 B4 Потребность/наличие 10 55 20 55 A1 30 1 2 5 3 А1=20 0 А2=30 А3=50 В1=10 В2=20 В3=40 В4=30 417 A2 60 1 6 5 2 A3 50 6 3 7 4

Решение

. Мы имеем закрытую транспортную задачу, т.к. суммарная потребность 10+55+20+55 = 140 равна суммарному наличию груза 30+60+50=140. Чтобы задача была невырожденной, план должен включать 3+4-1 = 6 перевозок, т.е. нужно заполнить 6 клеток таблицы. Первоначальный план перевозок построим методом наименьших затрат: в первую очередь заполняем клетки с наименьшими тарифами. В клетку А1В1 с тарифом 1 поставим меньшее из чисел(30; 10) т.е. наличие/потребность: А1В1=10. Теперь столбец В1 можно исключить из рассмотрения. Оставшиеся 30-10=20 единиц груза из пункта отправления А1 перевезем в пункт назначения В2( у него следующий по величине тариф в строке): А1В2=20. Оставшуюся потребность пункта В2 покроем перевозкой из пункта А3(там тариф ниже): А3В2=55-20=35. В клетку А2В4 с тарифом 2 поставим меньшее из чисел(60; 55) т.е. наличие/потребность: А2В4=55. Теперь столбец В4 тоже можно исключить из рассмотрения. В пункте отправления А2 останется еще 60-55=5 единиц груза – отправим их в пункт В3: А2В3=5. Туда же в пункт назначения В3 перевозим остаток груза из А3: А3В3= 50-35 = 15. Получим первоначальный план перевозок: Ai Bj B1 B2 B3 B4 Потребность/наличие 10 55 20 55 A1 30 1 10 2 20 5 3 A2 60 1 6 5 5 2 55 A3 50 6 3 35 7 15 4 Заполнено 6 клеток, все ресурсы распределены, все потребности удовлетворены. Стоимость перевозок по этому плану равна: S0 = 1*10+2*20+3*35+5*5+7*15+2*55 = 395 Проверим полученный план на оптимальность. Для этого рассчитаем потенциалы заполненных клеток, составив систему: а1+в1 = 1 а1+в2 = 2 а3+в2 = 3 а3+в3 = 7 а2+в3 = 5 а2+в4 = 2 Т.к. уравнений 6, а неизвестных 7, система неопределенная, для определенности примем а1=0. Находим: в1=1-0=1; в2 = 2-0 = 2 а3 = 3-2=1; в3=7-1 =6; а2=5-6 = -1; в4 = 2-(-1) = 3; . 418 Теперь для свободных клеток рассчитаем разности между фактическими и потенциальными тарифами: Δij = Cij –(ai +вj). Если такая разность отрицательна, то заполнение этой клетки уменьшит стоимость перевозки, т.е. улучшит план. Δ13 =5 – (0+6) = -1; Δ14 =3 – (0 +3) = 0; Δ21 = 1 – (-1+1) =1; Δ22 =6 – (-1+2) = 5; Δ31 = 6 – (1 +1) = 4; Δ34 = 4 – (1+3) = 0. Т.к. Δ13< 0, первоначальный план не является оптимальным. Для его улучшения нужно заполнить клетку А1В3. Составим цикл перевозки так, чтобы все остальные вершины были в заполненных клетках: