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

Приёмы моделирования

Прикладные задачи часто содержат конструкции, которые в их «естественной» формулировке нелинейны: фиксированные затраты, активные только при принятии решения; правила, действующие в одних режимах работы и не действующие в других; отклонения по модулю; ступенчатые функции стоимости; альтернативные технологические маршруты.

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

Приёмы из этого раздела — рабочий инструментарий смешанно-целочисленного программирования. Они позволяют оставаться в рамках линейной модели для широкого класса задач планирования и распределения ресурсов. В учебной и исследовательской литературе по операциям и оптимизации они известны под именами «big-M reformulation», «disjunctive constraints», «piecewise-linear approximation» и составляют ядро практики MIP-моделирования.

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

Индикаторные переменные и big-M​

Сценарий. Непрерывная переменная x ⩾ 0 — например, объём производства на линии — может принимать положительное значение только при активации (запуске линии). Активация связана с фиксированными затратами F, которые включаются в целевую функцию только при x > 0.

Формулировка. Вводится булева переменная-индикатор y ∈ {0, 1} («линия активна»). Связь между x и y выражается ограничением:

x ⩽ M · y

Здесь M — заведомо большое значение, ограничивающее x сверху. При y = 0 ограничение даёт x ⩽ 0, что в сочетании с x ⩾ 0 даёт x = 0. При y = 1 ограничение становится x ⩽ M — фактически неактивно при содержательно выбранном M.

Выбор M. Чрезмерно большое M — типичная причина медленного поиска. Оно ослабляет LP-релаксацию, и метод ветвей и границ перебирает существенно больше ветвей.

На практике M назначается равным содержательной верхней границе переменной x — мощности установки, оперативному лимиту, бюджету. «Заведомо большое число» в качестве M — плохая практика. Если содержательная граница известна, её и следует использовать. Если нет, ставится разумная и расширяется только при необходимости.

Прикладные задачи. Фиксированные затраты на открытие склада, на запуск производственной линии (lot-sizing), на использование транспортного средства; задачи facility location.

МощностьЛинииСутки = 10000;

ОбъёмВыпуска = Модель.Переменные().ДобавитьИзДиапазона(0, МощностьЛинииСутки, "ОбъёмВыпуска");
ЛинияАктивна = Модель.Переменные().ДобавитьБулеву("ЛинияАктивна");

// Объём положителен только при активной линии
Модель.Ограничения().ЗначениеМеньшеИлиРавно(
    ОбъёмВыпуска,
    Модель.Выражения().Терм(ЛинияАктивна, МощностьЛинииСутки)
);

// В целевой функции — переменные затраты на единицу плюс фиксированные затраты на запуск
Модель.ЦелеваяФункция().Минимизировать(
    Модель.Выражения().Сумма(
        Модель.Выражения().Терм(ОбъёмВыпуска, СтоимостьЕдиницы),
        Модель.Выражения().Терм(ЛинияАктивна, ФиксированныеЗатратыНаЗапуск)
    )
);

Условные ограничения через big-M​

Сценарий. Ограничение a · x ⩽ b должно действовать только в активном режиме, отмеченном булевой переменной y = 1. При y = 0 ограничение игнорируется. Пример: лимит на расход дешёвого сырья действует только при использовании альтернативной рецептуры.

Формулировка. К правой части добавляется слагаемое big-M, которое «выключает» ограничение при y = 0:

a · x ⩽ b + M · (1 − y)

При y = 1 множитель обнуляется, ограничение принимает исходный вид. При y = 0 правая часть увеличивается на M, и нарушить ограничение становится фактически невозможно — при содержательно выбранном M.

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

Расход      = Модель.Переменные().ДобавитьИзДиапазона(0, БольшойЛимит, "Расход");
РежимАктивен = Модель.Переменные().ДобавитьБулеву("РежимАктивен");

// При активном режиме расход не превышает Лимит; при неактивном — ограничение снимается
ВыключательОграничения = Модель.Выражения().Сумма(
    Лимит,
    Модель.Выражения().Терм(РежимАктивен, -БольшойЛимит)  // -M*y; при добавлении M даёт M*(1-y)
);

