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

заказ №38669

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

Решение.

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