Перейти к основному содержимому

Оптимизация: что это и зачем?

Оптимизация — это поиск наилучшего решения при заданных ограничениях.

Где это применяется?​

Типичные задачи из 1С:

1. Распределение задач​

Проблема:
Нужно распределить 100 заказов между 10-ю сотрудниками так, чтобы:

  • Все заказы были выполнены
  • Нагрузка была равномерной
  • Общее время работы минимальным

2. Составление расписаний производства​

Проблема:
Планируем выпуск продукции в 3-х цехах, где:

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

3. Маршрутизация доставки​

Проблема:
Доставить 50 заказов по городу с учетом:

  • Грузоподъемности 10-ти машин
  • Загруженности дорог
  • Временных окон получения
  • Приоритетных клиентов

4. Упаковка товаров​

Проблема:
Нужно разместить 85 товаров разных размеров в минимальное количество контейнеров, учитывая:

  • Габариты каждого товара
  • Габариты и максимальную грузоподъемность контейнеров
  • Ограничения по складированию (хрупкие товары сверху)

Все эти задачи объединяет:

  • Большое число вариантов (слишком долго перебирать)
  • Жесткие ограничения (бюджет, время, ресурсы)
  • Четкий критерий оптимальности (минимум затрат/максимум прибыли)

Что такое оптимизационная модель?​

Оптимизационная модель — это математическое представление задачи, где:

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

Оптимизационная модель может быть описана программным кодом и решена с использованием специализированных алгоритмов. Это выглядит примерно так:

// Хотим произвести столы и стулья, но материалы ограничены. Как быть?
// Ограничения: древесина (20 ед.) и краска (18 ед.)
// Прибыль: стул — 3 у.е., стол — 5 у.е.

// 1. Создаем модель
Модель = О2.СоздатьМодель();

// 2. Объявляем переменные модели
КолвоСтульев = Модель.Переменные().Добавить("КолвоСтульев");
КолвоСтолов  = Модель.Переменные().Добавить("КолвоСтолов");

// 3. Описываем ограничения
Модель.Ограничения().Соотношение("КолвоСтульев >= 0; КолвоСтолов >= 0");
Модель.Ограничения().Соотношение("2 * КолвоСтульев + 4 * КолвоСтолов <= 20"); // <-- расход древесины
Модель.Ограничения().Соотношение("3 * КолвоСтульев + 2 * КолвоСтолов <= 18"); // <-- расход краски

// 4. Устанавливаем цель — максимизировать прибыль
Модель.ЦелеваяФункция().Максимизировать("3 * КолвоСтульев + 5 * КолвоСтолов");

// 5. Решаем модель
Решение = Модель.Решить(); // <-- здесь происходит магия

// 6. Наслаждаемся результатом
Сообщить("Количество стульев: "     + Решение.ЗначениеПеременной(КолвоСтульев));    // --> 4
Сообщить("Количество столов: "      + Решение.ЗначениеПеременной(КолвоСтолов));     // --> 3
Сообщить("Максимальная прибыль: "   + Решение.ЗначениеЦелевойФункции());            // --> 27

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

Замечание

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

Виды оптимизационных моделей​

Линейное программирование (LP)​

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

Когда использовать:

  • Когда допустимы дробные значения (например, литры, килограммы)
  • Для задач пропорционального распределения
  • Условия можно свести к набору линейных соотношений

Целочисленное программирование (MIP)​

Целочисленное / смешанно-целочисленное программирование используется при работе с целыми числами, когда нельзя купить или произвести 3,5 товара. Некоторые виды моделей допускают наличие и дробных и целочисленных переменных, а некоторые только целочисленных. В таких моделях условия описываются так же линеными соотношениями.

Когда использовать:

  • Для определения количества сотрудников/машин
  • Присутствуют штучные товары в заказах
  • Условия можно свести к набору линейных соотношений

Программирование в ограничениях (CP)​

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

Когда использовать:

  • Составление расписаний
  • Задачи с нелинейными комбинаторными условиями ("если не А, то Б")

Маршрутизация (Routing)​

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

Когда использовать:

Гибридные модели (CP-SAT)​

Гибридная модель CP-SAT сочетает возможности программирования в ограничениях с решением задач выполнимости булевых формул. Модель позволяет устанавливать как линейные ограничения, так и различные логические ограничения. Модель работает только с целочисленнымми переменными.

Когда использовать:

  • Комбинация логических и линейных условий в целочисленных переменных
  • Сложные комбинаторные задачи
  • Невозможно свести условия только к линеййным соотношениям