Модель.Ограничения().ЗначениеМеньшеИлиРавно(
    Расход,
    Модель.Выражения().Сумма(
        ВыключательОграничения,
        БольшойЛимит
    )
);

Дизъюнкция «либо одно, либо другое»​

Сценарий. Должно быть выполнено одно из двух ограничений, но не обязательно оба. Пример: изделие обрабатывается либо на станке A со временем tA, либо на станке B со временем tB.

Формулировка. Каждому варианту ставится в соответствие булева переменная-индикатор y₁, y₂ с условием:

  • y₁ + y₂ ⩾ 1 — обязателен хотя бы один вариант;
  • y₁ + y₂ = 1 — ровно один вариант.

Каждое из дизъюнктных ограничений записывается в условной форме через big-M (см. предыдущий раздел). Оно действует только при истинности соответствующего индикатора.

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

МаршрутA = Модель.Переменные().ДобавитьБулеву("МаршрутA");
МаршрутB = Модель.Переменные().ДобавитьБулеву("МаршрутB");

// Изделие проходит ровно по одному маршруту
Модель.Ограничения().ЗначениеРавно(
    Модель.Выражения().Сумма(МаршрутA, МаршрутB),
    1
);

// Соответствующие операционные ограничения активируются по индикатору
// (запись через big-M аналогична разделу выше)

Абсолютное значение в целевой функции​

Сценарий. Минимизируется отклонение фактического значения от целевого по модулю. Примеры: отклонение фактического выпуска от плана, отклонение остатка склада от норматива, отклонение нагрузки от средней.

Формулировка. Минимизация |x| для свободной по знаку переменной x (или |f(x)| для линейного выражения) сводится к замене на новую неотрицательную переменную t ⩾ 0 и пару линейных ограничений:

t ⩾ x,    t ⩾ −x

В целевую функцию вместо |x| включается t. При минимизации решатель выберет t равным max(x, −x) = |x|, что и требовалось.

Условие применимости. Приём работает, когда |x| входит в целевую функцию с положительным коэффициентом при минимизации (или с отрицательным при максимизации). В обратном случае минимум t не совпадёт с |x| — потребуется введение булевой переменной знака и big-M-формулировка.

Прикладные задачи. Минимизация суммарного отклонения плана от прогноза, выравнивание нагрузки между подразделениями, регрессия по модулю отклонений (L¹).

Отклонение      = Модель.Переменные().ДобавитьИзДиапазона(0, БольшоеЗначение, "Отклонение");
ФактическийВыпуск = Модель.Переменные().ДобавитьИзДиапазона(0, МощностьСутки, "ФактическийВыпуск");

// Отклонение ⩾ |ФактическийВыпуск - Плановый|
Модель.Ограничения().ЗначениеБольшеИлиРавно(
    Отклонение,
    Модель.Выражения().Выражение(СтрШаблон("%1 - %2", ФактическийВыпуск.Имя, ПлановыйВыпуск))
);
Модель.Ограничения().ЗначениеБольшеИлиРавно(
    Отклонение,
    Модель.Выражения().Выражение(СтрШаблон("%1 - %2", ПлановыйВыпуск, ФактическийВыпуск.Имя))
);

Модель.ЦелеваяФункция().Минимизировать(Отклонение);

Минимум и максимум выражений​

Сценарий. В целевой функции участвует максимум (или минимум) из нескольких выражений: пиковая нагрузка, наихудшее по сценариям отклонение, минимальный из остатков по складам.

Формулировка. Для z = max(f₁, f₂, …, fₙ) вводится новая переменная z и набор ограничений:

z ⩾ f₁,  z ⩾ f₂,  …,  z ⩾ fₙ

В целевую функцию включается z, направление поиска — минимизация. Для z = min(...) всё симметрично: z ⩽ fᵢ и максимизация.

Условие применимости такое же, как для абсолютного значения: знак z в целевой функции должен «прижимать» переменную к нужному значению.

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

ПиковаяНагрузка = Модель.Переменные().ДобавитьИзДиапазона(0, МаксНагрузка, "ПиковаяНагрузка");

