(7 оценок, среднее: 4,86 из 5)
Загрузка...
Учебная работа. Реферат: Решение транспортных задач в Excel
Саратовский Муниципальный технический Институт
Кафедра «Организация перевозок и управление на транспорте»
КУРСОВАЯ РАБОТА
по дисциплине
«Информационные технологии на транспорте»
Зачетная книга №070047
Выполнил: студент гр. ОПТ-33
Авдошин А.С.
Проверил: Красникова Д.А.
Саратов 2009
Содержание
1. Традиционная транспортная задачка 3
1.1 Математическая постановка задачки 4
1.2 Решение задачки в среде Excel 6
2. Транспортная задачка с промежными пт 8
2.1 Математическая постановка задачки 9
2.2 Решение задачки в среде Excel 11
3. Задачка о назначениях 15
3.1 Математическая постановка задачки 15
3.2 Решение задачки в среде Excel 17
Заключение 24
Перечень использованной литературы 25
Задание 1
Традиционная транспортная задачка
Оптовая компания по продаже цемента имеет четыре склада, находящиеся в различных районах г.Саратова, объёмы припасов на которых представлены на рисунке 1. Компанияобслуживает строй организации, которые создают серьезный ремонт четырёх объектов, Спрос которых также представлен на рисунке 1. Расстояния меж складами и объектами строительства представлены в таблице 1.
4
Таблица 1 – Кратчайшие расстояния, км
Объекты строительства
Бассейн
Школа
Волжский
10
9
Ленинский
4
10
Средняя стоимость перевозки 1 мешка с цементом на 1 км составляет 5 рублей. В итоге получаем, представленную в таблице 2, стоимость перевозок по любому маршруту.
Таблица 2 — Стоимость перевозок по любому маршруту
Стоимость перезозки, руб
Объекты строительства
Бассейн
Школа
Волжский
50
45
Ленинский
20
50
1.1 Математическая постановка задачки
В исследовании операций под
обычно соображают задачку выбора плана перевозок некого продукта (изделий, груза) от
(пт производства, поставщиков) к
(станциям предназначения, пт сбыта), обеспечивающего малые транспортные Издержки. При всем этом подразумевают, что:
а)
(размер поставок продукта от
-го источника) равна Si
>0,
=1,…,
;
б)
(размер поставок продукта к
-му стоку) равна Dj
>0,
=1,…,
;
в) стоимость перевозки единицы продукта (в условных валютных единицах) от
-го источника к
-му стоку равна
ij
;
(1)
г) суммарная мощность всех источников равна суммарной мощности всех стоков, т.е.
Дальше под объемом продукта будем осознавать его количество в фиксированных единицах измерения.
(2.1)
(2.2)
(2.3)
(2.4)
Для математического описания транспортной задачки вводят переменные xij
, обозначающие объемы поставок продукта от
-го источника к
-му стоку. В этом
случае
i1
i2
xin
— общий размер поставок продукта от
-го источника, т.е. мощность этого источника;
1
j
2
j
xmj
— общий размер поставок продукта к j-му стоку, т.е. мощность этого стока;
11
11
12
12
cmn
xmn
— суммарная стоимость перевозок продукта от источников к стокам. С учетом этого рассматриваемая задачка быть может представлена в последующем виде:
На рисунке 3 показано количество перевозимого груза xij
. Размер грузов в пт отправления
равен Si
, а размер грузов в пт предназначения
равен Dj
. задачка состоит в определении неведомых величин xij
, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пт отправления (предложение) и пт предназначения (Спрос).
Когда суммарный размер предложений (грузов, имеющихся в пт отправления) не равен общему размеру спроса на продукты (грузы), запрашиваемые пт предназначения, транспортная задачка именуется
. В этом случае, при решении традиционной транспортной задачки
, используют прием, позволяющий несбалансированную транспортную задачку создать равновесной. Для этого вводят
пункты предназначения либо отправления. Выполнение баланса транспортной задачки нужно для того, чтоб иметь возможность применить метод решения, построенный на использовании транспортных таблиц.
1.2 Решение задачки в среде
Excel
Данную задачку можно решить симплекс-методом либо при помощи, так именуемой,
. Начальные данные для решения традиционной транспортной задачки целенаправлено представить в виде 2-ух таблиц, в первой из которых представлены значения цены перевозок единицы продукта cij
от
-го поставщика к
-му пользователю. Во 2-ой таблице представлены: значения Si
предложения всякого
-го поставщика; значения Dj
спроса всякого
-го пользователя; переменные xij
, сначало принимающие нулевые значения; вспомогательная строчка и вспомогательный столбец «Сумма». Мотивированная ячейка D24 обязана содержать формулу, выражающую мотивированную функцию:
=СУММПРОИЗВ(B12:C13;C20:D21)
Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в каком устанавливаем мотивированную ячейку равной минимальному значению, определяем спектр изменяемых ячеек и ограничения и запускаем функцию вычисления, щелкнув по кнопочке Выполнить.
В Excel несбалансированная транспортная задачка решается методом конфигурации ограничений по спросу (если Спрос превосходит предложение) либо по предложению (если предложение превосходит Спрос).
Таблица 9 – План рационального закрепления
Потребительский Спрос бассейна и школы удовлетворены стопроцентно. На складе Волжского района остается не вывезенным 300 мешков, на Ленинском складе – 250 мешков.
Общая стоимость перевозки составляет 53500 условных единств.
задачка 2.
В транспортной сети, показанной на рисунке 2, осуществляются перевозки груза из пт 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость перевозки единицы груза меж пт показана в таблице 3. Предложение пт 1, 2 (П1 и П2) и Спрос пт 5,6 (С5 и С6) выбирается соответственно из таблиц 4 и 5. Выстроить транспортную модель с промежными пт.
Набросок 2 – Схема транспортной сети
Таблица 3 – Стоимость перевозки единицы груза меж
пт транспортной сети
Поставщиики
Пользователи
3
4
5
6
1
2
3
100
100
2
5
4
100
100
3
0
3
6
100
4
3
0
4
5
5
100
100
0
4
Таблица 4 – Предложение пт 1 и 2
ПРЕДЛОЖЕНИЕ ПУНКТА 1
170
ПРЕДЛОЖЕНИЕ ПУНКТА 2
180
Таблица 5 – Спрос пт 5 и 6
СПРОС ПУНКТА 5
155
СПРОС ПУНКТА 6
195
2.1 Математическая постановка задачки
Одно фактически принципиальное обобщение традиционной транспортной задачки соединено с учетом способности доставки продукта от i-го источника к j-му стоку по маршруту, проходящему через некий промежный пункт (склад). Так, к примеру, промежные пункты являются составной частью распределительной системы хоть какой большой компании, имеющей сеть всепригодных магазинов в почти всех городках. Таковая компания обычно имеет зональные оптовые базы (источники), снабжающие продуктами наиболее маленькие региональные склады (промежные пункты), откуда эти продукты поступают в розничную торговую сеть (стоки). При всем этом продукт для всякого фиксированного стока в общем случае быть может доставлен не из хоть какого источника и по маршрутам, не непременно проходящим через все промежные пункты. Не считая того, промежные пункты могут владеть полностью определенной специфичностью. Так, к примеру, при транспортировке продукта от источника к стоку по маршруту, проходящему через склад, часть продукта быть может применена для сотворения неприкосновенного припаса на складе.
Задачку выбора плана перевозок продуктов от источников стокам с учетом промежных пт, обеспечивающего малые транспортные Издержки и потребности стоков, в исследовании операций именуют транспортной задачей с промежными пт. Для приобретения практических способностей в построении математических моделей таковых задач обратимся к последующему примеру.
На рисунке 4 представлена схема размещения складов, на которой указаны: а) склады в виде узлов сети с номерами от 1 до 6; б) излишек продукта на складе, который должен быть перераспределен в системе складов (указан в квадратных скобках с узлом сети положительным числом и выражен в единицах измерения продукта); в) недочет продукта на складе, который должен быть устранен за счет его поставок с остальных складов системы (указан в квадратных скобках рядом с узлом сети отрицательным числом).
[
200
]
[
150
]
Набросок 4 – Схема размещения складов
На рисунке 4 видно, что суммарный излишек продукта, имеющийся на складах системы с номерами 1 и 2, равен суммарному недочету продукта, имеющемуся на складах с номерами 5, 6. Перераспределение продукта может происходить через склады с номерами 3 и 4, которые в рассматриваемой задачке и являются промежными либо транзитными пт. Настоящими пт отправления являются только склады с номерами 1 и 2, на которых имеется излишек продукта и с которых продукт можно лишь вывозить, а настоящим пт предназначения является склад с номером 6, на котором есть недочет продукта, и на этот склад продукты можно лишь завозить. Заметим также, что меж складами с номерами 3 и 4 вероятны перевозки в обоих направлениях, но в общем случае c34
¹c43
(к примеру, наличие однобокого движения по кратчайшему маршруту). Объемы спроса и предложения, надлежащие сиим пт отправления и предназначения, рассчитываются последующим образом.
Размер предложения настоящего пт отправления = размер начального предложения.
Размер предложения транзитного пт = размер начального предложения + размер буфера.
Размер спроса настоящего пт предназначения = размер начального спроса.
Размер спроса транзитного пт = размер буфера.
Размер буфера должен быть таковым, чтоб вместить размер всего предложения (либо спроса).
(4.1)
(4.4)
(4.3)
(4.2)
(4.6)
(4.5)
Пусть J — огромное количество номеров складов, на которые продукт быть может доставлен с k-го склада, а I — огромное количество номеров складов, с которых продукт быть может доставлен на k-й склад. Tk
— величина незапятнанного припаса продукта, равная размеру начального предложения либо начального спроса. Тогда математическую модель данной задачки можно представить последующим образом:
(4.5)
2.2 Решение транспортной задачки с промежными пт в
Excel
нужно отыскать решение транспортной задачки с промежными пт, если стоимость перевозки единицы продукта составляет: c13
=2 у.е., c14
=3 у.е., c23
=5 у.е., c24
=4 у.е., c34
=3 у.е., c35
=6 у.е., c43
=3 у.е., c45
=4 у.е., c46
=5 у.е., c56
=4 у.е.
В Excel нужно сделать 2 таблицы: Стоимость перевозки единицы продукта и Плана перевозок продукта меж складами. В таблице Стоимость перевозки единицы продукта мы лицезреем, что если меж отдельными складами отсутствует возможность перевозки продукта, то в надлежащие ячейки таблицы заносится хоть какое огромное число (в данном случае 100)(таблица 10).
Таблица 10 – Стоимость перевозки единицы продукта
Поставщиики
Пользователи
3
4
5
6
1
2
3
100
100
2
5
4
100
100
3
0
3
6
100
4
3
0
4
5
5
100
100
0
4
(5)
Для того чтоб отыскать в таблице Плана перевозок продукта меж складами размер предложения и размер спроса, определим размер буфера B по последующему правилу:
B = общий размер предложения = S1
+S2
=170+180 = 350 ед.
(6)
либо
B = общий размер спроса =D6
+D5
= 155 + 195= 350 ед.
Для других складов объемы предложения Si
либо объемы спроса Dj
равны нулю.
(7)
В мотивированную ячейку, в данном случае D25, нужно занести формулу: =СУММПРОИЗВ(B5:E9;C18:F22)
Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в каком устанавливаем мотивированную ячейку равной минимальному значению, определяем спектр изменяемых ячеек и ограничения и запускаем функцию вычисления, щелкнув по кнопочке Выполнить.
Итог решения данной задачки представлен в таблице 11.
Таблица 11 – Лучший план перевозок
Видно, что лучший план перевозок продукта меж складами последующий:
— со склада 1 продукт в количестве 170 единиц перевозиться в транзитный пункт 4;
— со склада 2 продукт в количестве 180 единиц перевозиться в транзитный пункт 4;
— со склада 4 продукт в количества 155 и 195 единиц перевозиться в транзитный пункт 5 и 6, который является настоящим пт предназначения.
Стоимость перевозок при всем этом мала и составляет 2825 условных валютных единиц.
задачка 3
Задачка о назначениях
У автотранспортной компании имеется
каров различных марок (выбирается из таблицы 7). Авто различных марок имеют разную грузоподъёмность qi
(
) и различные удельные эксплуатационные Издержки ci
(
) – таблица 6. Компания получила заказы от
клиентов на перевозку грузов. Причём в любом заказе указан объём перевозимого груза Qj
(
) и расстояние перевозки
j
(
). Заказы на перевозку выбираются из таблицы 8. Требуется, используя табличный машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) (либо вычислительной системы) которое делает арифметические и логические операции данные программкой преобразования инфы управляет вычислительным действием и коор Excel, хорошим образом назначить авто на рейсы для выполнения заказов клиентов, полагая тарифы (руб./ткм) для клиентов на перевозки схожими.
Таблица 6 – свойства каров по маркам
Таблица 7 – структура парка каров автотранспортной компании
КОЛИЧЕСТВО АВТОМОБИЛЕЙ
МАРКИ А
МАРКИ В
МАРКИ С
МАРКИ D
МАРКИ Е
0
4
3
2
1
ХАРАКТЕРИСТИКИ
КЛИЕНТЫ
1
2
3
4
5
6
7
8
9
Qj
, Т
100
35
45
95
15
125
35
5
50
Lj
, КМ
50
60
70
18
20
10
12
25
28
3.1 Математическая постановка задачки
(8)
Представим, что имеется n разных работ, каждую которых может выполнить хоть какой из n завлеченных исполнителей. Стоимость выполнения i-й работы j-м исполнителем известна и равна cij
(в условных валютных единицах). нужно распределить исполнителей по работам (назначить 1-го исполнителя на каждую работу) так, чтоб минимизировать суммарные издержки, связанные с выполнением всего комплекса работ.
(9)
В исследовании операций задачка, сформулированная выше известна как задачка о назначениях. Введем переменные xij
, принимающие гарантирует выполнение каждой работы только одним исполнителем, ограничение
гарантирует, что любой из исполнителей будет делать только одну работу.
(10)
Стоимость выполнения всего комплекса работ равна
Таковым образом, задачку о назначениях можно записать последующим образом:
задачка о назначениях является личным случаем традиционной транспортной задачки, в какой нужно положить n = m, Si
= 1, i = 1,…,n, Dj
= 1, j = 1,…,n. При всем этом условие xij
Î{0, 1}, i,j = 1,…,n, значит выполнение требования целочисленности переменных xij
. Это соединено с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть лишь 0 и 1.
Как личный вариант традиционной транспортной задачки, задачку о назначениях можно разглядывать как задачку линейного программирования. Потому в данном случае употребляют терминологию и теоретические результаты линейного программирования.
В задачке о назначениях переменное xij
, может принимать значения 1. Таковым образом, хоть какое допустимое базовое решение задачки о назначениях будет вырожденным.
На практике встречаются задачки о назначениях, в постановках которых параметр cij
для i,j= 1,…,n понимается как эффективность выполнения i-й работы j-м исполнителем. В этих вариантах необходимо так распределить работы меж исполнителями, чтоб суммарная эффективность их выполнения был бы наибольшей, т.е.
(12)
где максимум ищется при обозначенных выше ограничениях.
3.2 Решение задачки о назначениях в
Excel
У автотранспортной компании имеется
каров различных марок. Авто различных марок имеют разную грузоподъёмность qi
(
) и различные удельные эксплуатационные Издержки ci
(
). Компания получила заказы от
клиентов на перевозку грузов. Причём в любом заказе указан объём перевозимого груза Qj
(
) и расстояние перевозки Lj
(
). Требуется, используя табличный машина — комплекс технических средств, предназначенных для автоматической обработки информации в процессе решения вычислительных и информационных задач) (либо вычислительной системы) которое делает арифметические и логические операции данные программкой преобразования инфы управляет вычислительным действием и коор Excel, хорошим образом назначить авто на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки схожими.
Покажем, что представленная задачка удовлетворяет рассмотренным выше требованиям.
1) Так как тарифы схожие, то в качестве мотивированной функции следует избрать эксплуатационные Издержки. Эти издержки нужно минимизировать путём рационального распределения каров по клиентам.
2) Так как в общем случае
, то задачку нужно сбалансировать путём введения фиктивных заказов либо фиктивных каров. Получим:
а) При
заказов меньше, чем каров (излишек провозных способностей). В этом случае добавочно вводятся
фиктивных клиентов с нулевыми объёмами заказов (т.е. Qj
=0 и Lj
=0). Так как для фиктивных клиентов заказы нулевые, то для их выполнения будут назначаться самые неэффективные по затратам авто. Фактически выполнение заказа фиктивного клиента значит резервирование кара (кар остаётся в парке).
б) При
заказов больше, чем каров (недочет провозных способностей). В этом случае добавочно вводятся
фиктивных каров с нескончаемо большенными удельными затратами (т.е.
j
®¥). Фактически это значит отказ от самых нерентабельных в смысле издержек заказов.
3) совсем получим равновесную задачку, описываемую квадратной матрицей эксплуатационных издержек размерностью
, где
max{
}.
метод решения данной задачки в Excel сводится к последующему.
количество рейсов
-го кара у
-го клиента рассчитывается по формуле
(13)
, для всех
=1,2,…
;
=1,2,…
.
количество рейсов — величина целочисленная, принимающая значение большее либо равное 1. Для её вычисления следует пользоваться функцией округления личного от деления в огромную сторону. К примеру, если начальные данные находятся в ячейках B29:C29 и D26:D27, то количество рейсов определяется функцией (2-ой параметр функции округления равен 0)
(14)
=ОКРУГЛВВЕРХ($B6/D$5;0)
Пробег
-го кара у
-го клиента рассчитывается по формуле
(15)
(16)
Эксплуатационные издержки рассчитываются по формуле
,
(17)
где ci
– удельные эксплуатационные Издержки, связанные с предназначением
-го кара для обслуживания
-го клиента, т.е. для приведенного выше примера в ячейку D6 нужно занести формулу
=ОКРУГЛВВЕРХ($B6/D$3;0)*$C6*D$4
Доборная целочисленная переменная логического типа воспринимает значения
(18)
Мотивированная функция имеет вид
(19)
при ограничениях:
(20)
; 
; 
целое для всех
=1,2,…
.
Найдем решение задачки 3.1 в Excel, используя последующие начальные данные.
Автотранспортная компания располагает 10 авто различных марок: 0 каров марки A; 4 кара марки B; 3 кара марки C; 2 кар марки D; 1 каров марки E.
Представим в Excel таблицу с начальными данными. Так как заказов меньше имеющихся у компании каров, нужно ввести фиктивного клиента с нулевым объёмом перевозок. В той же таблице произвести нужные промежные расчёты издержек по приведённым выше формулам
Таблица 12 – Матрица издержек Sij
Введем Матрицу Xij
, содержащую переменные логического типа xij
Матрица произведения Sij
*Xij
, в какой отразится итог рационального закрепления каров за клиентами и, надлежащие этому закреплению, малые Издержки. Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в каком устанавливаем мотивированную ячейку равной минимальному значению, определяем спектр изменяемых ячеек со значениями логической переменной xij
(Матрица Xij
) и ограничения, и запускаем функцию вычисления, щелкнув по кнопочке Выполнить. Итог поиска будет находиться в изменяемых ячейках Матрицы Xij
(
кар;
клиент) и в мотивированной ячейке (эксплуатационные издержки) (Таблица 13 и Таблица 14).
Таблица 13 — Наилучшее закрепление каров 
Разумеется, что девятый кар, назначенный фиктивному десятому клиенту, будет простаивать в парке.
Таблица 14 – Издержки, надлежащие хорошему закреплению каров
Видно, что малые Издержки на перевозки составят:
— кар №1 закреплен за 6-ым клиентом, малые Издержки на перевозку составляют 44;
— кар №2 закреплен за 3-ым клиентом, малые Издержки на перевозку составляют 116;
— кар №3 закреплен за 4-ым клиентом, малые Издержки на перевозку составляют 59;
— кар №4 закреплен за 1-ым клиентом, малые Издержки на перевозку составляют 192;
— кар №5 закреплен за 9-ым клиентом, малые Издержки на перевозку составляют 69;
— кар №6 закреплен за 5-ым клиентом, малые Издержки на перевозку составляют 14;
— кар №7 закреплен за 2-им клиентом, малые Издержки на перевозку составляют 105;
— кар №8 закреплен за 8-ым клиентом, малые Издержки на перевозку составляют 6;
— кар №10 закреплен за 7-ым клиентом, малые Издержки на перевозку составляют 22.
Эксплуатационные издержки составляют 627у.е.
Заключение
Применение таблиц Excel позволило заавтоматизировать поиск решений при решении транспортной задачки, а конкретно при решении традиционной транспортной задачки и транспортной задачки с промежными пт отыскать лучшую перевозку грузов меж пт с минимальными затратами, также наилучшее распределение машин меж клиентами для воплощения перевозки с минимальными затратами. Преимуществами данных способов решения является их универсальность и простота в работе при высочайшей точности результатов.
Перечень использованной литературы
1 Бочкарев А.А. Решение задач транспортного типа в Excel: Учеб. пособие по спец. 062200 — Логистика / А.А. Бочкарев. СПбГИЭУ. — СПб., 2002. — 64 с.
2 Волков И.К., Загоруйко Е.А. исследование операций: Учеб. для вузов / И.К. Волков, Е.А. Загоруйко. / Под ред. В.С. Зарубка, А.П. Крищенко. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. — 436 с.
3 Кожин А.П. Математические способы в планировании и управлении авто перевозками: Учеб. пособие для студентов экон. спец. вузов. / А.П. Кожин — М.: Высш. школа, 1979. -304 с.
4 Попов А.А. Excel: практическое управление: Учеб. пособие для вузов. / А.А. Попов — М.: ДЕСС КОМ, 2001. -302с.
5 Таха, Хэмди, А. Введение в исследование операций, 6-е издание.: / Таха, Хэмди, / Пер. с англ. — М.: Издательский дом «Вильямс», 2001. -912 с.
6 Транспортная логистика: Учебник для транспортных вузов. / Под общей редакцией Л.Б. Миротина. — М.: Издательство «Экзамен», 2002. -512 с.
]]>