1

Организация данных. Создание рабочей таблицы.

Сначала займемся организацией данных и создадим рабочую таблицу.
Распределительный центр работает каждый день, 7 дней в неделю. Поэтому добавим к таблице с данными задачи 7 столбцов (по числу дней недели).

1 - поставка есть;
0 - поставки нет.

Таким образом, в желтом поле в диапазоне от понедельника до воскресенья в строке ТТ №01 Барнаул должна стоять одна 1. Во второй строке ТТ №02 Екатеринбург поставим также одну 1, в третей строке ТТ №03 Екатеринбург три единицы и так далее.

Решить эту задачу означает,
оптимально расставить единицы в желтом поле переменных

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

Внизу таблицы в голубых ячейках

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

добавим новый столбец Величина одной поставки, ед.;
в каждую ячейку нового столбца введем формулу:
Ожидаемые продажи, ед. / Плановое число поставок (для каждой торговой точки)

Сложив число единиц одной поставки для каждой торговой точки за каждый день мы получим загруженность склада за день.

Напомню, что в MS Excel удобно для этого пользоваться функцией СУММПРОИЗВ().

С чем мы можем сравнить найденные ежедневные нагрузки распределительного центра?
Очевидно, что с его среднедневной нагрузкой.
Мы знаем, что сумма ожидаемых продаж всех торговых точек за неделю есть суммарное количество единиц, которое распределительный центр должен собрать и отгрузить за неделю.
Вычислим среднюю нагрузку распределительного центра за день.

Сумму ожидаемых продаж по всем торговым точкам разделим на 7.
Окрасим ячейку, в которой вычисляем среднюю дневную нагрузку распределительного центра в светло-оранжевый цвет
.

После этого, таблица будет выглядеть так:

Здесь та же таблица в файле MS Excel с соответствующими формулами:

Таблица данных для решения задачи планирования поставок в файле MS EXcel

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

2

Как измерять неравномерность (разброс) в нагрузке?

Поскольку мы должны составить план поставок таким образом, чтобы нагрузка на распределительный центр была равномерной, то возникает вопрос: как имерить неравномерность нагрузки?

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

Что же можно использовать в качестве линейной характеристики разброса?

По идее, лучше всего подошла бы разница между минимальной и максимальной загрузками распределительного центра. Вот только использовать функции Excel =МИН(..) и =МАКС(..) при оптимизации нельзя. Ведь это не математические функции, а специальные алгоритмы и записать их в виде системы уравнений не получится.

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

назовем это поле Разброс =;
в зеленой
ячейке вычислим этот разброс:
вычтем из суммарной нагрузки склада в понедельник суммарную нагрзку склада в воскресенье,

т.е. из значения светло-голубой ячейки
0
столбца Пн вычтем значение светло-глубой ячейки
0
столбца Вс

Конечно, пока эти ячейки содержат 0. Но как только оптимизатор решит задачу и расставит 1 в поле переменных, мы получим вполне конкретные значения.

В темно-зеленой

ячейке вычислим разницу в нагрузке в процентном соотношении. Для этого значение зеленой

ячейки разделим на значение светло-оранжевой

ячейки.
Теперь рабочая таблица готова, осталось только поставить задачу оптимизатору.

3

Установки оптимизатора.

Задача наша небольшая, всего 175 переменных, поэтому по силам даже штатному Поиску решения.

Целевая функция в данной задаче – разброс нагрузки распределительного центра, который вычисляется в зеленой
ячейке.
Мы хотим, чтобы нагрузка на распределительный центр была по возможности равномерной. Поэтому потребуем, чтобы значение целевой функции было минимальным.
Переменные нашей задачи - это все желтое поле в рабочей таблице.
Введем ограничения:
- поскольку мы волевым образом решили, что самая большая нагрузка приходится на понедельник, то нагрузка на склад в кажый следующий день, должна быть не больше нагрузки предыдущего дня:
  $E$28:$J$28 >= $F$28:$K$28
- Переменные должны быть бинарными:
  $E$3:$K$27 = бинарное
- Значения контрольного столбца OK? должны быть равны 0, что означает: число плановых поставок в каждую торговую точку равно числу реальных поставок в эту торговую точку.
  $N$3:$N$27 = 0

Установки оптимизатора для решения задачи о планировании поставок с учетом равномерного распределения нагрузки распределительного центра

Запустим задачу, и ...

Поиск решения ищет оптимальное решение столько времени, что не хватает терпения дождаться результата!

Хм... Может быть Поиск решения излишне упрощен?

Попробуем OpenSolver с солвером CBC.

Перенесем настройки оптимизатора в OpenSolver-Model:

Установки OpenSolver-Model для решения задачи о планировании поставок с учетом равномерного распределения нагрузки распределительного центра

Запустим задачу, и ...

Как ни странно, но здесь процесс тоже продолжается до бесконечности (во всяком случае дольше 12 часов)...

Еще более странно, что солвер от Gurobi тоже не может быстро выдать оптимальное решение и считает неопределенно долго (мне не хватило терпения дождаться результата).

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

