К идее написания этой статьи привели несколько соображений.
1. В настоящее время платформа «1С: Предприятие», обладая рядом достоинств, получила широкое распространение как среда разработки бизнес-решений для самых различных областей. Первоначально состав ее прикладных решений был ориентирован на решение задач автоматизации бухгалтерского и налогового учета предприятий и организаций, автоматизации торгового учета и расчета заработной платы, решение управленческих задач. Однако сегодня вследствие заметного роста функциональности она начинает представлять интерес и для таких областей как математическое моделирование бизнес-процессов, проектирование экономических, финансовых, производственных, технологических систем, решение задач прогнозирования и т.д.
2. Решение этих новых задач немыслимо без использования методов получения оптимальных решений. И поскольку речь идет о сложных системах, состояние которых зависит не от одного-двух, а от десятков независимых переменных, а критерием оптимизации систем является не одна целевая функция, а несколько, то для получения оптимальных решений становится очевидной необходимость использования методов многокритериальной и многопараметрической оптимизации.
3. Одним из наиболее эффективных методов решения задач многокритериальной и многопараметрической оптимизации систем является метод ЛПт-поиска или метод зондирования пространства независимых переменных пробными точками ЛПт-равномерно распределенной последовательности. Этот метод был разработан российским математиком Соболем И.М. [Л.1] и успешно применяется последние десятилетия в самых различных областях.
4. Ключевым звеном реализации метода ЛПт-поиска является генерация пробных точек ЛПт-равномерно распределенной последовательности. Функции для генерации этих последовательностей в настоящее время можно найти во многих библиотеках и системах научных и коммерческих расчетов: GNU Scientific Library, Matlab, MOVI, SobolSeq, однако они непригодны для непосредственной реализации на платформе «1С: Предприятие».
Приведенные соображения определили и основные задачи настоящей статьи:
- дать представление о методе ЛПт-поиска оптимальных решений в задачах многокритериальной оптимизации;
- рассмотреть существующие в математической литературе расчетные формулы и алгоритмы генерации ЛПт-равномерно распределенной последовательности;
- рассмотреть возможности языка программирования 1С для непосредственной реализации этого метода в среде «1С: Предприятие» без использования средств интеграции этой платформы с какими-либо специализированными математическими пакетами;
- показать конкретный пример реализации одного из алгоритмов генерации точек ЛПт-последовательности средствами языка 1С с приведением результатов вычислений декартовых координат этих точек в среде "1С: Предприятие".
Основные сведения о методе ЛПт-поиска оптимальных решений
Математически решение задач многокритериальной и многопараметрической оптимизации формулируется как задача нахождения в n-мерном пространстве Rn некоторого вектора независимых переменных X, который с учетом определенных условий (ограничений) минимизировал (максимизировал) бы m целевых функций (критериев качества) системы:
где fl(X) - целевые функции; X - вектор независимых переменных xj; D - множество допустимых решений; gr(X) - функции ограничений; Gr, Fl - предельно допустимые значения функций gr(X) и fl(X); aj, bj - величины, определяющие границы изменения независимых переменных.
Множество допустимых решений D характеризуется тем, что в его пределах выполняются все ограничения, которые необходимо учитывать. Ограничения накладываются на независимые переменные (варьируемые параметры), на характеристики функционирования проектируемой системы, а также на критерии качества и соответственно подразделяются на параметрические, функциональные и критериальные.
Параметрические ограничения записываются в виде неравенств aj ≤ xj ≤ bj и вводятся с целью исключения проектных решений, заведомо неприемлемых по условиям выполнимости. Функциональные ограничения, накладываемые на параметры проектов, имеют вид gr(X) ≤ Gr и при решении экономических задач часто представляют собой ограничения на ресурсы: сырьевые, денежные, трудовые и т.д. Критериальные ограничения fl(X) ≤ Fl устанавливают пределы изменения целевых функций и вводятся с целью исключения заведомо неконкурентоспособных вариантов проектных решений.
Особенностью решения задач многокритериальной и многопараметрической оптимизации является то, что в силу многоэкстремальности целевых функций и сложности их поведения, когда числовое значение одной из целевых функций можно улучшить лишь за счет ухудшения других, алгоритмы поиска оптимальных решений строятся на основе теории принятия решений и носят диалоговый характер. Блок-схема одного из таких алгоритмов [Л.2] приведена на рис.1 и включает несколько этапов.
Рис.1. Блок схема диалогового алгоритма ЛПт-поиска оптимальных решений
Этап I выполняется без вмешательства человека. На основе генерации точек ЛПт - последовательности Q1, ..., QN, равномерно расположенных в единичном многомерном кубе Kn, формируются N пробных точек A1, ..., AN, равномерно расположенных в многомерном пространстве варьируемых параметров Gn, где n - число измерений (варьируемых параметров). Декартовы координаты точек Qi в Kn (qi,1, .... qi,n) и точек Ai в Gn (αi,1, ..., αi,n) связаны следующим соотношением:
| αi,j = aj + (bj - aj) qi,j , i = 1, ..., N; j = 1, ..., n | (2) |
где aj, bj - границы варьируемых параметров.
В каждой из пробных точек Ai рассчитывается система и вычисляются значения всех целевых функций (критериев качества) Ф1(Ai), ..., Фm(Ai). По каждому критерию составляется таблица испытаний, в которой значения Фν(A1), ..., Фν(AN) расположены в порядке возрастания
(3)
где k - количество отобранных значений по каждому критерию.
Этап II предполагает вмешательство проектировщика (совета специалистов), который анализируя все таблицы должен назначить критериальное ограничение для каждого критерия:
| Фν(A) ≤ Фν** , | (4) |
где Фν** - худшее значение критерия Фν, которое проектировщик считает приемлемым.
На этапе III выполняется проверка непустоты множества допустимых точек D. Здесь фиксируется какой-нибудь из критериев, например Ф1, и рассматривается соответствующая ему таблица испытаний. Пусть s - количество значений в этой таблице, удовлетворяющих выбранному критериальному ограничению Ф1**, так что
Путем перебора значений всех критериев в точках Ai1, ..., Ais проверяется, есть ли среди этих точек хотя бы одна такая, в которой справедливы одновременно все неравенства (4):
Если такая точка Aij существует, то множество D непустое, и задача (1) разрешима (при любом выборе). В противном случае следует вернуться ко второму этапу и потребовать от совета специалистов уступок при назначении Фν**. Если такие уступки невозможны, то необходимо вернуться к первому этапу и увеличить количество N пробных точек, чтобы повторить второй и третий этапы с таблицами испытаний большего объема.
Наконец, если при неоднократном увеличении N точки Aij не обнаруживаются, то это означает, что выбранные критериальные ограничения Фν** несовместны.
Поскольку ключевым звеном реализации описанного алгоритма поиска оптимальных решений является генерация точек ЛПт -последовательности, то рассмотрим далее порядок их формирования [Л.1, Л.2]. Однако сначала приведем самые необходимые сведения из теории ЛПт-последовательностей, наиболее равномерно заполняющих многомерное пространство параметров.
Рассмотрим единичный n - мерный куб Kn, состоящий из точек P с декартовыми координатами
удовлетворяющими неравенствам 0 ≤ xj ≤ 1 при j = 1, ..., n. На рис.2 и рис.3 показаны две сетки – кубическая решетка и улучшенная сетка, которые при n = 2 и числе пробных точек N = 16 показывают возможности равномерного зондирования этого куба.
Рис.2. Кубическая решетка при n=2 (N=16) Рис.3. Улучшенная сетка при n=2 (N=16)
Сравнение рисунков показывает, что в обоих случаях каждому из 16 малых квадратов принадлежит одна и только одна точка сетки, так что, казалось бы, равномерность расположения точек обеих сеток примерно одинакова. Ситуация, однако, резко изменится, если потребуется исследовать функцию f(x1, x2), определенную в Kn, и которая сильно зависит лишь от одного аргумента, например f=f(x1). Вычислив значения функции в точках первой сетки (рис.2), мы получим лишь 4 различных значения, каждое повторенное четыре раза. При расчете же в точках второй сетки (рис.3) получим 16 значений, дающих гораздо лучшее представление о диапазоне изменения функции f(x1, x2). В многомерном случае при n > 2 кажущаяся равномерность кубической решетки еще больше ухудшается, так как потеря информации при вычислении f(x1, x2) еще больше возрастает.
Что же представляет собой ЛПт - последовательность? Согласно [Л.2] последовательность точек P0, P1, ..., Pi, ..., Pn единичного многомерного куба Kn называется ЛПт-последовательностью, если любой ее двоичный участок, содержащий не менее 2т+1 точек, представляет собой Пт-сетку. Сетка, состоящая из N=2v точек куба Kn, называется Пт-сеткой, если каждому двоичному параллелепипеду Пk с объемом VПk = 2т/N принадлежат 2τ точек сетки.
Двоичный параллелепипед Пk, на основании которого дается определение Пт-сетки, геометрически представляет собой часть многомерного куба Kn с числом измерений n и сторонами, параллельными координатным граням Kn. Понятие двоичного параллелепипеда Пk играет ключевую роль связующего звена между единичным гиперкубом Kn, где генерируются ЛПт-последовательности, и реальной областью варьируемых параметров Gn. При этом преобразовании, что важно, свойство равномерности сохраняется.
Название ЛПт-последовательность появилось как сокращение фразы «последовательность, любой двоичный участок которой представляет собой ЛПт-сетку». Под двоичным участком последовательности понимается множество точек P с номерами i, удовлетворяющими неравенству вида:
Например, участки 0 ≤ i < 8, 8 ≤ i < 16, 16 ≤ i < 24 являются двоичными (k=0,1,2; s=3), а участок 4 ≤ i < 16 двоичным не является.
Рассмотрим далее эффективный способ построения ЛПт-последовательностей, у которых координаты всех точек двоично рациональны. Для этого запишем бесконечную треугольную матрицу с единицами на главной диагонали вида
которая называется направляющей матрицей. Элементы vsj расположенные ниже главной диагонали, могут быть нулями и единицами, а выше нее – только нулями. Задание матрицы (vsj) равносильно заданию двоично рациональных дробей (в двоичной системе счисления)
которые называются направляющими числами и вычисляются по формуле:
| Vj(l) = rj(l) 2-l | j=1...n; l=1...lM (5) |
где rj(l) называются числителями направляющих чисел. В работе [Л.2] проведен расчет числителей направляющих чисел, которые представлены в таблице 1 при 1 ≤ j ≤ 51 и 1 ≤ l ≤ 20 и существенно облегчают расчет точек ЛПт-последовательности.
По таблице 1 можно вычислять точки Qi с номерами i = 1, ..., N в кубе Kn размерности n. Если количество измерений n существенно меньше 51, например n = 10, то можно использовать первые 10 строк таблицы. Если количество пробных точек заранее выбрано, то можно ограничиться первыми m столбцами таблицы, где m = 1 + [ln(N) / ln(2)]. Пусть, например, N = 1000, тогда m = 10, т.е. в таблице используются только первые 10 столбцов.
Рассмотрев самые необходимые сведения из теории ЛПт-поиска, перейдем к рассмотрению существующих в математической литературе основных расчетных формул и алгоритмов генерации точек ЛПт-равномерно распределенной последовательности [Л.1, Л.2, Л.3].
Исходный алгоритм [Л.2].
Исходный алгоритм генерации точек Qi ЛПт-последовательности строится на использовании логических операций и считается одним из быстродействующих.
1. Перед началом расчета проектировщиком (советом специалистов) выбираются:
N - количество пробных точек;
n - количество измерений (варьируемых параметров).
2. Производится генерация номеров пробных точек i от 1 до N и текущий номер i каждой пробной точки преобразуется в двоичную систему счисления и записывается в форме:
Например, если текущий номер пробной точки 9, то в двоичной форме i = 1001, где m = 4. Если текущий номер 1000, то i = 1111101000, где m = 10.
3. Производится вычисление декартовых координат текущей пробной точки Qi по формуле:
(6)
где Vj(l) - направляющие числа, которые определяются по формуле (5).
В формуле (6) знак * означает поразрядное сложение по модулю два в двоичной системе (операция «исключающее ИЛИ»). То есть, если el = 1, то соответствующее значение Vj(l) войдет в эту формулу, а если el = 0, то соответствующее значение Vj(l) пропускается. Таким образом для расчета по формуле (6) нужны только логические операции.
Арифметический алгоритм [Л.2].
Для реализации формулы (6) можно прибегнуть к расчету непосредственно по таблице числителей направляющих чисел rj(l) (табл. 1). Для этого по заданному номеру i вычисляем
(7)
а затем для j = 1, 2, ..., n
В последних двух формулах (7) и (8) квадратные [] и фигурные {} скобки означают соответственно целую и дробную части содержимого этих скобок.
Расчет по арифметическому алгоритму гораздо медленнее, чем расчет по формуле (6), но если количество используемых в расчете точек не превосходит 104, то он вполне приемлем.
Алгоритм на основе кода Грэя [Л.3].
В этом алгоритме из точек Qi составляется новая последовательность Q'i. Точки новой последовательности вычисляются на основе точек последовательности Qi по формуле:
(9)
где Г(i) – код Грэя, соответствующий номеру i:
| Г(i) = i * [ i / 2 ] | (10) |
В формуле (10) квадратные скобки означают целую часть числа, заключенную в них.
По определению код Грэя – это способ представления двоичных чисел, при котором два соседних значения отличаются только в одном бите.
Например, если в десятичной системе взять два числа: 3 и 4, то в двоичной системе они будут выглядеть как 011 и 100, а в коде Грэя – как 010 и 110. Сравнение представлений этих чисел показывает, что в двоичном коде переход от 3(011) к 4(100) меняет три бита, а в коде Грэя переход от 3(010) к 4(110) меняет только один бит (старший).
Разряд, который в коде Грэя меняется при переходе от одного числа к другому, вычисляется по формуле:
| l = 1 + log2[Г(i) * Г(i-1)] | (11) |
Таким образом, особенностью этого алгоритма является то, что каждая последующая точка Q'i легко вычисляется по предыдущей Q'i-1, при этом двоичные участки новой последовательности Q'i совпадают с двоичными участками последовательности Qi. Последнее гарантирует сохранение всех основных и дополнительных свойств равномерности.
Вычисление декартовых координат каждой последующей точки Q'i по предыдущей Q'i-1 вычисляется по формуле:
| q'i,j = q'i-1,j * Vj(l), j = 1,2, ..., n | (12) |
где Vj(l) - направляющие числа, которые определяются по формуле (5).
В формуле (12) знак * означает поразрядное сложение по модулю два в двоичной системе (операция «исключающее ИЛИ»).
В целом, порядок вычисления q'i,j по данному алгоритму следующий:
1) по формуле (10) вычисляем Г(i);
2) по формуле (11) вычисляем l и находим в таблице направляющие числа Vj(l);
3) по формуле (12) вычисляем q'i,j.
Возможности языка программирования 1С для непосредственной реализации метода ЛПт-поиска в среде «1С: Предприятия»
Как известно, язык программирования 1С – это предметно-ориентированный язык высокого уровня для разработки и настройки бизнес-приложений, ориентированных на автоматизацию учёта и управления в организациях любого масштаба.
Он поддерживает полный набор базовых арифметических функций и расширенный набор математических функций, позволяет работать с числами высокой точности, выполнять преобразования типов и использовать сложные математические выражения, включая тригонометрию, логарифмы, возведение в степень, выделение целого числа и т.д.
Поскольку, как показано выше, при реализации метода ЛПт-поиска широко используются двоичные числа и логические операции с ними, то возможности языка 1С соответствуют и этим требованиям. Так, начиная с версии 8.3.11, в платформе «1С: Предприятие» реализован набор функций для работы с целыми числами на уровне битов. Числа интерпретируются как беззнаковые 32-разрядные числа. Реализованы методы глобального контекста ПроверитьБит(), ПроверитьПоБитовойМаске(), УстановитьБит(), ПобитовоеИ(), ПобитовоеИли(), ПобитовоеНе(), ПобитовоеИНе(), ПобитовоеИсключительноеИли(), ПобитовыйСдвигВлево(), ПобитовыйСдвигВправо().
Автором данной публикации средствами языка 1С разработаны процедуры и функции, которые позволили реализовать все формулы и алгоритмы, описанные выше, и проверить их работу в среде «1С: Предприятие».
В качестве примера рассмотрим процедуру СформироватьQij_Двоичн(), которая реализует по формуле (6) исходный алгоритм генерации точек ЛПт-последовательности и вычисления декартовых координат пробных точек Qi.
Перем ТЗ_Rjl;
Перем Rjl,Vjl,Wjl,Qij;
//РАСШИФРОВКА ПЕРЕМЕННЫХ
// i - текущий номер пробной точки 1<=i<=Nпр
// Nпр - количество пробных точек
// j - текущий номер строки массива числителей направляющих чисел Rjl 0 < j < N
// N - количество строк массива числителей направляющих чисел Rjl (число размерностей гиперкуба)
// l - текущий номер столбца массива числителей направляющих чисел Rjl 0 < l < Lm
// Lm - количество столбцов массива числителей направляющих чисел Rjl
// ТЗ_Rjl - таблица числителей направляющих чисел Rjl (получена из таблицы 1)
// Двумерные массивы:
// Rjl - массив числителей направляющих чисел
// Vjl - массив направляющих чисел
// Wjl - массив сдвинутых влево направляющих чисел
// Qij - массив точек ЛПт-последовательности
// a - принятая в расчетах разрядность битовых чисел а <= 32
// d - максимальное целое число d = 2^a
Процедура СформироватьQij_Двоичн()
d = Pow(2,a);
Lm = 1 + Цел(Log(Nпр)/Log(2));
СформироватьМассивWjl();
Для i=1 По Nпр-1 Цикл
x=i-1;
Для j=1 По N Цикл
y=j-1;
Sum=0;
Для l=1 По Lm Цикл
z=l-1;
ksi=ПобитовыйСдвигВлево(1,z);
w=ПобитовоеИ(i,ksi);
Если w=ksi Тогда
Sum=ПобитовоеИсключительноеИЛИ(Sum,Wjl[y][z]);
КонецЕсли;
КонецЦикла;
Qij[x][y]=Sum/d;
КонецЦикла;
КонецЦикла;
КонецПроцедуры
Процедура СформироватьМассивWjl()
Для j=0 По Rjl.ВГраница() Цикл
Для l=0 По Rjl[j].ВГраница() Цикл
ll=a-l;
b = Rjl[j][l];
Wjl[j][l] = ПобитовыйСдвигВлево(b,ll-1);
КонецЦикла;
КонецЦикла;
КонецПроцедуры
Результаты работы процедуры СформироватьQij_Двоичн() представлены в таблице 2.
При расчете значений декартовых координат пробных точек Qij в качестве исходных данных были приняты:
Nпр = 512 - количество пробных точек;
N = 12 - число независимых переменных (число измерений многомерного куба).
Как показывает таблица 2, значения рассчитанных декартовых координат пробных точек qi,j находятся в диапазоне 0 ≤ qi,j ≤ 1. Это объясняется тем, что эти значения рассчитываются по формулам (6), (8), (12) для единичного многомерного куба Kn. Фактические же значения декартовых координат пробных точек Ai , находящихся в многомерном пространстве варьируемых параметров Gn , выражаются в единицах физических величин, рассчитываются по формуле (2) и используются в расчетах целевых функций fl(X) (см. формулу (1) и рис.1).
В заключение отметим, что возможности использования языка 1С для расчета целевых функций fl(X) конкретных систем (производственных, экономических, финансовых и т.д.) полностью определяются математическим аппаратом их описания и должны определяться в каждом конкретном случае. Задачей же настоящей статьи являлось показать, что ключевое звено метода ЛПт-поиска оптимальных решений, а именно - генерация точек ЛПт-равномерно распределенной последовательности, вполне может быть реализована в среде «1С: Предприятие» без обращения к сторонним математическим пакетам. Обращение к последним может быть использовано только в случаях, если средств языка 1С не хватает для сложных расчетов целевых функций конкретных систем.
Литературные источники
1. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. М.: Наука, 1969.
2. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд. М.: Дрофа, 2006.
3. Антонов И.А., Салеев В.И. Экономичный способ вычисления ЛП-последовательностей. Журнал вычислительной математики и математической физики, 1979, т.19, №1, с.243-245.
```
Вступайте в нашу телеграмм-группу Инфостарт