Промышленный лизинг
Методички
Таблица 3 Рис. 10 В таблице 4 методом северо-западного угла выделен опорный набор (см. также рис. 10). Таблица 4 Рис. 11 Вычислим соответствующее значение линейной функции затрат: 12 17 + 6 15 + 7 16+11 34 + 9 - 4 + 7 18 + 9 7+ 14 23 = 1327. Немного поизучав таблицу 4, заметим, что полученный опорный набор не является оптимальным. В самом деле, дешевый путь А2В4 не задействован, зато используются более дорогие А3Ва, А3В3 и А2В3 (рис. 11). © © © © ® ® © © © © Рис. 12 Рис. 13 Попробуем изменить ситуацию, а именно, заменим один из дорогих маршрутов, A3B4i на дешевый А2ВА, но сделаем это аккуратно и очень осторожно (рис. 12): закрывая маршрут А3ВА, мы переносим 18 единиц его груза на маршрут А2В4, а для того, чтобы весь набор оставался опорным, снимем 18 единиц груза с маршрута А2В3, перенесем их на более дешевый А3В3 (рис. 13) и окончательно получим взамен старого новый набор маршрутов - А2В4, А2В3 и А3В3 (в таблице 4 стоимости соответствующих перевозок подчеркнуты). Подведем итоги изменения маршрутов и перевезенных по ним грузов и вычислим стоимости старой и новой перевозок. Имеем соответственно 5 18 + 7 -0 + 9 -22 + 11 16 5 -0 + 7 18 + 9 -4+11 -34. Разность 5 (18 - 0) + 7 (0-18) + 9 (22-4) +11 (16-34) = = 5 18-7 18 + 9 18-11 18 = (5-7 + 9-11) 18 = = (-4) 18 = -72 отрицательна. Тем самым, на новом опорном наборе (таблица 5) Таблица 5 стоимость перевозки стала меньше на 72 единицы: 1327 - 72 = 1255. Заметим, что альтернированную сумму 5-7 + 9-11 легко получить путем перемещения по клеткам (2,4), (3,4), (3, 3) и (2, 3) по часовой стрелке, (2, 4) -> (3, 4) -> (3, 3) -> (2, 3), выбирая стоимость перевозки единицы груза в клетках с нечетными номерами со знаком +, а в клетках с четными номерам со знаком - (в таблице 4 стоимости соответствующих перевозок подчеркнуты). Рассматривая рисунки 11,12 и 13, мы можем заметить, что, добавляя к ломаной А2Вз, А3В3, А3ВА звено А2ВА мы сначала получаем цикл, а затем, отбрасывая из него звено А3В4, - новую схему перевозок. Замечание. В результате проведенного преобразования мы изменили часть величин, подлежащих определению (это х23, х2а, х33 и х34), никак не затронув остальные 16 = 20 - 4. При этом общий вклад измененных величин в систему траспортных равенств остался тем же самым: от связей *23 Х24 *33 *34 = 22, х2з + *зз ~~ 38, х24 + = 18 мы перешли к связям х23 + х24 = 34, хз + Ху = 22, +Х34 = 18, *23 +хзз ~~ 38, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 [ 33 ] 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |