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

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

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

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

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

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

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

Выполнил:

Проверил:

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

Саратов 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). Автомобили разных марок имеют разную грузоподъёмность q_i (т) и разные удельные эксплуатационные затраты c_i ($/км) – таблица 6. Компания получила заказы от m клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Q_j (т) и расстояние перевозки L_j (км). Заказы на перевозку выбираются из таблицы 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-го источника) равна S_i>0, i=l,...,m;

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

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

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

(1)

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

Для математического описания транспортной задачи вводят переменные x_ij, обозначающие объемы поставок товара от i-го ис­точника j-му стоку. В этом случае x_i1+x_i2+...+x_in — общий объ­ем поставок товара от i-го источника, т.е. мощность этого источ­ника; x_ij+x_i2+...+x_in — общий объем поставок товара к j-му стоку, т.е. мощность этого стока; c₁₁x₁₁+ c₁₂x₁₂+…+ c_mnx_mn — суммарная стоимость перевозок товара от источников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде:

(2)

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

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

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

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

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

Целевая ячейка С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 (величина c_ij рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).

Рисунок 2.1-1

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

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

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

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

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

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

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

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

(4)

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

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

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

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

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

В = общий объем спроса = D₆+D₅= 175+175 = 350 ед.

Для остальных складов объемы предложения S_i или объемы спроса D_j равны нулю (см. рис. 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, S_i = 1, i = 1,...,n, D_j = 1, j = 1,...,n. При этом условие , i,j = 1,...,n, означает выполнение требования целочисленности пере­менных х_ij. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом цело­численном решении значениями переменных могут быть только 0 и 1.

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

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

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

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

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

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

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

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

а) При n>m заказов меньше, чем автомобилей (избыток про­возных возможностей). В этом случае дополнительно вво­дятся n-m фиктивных клиентов с нулевыми объёмами зака­зов (т.е. Q_j=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-го клиента вычисляется по фор­муле

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

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

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

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

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

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

x_ij?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 с.