Реферат: Решение транспортных задач в Excel

👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

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

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

Кафедра «Организация перевозок и управление на транспорте»
«Информационные технологии на транспорте»
1. Классическая транспортная задача 3
1.1 Математическая постановка задачи 4
2. Транспортная задача с промежуточными пунктами 8
2.1 Математическая постановка задачи 9
2.2 Решение задачи в среде Excel 11
3.1 Математическая постановка задачи 15
3.2 Решение задачи в среде Excel 17
Список использованной литературы 25
Оптовая фирма по продаже цемента имеет четыре склада, находящиеся в разных районах г.Саратова, объёмы запасов на которых представлены на рисунке 1. Фирма обслуживает строительные организации, которые производят капитальный ремонт четырёх объектов, спрос которых также представлен на рисунке 1. Расстояния между складами и объектами строительства представлены в таблице 1.
Таблица 1 – Кратчайшие расстояния, км
Средняя стоимость перевозки 1 мешка с цементом на 1 км составляет 5 рублей. В результате получаем, представленную в таблице 2, стоимость перевозок по каждому маршруту.
Таблица 2 - Стоимость перевозок по каждому маршруту
1.1 Математическая постановка задачи

а) мощность i-го источника
(объем поставок товара от i
-го источника) равна S i

>0, i
=1,..., m
;
б) мощность j-го стока
(объем поставок товара к j
-му стоку) равна D j

>0, j
=1,..., n
;
в) стоимость перевозки единицы товара (в условных денежных единицах) от i
-го источника к j
-му стоку равна c
ij

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

+
x
i2

+...+
x in

— общий объем поставок товара от i
-го источника, т.е. мощность этого источника; x
1

j

+
x
2

j

+...+
x mj

— общий объем поставок товара к j-му стоку, т.е. мощность этого стока; c
11

x
11

+
c
12

x
12

+...+
c mn
x mn

— суммарная стоимость перевозок товара от источников к стокам. С учетом этого рассматриваемая задача может быть представлена в следующем виде:
На рисунке 3 показано представление транспортной задачи в виде сети с m
пунктами отправления и n
пунктами назначения, которые показаны в виде узлов
сети. Дуги
, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой ( i
,
j
), соединяющей пункт отправления i
с пунктом назначения j
, соотносятся два вида данных: стоимость c ij

перевозки единицы груза из пункта i
в пункт j
и количество перевозимого груза x ij

. Объем грузов в пункте отправления i
равен S i

, а объем грузов в пункте назначения j
равен D j

. Задача состоит в определении неизвестных величин x ij

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

от i
-го поставщика к j
-му потребителю. Во второй таблице представлены: значения S i

предложения каждого i
-го поставщика; значения D j

спроса каждого j
-го потребителя; переменные x ij

, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец "Сумма". Целевая ячейка D24 должна содержать формулу, выражающую целевую функцию:
Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.
В Excel несбалансированная транспортная задача решается путем изменения ограничений по спросу (если спрос превышает предложение) или по предложению (если предложение превышает спрос).
Таблица 9 – План оптимального закрепления
Потребительский спрос бассейна и школы удовлетворены полностью. На складе Волжского района остается не вывезенным 300 мешков, на Ленинском складе – 250 мешков.
Общая стоимость перевозки составляет 53500 условных единств.
В транспортной сети, показанной на рисунке 2, осуществляются перевозки груза из пунктов 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость перевозки единицы груза между пунктами показана в таблице 3. Предложение пунктов 1, 2 (П1 и П2) и спрос пунктов 5,6 (С5 и С6) выбирается соответственно из таблиц 4 и 5. Построить транспортную модель с промежуточными пунктами.
Рисунок 2 – Схема транспортной сети
Таблица 3 – Стоимость перевозки единицы груза между
2.1 Математическая постановка задачи

