Промышленный лизинг Промышленный лизинг  Методички 

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

Таблица 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