Вход

Информационному решению экономических задач

Курсовая работа по программированию
Дата добавления: 30 января 2006
Язык курсовой: Русский
Word, rtf, 6 Мб
Курсовую можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу



Министерство образования и науки РФ

Саратовский государственный технический университет


Кафедра: «Организация перевозок и управление на транспорте»





КУРСОВАЯ РАБОТА

по дисциплине

«Информационные технологии на транспорте»






Выполнил:

Проверил:

асс. каф. «ОПТ» Красникова Д.А.





Саратов 2005




Задание на курсовую работу


Задание 1

Классическая транспортная задача


Оптовая фирма по продаже цемента имеет четыре склада, находящиеся в разных р-нах г.Саратова, объёмы запасов на которых представлены на рисунке 1. Фирма обслуживает строительные организации, которые производят капитальный ремонт четырёх объектов, спрос которых также представлен на рисунке 1. Расстояния между складами и объектами строительства представлены в таблице 1.


Рисунок 1 - Объёмы спроса и предложения


Таблица 1 – Кратчайшие расстояния, км


 

Объекты строительства

1

2

Стадион

Театр

Склады

1

Волжский

8

5

2

Ленинский

14

15

3

Заводской

3

17


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


Таблица 2 - Стоимость перевозок по каждому маршруту.


 

стадион

театр

Волжский

40

25

Ленинский

70

75

Заводской

15

85





Задание 2

Транспортная задача с промежуточными пунктами

В транспортной сети, показанной на рисунке 2, осуществляются перевозки груза из пунктов 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость перевозок единицы груза между пунктами показана в таблице 3. Предложение пунктов 1, 2 (П1 и П2) и спрос пунктов 5,6 (С5 и С6) выбирается соответственно номеру зачётной книжки из таблиц 4 и 5. Постройте транспортную модель с промежуточными пунктами и решите задачу в Excel.





130

220

175

175




Рисунок 2 – схема транспортной сети




Таблица 3 – Стоимость перевозки единицы груза между пунктами транспортной сети


Пункты

1-3

1-4

2-3

2-4

3-4

3-5

4-3

4-5

4-6

5-6

Стоимость, у.е.

2

3

5

4

3

6

3

4

5

4


Таблица 4 –Предложение пунктов 1 и 2


Предложение пункта 1

130

Предложение пункта 2

220


Таблица 2.3 – Спрос пунктов 5 и 6


Спрос пункта 5

175

Спрос пункта 6

175






Задание 3

Задача о назначениях


У автотранспортной компании имеется n автомобилей разных марок (выбирается по номеру зачётной книжки из таблицы 7). Автомобили разных марок имеют разную грузоподъёмность qi (т) и разные удельные эксплуатационные затраты ci ($/км) – таблица 6. Компания получила заказы от m клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Qj (т) и расстояние перевозки Lj (км). Заказы на перевозку выбираются из таблицы 8 Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы (руб./ткм) для клиентов на перевозки одинаковыми.


Таблица 6 – Характеристики автомобилей по маркам


Характеристики

Марка автомобиля

A

B

C

D

E

Грузоподъёмность, т

qi

20

16

8

5

2,5

Удельные затраты, $/км

ci

0,8

0,55

0,35

0,25

0,13


Таблица 7 – Структура парка автомобилей автотранспортной компании


Количество автомобилей

марки А

1

марки B

2

марки C

3

марки D

2

марки E

2



Таблица 8 – Заказ на перевозку груза


Характеристики

Клиенты

1

2

3

4

5

6

7

8

9

Qj, т

90

45

20

120

10

50

80

55

10

Lj, км

12

24

36

55

17

20

30

15

40






























Содержание:


Задание на курсовую работу…………………………………………..2

Содержание……………………………………………………………..7

Введение………………………………………………………………...8

Классическая транспортная задача……………………………………9

Транспортная задача с промежуточными данными………………...13

Задача о назначениях………………………………………………….18

Заключение……………………………………………………………..24

Список рекомендуемой литературы………………………………….25























Введение


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
































