Оптимизация доставки

Постановка задачи

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

Карта магазинов и складов

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

Перед началом оптимизации необходимо будет составить несложную таблицу на листе Excel – нашу математическую модель, описывающую ситуацию:

Исходная модель для оптимизации

Подразумевается, что:

  • Светло-желтая таблица (C4:G6) описывает стоимость доставки одной единицы товара от каждого склада до каждого магазина.
  • Лиловые ячейки (C15:G14) описывают необходимое для каждого магазина количество товаров на реализацию.
  • Красные ячейки (J10:J13) отображают емкость каждого склада – предельное количество товара, которое склад вмещает.
  • Желтые (C13:G13) и синие (H10:H13) ячейки – соответственно, суммы по строке и столбцу для зеленых ячеек.
  • Общая стоимость доставки (J18) вычисляется как сумма произведений количества товаров на соответствующие им стоимости доставки - для подсчёта здесь используется функция СУММПРОИЗВ (SUMPRODUCT).

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

Решение

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

Кнопка Поиск решения на вкладке Данные

Если на вкладке Данные вашего Excel такой команды нет – ничего страшного - значит надстройка просто еще не подключена. Для ее активации откройте Файл, далее выберите Параметры НадстройкиПерейти (Options - Add-Ins - Go To). В открывшемся окне поставьте галочку напротив нужной нам строки Поиск решения (Solver).

Запустим надстройку:

Окно надстройки Поиск решения

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

  • Оптимизировать целевую функцию (Set target cell) – тут необходимо указать конечную главную цель нашей оптимизации, т.е. розовую ячейку с общей стоимостью доставки (J18). Целевую ячейку можно минимизировать (если это расходы, как в нашем случае), максимизировать (если это, например, прибыль) или попытаться привести к заданному значению (например, вписаться ровно в выделенный бюджет).
  • Изменяя ячейки переменных (By changing cells) – здесь укажем зеленые ячейки (C10:G12), варьируя значения которых мы хотим добиться нашего результата – минимальных затрат на доставку.
  • В соответствии с ограничениями (Subject to the Constraints) – список ограничений, которые надо учитывать при проведении оптимизации. Для добавления ограничений в список нужно нажать кнопку Добавить (Add) и ввести условие в появившееся окно. В нашем случае, это будет ограничение на спрос:

      Задаем ограничения

    и ограничение на предельный объем складов:

    Ограничение на объем складов

Кроме очевидных ограничений, связанных с физическими факторами (вместимость складов и средств перевозки, ограничения бюджета и сроков и т.д.) иногда приходится добавлять ограничения «специально для Excel». Так, например, Excel легко может устроить вам "оптимизацию" стоимости доставки, предложив возить товары из магазинов обратно на склад - расходы при этом станут отрицательными, т.е. мы получим прибыль! :)

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

После настройки всех необходимых параметров окно должно выглядеть следующим образом:

Окно Поиска решения с введенными параметрами

В выпадающем списке Выберите метод решения (Select a solving method) дополнительно требуется подобрать подходящий математический метод для решения на выбор из трех вариантов:

  • Симплекс-метод - простой и быстрый метод для решения линейных задач, т.е. задач, где выход линейно зависит от входа.
  • Метод общего понижающего градиента (ОПГ) - для нелинейных задач, где между входными и выходными данными есть сложные нелинейные зависимости (например, зависимость продаж от расходов на рекламу).
  • Эволюционный поиск решения - относительно новый метод оптимизации, основанный на принципах биологической эволюции (привет Дарвину). Этот метод работает в разы дольше первых двух, но может решать практически любые задачи (нелинейные, дискретные).

Наша задача явно относится к линейным: доставили 1 шт - затратили 40 р., доставили 2 шт - затратили 80 р. и т.д., так что симплекс-метод будет наилучшим выбором.

Теперь, когда данные для расчета введены, нажмем кнопку Найти решение (Solve), чтобы начать оптимизацию. В тяжелых случаях с большим количеством изменяемых ячеек и ограничений нахождение решения может занять продолжительное время (особенно с эволюционным методом), но наша задача для Excel проблемы не составит – через пару мгновений мы получим следующие результаты:

Готовое решение

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

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

Бывают, однако, ситуации, когда Excel не может найти подходящего решения. Имитировать такой случай можно, если указать в нашем примере требования магазинов в сумме большие, чем общая вместимость складов. Тогда при выполнении оптимизации Excel попытается приблизиться к решению, насколько это возможно, а затем выдаст сообщение о невозможности найти решение. Тем не менее, даже в этом случае мы имеем массу полезной информации – в частности можем видеть «слабые звенья» наших бизнес-процессов и понять направления совершенствования.

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

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

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



