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

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

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

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

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

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

       Зачетная  книжка №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.

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

 

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

 

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

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

 

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

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

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

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

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

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

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

      Для математического описания транспортной задачи вводят переменные x_ij, обозначающие объемы поставок товара от i-го источника к j-му стоку. В этом

      

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

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

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

 

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

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

     Данную  задачу можно решить симплекс-методом  или с помощью, так называемой, транспортной таблицы. Исходные данные для решения классической транспортной задачи целесообразно представить в виде двух таблиц, в первой из которых представлены значения стоимости перевозок единицы товара c_ij от i-го поставщика к j-му потребителю. Во второй таблице представлены: значения S_i предложения каждого i-го поставщика; значения D_j спроса каждого j-го потребителя; переменные x_ij, первоначально принимающие нулевые значения; вспомогательная строка и вспомогательный столбец "Сумма". Целевая ячейка 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 – Стоимость  перевозки единицы груза между 

                      пунктами транспортной сети                               

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

 

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

 

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

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