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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// Хотим закупить груши и яблоки, но бюджет ограничен. Как быть?

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

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

// 3. Описываем ограничения
Модель.Ограничения().Соотношение("КолвоЯблок >= 0; КолвоГруш >= 0"); 
Модель.Ограничения().Соотношение("210 * КолвоЯблок + 300 * КолвоГруш <= 10000"); // <-- макс. бюджет на закупку

// 4. Устанавливаем цель - максимизировать выручку
Модель.Максимизировать("300 * КолвоЯблок + 440 * КолвоГруш");

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

// 6. Наслаждаемся результатом
Сообщить("Количество яблок: "   + Решение.ЗначениеПеременной(КолвоЯблок));
Сообщить("Количество груш: "    + Решение.ЗначениеПеременной(КолвоГруш));

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

Замечание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Используется для построение оптимальных путей между точками.

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

  • Логистика доставки
  • Обслуживание клиентов с выездом

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

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

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

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