Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФГОУ СПО «Волгоградский государственный экономико-технический колледж»

ПЦК Информационных технологий

КУРСОВОЙ ПРОЕКТ

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

на тему: Проблема доставки груза в кратчайшие сроки

Студента Клыгина Артема Сергеевича

Руководитель Еловенко Н.А.

Волгоград 2011



Содержание

Введение

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

1.1 Понятие сетевого моделирования

1.2 Транспортная задача в сетевой постановке

1.3 Планирование работ коммерческой деятельности

2. Практическая часть

2.1 Решение задачи с помощью математического аппарата

2.2 Решение задачи в Excel

2.3 Автоматизация решения задачи

Заключение

Библиографический список

Приложение



Введение

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

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

1) изучить предметную область;

2) разобрать этапы (методы) решения задач с помощью математического аппарата;

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

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



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

1.1 Сетевое моделирование

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

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

Рис. 1.1.1 Ориентированный граф движения денежных средств на счетах бухгалтерского учета



Например, на рис.1.1.2 изображена сетевая модель комплекса работ по переводу торгового предприятия на самообслуживание.

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

Рис. 1.1.2 Сетевая модель перевода торгового предприятия на самообслуживание

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

Исходное (1) - это такое событие, с которого начинается выполнение всего комплекса операций, а завершается событие (32) соответствует достижению конечной цели. События обозначаются кружками, квадратиками, ромбами или другими геометрическими фигурами.

В сетевом моделировании различают следующие понятия:

1) фактическая работа (6, 7) изображена стрелкой (>), это процесс, требующий затрат ресурсов - времени, денег, людей, электроэнергии, товаров и т.д.;

2) работа-ожидание (?•?•>), это процесс, требующий только затрат времени, например ожидание, сушка, старение, затвердевание цементного раствора и т.д.;

3) критическая работа (=>), наиболее напряженная, нагруженная работа (13, 15);

4) фиктивная работа (? ? ? >) обозначает логическую зависимость между работами (28, 29), имеет нулевую продолжительность;

5) путь - любая непрерывная последовательность событий и работ;

6) критический путь - это путь, не имеющий резерв, включает только критические работы (1, 2), (2, 12), (12, 13), (13, 15), (15, 27), (27, 29), (29, 30), (30, 31), (31, 32).

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

1.2 Транспортная задача в сетевой постановке

моделирование математический программа

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

Имеется ряд пунктов производства А₁, А₂, …,А_m с объемами производства в единицу времени (месяц, квартал), равными соответственно a₁, a₂, …, a_m, и пункты потребления B_1, B_2, …, B_n потребляющие за тот же промежуток времени соответственно b₁, b₂, …, b_n продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех m пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-получателях:

(1.2.1)

Кроме того, известны затраты по перевозке единицы продукта от каждого поставщика к каждому получателю - эти величины обозначаются C_ij. В качестве неизвестных величин выступают объемы продукта, перевозимого из каждого пункта производства в каждый пункт потребления, соответственно обозначаемые X_ij.

Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

(1.2.2)

При этом каждый потребитель получает нужное количество продукта:

(1.2.3)



и каждый поставщик отгружает весь произведенный им продукт:

(1.2.4)

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

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

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

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

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

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

1.3 Планирование работ коммерческой деятельности

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

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

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

Множество возникающих задач коммерческой деятельности можно свести к одной из трех наиболее типичных постановок задач оптимизации.

1) Какое максимальное количество средств и каким образом может быть высвобождено при заданной организации работ при условии, что общее время выполнения всего комплекса работ не возросло?

2) Как наилучшим образом использовать выделенные ограниченные ресурсы, чтобы время выполнения всего комплекса работ не превысило заданной величины?

3) Как распределить выделенные ресурсы между работами, чтобы время выполнения всего комплекса работ было бы минимальным?

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

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

- В - общие ресурсы по выполнению комплекса работ;

- b_ij - выделенные ресурсы для выполнения элементарной работы (i, j);

- t_ij - длительность выполнения элементарной работы (i, j) выделенными ресурсами b_ij;

- c_ij - коэффициент пересчета ресурсов работы (i, j); c_ij=;

- Т - время выполнения всего комплекса;

- п - количество работ.

