2015-06-10
605
Метод северо-западного угла является самым простым методом построения первоначального Т-плана.
Содержание метода:
1). Построим таблицу перевозок (Таблица 1).
2). Приведем задачу к сбалансированному виду, если это необходимо.
3). Выделим верхнюю левую клетку таблицы (l,k). Присвоим выбранной клетке объем поставки xl,k, равный минимальному из значений аl (объем продукта, имеющийся у l -го производителя) и b k (объем продукта, необходимый k -му потребителю), т.е. xl,k=min { аl, b k }.
4). Рассмотрим случай, когда аl > b k . Эта ситуация означает то, что запросы k-го потребителя полностью удовлетворены, а объем продукта, имеющийся у l -го производителя уменьшились на величину равную xl,k. Следовательно необходимо вычеркнуть из таблицы k- й столбец и значение аl уменьшить на b k.
В случае аl < b k предполагается, что запас продукта l -го производителя исчерпан, а k-у потребителю необходимо доставить еще (b k - аl) объема продукта. Следовательно необходимо вычеркнуть из таблицы строку с номером l, а значение b k уменьшить на аl.
|
|
|
5). Выделим следующую левую верхнюю клетку таблицы из числа оставшихся и повторим процедуру, описанную в 3 пункте.
Замечание 4: Очевидно, что сумма произведения стоимости перевозки единицы продукта на величину поставкив выделенных клетках определяет общую стоимость перевозок продукта.
Рассмотрим на примере построение первоначального Т-плана методом севере-западного угла.
задача (*): На трех складах А, В, С находится соответственно 100, 130 и 170 усл. ед. одноименного груза, который необходимо доставить в четыре пункта потребления а, в, с, д в объеме 150, 120, 80, 50 усл.ед. соответственно. Затраты на перевозку груза приведены в таблице 3:
Таблица 3
| Склады | Пункты - потребители | |||
| а | б | с | д | |
| А | ||||
| В | ||||
| С |
Найти план перевозок одноименного груза со складов в пункты потребления, при котором транспортные издержки будут минимальными.
1). Построим исходную таблицу:
Таблица 4
| а | б | с | д | ||
| А | |||||
| В | |||||
| С | |||||
2). Данная задача является сбалансированной, так как объем груза, имеющийся на всех складах равен объему груза необходимому всем поставщикам:
=100+130+170 = 400 и 
= 150+120+80+50 = 400
3). -Выберем верхнюю левую клетку - (1;1). Укажем величину поставки x11 = min { а1, b1} = min { 100, 150} = 100. Это означает, что 100 усл.ед. груза отправили от первого поставщика (склад А) первому потребителю (пункт а).
У первого поставщика (склад А) не осталось груза, поэтому первую строку таблицы вычеркнем.
|
|
|
Потребности первого потребителя сократились на 100 усл. ед. груза. Поэтому значение b 1 необходимо уменьшить на 100, т.е. b1=150-100=50. Все изменения внесем в таблицу 5.
- Следующая клетка – (2;1). х21 = min {а2, b1}= min {130,50}= 50. Потребности первого потребителя полностью удовлетворены, поэтому вычеркиваем первый столбец таблицы. У второго поставщика (склад В) осталось еще 80 усл. ед. груза, т.е. а2 =80 (Таблица 6).
- Выделяем клетку (2;2). х22 = min {а2, b2}= min {80, 120}= 80. На складе В больше не осталось груза. Поэтому вычеркиваем вторую строку таблицы. Второму поставщику необходимо доставить еще b2 = 120-80 = 40 усл.ед. груза (Таблица 7).
Таблица 5 Таблица 6
| а | б | с | д | а | б | с | д | |||||
| (150) | ||||||||||||
| +50 | +0 | |||||||||||
| А | (100) | А | (100) | |||||||||
| В | В | (130) | ||||||||||
| С | С | |||||||||||
- Следующая выделенная клетка – (3;2). Соответствующая ей величина поставки будет равна х32 = min {а3, b2}= min {170, 40}=40. Это означает, что второму потребителю (пункт б) доставили 40 усл.ед груза, и его потребность удовлетворена. Это означает, что 2-й столбец таблицы необходимо вычеркнуть. На складе С осталось еще а3=170-40 = 130 усл.ед. груза (Таблица 8).
Таблица 7 Таблица 8
| а | б | с | д | а | б | с | д | |||||
| (150) | (120) | (150) | (120) | |||||||||
| +0 | +40 | +0 | +0 | |||||||||
| А | (100) | А | (100) | |||||||||
| В | (130) | В | (130) | |||||||||
| С | С | (170) | ||||||||||
- Выделим верхнюю левую клетку из числа еще не вычеркнутых клеток – (3;3). Ей соответствует поставка х33 = min {а3, b3}= min {130, 80}=80. В пункт б доставили весь необходимый груз - вычеркиваем третий столбец таблицы. На складе С осталось а3=130-80 = 50 усл.ед. груза (Таблица 9).
- В таблице осталась последняя не вычеркнутая клетка – (3;4). Выделим ее. х34 = min {а3, b4}= min {50, 50}=50. Оставшийся объем груза равен объему, необходимому последнему потребителю (Таблица 10).
Таблица 9 Таблица 10
| а | б | с | д | а | б | с | д | |||||
| (150) | (120) | (80) | (150) | (120) | (80) | (50) | ||||||
| +0 | +0 | +0 | +0 | +0 | +0 | +0 | ||||||
| А | (100) | А | (100) | |||||||||
| В | (130) | В | (130) | |||||||||
| С | (170) | С | (170) |
Первоначальный Т-план построен. На заключительном этапе построения первоначального плана перевозок полезно проверить его на наличие ошибок. Для этого:
а). Суммируем величины всех поставок в каждой строке, результат должен совпадать с имеющимся объемом груза у соответствующего поставщика:
1 строка (склад А): 100=100;
2 строка (склад В): 130 = 50+80;
3 строка (склад С): 170 = 40+80+50.
б). Суммируем величины всех поставок в каждом столбце, результат должен совпадать с объемом груза, необходимым соответствующему потребителю:
1 столбец (пункт а): 150 =100+50;
2 столбец (пункт б): 120 =80+40;
3 столбец (пункт с): 80 =80;
4 столбец (пункт д): 50 =50.
Проверка показала правильность построения первоначального Т-плана. Сделаем выводы:
1). П остроенный план перевозок заключается в доставке 100 и 50 усл.ед. груза со склада А и В соответственно в пункт а; 80 и 40 усл.ед. груза со склада В и С соответственно в пункт б; 80 усл.ед. груза со склада С в пункт с и 50 усл.ед. груза со склада С в пункт д.
2). Суммарные затраты на перевозку груза составляют:
|
|
|
L=3*100+1*50+4*80+8*40+12*80+7*50 = 2300 (ден.ед).
Построенный Т-план необходимо проверить на оптимальность.
Построение первоначального Т-плана