Для Каждого Период Из Периоды Цикл
    // ПиковаяНагрузка ⩾ Нагрузка[Период]
    Модель.Ограничения().ЗначениеБольшеИлиРавно(
        ПиковаяНагрузка,
        Нагрузка[Период]
    );
КонецЦикла;

Модель.ЦелеваяФункция().Минимизировать(ПиковаяНагрузка);

Кусочно-линейная функция​

Сценарий. Зависимость нелинейная по форме, но представима последовательностью линейных участков. Примеры: ступенчатые скидки от объёма закупки, ступенчатый тариф на электроэнергию, ставка налога с прогрессивной шкалой, ступенчатые затраты на хранение.

Формулировка. Аппроксимация кусочно-линейной функции в линейной модели выполняется через сегментацию. Переменная-аргумент представляется как сумма переменных-сегментов:

x = x₁ + x₂ + … + xₖ,   0 ⩽ xᵢ ⩽ Δᵢ

Значение функции — сумма произведений сегментов на угловые коэффициенты соответствующих участков.

Если порядок выбора сегментов важен (следующий участок используется только после полного исчерпания предыдущего), добавляются булевы переменные-индикаторы участков и связывающие big-M-ограничения.

Прикладные задачи. Lot-sizing со ступенчатыми затратами на партию, прогрессивные тарифы и налоги, затраты на хранение и оборотные средства, объёмные скидки.

Кусочно-линейные конструкции — наиболее техноёмкий из приёмов моделирования. В больших задачах требуется аккуратное управление численной стабильностью и качеством LP-релаксации. Полные сценарии — в специализированной литературе по линейному программированию и в примерах со ступенчатыми функциями стоимости.

Дискретный выбор «один из вариантов»​

Сценарий. Из набора альтернатив (поставщиков, технологических маршрутов, конфигураций оборудования) выбирается ровно одна или не более одной.

Формулировка. Каждому варианту ставится в соответствие булева переменная yᵢ ∈ {0, 1}. Условие выбора:

  • Σ yᵢ = 1 — выбрана ровно одна альтернатива;
  • Σ yᵢ ⩽ 1 — выбрана не более одной альтернативы;
  • Σ yᵢ ⩾ 1 — выбрана хотя бы одна альтернатива.

Содержательные параметры выбранного варианта — стоимость, сроки, нормативы — включаются в модель через произведение этих параметров на соответствующую yᵢ.

Прикладные задачи. Выбор поставщика, выбор размещения склада из нескольких кандидатов, выбор конфигурации продукта, задачи о назначениях. Полный пример — Назначение исполнителей.

ВыбранПоставщик = Модель.Переменные().ДобавитьМассивБулевых(
    ПоставщикиКандидаты.Количество(),
    "ВыбранПоставщик"
);

// Ровно один поставщик
Модель.Ограничения().ЗначениеРавно(
    Модель.Выражения().Сумма(ВыбранПоставщик),
    1
);

// Стоимость закупки = сумма стоимостей выбранного поставщика
СтоимостьЗакупки = Модель.Выражения().СоздатьПостроительВыражений();
Для К = 0 По ПоставщикиКандидаты.ВГраница() Цикл
    СтоимостьЗакупки.ДобавитьТерм(
        ВыбранПоставщик[К],
        ЦенаПоставщика[К]
    );
КонецЦикла;

Линейное масштабирование коэффициентов​

Скорость и численная стабильность поиска существенно зависят от порядков величины коэффициентов модели.

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

Стандартный приём — приведение к одному порядку:

  • рубли пересчитываются в тысячи рублей или в миллионы;
  • время — в часах или в минутах в зависимости от характерной длительности задачи;
  • доли — в процентах.

После расчёта значения масштабируются обратно на этапе обработки решения.

Контрольные признаки плохого масштабирования:

  • большие значения констант M в big-M-ограничениях — десятки тысяч и больше при содержательных значениях переменных в единицах;
  • коэффициенты в одной строке матрицы, различающиеся на 6 и более порядков.

При таких признаках масштабирование выполняется до запуска решателя.

См. также​