4

Как выяснить, что пошло не так и все-таки решить задачу.

В меню Options установок OpenSolver OpenSolver-Model есть пункт Show optimization progress while solving.

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

И тут мы можем видеть камень преткновения. Оптимизатор уже через 10 секунд (числа в правой колонке: 10s) достигает разброса 550 ед, что составляет примерно 1% от средней нагрузки распределительного центра, через 30 секунд доходит до варианта с разбросом 90 ед. и… продолжает процесс поиска дальше и дальше...и через 1000 секунд оптимизатор продолжает пережевывать варианты размещения поставок с одним и тем же разбросом 90…

С одной стороны, это печальный исход тем более, что попытка озадачить облачный сервер NEOS специально подготовленной для него в формате gms задачей тоже оказывается не успешной и через 8 часов оптимизации задача вылетает не решенной по достигнутому лимиту времени. А как-то подсказать создателям солверов, что у них что-то не так в инструменте – дело не простое и долгое.
С другой стороны, раз мы видели, что OpenSolver получает нужный нам результат и даже с запасом, но почему-то им не удовлетворяется, мы можем сами поставить ограничение на результат.

Применим опцию taget value = 90 (раз мы видели такой результат оптимизации).

Установки оптимизатора для приближенного решения задачи о планировании поставок с учетом равномерного распределения нагрузки распределительного центра

Оптимизатор от Gurobi получает оптимальное решение примерно за 60 секунд.

Однако, такой подход неудобен. Ведь мы заранее не знаем, какие варианты разброса возможны.
Если мы зададим, например, taget value = 100 … а такого решения вообще нет, то задача не будет решена, и мы зря потратим время.
Можно обойти это неудобство оставив целью оптимизации минимум, но добавив ограничение на целевую функцию:
L29>=100.

Установки OpenSolver-Model с ограничением для целевой функции

Оптимизатор от Gurobi получает оптимальное решение с разбросом 100 за 92 сек.

Необходимо заметить, что другие оптимизаторы ищут решение значительно дольше, поэтому решение может быть и не найдено.
Но нужно ли запрашивать такую точность? При средней нагрузке около 58 000 и допустимой неравномерности в 1% предел оптимизации можно было бы поставить равным 580.
С практической точки зрения и 5%-ная разница в нагрузке будет весьма мало заметна, так что смело можно было бы поставить в качестве предела и 2-3 тыс. Задачу при подобном ограничении солвер COIN-OR CBC решает менее чем за полминуты.
Итак, модель решения задачи планирования поставок с учетом равномерной нагрузки распределительного центра построена. Теперь оценим качество полученного решения и по возможности улучшим его.

5

Как учесть равномерность поставок.

Внимательно изучив полученное решение, мы сочтем его не самым оптимальным. Равномерность поставок оставляет желать лучшего. Так например, в ТТ №11 в Омске предлагается все три поставки собирать и отправлять одну за другой три дня подряд. В то время, как было бы гораздо разумнее, получать их через день.
Как задать ограничение на равномерность поставок?
В общем виде это сделать не просто, необходимо иметь дополнительные конкретные данные. Но для примера можно предложить следующий вариант решения этой проблемы.

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

Создадим такую контольную таблицу размером 7х25. В каждую ячейку контрольной таблицы введем формулу, вычисляющую сумму поставок за два дня: сегодняшний и предыдущий. И не забудем, для понедельника предыдущим днем будет воскресенье.
В файле MS Excel таблица с формулами выглядит так:

Условным форматированием в контрольной таблице выделены ячейки, отличные от 1.

значение всех ячеек контрольной таблицы должны быть не больше 1:
$P$3:$V$27 <=1

Установки OpenSolver-Model с ограничением для контрольной таблицы

После запуска OpenSolver получим новое решение:

Оптимальное решение задачи планирования равномерных поставок в 25 торговых точек

Теперь в модели наблюдается только один недостаток:
мы задаем одинаковые требования для промежутков между поставками при любом числе поставок в неделю.

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

Oтсортировать торговые точки по числу поставок.
В контрольной таблице визуально выдлить области, соответствующие поставкам 1 раз в неделю, 2 раза в неделю и 3 раза в неделю.
В зонах с 1 и 3 поставками в неделю формулы менять не нужно.
В контрольной таблице в зоне с 2 поставками в неделю формулы нужно откорректировать.

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

вместо P3:V27<=1 достаточно требовать P7:V27<=1.

Получим новое решение.

Новое оптимальное решение задачи планирования равномерных поставок в 25 торговых точек

Разумеется, разброс загрузки распределительного центра несколько увеличился, но все равно остался очень маленьким.

Как запретить поставки в определенные дни?

Cоответствующая переменная в желтом поле таблицы переменных должна быть равна 0 в установках OpenSolver-Model

Как потребовать поставку в определенный день?

Cоответствующая переменная в желтом поле таблицы переменных должна быть равна 1 в установках OpenSolver-Model