Решение транспортных задач венгерским методом

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование



в столбце с положительной невязкой. В данном случае полученная цепочка показана в таблице:

(+)(+)'*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 [евро].

Соответствующая структура коммуникаций имеет вид:

Выполним анализ модели.

  1. Определим пункт, изменение запасов груза в котором является наиболее выгодным с точки зрения минимизации затрат на его перевозку потребителям.

Целевую функцию 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 евро в месяц.

ЗАКЛЮЧЕНИЕ

В результате выполнения курсового проекта были изучены методы решения транспортных задач, более углубленно был изучен венгерский метод. Венгерский метод решения транспортной задачи является сравнительно простым, и его можно широко применять на предприятиях, где требуется вести подсчет минимальных затрат на перевозку груза, например, с заводов в пункты потребления.

Была приведена экономическая интерпретация аздачи, построена ее математическая модель. С помощью алгоритма венгерского был получен оптимальный план перевозок и рассчитано оптимальное значение целевой функции.

Ал