Министерство образования и науки РФ Саратовский государственный технический университет Кафедра Организация перевозок и управление на транспорте КУРСОВАЯ РАБОТА по дисциплине Информационные технологии на транспорте Выполнил Проверил асс. каф. ОПТ Красникова Д.А. Саратов 2005 Задание на курсовую работу Задание 1 Классическая транспортная задача
Оптовая фирма по продаже цемента имеет четыре склада, находящиеся в разных р-нах г.Саратова, объмы запасов на которых представлены на рисунке 1. Фирма обслуживает строительные организации, которые производят капитальный ремонт четырх объектов, спрос которых также представлен на рисунке 1. Расстояния между складами и объектами строительства представлены в таблице 1. Рисунок 1 – Объмы спроса и предложения
Таблица 1 Кратчайшие расстояния, км Объекты строительства12СтадионТеатрСклады1Волжск ий852Ленинский14153Заводской317 В результате получаем, представленную в табл. 2, стоимость перевозок по каждому маршруту. Таблица 2 – Стоимость перевозок по каждому маршруту. стадионтеатрВолжский 4025Ленинский7075Заводской1585 Задание 2 Транспортная задача с промежуточными пунктами В транспортной сети, показанной на рисунке 2, осуществляются перевозки груза из пунктов 1 и 2 в пункты 5
и 6 через транзитные пункты 3 и 4. Стоимость перевозок единицы груза между пунктами показана в таблице 3. Предложение пунктов 1, 2 П1 и П2 и спрос пунктов 5,6 С5 и С6 выбирается соответственно номеру зачтной книжки из таблиц 4 и 5. Постройте транспортную модель с промежуточными пунктами и решите задачу в Excel. Рисунок 2 схема транспортной сети Таблица 3
Стоимость перевозки единицы груза между пунктами транспортной сети Пункты1-31-42-32-43-43-54-34-54-65-6Стои мость, у.е.2354363454 Таблица 4 Предложение пунктов 1 и 2 Предложение пункта 1130Предложение пункта 2220 Таблица 2.3 Спрос пунктов 5 и 6 Спрос пункта 5175Спрос пункта 6175 Задание 3 Задача о назначениях У автотранспортной компании имеется n автомобилей разных марок выбирается пунктам сбыта, обеспечивающего минимальные транспортные затраты. При этом предполагают, что а мощность i-го источника объем поставок товара от i-го источника равна Si 0, il m б мощность j-го стока объем поставок товара к j-му стоку равна Dj O, j1 n в стоимость перевозки единицы товара в условных денежных единицах от i-го источника к j-му стоку равна сij г суммарная мощность всех источников равна суммарной мощности всех стоков, т.е.
1 Далее под объемом товара будем понимать его количество в фиксированных единицах измерения. Для математического описания транспортной задачи вводят переменные xij, обозначающие объемы поставок товара от i-го источника j-му стоку. В этом случае xi1xi2 xin общий объем поставок товара от i-го источника, т.е. мощность этого источника xijxi2 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 должна содержать формулу, выражающую целевую функцию СУММПРОИЗВС3D6С12D14 Средняя стоимость перевозки 1 мешка цемента стадионтеатрВолжский 4025Ленинский7075Заводской1585
ПоставщикиПредложениеПотребителиСуммаста дионтеатрСпрос 85015002350Волжский 101000Ленинский135000763Заводской1200005 87 35508501500 Стоимость перевозок руб.144870 Рисунок 1.2-1 Используя меню СервисПоиск решения открываем диалоговое окно Поиск решения см. рис. 2.2-2, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щелкнув по кнопке Выполнить. Рисунок 1.2-2 Данная задача является несбалансированной, т.к. спрос превышает предложение. На рисунке 1.2-3 представлено оптимальное решение. На складах цемента не останется. ПоставщикиПредложениеПотребителиСуммаста дионтеатрСпрос 85015002350Волжский 10008501501000Ленинский13500763763Заводс кой12000587587 35508501500 Стоимость перевозок руб.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 возможны перевозки в обоих направлениях, но в общем случае c45c54 например, наличие одностороннего движения по кратчайшему маршруту. Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом. Объем предложения истинного пункта отправления объем исходного предложения. Объем предложения транзитного пункта объем исходного предложения объем буфера. Объем спроса истинного пункта назначения объем исходного спроса. Объем спроса транзитного пункта объем буфера. Объем буфера должен быть таким, чтобы вместить объем всего предложения или спроса. Пусть J множество номеров складов, на которые товар может быть доставлен с k-то склада, а I множество номеров складов, с которых товар может быть доставлен на k-й склад. Tk величина чистого запаса товара, равная объему исходного предложения или исходного спроса.
Тогда математическую модель данной задачи можно представить следующим образом 4 2.2. Решение транспортной задачи с промежуточными пунктами в Excel Необходимо найти решение транспортной задачи с промежуточными пунктами стоимость перевозки единицы товара см. табл. 3. В Excel представлены таблицы Стоимость перевозки единицы товара и План перевозок товара между складами, сформированные на рабочем листе
Excel. Здесь в таблице Стоимость перевозки единицы товара мы видим, что если между отдельными складами отсутствует возможность перевозки товара, то в соответствующие ячейки таблицы выделенные темным фоном заносится любое большое число в данном случае 100. Для того, чтобы найти в таблице Плана перевозок товара между складами объем предложения и объем спроса, определим объем буфера В по следующему правилу В общий объем предложения
S1S4130220 350 ед. или В общий объем спроса D6D5 175175 350 ед. Для остальных складов объемы предложения Si или объемы спроса Dj равны нулю см. рис. 2.1-1. Рисунок 2.2-1 В целевую ячейку, в данном случае B23, необходимо занести формулу СУММПРОИЗВC4F8C15F19 Используя меню Сервис Поиск решения открываем диалоговое окно
Поиск решения см. рис. 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. Тогда ограничение гарантирует выполнение каждой работы лишь одним исполнителем, ограничение гарантирует, что каждый из исполнителей будет выполнять лишь одну работу. Стоимость выполнения всего комплекса работ равна Таким образом, задачу о назначениях можно записать следующим образом Задача о назначениях является частным случаем классической транспортной задачи, в которой надо положить
nm, 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 Поскольку в общем случае mn, то задачу необходимо сбалансировать путм введения фиктивных заказов или фиктивных автомобилей. Получим а При n m заказов меньше, чем автомобилей избыток провозных возможностей. В этом случае дополнительно вводятся n-m фиктивных клиентов с нулевыми объмами заказов т.е. QjO и Хj0. Поскольку для фиктивных клиентов заказы нулевые, то для их выполнения будут назначаться самые неэффективные по затратам автомобили. Практически выполнение заказа фиктивного клиента означает
резервирование автомобиля автомобиль остатся в парке. б При n m заказов больше, чем автомобилей недостаток провозных возможностей. В этом случае дополнительно вводятся m-n фиктивных автомобилей с бесконечно большими удельными затратами т.е. сj . Практически это означает отказ от самых невыгодных в смысле затрат заказов. 3 Окончательно получим сбалансированную задачу, описываемую квадратной матрицей эксплуатационных затрат
размерностью kxk, где kmахm,n. Алгоритм решения данной задачи в Excel сводится к следующему. Количество рейсов i-го автомобиля у j-го клиента вычисляется по формуле , для всех ш1,2 k j1,2,k. Количество рейсов – величина целочисленная, принимающая значение большее или равное 1. Для е вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках В7С7 и D4D5, то количество рейсов определяется функцией второй параметр функции округления равен 0 ОКРУГЛВВЕРХB7D50 Пробег i-го автомобиля у j-го клиента вычисляется по формуле Эксплуатационные затраты вычисляются по формуле где ci – удельные эксплуатационные затраты, связанные с назначением i-го автомобиля для обслуживания j-го клиента, т.е. для приведенного выше примера в ячейку D7 необходимо занести формулу ОКРУГЛВВЕРХB7D50C7D4
Дополнительная целочисленная переменная логического типа принимает значения Целевая функция имеет вид при ограничениях xij0 целое для всех ш,о1,2,k. Найдем решение задачи 3.1 в Excel, используя следующие исходные данные. Автотранспортная компания располагает 10 автомобилями разных марок 2 автомобиля марки А 2 автомобиля марки В 3 автомобиля марки С 2 автомобиль марки
D 1 автомобиль марки Е. На рис. 3.2-1 представлена таблица с исходными данными. Поскольку заказов меньше имеющихся у компании автомобилей, необходимо ввести фиктивного клиента с нулевым объмом перевозок. В той же таблице произвести необходимые промежуточные расчты затрат по приведнным выше формулам. Рисунок 2.2-2 На рис. 3.2-2 и 3.2-3 представлены Матрица Хij, содержащая переменные логического типа хij и
Матрица произведения SijXij в которой отразится результат оптимального закрепления автомобилей за клиентами и, соответствующие этому закреплению, минимальные затраты Рисунок 3.2-2 Используя меню Сервис Поиск решения открываем диалоговое окно Поиск решения см. рис. 3.2-4, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек со значениями логической переменной хij
Матрица Хij и ограничения, и запускаем процедуру вычисления, щелкнув по кнопке Выполнить. Рисунок 3.2-4 Результат поиска будет находиться в изменяемых ячейках Матрицы Хij i – автомобиль j – клиент и в целевой ячейке эксплуатационные затраты см. рис. 3.2-5 и рис. 3.2-6. Рисунок 3.2-5 Рисунок 3.2-6 Заключение Применение таблиц Excel позволило автоматизировать поиск решений при решении транспортной задачи, а именно при решении классической транспортной задачи и транспортной задачи с промежуточными пунктами найти оптимальную грузоперевозку между пунктами с минимальными затратами, а также оптимальное распределение машин между клиентами для осуществления перевозок с минимальными затратами. Преимуществами данных методов решения является их универсальность и простота в работе при высокой точности результатов. Список используемой литературы 1 Бочкарев
А.А. Решение задач транспортного типа в Excel Учеб. пособие по спец. 062200 – Логистика СПбГИЭУ СПб 2002 64 с. 2 Волков И.К Загогуйко Е.А. Исследование операций Учеб. для вузов Под ред. В.С. Зарубкина, А.П. Дрищенко М. Изд-во МГТУ им. Н.Э. Баумана, 2000 436 с. 3 Кожин А.П. Математические методы в планировании и управлении автомобильными
перевозками Учеб. пособие для студентов экон. спец. вузов М. Высш. школа, 1979. -304 с. 4 Попов А.А. Excel практическое руководство Учеб. пособие для вузов М. ДЕСС КОМ, 2001. -302с. 5 Таха, Хэмди, А. Введение в исследование операций, 6-е издание. Пер. с англ М. Издательский дом Вильямс, 2001 912 с.
6 Транспортная логистика Учебник для транспортных вузов. Под общей редакцией Л.Б. Миротина М. Издательство Экзамен, 2002 512 с.