Студопедия
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
|
Метод северо-западного угла
Пусть условия транспортной задачи заданы таблице 2.2. Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя за счет запаса поставщика Для этого сравниваем с , меньший из объемов, т. е. = 100 ед. записываем в левый нижний угол клетки А1B1. Запасы первого поставщика полностью израсходованы, по этому остальные клетки первой строки прочеркиваем. Потребности остались неудовлетворенными на . Сравниваем этот остаток с запасами поставщика : так как , то ед. записываем в клетку , чем полностью удовлетворяем потребности потребителя , а оставшиеся клетки в первом столбце прочеркиваем.
Таблица 2.2
У поставщика осталось 150 ед. груза. Удовлетворяем потребителя за счет оставшегося у поставщика груза. Для этого сравниваем этот остаток с потребностями потребителя : , записываем 150 ед. в клетку и, так как запасы полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности остались неудовлетворенными на 50 ед. Удовлетворяем их за счет поставщика и переходим к удовлетворению за счет остатка, имеющегося у поставщика , и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается. Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя. Проверим, является ли план, построенный в табл. 2.2, опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точно занятых клеток. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ. Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же ячейках: Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.
Пример 1
Методом северо-западного угла составить опорный план перевозок груза из трех пунктов отправления с запасами 30, 48, 24 т в четыре пункта назначения с потребностями 18, 27, 42, 15т. Тарифы перевозок (в ден/ед.) из приведены в матрице.

Решение. Составим распределительную таблицу (табл. 2.2), в которой последовательно, начиная с верхнего левого угла (ячейка , ) и двигаясь по диагонали таблицы, заполним клетки до A3 , B4.
Таблица 2.3
|
|
|
|
| Запасы
|
| 13
18
| 7
12
| 11
| 5
| 30
|
| 11
| 8
15
| 13
33
| 7
| 48
|
| 6
| 10
| 12
9
| 9
15
| 24
| Потребности
| 18
| 27
| 42
| 15
| 102
|
Получили 6 заполненных клеток, данный план является опорным ). Вычислим общую сумму затрат на перевозки груза по этому плану: План не учитывал тарифов перевозок и, наверное, не будет оптимальным.
|