Автоматика и телемеханика, № 1, 2015
Робастные и адаптивные системы
И.Н. КАРБОВСКИИ
канд. техн. наук
© 2015 г. _
(Институт энергетических исследований РАН, Москва)
ТЕХНОЛОГИЯ ПОЛИЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ЕСТЕСТВЕННО ОБУСЛОВЛЕННЫХ МОДЕЛЯХ. II
Статья содержит изложение новых алгоритмов программной реализации фазового метода полилинейного программирования и исследование поведения этого метода в точках стагнации.
1. Введение
Настоящая статья является продолжением [1]. Рассматриваются аспекты, связанные с генерацией и решением задач линейного программирования (ЛП) в общей технологии использования метода полилинейного программирования. В разделе 2 дается формальное описание ЛП задачи. Раздел 3 включает общую организацию потока независимых решений ЛП задач для последовательных фаз. Наличие подобного потока вызывает необходимость использования специальных мер по преодолению накопления ошибок округления в случае плохо обусловленных линейных подзадач. В разделе 4 представлены некоторые способы применения метода условного градиента (метода возможных направлений) для размораживания точки стагнации. В разделе 5 представлен расширенный синтаксис задания полилинейных задач, упрощающий описание задач для однородных объектов (продукты, отрасли, территории) и задач, связанных последовательными шагами в дискретное время (динамические задачи). Хотя подобные задачи могут решаться без какого-либо расширения синтаксиса, но для класса далее определенных регулярных моделей предложенные расширения обеспечивают значительное сокращение описания модели и трудоемкости вычислений.
В заключении рассматриваются практические аспекты реализации описанной технологии.
2. Конструкция линейных задач
Сначала необходимо построить формальное описание задач линейного программирования, которые должны быть созданы и переданы решателю ЛП для всех фаз в циклическом порядке. Каждое такое описание включает:
- список активных переменных с их начальными величинами и предварительно установленными границами;
- список активных индикаторов с их предварительно установленными границами;
- список матричных ограничений с ненулевыми элементами и с индикацией их величин и именами соответствующих строк и столбцов;
- опциональную индикацию целевых переменных, отобранных из списка индикаторов.
Пусть F € Ф является определенной фазой, включающей n(F) = |F| переменных. В линейной задаче, построенной для F, активными переменными являются элементы из F. Множество T активных индикаторов является подмножеством множества Y, компоненты которого имеют наследственные зависимости от переменных из F:
T = {y € Y | y.HVars П F = 0}.
Предположим, что A является матрицей задачи ЛП для F. Входами A являются коэффициенты линейных форм, выражения величин y € T через величины x € F снабженными ранее заданными численными величинами всех x / F
(2.1) y = ^2 avxX + ayo, ayx = dy/dx.
xeF
Значения ayx могут выражаться через некоторые x / F, но не через x € F, и должны вычисляться только для тех пар y T, x F, для которых x € y.HVars, в противном случае они априорно полагаются нулевыми. Значения ayx в простейшей версии могут вычисляться n(F)-проходным алгоритмом через приращения y T в ответ на единичное приращение переменной x € F по отношению к произвольной базе. Недостаток этой схемы проявляется, когда некоторые из ayx являются малыми разностями большйх по модулю величин базы приращений. Поэтому при использовании этой схемы точность результатов вычислений уменьшается и искажение генерируемой линейной задачи может быть существенным, особенно для плохо обусловленных задач. Далее будет представлена более устойчивая вычислительная схема, имитирующая формулы вычислений для dy/dx, но без точного построения таких формул.
VD (аббревиатура для Value - численное значение и Derivative - производная) имеет тип данных такой, что с некоторым предварительно определенным n € Z элементы z € VD имеют свойства z. Val € R, z.Drv € Rn. Конструктор VD( Val € R, Drv € Rn) производит VD-объект с заданными свойствами. VD-арифметика определяется так:
z1 ± z2= VD(z1.Val ± z2.Val, zl.Drv ± z2.Drv),
zl ■ z2= VD(z1. Val ■ z2. Val, zl.Drv ■ z2. Val + z2.Drv ■ zl. Val),
z1/z2 = VD(z1.Val/z2.Val, (zl.Drv ■ z2.Val - z2.Drv ■ zl.Val )/(z2.Val )2).
Для фазы F положим Id(F) множеством идентификаторов переменных в F. Для объектов z VD входы векторов z.Drv индексируются идентификаторами из Id(F), так что для t € Id(F) компонента z.Drvt соответствует переменной Obj(t) € F. Пусть для t € Id(F) вектор et € Rn является ортом
с единицей на входе, индексируемым t, и с нулями на всех других переменных. Пусть y. VD является VD-типом свойства y € Y. Пусть 0n - нулевой вектор в Rn. Следующее утверждение определяет однопроходный алгоритм вычисления всех компонент матрицы ограничений.
Утверждение 2.1. Пусть установками GCS (общая вычислительная схема, см. [1, раздел 3]) являются:
- принудительно устанавливаемые: M = VD; Q(t,u,v): VD-арифмети-
G(t) : если t € Id(F), то G(t) = VD(0,et), иначе G(t) = VD(t.Value, 0n);
- выходные: y. < Property > = y. VD.
Тогда множества GCS для каждого y € Y значения из y.VD, где каждый y.VD.Drvt есть ayx = dy/dx для x = Obj(t) и y.VD.Val есть ay0.
При оперировании в классе вполне полилинейных функций деление VD-арифметики может быть упрощено, так как в этом случае делитель всегда является константой, и тогда z1/z2 = VD(z1.Val/z2.Val, z1.Drv/z2.Val). Вычислительная сложность описанного процесса построения матрицы ограничений может быть оценена как O(n(Y) ■ (n(F) + 1)) в соответствии с размерностью VD-объектов. Решателю ЛП надо передать только значения ay0 = y. VD. Val для y € T и ненулевые значения ayx = y. VD.Drvxjdent для x € y.HVars.
3. Управление потоком задач ЛП
Для "естественно обусловленных моделей" (ЕОМ) (см. [1, раздел 2]) проверка полилинейности и построение фаз являются предварительными процедурами, которые выполняются однократно. Далее должен быть запущен цикл, где для каждой фазы выполняются следующие действия:
- построение и решение задачи ЛП;
- формирование результатов решателя в качестве новых значений активных переменных;
- ревизия тестирования и исследование условий прерывания.
Серийный запуск всех фаз (от первой до последней) в дальнейшем будем
называть итерацией, а циклический запуск фаз будет реализовываться как серийный запуск итераций.
Далее рассматривается использование решателя ЛП как стандартного двустороннего прямого симплекс-метода со словарями. Начальный словарь для каждой текущей фазы представлен множеством базисных переменных T, множеством небазисных переменных F, матрицей ограничений A и собственными граничными условиями, как было обозначено ранее. Начальный словарь может быть допустимым или недопустимым. Даже если решатель нашел допустимое и оптимальное решение для фазы F¿., начальный словарь для следующей фазы F^+i может быть найден как недопустимый, поскольку:
- индикатор y € T П T&+1 попадает в границы решения для фазы F&, но при переходе к следующей фазе он выходит за границы в результате оши-
бок округления при вычислении компонент ayx и начальных значений y для следующей фазы по (2.1);
- существуют некоторые индикаторы y € Тд+ДТ^ с величинами вне их границ.
Пока текущий словарь недопустим, положим LOYALS = {y € Т | y.Low ^ ^ y.Value ^ y.Up}, FAULTS = T\LOYAL, и пусть y € FAULTS является индикатором с наименьшим уклонением в FAULTS. Тогда текущая подзадача улучшения словаря такова:
если y.Value < y.Low, то y.Value — maxx ly.Value ^ y.Low; если y.Value > y.Up, то y.Value — minx ly.Value ^ y.Up, и для обоих случаев требования [1, (2.2)] сохраняют силу только для всех x € F и для всех yk € LOYALS.
В таком случае наименьшее уклонение помещается на первое место и устраняется минимально возможным изменением переменных. В противном случае существенное увеличение отклонений и даже увеличение их числа может увеличиваться в течение нескольких фаз. Эта особенность несущественна в основных приложениях решателя ЛП, но может оказаться существенной для серии независимых подзадач ЛП фазового метода.
Исполнение итераций прерывается либо по номеру итерации, определяемому пользователем, либо вплоть до обнаружения неулучшения на текущей итерации. Улучшение при поиске допустимого решения фиксируется при уменьшении количества отклонений или если количество отклонений не уменьшается, то при уменьшении величины максимального отклонения. Если допустимое решение уже достигнуто, то в процедуре поиска максимума дальнейшее улучшение фиксируется по улучшению значения критериального показателя.
4. Условно градиентный метод в точках стагнации
Если допустимый план найден и фазовым методом достигнута стационарная точка x = x*, а задача включает не только поиск допустимого плана, но и поиск экстремума в ЕОМ, тогда возникает вопрос, является ли эта точка локальным экстремумом или неэкстремальной точкой стагнации фазового метода. В последнем случае существует, и в общем случае не единственное, направление подъема, представленное вектором u € Rn такое, что для некоторого T > 0 для всех 0 < t ^ T план
(4.1) x(t)= x* + t ■ u
является допустимым и дает рост критерия. Если, более того, x(t) является внутренней точкой допустимой области, то это гарантирует возможность обновления фазового метода запуском из точки x(t).
Собственное назначение вектора u с компонентами щ может быть получено конструкцией, основанной на градиенте с упрощениями, обусловленными свойствами полилинейной задачи. Благодаря специфике фазового метода точка стагнации x* всегда является граничной. Пусть шкала u определяется единичной кубической нормой. Тогда для u действуют очевидные граничные
и нормализованные ограничения: и.Ьот ^ и ^ и.ир, где если переменная Хг в х* находится в своей нижней границе, то (и.Ьои:)г = 0, иначе (и.Ьои:)г = = — 1, и если Хг находится в своей верхней границе, то (и.ир)г = 0, иначе (и.ир)г = 1. Для индикаторов согласно их величинам в х = х* обозначим:
вь°ш = {с} у {у е у : у.УаЫе = у.Ьош); Вир = {у € У : у.УаЫе = уЛр};
В = Вир и ВЬо'ш, Б = У у.ИУатз.
уев
Для всех
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.