Решение транспортных задач венгерским методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
в столбце с положительной невязкой. В данном случае полученная цепочка показана в таблице:
(+)(+)'*2.5+C14.6'*+'8.321.6+6'7.4
Этап коррекции плана Х
Этот этап начинается сразу после построения цепочки. Для коррекции плана находим корректирующий элемент . Находим его по минимуму из невязки строки начала цепочки, из невязки столбца конца цепочки и значения элемента Xij, соответствующего 0*. =min{900, 900, 3100}=900;
Прибавляем =900 к элементам Xij, которым в цепочке соответствовали элементы Сij=0, и отнимаем =900 от элементов Xij, которым в цепочке соответсвовали элементы Cij=0*:
AiХ1:900220003052001200018500Bj000
Теперь рассчитаем невязки по столбцам и по строкам.
по столбцам:
b1=2100-1200-900=0;
b2=4800-2200-30-1850=0;
b3=520-520=0;
по строкам:
а1=3100-900-2200=0;
а2=550-30-530=0;
а3=1200-1200=0;
а4=1850-950=900;
После коррекции плана суммарная невязка Переходим к расчёту целевой функции:
L=900*12+2200*14+30*12.4+520*3.1+1200*7.7+1850*19=87974.
5.2 Решение задачи на ЭВМ
Для проведения вычислительного эксперимента была разработана программа в среде Builder С++, которая выполняет расчет транспортной задачи венгерским методом. Ввод (загрузка) данных отображен на рисунке 5.1.
Рисунок 5.1 - Ввод данных в таблицу
После нажатия кнопки Решить появляются вкладки с итерациями. Каждая вкладка описывает 1 шаг. Сверху находится матрица С, снизу матрица Х. Результаты програмных подсчётов на ЭВМ показаны на рисунках 5.2 - 5.6.
Рисунок 5.2 - Реализация предварительного этапа на ЭВМ
Рисунок 5.3 - Реализация первой иттерации на ЭВМ
Рисунок 5.4 - Реализация этапа эквивалентных преобразований на ЭВМ
Рисунок 5.5 - Реализация этапо повторного поиска на ЭВМ
Рисунок 5.6- Реализация этапа коррекции плана на ЭВМ и получения оптимального плана
6 АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ
Проведем анализ модели на чувствительность в соответствии с постановкой задачи.
Условие задачи:
AiС:12147.231001512.43.15507.718221200231917.11850Bj210040805206700
Оптимальный план Хopt, соответствующий данной задаче имеет вид:
AiХopt:900220003052001200018500Bj000
Значение целевой функции составляет L = 87974 [евро].
Соответствующая структура коммуникаций имеет вид:
Выполним анализ модели.
- Определим пункт, изменение запасов груза в котором является наиболее выгодным с точки зрения минимизации затрат на его перевозку потребителям.
Целевую функцию L можно представить в виде суммы
где Li - значения минимальных транспортных издержек, вычисленные по строкам матрицы Хopt.
L1 = 900*12 + 2200*14 =41600 [у.е].
L2 = 30*12.4 + 520*3.1=1984 [у.е].
L3 = 1200*7.7= 9240 [у.е].
L4 = 1850*19= 35150 [у.е].
Поэтому наиболее выгодно уменьшить объем производимого продукта в пункте А1, так как L1 вносит наибольший вклад в целевую функцию, а увеличивать его выгоднее всего в пункте А2, так как перевозка из данного пункта стоит дешевле, чем из других пунктов.
Установим ориентировочные, а затем уточненные пределы изменения запаса груза. Так как ориентировочный диапазон устанавливается из диапазона 0 < D max Ai (i=1,4), и А1=3100, А2=550, А3=1200 А4=1850, то max Ai(i=1..4)=A1=3100. Для нашей задачи 0<<3100.
Решение транспортной задачи будем определять для следующиих векторов объема производства:
А = (3000, 650, 1200, 1850),
А = (2900, 750, 1200, 1850),
А = (2800, 850, 1200, 1850),
А = (1000, 2650, 1200, 1850),
А = (990, 2660, 1200, 1850),
А = (960, 2690, 1200, 1850),
А = (930, 2720, 1200, 1850),
А = (900, 2750, 1200, 1850).
Результаты вычислений показали, что, начиная с вектора А = (900, 2750, 1200, 1850), структура оптимального решения будет изменяться. Она определяется следующим планом Хopt:
AiХ'opt:9000223052001200018500Bj000
Этому плану соответствует граф коммуникаций:
Оптимальное решение транспортных издержек составит L = 84454 евро.
Поэтому уточненный диапазон D будет находиться в пределах 0 < D < 2200.
) Найдем зависимость оптимального решения и оптимального значения целевой функции от изменений компонент вектора запаса груза. Условия и результаты вычислительного эксперимента приведены в таблице 6.1.
Таблица 6.1 - Условия и результаты вычислительного эксперимента
01234567891011a131002900270025002300210019001700150013001100900a2550750950115013501550175019502150235025502750a3120012001200120012001200120012001200120012001200a4185018501850185018501850185018501850185018501850DL, евро032064096012801600192022402560288032003520L, евро879748765487334870148669486374860548573485414850948477484454
Рисунок 6.1 - График зависимости затрат на перевозки от изменения объемов производства
Таким образом, с уменьшением объема производимого продукта в пункте А1 (Киеве) на 2200кг и увеличением на такую же величину объема производимого продукта в пункте А2 (Запорожье), транспортные расходы на перевозку черного шоколада удается сократить еще на 3520 евро. При этом общая стоимость транспортных расходов составит 84454 евро в месяц.
ЗАКЛЮЧЕНИЕ
В результате выполнения курсового проекта были изучены методы решения транспортных задач, более углубленно был изучен венгерский метод. Венгерский метод решения транспортной задачи является сравнительно простым, и его можно широко применять на предприятиях, где требуется вести подсчет минимальных затрат на перевозку груза, например, с заводов в пункты потребления.
Была приведена экономическая интерпретация аздачи, построена ее математическая модель. С помощью алгоритма венгерского был получен оптимальный план перевозок и рассчитано оптимальное значение целевой функции.
Ал