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

Муниципальное образовательное учреждение

среднего профессионального образования

"Колледж экономики и управления"

Курсовая работа

по дисциплине "Математические методы"

Тема: Нахождение минимальных затрат при распределении товаров среди магазинов методами решения транспортной задачи

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1 Транспортная задача

1.2 Методы составления опорного плана транспортной задачи

1.2.1 Метод северо-западного угла

1.2.2 Метод наименьшей стоимости

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

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

Глава 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 Постановка задачи

2.2 Нахождение первоначального плана методом северо-западного угла

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

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

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

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

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

ВВЕДЕНИЕ

Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям.

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

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

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

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

ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимального раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

1.1 Транспортная задача

Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок и т. д. При решении транспортной задачи необходимо:

· обеспечить всех потребителей ресурсами;

· распределить все произведенные ресурсы;

· переместить ресурсы от производителей к потребителям с наименьшими затратами.

От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.

1.2 Методы составления опорного плана транспортной задачи

1.2.1 Метод северо-западного угла

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

1.2.2 Метод наименьшей стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел a_i или b_j . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм:

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

· Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.

· Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п.1, в противном случае задача решена.

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

Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа U_i ,V_j , приписанные определённым образом каждому поставщику и потребителю.

Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток

Опорный план должен быть не вырожденным (r=m+n-1 - невырожденный план)

Алгоритм решения:

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

2. Находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана U_i + V_j < C_ij

3. Проверяем второе условие оптимальности плана для свободных клеток

Если оно выполнено, то план оптимален, если нет то улучшаем план.

4. Улучшение плана:

a. При не выполнении второго условия в клетку заносим нарушение со знаком плюс. Такие клетки называются потенциальными.

b. Среди всех потенциальных клеток выбираем клетку с наибольшим

нарушением.

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

За исключением той клетки, для которой строится контур

d. Вершины контура поочерёдно помечаем знаками плюс и минус, начиная с клетки, для которой строится контур.

e. Среди клеток помеченных знаком минус выбираем наименьшею перевозку и на эту величину увеличиваем перевозку в клетках помеченных знаком плюс и уменьшаем в клетках помеченных знаком минус в результатах переназначения освобождается одна клетка.

5. Вновь полученный план проверяем на оптимальность.

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

Данный метод состоит в следующем:

1. На каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;

2. Находят max Дc_ij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

2.1 Постановка задачи

Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный распределения товаров с минимальными затратами.

Дано:

Склад №1=200 шт.

Склад №2=250шт.

Склад №3=200шт.

Требуется доставить штук:

Магазин "Терабайт"= 190шт.

Магазин "Лидер"= 100 шт.

Магазин "Эксперт" = 120 шт.

Магазин "Ока-сервис" =110 шт.

"Владимирский рынок" =130 шт.

Сетка тарифов:

28	27	18	27	24
18	26	27	32	21
27	33	23	31	34

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

Магазины:

Магазин "Терабайт"= B₁

Магазин "Лидер"= B₂

Магазин "Эксперт" = B₃

Магазин "Ока-сервис" = B₄

"Владимирский рынок" = B₅

Товары:

Склад №1= A₁

Склад №2 = A₂

Склад №3= A₃

Тогда матрица будет выглядеть так:

	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

Следуя данной модели можно найти опорный план и решение поставленной задачи.

2.2 Нахождение первоначального плана методом северо-западного угла

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

	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	Запасы
A1	28 [190]	27 [10]	18	27	24	200
A2	18	26 [90]	27 [120]	32 [40]	21	250
A3	27	33	23	31 [70]	34 [130]	200
Потреб.	190	100	120	110	130

Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([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 Нахождение первоначального плана методом наименьшей стоимости

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

	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	Запасы
A1	28	27[10]	18[120]	27	24[70]	200
A2	18 [190]	26	27	32	21[60]	250
A3	27	33 [90]	23	31 [110]	34	200
Потреб.	190	100	120	110	130

Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([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 Метод потенциалов

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

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

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

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

Проверим оптимальность опорного плана. Найдем потенциалы 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

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

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

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

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



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

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

Проверим оптимальность опорного плана. Найдем потенциалы 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. Оптимальное решение для транспортной задачи

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

ЗАКЛЮЧЕНИЕ

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

Получены следующие результаты

Метод северо-западного угла: 19040 рублей

Метод наименьшей стоимости: 15170 рублей

Метод потенциалов: 15080 рублей

Метод аппроксимации Фогеля: 15110 рублей

Из этих методов наиболее оптимальным для данной задачи является метод потенциалов, так как при распределении товаров этим методом затраты оказались самыми минимальными в размере 15080 рублей

Также были применены возможности электронных таблиц MS Excel при решении транспортной задачи, получены оптимальные результаты, подтверждающие результат метода потенциалов.

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

СПИСОК ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

1. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование , М.: Высшая школа 2008г.

2. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании, М.: Дело, 2006г.

3. В.И. Ермаков Общий курс высшей математики для экономистов М.:, Инфра-М, 2005г.

4. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 2007

5. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 2006

6. .Кузнецов Ю.Н., Кузубов В.И., Волощснко А. Б. Математическое программирование. М.: Высшая школа, 2009

7. Большакова И. В. , Кураленко М. В. Линейное программирование: учебно-методическое пособие М.: Айрис-пресс, 2009

8. Агальцов В.П., Волдайская И.В. Математические методы в программировании. М.: Инфра-М, 2006.

9. Рудикова Л.В. Microsoft Excel для студента СПб.: БХВ-Петербург, 2006

10. Партыка Т.Л., Попов И.И. Математические методы М.:Форум,2007