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

Глава 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 или _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₃

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28	27	18	27	24	200
A₂	18	26	27	32	21	250
A₃	27	33	23	31	34	200
Потребности	190	100	120	110	130

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

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

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28	27	18	27	24	200
A₂	18	26	27	32	21	250
A₃	27	33	23	31	34	200
Потреб.	190	100	120	110	130

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

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28 (190)	27 (10)	18	27	24	200
A₂	18	26 (90)	27 (120)	32 (40)	21	250
A₃	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 Нахождение первоначального плана методом наименьшей стоимости

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28	27	18	27	24	200
A₂	18	26	27	32	21	250
A₃	27	33	23	31	34	200
Потреб.	190	100	120	110	130

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

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28	27(10)	18(120)	27	24(70)	200
A₂	18 (190)	26	27	32	21(60)	250
A₃	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 Метод потенциалов

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

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

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

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁	28	27(10)	18(120)	27	24(70)	200
A₂	18(190)	26	27	32	21(60)	250
A₃	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, стоящих в минусовых клетках. В результате получим новый опорный план.

	B₁	B₂	B₃	B₄	B₅	Запасы
A₁