Курсовая работа: Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспо

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

v1=0	v2=27	v3=18	v4=26	v5=24
u1=0	28	27[100]	18[30]	27	24[70]
u2=-3	18[190]	26	27	32	21[60]
u3=5	27	33	23[90]	31[110]	34

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

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

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

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

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

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

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

B1	B2	B3	B4	B5	Запасы
A1	28	27	18	27	24	200
A2	18	26	27	32	21	250
A3	27	33	23	31	34	200
Потребности	190	100	120	110	130

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

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

B1	B2	B3	B4	B5	Запасы	Δcij
A1	28	27[100]	18	27[30]	24[70]	200	6,6,3,0
A2	18[190]	26	27	32	21[60]	250	3,5,5
A3	27	33	23[120]	31[80]	34	200	4,8,2,2
Потреб.	190	100	120	110	130
Δcij	9	1,6	5	4,4	3,10

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

И так продолжаем до тех пор пока все товары не будут найдены.

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

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

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

F = 27*100 + 30*30 + 24*70 + 18*190 + 21*60 + 23*120 + 31*80 = 15110

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

2.6 Применение возможностей электронных таблиц при решении транспортной задачи

Для решения транспортной задачи также можно применять электронные таблицы (Microsoft Office Excel ).

Для решения задачи сначала нужно подготовить рабочий лист как показано на рис 1.

Рис 1. Исходные данные для решения транспортной задачи

Далее производим ввод данных в окно "Поиск решения" как показано на рис 2.

Рис 2. Ввод данных в окно "Поиск решения"

И нажимаем кнопку выполнить. Результат решения задачи представлен на рис 3.

Рис 3. Оптимальное решение для транспортной задачи

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