1. Классическая транспортная задача


1.1 Математическая постановка задачи


В исследовании операций под транспортной задачей обычно понимают задачу выбора плана перевозок некоторого то­вара (изделий, груза) от m источников (пунктов производства, поставщиков) к n стокам (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что:

а) мощность i-го источника (объем поста­вок товара от i-го источника) равна Si>0, i=l,...,m;

б) мощность j-го стока (объем поставок товара к j-му стоку) равна Dj >O, j=1,...,n;

в) стоимость перевозки единицы товара (в условных де­нежных единицах) от i-го источника к j-му стоку равна сij;

г) суммарная мощность всех источников равна суммарной мощно­сти всех стоков, т.е.

(1)

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

Для математического описания транспортной задачи вводят переменные xij, обозначающие объемы поставок товара от i-го ис­точника j-му стоку. В этом случае xi1+xi2+...+xin — общий объ­ем поставок товара от i-го источника, т.е. мощность этого источ­ника; xij+xi2+...+xin — общий объем поставок товара к j-му стоку, т.е. мощность этого стока; c11x11+ c12x12+…+ cmnxmn — суммарная стоимость перевозок товара от источников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде:

(2)

На рис. 1.1-1 показано представление транспортной задачи в виде сети с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы се­ти, соответствуют маршрутам, связывающим пункты отправле­ния и назначения. С дугой (i,j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: стоимость cij перевозки единицы груза из пункта i в пункт j и количество перевозимого груза хij. Объем грузов в пункте отправления i ра­вен Si, а объем грузов в пункте назначения j равен Dj. Задача со­стоит в определении неизвестных величин xij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограни­чениям, накладываемым на объемы грузов в пунктах отправления (предложение) и пунктах назначения (спрос).



Рисунок 1.1-1 – Представление транспортной задачи в виде сети


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


1.2 Решение задачи в среде Excel


Данную задачу можно решить симплекс-методом или с по­мощью, так называемой транспортной таблицы. Исходные данные для решения классической транспортной задачи целесообразно представить в виде двух таблиц (см. рис. 1.2-1), в первой из которых представлены значения стоимости перевозок единицы товара cij от i-го поставщика к j-му потреби­телю. Во второй таблице представлены: значения Si предложения каждого i-го поставщика; значения Dj спроса каждого j-го потребителя; переменные xij, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец «Сумма».

Целевая ячейка С17 должна содержать формулу, выра­жающую целевую функцию:

=СУММПРОИЗВ(С3:D6;С12:D14)


Средняя стоимость перевозки 1 мешка цемента



 

стадион

театр



Волжский

40

25



Ленинский

70

75



Заводской

15

85












Поставщики

Предложение

Потребители

Сумма

стадион

театр


Спрос

 

 

850

1500

2350

Волжский

1000

0

0

1000

Ленинский

1350

0

0

763

Заводской

1200

0

0

587

 

3550

850

1500

 

Стоимость перевозок руб.

144870



Рисунок 1.2-1


Используя меню Сервис?Поиск решения открываем диало­говое окно Поиск решения (см. рис. 2.2-2), в котором устанавли­ваем целевую ячейку равной минимальному значению, определя­ем диапазон изменяемых ячеек и ограничения и запускаем про­цедуру вычисления, щелкнув по кнопке Выполнить.



Рисунок 1.2-2


Данная задача является несбалансированной, т.к. спрос превышает предложение.

На рисунке 1.2-3 представлено оптимальное решение. На складах цемента не останется.


Поставщики

Предложение

Потребители

Сумма

стадион

театр

Спрос

 

 

850

1500

2350

Волжский

1000

850

150

1000

Ленинский

1350

0

763

763

Заводской

1200

0

587

587

 

3550

850

1500

 






Стоимость перевозок руб.

144870





Рисунок 1.2-3







2. Транспортная задача с промежуточными пунктами


2.1. Математическая постановка задачи


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

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

На рис. 2.1-1 представлена схема размещения складов, на ко­торой указаны: а) склады в виде узлов сети с номерами от 1 до 8; б) избыток товара на складе, который должен быть перераспре­делен в системе складов (указан в квадратных скобках рядом с узлом сети положительным числом и выражен в единицах изме­рения товара); в) недостаток товара на складе, который должен быть устранен за счет его поставок с других складов системы (указан в квадратных скобках рядом с узлом сети отрицательным числом); г) возможность перевозки товара со склада i на склад j (ориентированная дуга от круга с номером i к кругу с номером j); д) затраты, связанные с перевозкой единицы товара со склада i на склад j (величина cij рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).


