Ai Bj B1 B2 B3 B4 Потребность/наличие 50 90 90 70 A1 110 7 8 5 3 A2 110 2 4 5 9 A3 80 6 3 1 2 (Решение → 8454)

заказ №38669

Ai Bj B1 B2 B3 B4 Потребность/наличие 50 90 90 70 A1 110 7 8 5 3 A2 110 2 4 5 9 A3 80 6 3 1 2

Решени

е. Мы имеем закрытую транспортную задачу, т.к. суммарная потребность 50+90+90+70 = 300 равна суммарному наличию груза 110+110+80=300. Чтобы задача была невырожденной, план должен включать 3+4-1 = 6 перевозок, т.е. нужно заполнить 6 клеток таблицы. А1=6 А2=13 0 А3=9 В1=3 В2=8 В3=6 В4=11 0 429 Первоначальный план перевозок построим методом наименьших затрат: в первую очередь заполняем клетки с наименьшими тарифами. В клетку А3В3 с тарифом 1 поставим меньшее из чисел(80; 90) т.е. наличие/потребность: А3В3=80. Теперь строку А3 можно исключить из рассмотрения. Заполняем клетку А2В1 с наименьшими затратами =2, ставим в нее А2В1 = min(110; 50) = 50. Остальные 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 Потребность/наличие 50 90 90 70 A1 110 7 8 30 5 10 3 70 A2 110 2 50 4 60 5 9 A3 80 6 3 1 80 2 Заполнено 6 клеток, все ресурсы распределены, все потребности удовлетворены. Стоимость перевозок по этому плану равна: S0 = 2*50+8*30+4*60+5*10+1*80+3*70 =920 Проверим полученный план на оптимальность. Для этого рассчитаем потенциалы заполненных клеток, составив систему: а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. Теперь для свободных клеток рассчитаем разности между фактическими и потенциальными тарифами: Δ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. 430 Т.к. Δ32< 0, первоначальный план не является оптимальным. Для его улучшения нужно заполнить клетку А3В2. Составим цикл перевозки так, чтобы все остальные вершины были в заполненных клетках: -30 +30 +30 -30 Получим новый опорный план: Ai Bj B1 B2 B3 B4 Потребность/наличие 50 90 90 70 A1 110 7 8 5 40 3 70 A2 110 2 50 4 60 5 9 A3 80 6 3 30 1 50 2 Стоимость перевозки по нему равна: S1= 2*50+4*60+3*30+5*40+1*50+3*70= 890 Проверим новый план на оптимальность: рассчитываем потенциалы