Венгерский метод. Содержание введение 4 математическая постановка задачи 5 определение опорного плана 8
 Скачать 105.72 Kb.
|
ОПРЕДЕЛЕНИЕ ОПОРНОГО ПЛАНА2.1. Предварительные сведенияДля определения начального опорного плана существует несколько методов. В дальнейшем рассмотрим два метода с примерами. Опорный план транспортной задачи находим следующим образом. На каждом шаге в таблице условий задачи заполняем одну клетку, которая называется занятой. Обозначим  клетку, где  -номер пункта отправления (строка),  -номер пункта назначения (столбец). Клетку заполняем так, чтобы удовлетворялись полностью потребности пункта назначения , либо обеспечивался полный вывоз груза из пункта отправления  В первом случае временно исключаем из рассмотрения столбец и изменяем запас груза пункта отправления . Во втором случае временно исключаем из рассмотрения строку и изменяем потребность груза пункта назначения . Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом.В  -ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем -ый шаг и получаем опорный план.Если на некотором шаге (не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана.2.2. Метод северно-западного углаПри нахождении опорного плана транспортной задачи методом северно-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки  поэтому метод и называется «методом северно-западного угла».Рассмотрим данный метод на конкретном примере. Пример 1. На три базы  поступил очередной груз в количествах равных 140, 160, 120 единиц. Этот груз требуется перевезти в четыре пункта назначения  в количествах 150, 90, 100, 80. Тарифы перевозок представлены матрицей: (2.1)Найти опорный план перевозок данной транспортной задачи методом северно-западного угла. Запишем все данные в табл. 2.1. Таблица 2.1. Данные примера 1
Число пунктов отправления  , а число пунктов назначения  . Следовательно опорный план задачи определяется числами, стоящими  заполненных клетках таблицы.Наличие груза у поставщиков равно  Общая потребность в грузе в пунктах назначения равна  .Модель транспортной задачи является закрытой, т.к.  . Следовательно, она разрешима.Найдем опорный план задачи методом северно-западного угла.  Следовательно в клетку  помещаем число  . Запасы пункта  полностью исчерпаны. Поэтому исключаем из рассмотрения точку и будем считать потребности пункта  равными 150-140=10. Промежуточные результаты приведены в табл. 2.2.Таблица 2.2. Промежуточные результаты
 Следовательно в клетку  помещаем число  . Потребности пункта полностью удовлетворены. Поэтому исключаем из рассмотрения столбец и будем считать запасы пункта  равными 160-10=150. Промежуточные результаты приведены в табл. 2.3.Таблица 2.3. Промежуточные результаты
Таким образом, продолжая процедуру в -ом шаге получим в табл. 2.4.:Таблица 2.4. Результаты вычислений
Запишем полученный опорный план:  (2.2)При этом плане стоимость перевозок вычисляется так:  . | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
