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

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

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

      

Рисунок 4 – Схема размещения складов 

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

Объем предложения истинного пункта отправления = объем исходного предложения.

Объем предложения транзитного пункта = объем исходного предложения + объем буфера.

Объем спроса истинного пункта назначения = объем исходного спроса.

Объем спроса транзитного пункта = объем  буфера.

      Объем буфера должен быть таким, чтобы вместить объем всего предложения (или  спроса).

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

       

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

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

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

Таблица 10 – Стоимость перевозки единицы товара

 

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

     B = общий объем предложения = S₁+S₂=170+180 = 350 ед.

или

     B = общий объем спроса =D₆+D₅= 155 + 195= 350 ед.

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

      В целевую ячейку, в данном случае D25, необходимо занести формулу: =СУММПРОИЗВ(B5:E9;C18:F22)

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

     

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

Таблица 11 – Оптимальный  план перевозок

 

 

Видно, что оптимальный план перевозок товара между складами следующий:

• со склада 1 товар в количестве 170 единиц перевозиться в транзитный пункт 4;
• со склада 2 товар в количестве 180 единиц перевозиться в транзитный пункт 4;
• со склада 4 товар в количества 155 и 195 единиц перевозиться в транзитный пункт 5 и 6, который является истинным пунктом назначения.

       Стоимость перевозок при этом минимальна и  составляет 2825 условных денежных единиц.

      Задача 3

       Задача  о назначениях

       У автотранспортной компании имеется  n автомобилей разных марок (выбирается из таблицы 7). Автомобили разных марок имеют разную грузоподъёмность q_i (т) и разные удельные эксплуатационные затраты c_i ($/км) – таблица 6. Компания получила заказы от m клиентов на перевозку грузов. Причём в каждом заказе указан объём перевозимого груза Q_j (т) и расстояние перевозки L_j (км). Заказы на перевозку выбираются из таблицы 8. Требуется, используя табличный процессор Excel, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы (руб./ткм) для клиентов на перевозки одинаковыми. 
 
 

Таблица 6 – Характеристики автомобилей по маркам

 
 
 
 
 
 

Таблица 7 – Структура  парка автомобилей автотранспортной компании

Таблица 8 – Заказ на перевозку груза

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

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

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

гарантирует выполнение каждой работы лишь одним  исполнителем, ограничение 

гарантирует, что каждый из исполнителей будет  выполнять лишь одну работу.

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

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

     Задача  о назначениях является частным  случаем классической транспортной задачи, в которой надо положить 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, оптимальным образом назначить автомобили на рейсы для выполнения заказов клиентов, полагая тарифы на перевозки одинаковыми.