Одно практически важное обобщение классической транспортной задачи связано с учетом возможности доставки товара от i-го источника к j-му стоку по маршруту, проходящему через некоторый промежуточный пункт (склад). Так, например, промежуточные пункты являются составной частью распределительной системы любой крупной компании, имеющей сеть универсальных магазинов во многих городах. Такая компания обычно имеет зональные оптовые базы (источники), снабжающие товарами более мелкие региональные склады (промежуточные пункты), откуда эти товары поступают в розничную торговую сеть (стоки). При этом товар для каждого фиксированного стока в общем случае может быть доставлен не из любого источника и по маршрутам, не обязательно проходящим через все промежуточные пункты. Кроме того, промежуточные пункты могут обладать вполне определенной спецификой. Так, например, при транспортировке товара от источника к стоку по маршруту, проходящему через склад, часть товара может быть использована для создания неприкосновенного запаса на складе.
Задачу выбора плана перевозок товаров от источников стокам с учетом промежуточных пунктов, обеспечивающего минимальные транспортные затраты и потребности стоков, в исследовании операций называют транспортной задачей с промежуточными пунктами. Для приобретения практических навыков в построении математических моделей таких задач обратимся к следующему примеру.
На рисунке 4 представлена схема размещения складов, на которой указаны: а) склады в виде узлов сети с номерами от 1 до 6; б) избыток товара на складе, который должен быть перераспределен в системе складов (указан в квадратных скобках рядом с узлом сети положительным числом и выражен в единицах измерения товара); в) недостаток товара на складе, который должен быть устранен за счет его поставок с других складов системы (указан в квадратных скобках рядом с узлом сети отрицательным числом).
Рисунок 4 – Схема размещения складов
На рисунке 4 видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 2, равен суммарному недостатку товара, имеющемуся на складах с номерами 5, 6. Перераспределение товара может происходить через склады с номерами 3 и 4, которые в рассматриваемой задаче и являются промежуточными или транзитными пунктами. Истинными пунктами отправления являются лишь склады с номерами 1 и 2, на которых имеется избыток товара и с которых товар можно только вывозить, а истинным пунктом назначения является склад с номером 6, на котором есть недостаток товара, и на этот склад товары можно только завозить. Заметим также, что между складами с номерами 3 и 4 возможны перевозки в обоих направлениях, но в общем случае c 34
¹c 43
(например, наличие одностороннего движения по кратчайшему маршруту). Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом.
Объем предложения истинного пункта отправления = объем исходного предложения.
Объем предложения транзитного пункта = объем исходного предложения + объем буфера.
Объем спроса истинного пункта назначения = объем исходного спроса.
Объем спроса транзитного пункта = объем буфера.
Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса).
2.2 Решение транспортной задачи с промежуточными пунктами в
Excel

Необходимо найти решение транспортной задачи с промежуточными пунктами, если стоимость перевозки единицы товара составляет: c 13
=2 у.е., c 14
=3 у.е., c 23
=5 у.е., c 24
=4 у.е., c 34
=3 у.е., c 35
=6 у.е., c 43
=3 у.е., c 45
=4 у.е., c 46
=5 у.е., c 56
=4 у.е.
В Excel необходимо создать 2 таблицы: Стоимость перевозки единицы товара и Плана перевозок товара между складами. В таблице Стоимость перевозки единицы товара мы видим, что если между отдельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы заносится любое большое число (в данном случае 100)(таблица 10).
Таблица 10 – Стоимость перевозки единицы товара
B = общий объем предложения = S 1
+S 2
=170+180 = 350 ед.
B = общий объем спроса =D 6
+D 5
= 155 + 195= 350 ед.
Для остальных складов объемы предложения S i
или объемы спроса D j
равны нулю.
Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить.
Результат решения данной задачи представлен в таблице 11.
Таблица 11 – Оптимальный план перевозок
Видно, что оптимальный план перевозок товара между складами следующий:
- со склада 1 товар в количестве 170 единиц перевозиться в транзитный пункт 4;
- со склада 2 товар в количестве 180 единиц перевозиться в транзитный пункт 4;
- со склада 4 товар в количества 155 и 195 единиц перевозиться в транзитный пункт 5 и 6, который является истинным пунктом назначения.
Стоимость перевозок при этом минимальна и составляет 2825 условных денежных единиц.
У автотранспортной компании имеется n
автомобилей разных марок (выбирается из таблицы 7). Автомобили разных марок имеют разную грузоподъёмность q i

( т
) и разные удельные эксплуатационные затраты c i

( $/км
) – таблица 6. Компания получила заказы от m
клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Q j

( т
) и расстояние перевозки L

j

( км
). Заказы на перевозку выбираются из таблицы 8. Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы (руб./ткм) для клиентов на перевозки одинаковыми.
Таблица 6 – Характеристики автомобилей по маркам
Таблица 7 – Структура парка автомобилей автотранспортной компании
3.1 Математическая постановка задачи

гарантирует выполнение каждой работы лишь одним исполнителем, ограничение
Стоимость выполнения всего комплекса работ равна
Таким образом, задачу о назначениях можно записать следующим образом:
Задача о назначениях является частным случаем классической транспортной задачи, в которой надо положить n = m, S i
= 1, i = 1,...,n, D j
= 1, j = 1,...,n. При этом условие x ij
Î{0, 1}, i,j = 1,...,n, означает выполнение требования целочисленности переменных x ij
. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.
Как частный случай классической транспортной задачи, задачу о назначениях можно рассматривать как задачу линейного программирования. Поэтому в данном случае используют терминологию и теоретические результаты линейного программирования.
В задаче о назначениях переменное x ij
, может принимать значение 0 или 1. При этом в любом допустимом решении лишь n переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.
На практике встречаются задачи о назначениях, в постановках которых параметр c ij
для i,j= 1,...,n понимается как эффективность выполнения i-й работы j-м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения был бы максимальной, т.е.
где максимум ищется при указанных выше ограничениях.
3.2 Решение задачи о назначениях в
Excel