Рисунок 2.1-1


На рис. 2.1-1 видно, что суммарный избыток товара, имею­щийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 той же системы. Перераспределение товара может происходить через склады с номерами 2, 4-7, которые в рассматриваемой зада­че и являются промежуточными или транзитными пунктами. Истинным пунктом отправления является лишь склад с номе­ром 1, на котором имеется избыток товара и с которого товар можно только вывозить, а истинными пунктами назначения являются склады с номерами 3 и 8, на которых есть недостаток товара, и на эти склады товары можно только завозить. Заметим также, что между складами с номерами 4 и 5 возможны перевоз­ки в обоих направлениях, но в общем случае c45?c54 (например, наличие одностороннего движения по кратчайшему маршруту).

Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом.

Объем предложения истинного пункта отправления = объем исходного предложения.

Объем предложения транзитного пункта = объем исходно­го предложения + объем буфера.

Объем спроса истинного пункта назначения = объем исход­ного спроса.

Объем спроса транзитного пункта = объем буфера.

Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса).

Пусть J —множество номеров складов, на которые товар может быть доставлен с k-то склада, а I — множество номеров складов, с которых товар может быть доставлен на k-й склад. Tk — величина чистого запаса товара, равная объему исходного предложения или исходного спроса. Тогда математическую мо­дель данной задачи можно представить следующим образом:

(4)



2.2. Решение транспортной задачи с промежуточными пунктами в Excel


Необходимо найти решение транспортной задачи с промежу­точными пунктами (стоимость перевозки единицы товара см. табл. 3).

В Excel представлены таблицы: Стоимость перевозки единицы товара и План перевозок товара между складами, сформированные на рабочем листе Excel. Здесь в таблице Стои­мость перевозки единицы товара мы видим, что если между от­дельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы (выделенные темным фо­ном) заносится любое большое число (в данном случае 100).

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

В = общий объем предложения = S1+S4=130+220 = 350 ед. или

В = общий объем спроса = D6+D5= 175+175 = 350 ед.

Для остальных складов объемы предложения Si или объемы спроса Dj равны нулю (см. рис. 2.1-1).



Рисунок 2.2-1

В целевую ячейку, в данном случае B23, необходимо зане­сти формулу: =СУММПРОИЗВ(C4:F8;C15:F19)

Используя меню Сервис =>Поиск решения открываем диало­говое окно Поиск решения (см. рис. 2.2-2), в котором устанавли­ваем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем про­цедуру вычисления, щелкнув по кнопке Выполнить.


Рисунок 2.2-2

Результат решения данной задачи представлен на рис. 2.2-3:



Рисунок 2.2-2















3. Задача о назначениях



3.1. Математическая постановка задачи


Предположим, что имеется n различных работ, каждую ко­торых может выполнить любой из n привлеченных исполнителей. Стоимость выполнения i-й работы j-ым исполнителем известна и равна сij (в условных денежных единицах). Необходимо распре­делить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затра­ты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше известна как задача о назначениях. Введем переменные хij, при­нимающие значение 1 в случае, когда i-ю работу выполняет i-й исполнитель и значение 0 во всех остальных случаях, ij = 1, n. Тогда ограничение

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

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

Таким образом, задачу о назначениях можно записать сле­дующим образом:

Задача о назначениях является частным случаем классиче­ской транспортной задачи, в которой надо положить n=m, Si = 1, i = 1,...,n, Dj = 1, j = 1,...,n. При этом условие , i,j = 1,...,n, означает выполнение требования целочисленности пере­менных хij. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом цело­численном решении значениями переменных могут быть только 0 и 1.

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

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

