Задача о минимизации стоимости перегона транспортных средств

МИНОБРНАУКИ РОССИИ Орский политехнический колледж (филиал) федерального государственного  бюджетного образовательного учреждения  высшего профессионального образования  «Оренбургский государственный университет»   Отделение экономики и информационных технологий
курсовая работа по дисциплине «Математические методы»
Задача о минимизации стоимости перегона транспортных средств Пояснительная записка   ОПтК 230105.5013.08 ПЗ
Руководитель работы преподаватель __________________ Петрова П.П. «____» ______________ 2013 г. Исполнитель студент гр. ПО-319 __________________ Иванова И.И. «____» ______________ 2013 г.
Орск 2013
МИНОБРНАУКИ РОССИИ Орский политехнический колледж (филиал) федерального государственного  бюджетного образовательного учреждения  высшего профессионального образования  «Оренбургский государственный университет»   Отделение экономики и информационных технологий
Задание на курсовую работу
Задача о минимизации стоимости перегона транспортных средств
Исходные данные:	четыре овощехранилища, три магазина, тарифы по доставке груза (в д. е. за 1 т.), учебная литература.
Перечень подлежащих разработке вопросов:
	выявить существенные признаки описательной модели; описать формализованную модель задачи; создать компьютерную модель задачи,используя возможности «Поиска решений» в Microsoft Office Excel 2010.
Перечень графического материала:
	рисунки 9, таблицы 4.
Дата выдачи задания«___» ______________20__ г. Руководитель преподаватель  Исполнитель      студент группы ПО-319  Срок защиты работы «___» ______________20__ г.

 

 

Анн

отация

 

Пояснительная записка содержит 22 страниц, в том числе 9 рисунков, 4 таблиц, 6 источников.

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

Кроме того, после представлено практическое применение данной теории к решению конкретной задачи.

Курсовой работой предусмотрено применение Microsoft Office Excel 2010.

 

 

 

Содержание

 

 

 

Введение

 

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

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

Универсальность применения симплекс-метода связана с самой природой таких задач, ведь оптимизация заключается в максимизации или минимизации значения какой-либо целевой функции (например максимизации прибыли/дохода или минимизации затрат) в условиях выполнения различных ограничений (например по количеству или стоимости доступных ресурсов).

В рамках курсовой работы по математическим методам была поставлена задача:

1. рассмотреть суть транспортной задачи, ее применение и назначение;
2. найти способы решения транспортной задачи и разработать компьютерную модель.

 

 

1. Теоретическая часть

 

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителей этих ресурсов.

На автомобильном транспорте наиболее часто встречаются следующие задачи, относящиеся к транспортным:

1. прикрепление потребителей ресурса к производителям;
2. привязка пунктов отправления к пунктам назначения;
3. взаимная привязка грузопотоков прямого и обратного направлений;
4. отдельные задачи оптимальной загрузки промышленного оборудования;
5. оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассматривается экономико-математическая модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту а1, а2 ,…, аm. Известна потребность в грузах b1, b2, …, bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту сij, i=, j=. Необходимо рассчитать оптимальный план перевозок, т. е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-й пункт назначения (до потребителя) xij с минимальными транспортными издержками.

В общем виде исходные данные представлены в таблице 1. Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений.

 

Таблица 1 – Исходные данные

Поставщики	Потребители				Запасы (объемы отправления)
	B1	B2	…	Bn
A1	c11 x11	c12 x12	…	c1n x1n	a1
A2	c21 x21	c22 x22	…	c2n x2n	a2
…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmn xmn	am
Потребность	b1	b2	…	bn

 

Все грузы из i пунктов должны быть отправлены, т. е.:

    (1.1)

Все j пункты (потребители) должны быть обеспечены грузами в плановом объеме:

   (1.2)

Суммарные объемы отправления должны равняться суммарным объемам назначения:

=   (1.3)

Должно выполняться условие неотрицательности переменных: xij≥0, i=, j=. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

Zmin=.   (1.4)

В модели (1.1) – (1.4) вместо матрицы стоимостей перевозок (сij) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматриваются минимум суммарной транспортной работы. Как видно из выражения (1.3), уравнение баланса является обязательным условием решения транспортной задачи.

Транспортным задачам присущи следующие особенности:

1. распределению подлежат однородные ресурсы;
2. условия задачи описываются только уравнениями;
3. все переменные выражаются в одинаковых единицах измерения;

 

4. во всех уравнениях коэффициенты при неизвестных равны единице;
5. каждая неизвестная встречается только в двух уравнениях системы ограничений.

Виды транспортных задач:

1. Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

= .

2. Транспортная задача называется открытой, если суммарный объем отправляемых грузов не равен суммарному объему потребности в этих грузах по пунктам назначения (потребности выше запасов или наоборот), т.е.:

 ≠ .

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

1. потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;
2. запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.

 

 

1. Математические методы решения задачи

 

Методы решения транспортных задач.

Метод северно-западного угла (диагональный).

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

Метод наименьшего элемента.

Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьшую оценку; в случае наличия нескольких таких равных оценок заполняется та, в которую производится наибольшая доставка груза. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворяются все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана xij горизонтальным и вертикальным уравнениям.

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

При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными оценками. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальную стоимость. Если минимальная стоимость одинакова для нескольких клеток столбца (строки), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными стоимостями, находящимися в данном столбце (строке).

 

 

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

Решение задачи методом потенциалов включает следующие этапы:

1. разработку начального плана (опорного решения);
2. расчет потенциалов;
3. проверка плана на оптимальность;
4. поиск максимального звена неоптимальности (если условие п.3 не было достигнуто);
5. составление контура перераспределения ресурсов;
6. определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру;
7. получение нового плана.

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

 

2. Математическая модель

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

 

Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки на 17,12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. Тарифы (в д. е. за 1 т.) указаны в таблице 2.

Таблица 2 – Исходные данные задачи