Для решения задачи на рабочем листе Excel разработаем модель рассматриваемой задачи. Разрабатываемую модель необходимо представить в виде трех таблиц: матрицы теневых цен сij, матрицы переменных хij и матрицы произведения сij*хij. Для решения задачи необходимо связать значения таблиц формулами. Зависимости, связывающие переменные модели, представлены в табл. 6–8.
В табл. 1 мы видим, что теневые цены рассчитываются по формуле (1), для чего в ячейку В6 занесена формула
Таблица 1
Зависимости, связывающие переменные в матрице теневых цен
В6=($16/В$12)×В$5, которая затем распространяется на весь диапазон ячеек В6:Н10, содержащих теневые цены.
Таблица 2
Зависимости, связывающие переменные в матрице переменных
Таблица 3
Матрица произведения сij *хij.
Фактическую загрузку подвижного состава рассчитывают по формуле (4), которая занесена в ячейке В11 в виде В11=СУММПРОИЗВ ($16:$110;1_6:1_10). Аналогично данная формула распространяется на весь диапазон ячеек В11:Н11, содержащих значения загрузки.
В табл. 2 мы видим, что в диапазоне L6:R10 содержатся изменяемые ячейки, формулы, занесенные в диапазон S6:S10, суммируют значения изменяемых ячеек по строкам, а занесенные в диапазон L11:R11 – по столбцам. Функция, занесенная в ячейки строки «Выбор», возвращает значение 1, если в ячейках строки «Сумма» находится значение, большее или равное 1, и значение О-в противном случае.
Таблица 4
Параметры надстройки Excel – Поиск решения
Обязательное условие для расчетов: в табл. 2 и 3 нужно установить числовой формат ячейки без знаков после запятой ( , числовые форматы – числовой, число десятичных знаков – 0).
Представленные в табл. 3 формулы служат для вычисления целевой функции, то есть суммы теневых цен для обслуженных клиентов.
В диалоговое окно «Поиск решения» заносятся целевая ячейка, диапазон изменяемых ячеек и ограничения. Свод параметров модели представлен в табл. 4.
В результате использования программы «Поиск решения» (надстройка Excel) осуществляется оптимизация транспортного плана.
При заполнении формы «Поиск решения» получаем следующее:
При введении ограничения двоичности может возникнуть сложность в введении этого параметра. Поэтому необходимо задавать его следующим образом:
Параметры «Поиска решения» приведены на рисунке:
В итоге получается следующий результат (см. рис. на стр. 215).
Задача для самостоятельного решения
Продемонстрируем возможность фактического применения рассмотренного алгоритма на практическом примере. Одна из крупных дистрибьюторских компаний Санкт-Петербурга ООО «Холдинг78», осуществляющая поставку продуктов питания в магазины города и Ленинградской области, использует для перевозки арендованный подвижной состав. Поскольку ежедневно данная компания обслуживает до полутора тысяч клиентов, что вызывает серьезные проблемы при формировании маршрутов, весь город разбит на зоны обслуживания и секторы развозки. Перед диспетчерами, занимающимися формированием маршрутов, ставится задача – обслужить всех клиентов, используя минимальное количество подвижного состава.
Решение данной задачи до настоящего времени не автоматизировано, но имеется определенный алгоритм, в соответствии с которым, во-первых, выбирается рациональный по грузоподъемности подвижной состав из имеющегося в наличии. Во-вторых, формируются маршруты внутри секторов развозки при условии, что число пунктов, объединенных в один маршрут, не должно превышать двенадцати. Если число клиентов в данном секторе развозки превышает двенадцать, то часть их присоединяется к клиентам ближайших секторов таким образом, чтобы выполнялось данное ограничение.
В качестве примера взяты данные об обслуживании клиентов данной компании в зоне Московского района Санкт-Петербурга за один день. Сводная таблица грузопотоков и фактически сформированные маршруты представлены в табл. 5.
В табл. 5 представлены следующие данные:
– в «шапке» таблицы отмечены: дата, регион, сектор развозки, номер магазина, номера рейсов и модели автомобилей, которыми были обслужены данные клиенты (магазины);
– в столбце «сумма» указан вес заказа каждого магазина (кг);
– в строке «сумма» – фактическая загрузка каждого автомобиля (кг).
В ячейках таблицы на пересечении соответствующих строк и столбцов представлен вес товара, доставленного клиенту данным рейсом (кг).
Анализ данной таблицы показывает: для обслуживания 25-ти клиентов потребовалось девять единиц подвижного состава, рейсы 48,54 и 57 выполнены с крайне низкой загрузкой автомобилей, заказ магазина номер 7254 распределен между двумя единицами подвижного состава, что может быть оправдано только при отсутствии автомобиля требуемой грузоподъемности.
Расчет фактических затрат на перевозку представлен в табл. 6.
Таблица 5
Сводная таблица грузопотоков в базовом варианте
Расчет показывает, что в базовом варианте общие затраты на перевозку, включающие затраты на аренду автомобиля и затраты на экспедирование, составили 12,405 тыс. руб.
