Муниципальное образовательное учреждение
среднего профессионального образования
«Колледж экономики и управления»
Курсовая работа
по дисциплине «Математические методы»
Тема: Нахождение минимальных затрат при распределении товаровсреди магазинов методами решения транспортной задачи
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Глава 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 Методнаименьшей стоимости
Суть метода заключается втом, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ейсоответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотренияисключают либо строку, соответствующую поставщику, запасы которого полностьюизрасходованы, либо столбец, соответствующий потребителю, потребности которогополностью удовлетворены. Либо и строку и столбец, если израсходованы запасыпоставщика и удовлетворены потребности потребителя. Из оставшейся части таблицыстоимостей снова выбирают наименьшую стоимость, и процесс распределения запасовпродолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Алгоритм:
· Из таблицытарифов выбирают наименьшую стоимость. И в клетку, которая ей соответствует,вписывают меньшее из чисел.
· Проверяютсястроки поставщиков на наличии строки с израсходованными запасами и столбцыпотребителей на наличие столбца, потребности которого полностью удовлетворены.Такие столбцы и строки далее не рассматриваются.
· Если не всепотребители удовлетворены и не все поставщики израсходовали товары, возврат кп.1, в противном случае задача решена.
1.2.3 Методпотенциалов
Наиболее простым методомТЗ является метод потенциалов. Потенциалами называются условные числа Ui,Vj, приписанные определённым образомкаждому поставщику и потребителю.
Теорема(условияоптимального плана): Сумма потенциалов поставщика и потребителя равна тарифнойставке для занятых клеток; сумма потенциалов поставщика и потребителя непревышает тарифную ставку для свободных клеток
/>/> />
/> />
Опорный план должен бытьне вырожденным (r=m+n-1 – невырожденный план)
Алгоритм решения:
1. Строим начальныепланы методом северо-западного угла и методом наименьшей стоимости из нихвыбираем лучший
2. Находимпотенциалы поставщика и потребителя, пользуясь первым условием оптимальностиплана Ui+ Vj
3. Проверяем второеусловие оптимальности плана для свободных клеток
/> />
Если оно выполнено, топлан оптимален, если нет то улучшаем план.
4. Улучшение плана:
a. При не выполнениивторого условия в клетку заносим нарушение /> сознаком плюс. Такие клетки называются потенциальными.
b. Среди всехпотенциальных клеток выбираем клетку с наибольшим
нарушением.
c. Строим длявыбранной клетки замкнутый контур, состоящий из вертикальных и горизонтальныхотрезков прямой, причем вершины контура лежат в занятых клетках.
За исключением тойклетки, для которой строится контур
d. Вершины контурапоочерёдно помечаем знаками плюс и минус, начиная с клетки, для которойстроится контур.
e. Среди клетокпомеченных знаком минус выбираем наименьшею перевозку и на эту величину увеличиваемперевозку в клетках помеченных знаком плюс и уменьшаем в клетках помеченныхзнаком минус в результатах переназначения освобождается одна клетка.
5. Вновь полученныйплан проверяем на оптимальность.
1.2.4 Методаппроксимации Фогеля
Данный метод состоит вследующем:
1. На каждойитерации находят разности между двумя наименьшими тарифами во всех строках истолбцах, записывая их в дополнительные столбец и строку таблицы;
2. Находят max?cij и заполняют клетку с минимальной стоимостью встроке (столбце), которой соответствует данная разность.
Процесс продолжается дотех пор, пока все грузы не будут развезены по потребителям. Данный метод в рядезадач приводит к оптимальному плану.
ГЛАВА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
Построимдля данной задачи матрицу тарифов, по которой будет происходить поископтимального плана распределения товаров между магазинами. Для более удобногорешения задачи обозначим магазины и товары переменными:
Магазины:
Магазин«Терабайт»= B1
Магазин«Лидер»= B2
Магазин«Эксперт» = B3
Магазин«Ока-сервис» = B4
«Владимирскийрынок» = B5
Товары:
Склад№1= A1
Склад№2 = A2
Склад№3= A3
Тогдаматрица будет выглядеть так:
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
Решениезадачи методом северо-западного угла всегда начинается с левого, верхнеготарифа([A1;B1]). Полностью удовлетворяемпотребность данного тарифа. Исключаем первый столбец. Дальше смотрим еслизапасы ещё остались, рассматриваем рядом стоящий тариф ([A2;B1]), если нет, то исключаем и первуюверхнею строк. И рассматриваем следующий тариф по аналогичной схеме. Врезультате получен опорный план, который является допустимым, так как все грузыиз баз вывезены, потребность магазинов удовлетворена, а план соответствуетсистеме ограничений транспортной задачи. Подсчитаем число занятых клетоктаблицы, их 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
Длярешения задачи методом наименьшей стоимости сначала из все матрицы тарифоввыбираем наименьший тариф ([A2;B1]). Полностью удовлетворяем его потребность. Исключаем изрешения столбец в котором он находился. Ищем следующий минимальный тариф ([A2;B3]). Удовлетворяем его потребности.Исключаем из решения столбец в котором он находился. Дальше продолжаем до техпор, пока все запасы не будут розданы.
Врезультате получен опорный план, который является допустимым, так как все грузыиз баз вывезены, потребность магазинов удовлетворена, а план соответствуетсистеме ограничений транспортной задачи.
Подсчитаемчисло занятых клеток таблицы, их 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
Проверимоптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, вкоторых ui + vi = cij
Дляэтого построим систему уравнений:
/>
Изэтой системы уравнений находим потенциалы, полагая, что u1 = 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
Опорныйплан не является оптимальным, так как существуют оценки свободных клеток длякоторых ui + vi > cij, (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
Проверимоптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, вкоторых ui + vi = cij (Алгоритм нахождения потенциаловописан выше). 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
Длянахождения опорного плана данным методом нужно найти разность между наименьшимиэлементами в столбцах и строках. Затем определяем наибольшую разность(?cij). Дальше находим минимальный тариф встолбце (или строке) которому принадлежит ?cij, и отдаём ему сколько можно отдать: это тариф [A2;B1]. Исключаем из вычислений первыйстолбец .
И такпродолжаем до тех пор пока все товары не будут найдены.
Врезультате получен опорный план, который является допустимым, так как все грузыиз баз вывезены, потребность магазинов удовлетворена, а план соответствуетсистеме ограничений транспортной задачи.
Подсчитаемчисло занятых клеток таблицы, их 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