Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
т минимальны.
Потребности потребителей (в условных единицах), количество продукта (груза) в каждом пункте (в тех же условных единицах) и транспортные затраты на перевозки продукции (груза) из пункта Аi и Вj заданы в таблице 1.1.
Таблица 2.1 - Исходные данные к расчету транспортной задачи венгерским методом
ВариантАiB1B2B3Запасы24A112147.23100A21512.43.1550A37.718221200А4231917.11850Потребности21004080520
.1 Экономическая интерпретация поставленной задачи
В Украине известна фабрика производства шоколада Рошен. Эта фабрика имеет 4 завода, расположенных в разных частях Украины, - в Киеве, Запорожье, Харькове и Виннице. Объем производства каждого завода составляет 3100, 550, 1200 и 1850 килограмм черного шоколада в месяц. Реализация продукции производится в трех крупых городах Украины - Донецке, Одессе и Львове. Объемы потребления в каждом городе различны и составляют 2100, 4080 и 520 килограмм черного шоколада в месяц соотвественно. Известна стоимость доставки продукции из каждого завода фирмы "Рошен" в названные города. Данные представлены в виде таблицы (таблица 1.2).
Таблица 2.2 - Таблица стоимости перевозки продукции
Стоимость перевозок, евро./кг шоколадаОбъем производства, кг12147.231001512.43.15507.718221200231917.11850Потребности, кг21004080520
Требуется найти такой план поставок, при котором весь товар будет вывезен из пунктов производства (шоколадные фабрики), а в пунктах потребления (фирмы) будет полное удовлетворение спроса, и общая стоимость перевозок будет минимальной.
3 РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
Венгерский метод базируется на следующих определениях: суммарная невязка плана, суммарная невязка по строкам и столбцам. Суммарной невязкой плана называется величина
Суммарная невязка по строкам:
di = i = 1..m
Суммарная невязка по столбцам:
dj = j = 1..n
Физически невязка представляет собой удвоенную величину единицы товара, которую надо распределить поставщикам и потребителям. Структурная схема алгоритма приведена на рисунке 4.1. Величина невязки определяет наихудшее из возможных случаев итераций, которое необходимо выполнить для достижения оптимального решения. Поэтому число итераций подчиняется следующему неравенству:
Существенным нулем называется нуль матрицы С, соответствующая коммуникация которого в плане Х больше 0.
.1 Предварительный этап
В каждом столбце матрицы С отыскивается минимальный элемент, который вычитается из всех элементов данного столбца. В итоге получаем матрицу С.
Аналогичная операция проделывается по строкам матрицы С. В пезультате получаем матрицу С0. Для нулей матрицы С0, перемещаясь по столбцам сверху вниз и меняя столбцы слева направо строим начальный план Х0 и определяем невязку этого плана. Если невязка равна нулю, то рассчитывается целевая функция плана, в противном случае переходят к итерационной части алгоритма.
Разметка выполняется в начале итерации и сохраняется до ее конца. В ходе эквивалентных преобразований матрицы С разметка переносится. Различают символом + столбцы, невязки которых нулевые и существенные нули. Прочие элементы разметки добавляются в ходе итерации. Столбцы (или строки), отмеченные символом +, называются выделенными и образуют выделенную часть матрицы С.
.2 Поисковый этап
Необходимо найти ноль матрицы С, находящий в невыделенной части матрицы и стоящий на строке с положительной невязкой. Если в процессе поиска обнаруживается, что таких нулей нет, то прибегают к эквивалентным преобразованиям матрицы. Если ноль найдется, то строят цепочку и корректируют план.
Поиск выполняют, двигаясь по невыделенным столбцам сверху вниз. Первый найденный ноль отмечают штрихом и анализируют его невязку по строке. Если невязка положительна, то это искомый ноль. В противном случае невязка по строке равна нулю, строчку выделяют знаком +. Просматривают выделенную строку по элементам выделенных столбцов, если на пересечении выделенной строки и выделенного столбца оказывается ноль, то его отмечают *, а знак выделения над столбцом снимают, после этого столбец считается невыделенным и в нем можно осуществить поиск. Поиск заканчивается, когда найден искомый ноль, либо когда все нули матрицы находятся либо в выделенных строках, либо в выделенных столбцах.
3.3 Этап построения цепочки и коррекции плана
Цепочка незамкнута, содержит нечетное число элементов и, в принципе, может состоять из одного нуля со штрихом.
Построение цепочки происходит в следующей последовательности: от найденного нуля со штрихом по столбцу к нулю со звездой, а от нуля со звездой по строке к нулю со штрихом. Далее выбирается корректирующий элемент по правилу: невязка строки начала, невязка строки конца и элементы плана Х, которые соответствуют нулю со *, входящих в цепочку. Q = min {di, dj, " Х*ij цепочка}
Как только найден такой элемент, план корректируют. Из элементов, которые соответствуют нулям со звездочкой, вычитают Q, а к элементам соответствующим нулям со штрихом прибавляют Q.
.4 Этап эквивалентных преобразований
В невыделенной части матрицы С выбирается наименьший положительный элемент, который прибавляется к элементам выделенных столбцов и вычитается из элементов невыделенных строк.
Рисунок 3.1 - Структурная схема алгоритма венгерского метода
4 ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ
.1 Переменные
&