183896 (629960), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([A₁;B₁]). Полностью удовлетворяем потребность данного тарифа. Исключаем первый столбец. Дальше смотрим если запасы ещё остались, рассматриваем рядом стоящий тариф ([A₂;B₁]), если нет, то исключаем и первую верхнею строк. И рассматриваем следующий тариф по аналогичной схеме. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F=28*190+27*10+26*90+27*120+32*40+31*70+34*130=19040

Результат: Затраты на распределение товаров между магазинами найденные методом северо-западного угла составят 19040 рублей.

2.3 Нахождение первоначального плана методом наименьшей стоимости

Используя построенную матрицу тарифов, найдём оптимальный опорный план методом наименьшей стоимости.

Проверим необходимое и достаточное условие разрешимости задачи.

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([A₂;B₁]). Полностью удовлетворяем его потребность. Исключаем из решения столбец в котором он находился. Ищем следующий минимальный тариф ([A₂;B₃]). Удовлетворяем его потребности. Исключаем из решения столбец в котором он находился. Дальше продолжаем до тех пор, пока все запасы не будут розданы.

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F=27*10+18*120+24*70+18*190+21*60+33*90+31*110=15170

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15170 рублей.

2.4 Метод потенциалов

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

Для данной задачи минимальным является метод наименьшей стоимости.

Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij

Для этого построим систему уравнений:

Из этой системы уравнений находим потенциалы , полагая, что u₁ = 0:

v1=0, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6

Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых u_i + v_i > c_ij, (3;3): 6 + 18 > 23

Выбираем максимальную оценку свободной клетки (3;3): 23

Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij (Алгоритм нахождения потенциалов описан выше).

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.

2.5 Метод аппроксимации Фогеля

Используя построенную матрицу тарифов, найдём оптимальный опорный план методом аппроксимации Фогеля.

Характеристики

Список файлов курсовой работы