Затем проводят выбор главного экономического показателя, критерия эффективности, по которому определяется успех выполнения всего комплекса, например время выполнения работ Т или ресурсы В. В качестве критерия эффективности выбираем T - время, которое необходимо найти минимальным из возможных.

В начале решения задачи рассматривается исходный вариант распределения общих ресурсов В по элементарным работам b_ij, что и определяет длительность их выполнения, поскольку известна t_ij= f(b_ij).

Затем проводятся следующие операции:

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

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

Поскольку управляемыми параметрами являются ресурсы элементарных работ b_ij, определяющие длительность их выполнения t_ij, то необходимо найти новый вариант перераспределения выделенных ресурсов В путем переноса с одних работ (i, j) части ресурсов 0 < x_ij ? b_ij на другие работы (h, k), т. е. x_ij = x_hk так, чтобы общий срок выполнения работ был минимальным из возможных. Математическую модель задачи по переводу предприятия розничной торговли на самообслуживание можно представить таким образом: найти такой вариант распределения ограниченных ресурсов В между элементарными работами

(1.3.1)

и такие неотрицательные значения длительностей их выполнения

(1.3.2)

обращали бы в минимум функцию цели:

(1.1.3.3)

Решение задач этого класса может быть решено методами сетевого планирования.



2. Практическая часть

Условие задачи: Постройте сетевую модель задачи планирования поставки товаров оптовым покупателям. Проведите оптимизацию по критерию времени, определите критический путь, резервы времени и экономию.

Табл. 1. Исходных данных

Содержание работ	Работа	Длительность, ti
	Коэффициент, ci	Обозначение, ai	Опорная, aj
Отбор товара	0,1	a1	-	2
Подготовка к отправке	0,2	a2	a1	3
Выписка накладных	0,3	a3	a2	1
Определение объема отгрузки	0,4	a4	a3	1
Проверка цен	0,5	a5	a3	1
Оформление счета	0,6	a6	a5	1
Заказ автомашин	0,7	a7	a4 a6	3
Отправление счета покупателю	0,8	a8	a4 a6	1
Проверка товара по счету	0,9	a9	a7	2
Оплата счета	1,0	a10	a7	12
Погрузка товара и проверка колличества	1,1	a11	a9 a10	2
Перевозка товара	1,2	a12	a11	4
Выгрузка и сверка с документами	1,3	a13	a12	4

Входные данные:

T_i - длительность работ (дни);

с_i - коэффициент напряженности.

Выходные данные:

T_i - оптимальное время выполнения комплексов работ;

R - резерв времени.



2.1 Решение задачи с помощью математического аппарата

Построение сетевой модели.

Рис. 2.1.1 Исходный временной график.

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

L₁= [(0,1) (1,2) (2,3) (3,5) (5,6) (6,8) (8,10) (10,11) (11,12) (12,13)],

L₂= [(0,1) (1,2) (2,3) (3,5) (5,6) (6,7) (7,9) (9,11) (11,12) (12,13)],

L₃= [(0,1) (1,2) (2,3) (3,4) (4,6) (6,8) (8,10) (10,11) (11,12) (12,13)],

L₄= [(0,1) (1,2) (2,3) (3,4) (4,7) (7,9) (9,11) (11,12) (12,13)].

Определим длительность этих путей :

T₁= t(L₁) = a₁ + a₂ + a₃ + a₅ + a₆ + a₈ + a₁₀ + a₁₁ + a₁₂ + a₁₃ =

= 2 + 3 + 1 + 1 + 1 + 1 + 12 + 2 + 4 + 4 = 31 дн.

T₂= t(L₂) = a₁ + a₂ + a₃ + a₅ + a₆ + a₇ + a₉ + a₁₁ + a₁₂ + a₁₃ =

= 2 + 3 + 1 + 1 + 1 + 3 + 2 + 2 + 4 + 4 = 23 дн.

T₃= t(L₃) = a₁ + a₂ + a₃ + a₄ + a₈ + a₁₀ + a₁₁ + a₁₂ + a₁₃ =

= 2 + 3 + 1 + 1 + 1 + 12 + 2 + 4 + 4 = 30 дн.

T₄= t(L₄) = a₁ + a₂ + a₃ + a₄ + a₇ + a₉ + a₁₁ + a₁₂ + a₁₃ =

