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

Линейные выражения

Линейное выражение — линейная комбинация переменных модели вида:

a₁·x₁ + a₂·x₂ + … + aₙ·xₙ + c

Все коэффициенты aᵢ и константа c известны на этапе построения модели. Неизвестны только переменные xᵢ.

Линейные выражения — единственный «строительный материал» для ограничений и целевой функции во всех трёх подклассах модели: LP, IP, MIP. Тип переменной (непрерывная, целочисленная, булева) на структуру выражения не влияет: коэффициенты в любом случае могут быть произвольными вещественными числами.

Что выразимо линейно, а что — нет​

Линейны только две операции над переменными: умножение переменной на известный числовой коэффициент и сложение полученных слагаемых. Прибавление константы и умножение всего выражения на константу также линейны.

Нелинейные — то есть напрямую невыразимые в линейной модели — конструкции:

  • произведение двух переменных (x · y);
  • деление на переменную (a / x, x / y);
  • возведение переменной в степень (x², xⁿ при n > 1);
  • абсолютное значение, минимум, максимум от выражений, зависящих от переменных;
  • индексирование массива по переменной (значение, выбираемое из списка по индексу-переменной);
  • условные конструкции «если, то иначе», в которых правая часть зависит от выбора между альтернативами.

Часть из них моделируется в линейной модели через введение вспомогательных переменных и булевых индикаторов. Соответствующие приёмы моделирования описаны в отдельном разделе.

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

Способы записи выражений​

Линейное выражение в коде задаётся в одной из трёх форм. Все три формы взаимозаменяемы и принимаются методами модели наравне.

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

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

Модель.Ограничения().ЗначениеМеньшеИлиРавно(ОбъёмСырья, 1000); // переменная и число — линейные выражения

Строковая запись. Линейное выражение записывается строкой в естественной алгебраической нотации с именами переменных, числовыми литералами, операциями +, -, * и круглыми скобками. Удобно для коротких выражений, фиксированных на этапе разработки.

Пx = Модель.Переменные().Добавить("x");
Пy = Модель.Переменные().Добавить("y");

Модель.Ограничения().ЗначениеРавно("2*x - 3*(2 + 7.5*y) + 15", 45.8);

Объект «Линейное выражение». Создаётся методами менеджера выражений (Модель.Выражения()) или накапливается построителем выражений (см. ниже). Применяется, когда выражение строится программно — из коэффициентов и переменных, известных только во время выполнения кода.

Пx = Модель.Переменные().Добавить("x");
Пy = Модель.Переменные().Добавить("y");

Выражение = Модель.Выражения().ВзвешеннаяСумма(
    О2.Утилиты().Массив(Пx, Пy),
    О2.Утилиты().Массив(2.5, 3.0)
);   // соответствует "2.5*x + 3.0*y"
Строковые выражения в горячих циклах

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

Построитель выражений​

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

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

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

Построитель = Модель.Выражения().СоздатьПостроительВыражений();

Для К = 0 По ОбъёмыПоПериодам.ВГраница() Цикл
    Построитель.ДобавитьТерм(
        ОбъёмыПоПериодам[К],
        СтоимостьЕдиницы[К]
    );
КонецЦикла;

СуммарныеЗатраты = Построитель.ПолучитьВыражение();

Одновременно может быть создано несколько построителей — например, для отдельного формирования выражений «суммарные затраты» и «суммарный объём» в одном цикле.

См. также​