У автотранспортной компании имеется n
автомобилей разных марок. Автомобили разных марок имеют разную грузоподъёмность q i

( т
) и разные удельные эксплуатационные затраты c i

( $/км
). Компания получила заказы от m
клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Q j

( т
) и расстояние перевозки L j

( км
). Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки одинаковыми.
Покажем, что представленная задача удовлетворяет рассмотренным выше требованиям.
1) Поскольку тарифы одинаковые, то в качестве целевой функции следует выбрать эксплуатационные затраты. Эти затраты необходимо минимизировать путём оптимального распределения автомобилей по клиентам.
2) Поскольку в общем случае m
¹
n
, то задачу необходимо сбалансировать путём введения фиктивных заказов или фиктивных автомобилей. Получим:
а) При n
>
m
заказов меньше, чем автомобилей (избыток провозных возможностей). В этом случае дополнительно вводятся n
-
m
фиктивных клиентов с нулевыми объёмами заказов (т.е. Q j

=0 и L j

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

®¥). Практически это означает отказ от самых невыгодных в смысле затрат заказов.
3) Окончательно получим сбалансированную задачу, описываемую квадратной матрицей эксплуатационных затрат размерностью k
´
k
, где k
=
max{ m
,
n
}.
Алгоритм решения данной задачи в Excel сводится к следующему.
Количество рейсов i
-го автомобиля у j
-го клиента вычисляется по формуле
Количество рейсов - величина целочисленная, принимающая значение большее или равное 1. Для её вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках B29:C29 и D26:D27, то количество рейсов определяется функцией (второй параметр функции округления равен 0)
Пробег i
-го автомобиля у j
-го клиента вычисляется по формуле
Дополнительная целочисленная переменная логического типа принимает значения
Найдем решение задачи 3.1 в Excel, используя следующие исходные данные.
Автотранспортная компания располагает 10 автомобилями разных марок: 0 автомобилей марки A; 4 автомобиля марки B; 3 автомобиля марки C; 2 автомобиль марки D; 1 автомобилей марки E.
Представим в Excel таблицу с исходными данными. Поскольку заказов меньше имеющихся у компании автомобилей, необходимо ввести фиктивного клиента с нулевым объёмом перевозок. В той же таблице произвести необходимые промежуточные расчёты затрат по приведённым выше формулам
Введем Матрицу X ij
, содержащую переменные логического типа x ij

Матрица произведения S ij
*X ij
, в которой отразится результат оптимального закрепления автомобилей за клиентами и, соответствующие этому закреплению, минимальные затраты. Используя меню СервисÞПоиск решения открываем диалоговое окно Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек со значениями логической переменной x ij

(Матрица X ij
) и ограничения, и запускаем процедуру вычисления, щелкнув по кнопке Выполнить. Результат поиска будет находиться в изменяемых ячейках Матрицы X ij
( i
-
автомобиль; j
-
клиент) и в целевой ячейке (эксплуатационные затраты) (Таблица 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 с.

Название: Решение транспортных задач в Excel
Раздел: Рефераты по информатике
Тип: реферат
Добавлен 10:10:42 22 июня 2011 Похожие работы
Просмотров: 1305
Комментариев: 13
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Решение транспортных задач в Excel
Реферат: Николай II: реформы или революция
Курсовая работа по теме Средства массовой информации как инструмент социально-политической борьбы
Дипломная работа по теме Разработка информационной системы производства и реализации продукции на примере ТОО 'Мебель–Комп'
Лабораторная Работа Дождевой Червь 7 Класс
Бездушие Сочинение 9.3 Аргументы
Курсовой Проект Образец Архитектура
Сочинение Моя Семья 4 Класс Орксэ
Реферат по теме Автоматизация электрических сетей и систем
Реферат На Тему Внебюджетные Фонды В Рф
Творческая Работа На Тему Двигатели Внутреннего Сгорания
Курсовая работа: Формальные и неформальные группы в коллективе
Курсовая Работа На Тему Функции И Основные Принципы Организации Местного Самоуправления
Темы Для Рефератов По Физкультуре 4 Класс
Дипломная работа по теме Проектирование несущих и ограждающих конструкций одноэтажного производственного здания
Философия Науки Шокана Уалиханова Реферат
Диагностическая Контрольная Работа По Алгебре 9 Класс
Реферат На Тему Гурткова Робота З Образотворчого Мистецтва У Школі
Образец Характеристики О Прохождении Практики
Курсовая работа по теме Инженерная графика как эффективная методика в лесном хозяйстве
Магистерская диссертация по теме Государственное регулирование деятельности транспортной сферы Республики Казахстан
Контрольная работа: Система государственных органов, регулирующих финансовые отношения в Российской Федерации. Правовой режим функционирования внебюджетных фондов государства
Реферат: Загальна будова ПК Опис основних функціональних частинdf
Реферат: Белки-ферменты