= 2 + 3 + 1 + 1 + 3 + 2 + 2 + 4 + 4 = 22 дн.



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

Т_КР= max{t(L_i)} = 31дн.

Длительность пути L₄ составляет t(L₄) = 22 дней, т.е. минимальна, однако не позволяет выполнить поставку товаров.

Теперь определим полные резервы времени по всем путям:

R(L₁) = T_KP - T₁ = 0

R(L₂) = T_KP - T₂ = 8 дн.

R(L₃) = T_KP - T₃ = 1дн.

R(L₄) = T_KP - T₄ = 9дн.

Сетевой график поставки товаров составлен таким образом, что израсходованы все ресурсы. Однако на этом графике не все работы критические, поэтому можно уменьшить время T_KP за счет резервов, имеющихся на некритических работах. Перенеся эти резервы на критические работы, можно уменьшить время их выполнения и тем самым получить новые сроки выполнения работ и соответственно меньший T_KP. Оптимальным сетевым планом будет такой план, когда T⁰_KP получится наименьшим из всех возможных в данных условиях. Очевидно, новые длительности всех путей в таком случае будут равны, т.е.



Величину переносимых средств и длительности новых равных критических путей = = можно найти, составив и решив следующую систему уравнений:

Рис. 2.1.2 Временной график после первого этапа оптимизации.

,

Определим длительность этих путей :



дн.

дн.

дн.

дн.

дн.

Рис. 2.1.3 Оптимальный временной график.

,

Определим длительность этих путей :



дн.

дн.

дн.

Оптимизация закончена. Таким образом, применение методов сетевого моделирования позволило выявить экономию 31 - 23,48 = 7,52 дня для поставки товаров оптовым покупателям.

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

2.2 Решение задачи в Excel

Создание формы для ввода исходных данных

Процесс разработки формы в Microsoft Office Excel 2007:

1. Запустить Microsoft Office Excel 2007.

2. Открыть вкладку «Разработчики» (нажмите кнопку Office правой кнопкой мыши / Настройка панели быстрого доступа / Основные / поставить флажок «Показывать вкладку Разработчик на ленте»).

3. Разместить на Рабочем листе Excel элемент управления Кнопка и настроить его вид.

4. В окне «Назначить макрос объекту» нажать кнопку «Создать».

5. В открывшемся окне Microsoft Visual Basic выбрать команду для создания новой формы: Insert / UserForm.

6. В тексте процедуры Кнопка1_Щелчок() записать команду вызова формы при нажатии на кнопку: UserForm1.Show

7. Разместить на форме элементы Label, TextBox и CommandButton.

8. В обработчике события Нажатие на кнопку «ввести» описать процедуру заполнения ячеек на Рабочем листе Excel, данными, введёнными соответственно в форму. Процедура описывается следующим образом:

Private Sub CommandButton1_Click()

Worksheets("Лист1").Range("A1") = TextBox1.Text



Заключение

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

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

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

Автоматизировать процесс решения задачи удалось с помощью встроенного в MS Office языка программирования - Microsoft Visual Basic 6.5. Однако это не сделало процесс решения универсальным: разработанное приложение решает только задачу, представленную данной темой курсового проектирования.

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



Библиографический список

1) ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

2) Варфоломеев, В.И. Алгоритмическое моделирование элементов экономических систем.: Практикум. Учеб. Пособие / В.И. Варфоломеев; - М.: Финансы и статистика, 2008.- 280 с.

3) Лукасевич, И.Я. Анализ финансовых операций. Методы, модели, техника вычислений в EXCEL.: Учеб. Пособие/ И.Я. Лукасевич; - М.: Финансы, 2009. - 400 с.

4) Советов, Б.Я. Моделирование систем.: Учебник для вузов по спец. ЭВМ/ Б.Я Советов, С.А. Яковлев; - М.: Высш. шк. 2007. - 345 с.

5) Фомин, Г.П. Математические методы и модели в коммерческой деятельности.: Учебник / Г.П. Фомин; - 2-е изд. - М.: Финансы и статистика, 2005. - 616 с.: ил.

6) Шаповал, А.Б. Математические методы.: Учебное пособие для вузов / А.Б. Шаповал. - М.: ИНФРА-М, 2007.



Приложение

Блок-схема решения задачи

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на Allbest.ru