![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
А) Метод северо-западного угла (диагональный метод)
На каждом шаге заполняется верхняя левая клетка («северо-западный угол») оставшейся части распределительной таблицы. Заполнение таблицы начинают с клетки (1; 1), при этом
Пример 2. Рассмотрим пример составления начального опорного плана методом северо-западного угла. Запасы груза у поставщиков а = (90; 100; 90); потребности потребителей b = (70; 60; 80; 70); тарифы перевозок Решение. Задача закрытая, так как Строим распределительную таблицу и находим в клетке (1; 1) количество груза х 11 = min(90; 70) = 70. Спрос 1-го потребителя удовлетворен полностью. По 1-му столбцу не перемещаемся, так как спрос 1-го потребителя удовлетворен. Перемещаемся по 1-й строке в клетку (1; 2): х 12 = min(а 1- х 11; b 2) = min(90-70; 60) = min(20; 60) = 20. Груз от 1-го поставщика вывезен полностью (70+20=90).По 1-й строке не перемещаемся, переходим по 2-му столбцу в клетку (2; 2): х 22 = min(100; b 2- х 12) = min(100; 60-20) = min (100; 40) = 40. Спрос 2-го потребителя удовлетворен (20+40=60). Переходим в клетку (2; 3): х 23 = min(а 2- х 22; b 3) = min(100-40; 80) = min(60; 80) = 60. У 2-го поставщика груз выбран полностью (40+60=100). Переходим в клетку (3; 3): х 33 = min(а 3; b 3- х 23) = min(90; 80-60) = min(90; 20) = 20. Спрос 3-го потребителя удовлетворен (60+20=80). Переходим в клетку (3; 4): х 34 = min(а 3- х 34; b 4) = min(90-20; 70) = min(70; 70) = 70. Таким образом, получен начальный план перевозок:
Ранг матрицы системы Для подсчета стоимости перевозок количество груза в каждой заполненной клетке умножим на соответствующий тариф и результаты сложим:
Как правило, исходный опорный план, полученный данным методом, оказывается весьма далеким от оптимального, так как при его определении игнорируются величины затрат cij. Поэтому в дальнейших расчетах для определения оптимального плана требуется много итераций (шагов). Число итераций можно сократить, если исходный план строить по более рациональному методу «минимального элемента».
|