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

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

 

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

 

 

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

 

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

 

 

          Рис.4.Стоимость перевозки единицы товара

 

 

 

 

 

                   Рис.5. Значения спроса и предложения

 

Целевая ячейка C18 должна содержать формулу, выражающую целевую функцию:

 

=СУММПРОИЗВ(В4:D6;С13:Е15).

 

Используя меню Сервис Поиск решения, открываем диалоговое окно Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек (C13:Е15) и ограничения и запускаем процедуру вычисления, щёлкнув по кнопке Выполнить (Рис.6). В Excel несбалансированная транспортная задача  решается путём изменения ограничений по спросу (если спрос превышает предложение) или по предложению (если предложение превышает спрос, т.е. в данном случае F13:F15<=B13:B15).

 

 

   Рис.6. Диалоговое окно Поиск решения при решении классической транспортной задачи

 

 

 

 

 

 

 

 

 

 

        

                                

       Рис.7. План оптимального закрепления потребителей за поставщиками

 

 

 

2. ТРАНСПОРТНАЯ ЗАДАЧА  С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

 

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

 

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

Задачу выбора плана  перевозок товаров от поставщиков  к потребителям с учётом промежуточных пунктов, обеспечивающего минимальные транспортные затраты и спрос потребителей, в исследовании операции называют транспортной задачей с промежуточными пунктами. Для приобретения практических навыков в построении математических моделей таких задач обратимся к следующему примеру. На рис.8 представлена схема размещения складов, на которой указаны:

а) склады в виде узлов сети с  номерами от 1 до 6; б) возможность перевозки  товара со склада i на склад j (ориентированная дуга от круга с номером i к кругу с номером j); в) затраты, связанные с перевозкой единицы товара со склада i на склад j (величина c_ij  рядом с соответствующей ориентированной дугой, выраженная в денежных единицах).

Рис.8 Схема размещения складов

 

 

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

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

1. Объём предложения истинного пункта отправления = объём исходного предложения.
2. Объём предложения транзитного пункта = объём буфера + объём исходного предложения или объём буфера – объём исходного спроса.
3. Объём спроса истинного пункта назначения = объём исходного спроса.
4. Объём спроса транзитного пункта = объём буфера.
5. Объём буфера должен быть таким, чтобы вместить объём всего предложения (или спроса).

Объём буфера В определяется по следующему правилу:

В = общий объём предложения = S₁+S₂

или

В = общий объём спроса = D₆+D₅

 

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

 

 

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

 

Необходимо найти решение транспортной задачи  с промежуточными пунктами, если стоимость перевозки единицы  товара составляет: с₁₃=2 у.е., с₁₄=3 у.е., с₂₃=5 у.е.,  с₂₄=4 у.е.,  с₃₄=3 у.е.,  с₃₅=6  у.е., с₄₃=3 у.е.,  с₄₅=4 у.е., с₄₆=5 у.е., с₅₆=4 у.е.

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

 

                                   

 

Рис. 9. Стоимость перевозки единицы  товара

 

 

 

 

 

 

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

Для остальных складов объёмы предложения  S_i  или объёмы спроса D_j разны нулю.

В целевую ячейку , В данном случае Т16, необходимо занести формулу:

 

=СУММПРОИЗВ( М4:Р8; Т7:W11).

 

Используя меню Сервис Поиск решения, открываем диалоговое окно  Поиск решения, в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления, щёлкнув по кнопке Выполнить (рис.10).

 

            

 

           Рис. 10. Диалоговое окно Поиск решения при решении транспортной задачи с   промежуточными пунктами

 

                          Результат решения данной задачи представлен на рис. 11

 

             

 

                                            Рис.11. Оптимальный план перевозок

 

3. ЗАДАЧА О НАЗНАЧЕНИЯХ

 

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

 

 

Предположим, что имеется n различных работ, каждую которых может выполнить любой из n перечисленных исполнителей. Стоимость выполнения i-й работы j-м исполнителем  известна и равна cij ( в условиях денежных единицах). Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

В исследовании операций задача, сформулированная выше известна как задача  о назначениях. Введём переменные x_ij, принимающие значение

=1, i=1,….n,

1 в случае, когда i-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j =1, n. Тогда ограничение гарантируют выполнение каждой работы лишь одним исполнителем, ограничение гарантирует, что каждый из исполнителей будет выполнять лишь одну работу.

Стоимость выполнения всего комплекса работ равна

=1, j=1,…..n,

Таким образом, задачу о назначениях  можно записать следующим образом:

Задача о назначениях является частным случаем классической транспортной задачи, в которой надо положить n=m, S_i=1,  i=1 ,……,n, D_j=1,  j=1,….,n. При этом условии x_ij 0,1, ij=1,….,n, означает выполнение требования целочисленности переменных x_ij. Это связано с тем, что мощности  все источников и стоков равны единице, откуда следует, что в допустимом  целочисленном решении значениями переменных могут быть только 0 и 1.

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

В задаче о назначениях переменная x_ij может принимать значение 0 или 1. При этом в любом допустимом решении лишь n переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным. На практике встречаются задачи о назначениях, в постановках которых параметр с_ij для i,j=1,…,n понимается как эффективность выполнения i-й работы j –м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения была максимальной, т.е.

,

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

 

 

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

 

У автотранспортной компании имеется п автомобилей разных марок. Автомобили разных марок имеют разную грузоподъёмность q_i (m) и разные удельные эксплуатационные c_i( $/км). Компания получила заказы от m клиентов на перевозку грузов, причём в каждом заказе указан объём перевозимого груза Q_i (m) и расстояние перевозки L_j (км). Требуется, используя табличный процессор Ехсеl, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки одинаковыми.  
 Покажем, что представленная задача удовлетворяет рассмотренным выше требованиям.  
1)  Поскольку тарифы одинаковые, то в качестве целевой функции следует выбрать эксплуатационные затраты. Эти затраты необходимо минимизировать путём оптимального распределения автомобилей по клиентам. 
2) Поскольку в общем случае m не равно n, задачу необходимо сбалансировать путём введения фиктивных заказов или фиктивных автомобилей. Получим:  
а) При n>m заказов меньше, чем автомобилей (избыток провозных возможностей). В этом случае дополнительно вводятся n-m фиктивных клиентов с нулевыми объемами заказов (т.е Q_j=0 и L_j=0). Поскольку для фиктивных клиентов заказы нулевые, то для их выполнения будут назначаться самые неэффективные по затратам автомобили. Практически выполнение заказа фиктивного клиента означает резервирование автомобиля (автомобиль остаётся в парке).  
б) При n<m заказов больше, чем автомобилей (недостаток провозных возможностей). В этом случае дополнительно вводятся m-n фиктивных автомобилей с бесконечно большими удельными затратами (т.е. c_j ). Практически это означает отказ от самых невыгодных в смысле затрат заказов.  
3) Окончательно получим сбалансированную задачу, описываемую квадратной матрицей эксплуатационных затрат размерностью k*k, где k=мах m, n. 
 Алгоритм решения данной задачи в Ехсеl сводится к следующему.  
Количество рейсов i-го автомобиля у ]-го клиента вычисляется по формуле

, для всех i=1,2…..k;j=1,2,…k.

Количество рейсов – величина целочисленная, принимающая значение большее или равное 1. Для её вычисления следует воспользоваться функцией округления частного от деления в большую сторону. Например, если исходные данные находятся в ячейках В7:С7 и D4:D5, то количество рейсов определяется функцией (второй параметр функции округления равен0)

ОКРУГЛВВЕРХ($В7/D$5;0)

Пробег i-го автомобиля у j-го клиента вычисляется по формуле