13.05.2013 14:33:00
Николай, насколько я знаю, Поиск решения ограничен 200 переменными и 200 ограничений.
Нельзя ли, как в случае с описанными выше "откатами", увеличить это число?
14.05.2013 09:52:57
Увеличить - сомневаюсь, не видел такого, но есть отдельные программные продукты для апгрейда Solver. Например http://www.solver.com/upgrade-excel-solver
28.06.2013 20:17:31
Николай, у Вас на старой Планете, Поиск решения рассматривался на примере "выгодности" кредита. Вы могли бы снова разместить тот пример?
01.07.2013 21:00:46
На примере выгодности кредита рассматривался не Поиск решения, а Сценарии. Весьма спорный был пример с кучей справедливой критики от финансистов, поэтому я его и убрал :)
01.07.2013 21:39:42
Спасибо, Вас понял. Теперь ясно, а то у меня Поск решения на кредитной таблице только сумму аннуитетных платежей может раскинуть. Пошел курить "Что если"
02.07.2013 10:26:10
Таблицу данных тоже можно "покурить" :) Будет раскидывать все возможные варианты по набору значений двух параметров (например, по одной оси - различные варианты ставки, по другой - срока, на пересечении - сумма выплат).
17.11.2014 07:50:40
могли бы поделиться решением выгодности кредита от разных банков?
Николай, спасибо Вам огромное за Ваш труд!
26.07.2013 10:59:55
Вы спрашивали про управление Поиском решения с помощью VBA - посмотрите тут хорошую статью http://peltiertech.com/Excel/SolverVBA.html
12.01.2014 08:42:33
  Доброго времени суток Николай! Извените что обращаюсь к Вам так часто с вопросами, но мои знания в этой области хромают. По этому у меня к Вам не вопрос, а просьба нельзя л и сконструировать Solver отдельно по моему случаю? Если Я опишу ситуацию?
12.01.2014 10:41:27
Ихтиёр, с такими задачами лучше на форум, он для того и существует :) Только правила сначала почитайте.
06.11.2019 11:06:24
Доброго дня. Николай, спасибо за статью, очень познавательно. Только подправьте в самом первом же предложении статьи вы пишите про "два складских помещения", а далее по тексту их везде три. ;)
06.11.2019 12:31:53
Спасибо, Алексей! Подправил :)
06.11.2019 17:49:11
7 лет висела статья, никому не мешала, и тут вот пришел корректор.:D
11.11.2019 09:08:25
Николай, спасибо большое за ваши уроки!
В данном примере осталось добавить расчет таблицей: для перечня SKU; учет наличия остатков на складе и распределение с основного склада по РЦ)
28.09.2020 14:33:16
Николай, большое спасибо, за ценные уроки.

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

есть массив деталей разной длины,
максимальная труба поставляется по 600 см или её могут порезать на погрузке по 300 см, плюс минус 30 см (то есть можно порезать на два куска 300 и 300, или 330 и 270, или 310 и 290 и тд.  

Интуиция подсказывает, что инструмент "Поиск решения" - это то, что может мне помочь, но никак не могу сообразить как и что настроить для этой задачи, ... или может я копаю не в том направлении.
26.03.2021 13:04:18
Павел, здравствуйте! Математическую постановку и пример решения в Excel раскройной задачи (это отдельный класс проблем) можно найти, например, в учебнике Шадриной по решению задач оптимизации.
19.11.2022 06:27:00
Здравствуйте, помогите как можно сделать расчет по распределению самосвалов на карьере (10 ед.самосвалов) по перевозке горной массы по разным плечам откатки и местам разгрузки исходя из того чтобы один экскаватор был загружен максимально?
Необходима матрица.
Например утром на разнарядке дают 10 самосвалов и 1 экскаватор для работы в дневную смену, есть два места разгрузки горной массы самосвалов с плечами откатки отвал №1=2км и отвал№2=3км.

Параметры самосвала и экскаватора:
Объем кузова самосвала 18м3
Скорость движения самосвала 20км/час
Время загрузки экскаватором 1 самосвала равна 3 минутам
Длительность рабочей смены 10 часов с учетом всех перерывов.
Условия необходимо соблюсти следующие:
- Самосвал нужно оптимально распределить на 2 места разгрузки исходя из плеча перевозки
- Экскаватор по минимум должен простаивать в ожидании подъезда самосвала
Наверх