На практике встречаются задачи о назначениях, в постанов­ках которых параметр cij для i.j = 1,...,n понимается как эффектив­ность выполнения i-й работы j-м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения был бы максимальной, т.е.

где максимум ищется при указанных выше ограничениях.



3.2. Решение задачи о назначениях в Excel


Представленная задача удовлетворяет рас­смотренным выше требованиям:

  1. Поскольку тарифы одинаковые, то в качестве целевой функ­ции следует выбрать эксплуатационные затраты. Эти затраты необходимо минимизировать путём оптимального распреде­ления автомобилей по клиентам.

  2. Поскольку в общем случае m?n, то задачу необходимо сбалан­сировать путём введения фиктивных заказов или фиктивных автомобилей. Получим:

а) При n>m заказов меньше, чем автомобилей (избыток про­возных возможностей). В этом случае дополнительно вво­дятся n-m фиктивных клиентов с нулевыми объёмами зака­зов (т.е. Qj=O и Хj=0). Поскольку для фиктивных клиентов заказы нулевые, то для их выполнения будут назначаться самые неэффективные по затратам автомобили. Практиче­ски выполнение заказа фиктивного клиента означает резер­вирование автомобиля (автомобиль остаётся в парке).

б) При nj ??). Практически это означает отказ от самых невыгодных в смысле затрат зака­зов.

3) Окончательно получим сбалансированную задачу, описывае­мую квадратной матрицей эксплуатационных затрат размер­ностью kxk, где k=mах{m,n}.

Алгоритм решения данной задачи в Excel сводится к сле­дующему.

Количество рейсов i-го автомобиля у j-го клиента вычисляет­ся по формуле

, для всех ш=1,2,…,k; j=1,2,…k.

Количество рейсов - величина целочисленная, принимаю­щая значение большее или равное 1. Для её вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках В7:С7 и D4:D5, то количество рейсов определяется функцией (второй параметр функции округления равен 0)

=ОКРУГЛВВЕРХ($B7/D$5;0)

Пробег i-го автомобиля у j-го клиента вычисляется по фор­муле

Эксплуатационные затраты вычисляются по формуле

где ci - удельные эксплуатационные затраты, связанные с назна­чением i-го автомобиля для обслуживания j-го клиента, т.е. для приведенного выше примера в ячейку D7 необходимо занести формулу

=ОКРУГЛВВЕРХ($B7/D$5;0)*$C7*D$4


Дополнительная целочисленная переменная логического типа принимает значения

Целевая функция имеет вид

при ограничениях:

xij?0 целое для всех ш,о=1,2,…k.

Найдем решение задачи 3.1 в Excel, используя следующие исходные данные.

Автотранспортная компания располагает 10 автомобилями разных марок: 2 автомобиля марки А; 2 автомобиля марки В; 3 автомобиля марки С; 2 автомобиль марки D; 1 автомобиль марки Е.

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



Заключение


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

















Список используемой литературы:



  1. Бочкарев А.А. Решение задач транспортного типа в Excel: Учеб. пособие по спец. 062200 - Логистика / СПбГИЭУ. - СПб., 2002. - 64 с.

  2. Волков И.К., Загогуйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С. Зарубкина, А.П. Дрищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с.

  3. Кожин А.П. Математические методы в планировании и управлении автомобильными перевозками: Учеб. пособие для студентов экон. спец. вузов. - М.: Высш. школа, 1979. -304 с.

  4. Попов А.А. Excel: практическое руководство: Учеб. пособие для вузов. - М.: ДЕСС КОМ, 2001. -302с.

  5. Таха, Хэмди, А. Введение в исследование операций, 6-е издание.: Пер. с англ. - М.: Издательский дом "Вильямс", 2001. - 912 с.

  6. Транспортная логистика: Учебник для транспортных вузов. / Под общей редакцией Л.Б. Миротина. - М.: Издательство "Экзамен", 2002. - 512 с.



© Рефератбанк, 2002 - 2018