Все выпуски

Рассматривается прямой алгоритм решения задачи линейного программирования (ЛП), заданной в каноническом виде. Алгоритм состоит из двух последовательных этапов, на которых прямым методом решаются приведенные ниже задачи ЛП: невырожденная вспомогательная задача (на первом этапе) и некоторая задача, равносильная исходной (на втором). В основе построения вспомогательной задачи лежит мультипликативный вариант метода исключения Гаусса, в самой структуре которого заложены возможности: идентификации несовместности и линейной зависимости ограничений; идентификации переменных, оптимальные значения которых заведомо равны нулю; фактического исключения прямых переменных и сокращения размерности пространства, в котором определено решение исходной задачи. В процессе фактического исключения переменных алгоритм генерирует последовательность мультипликаторов, главные строки которых формируют матрицу ограничений вспомогательной задачи, причем возможность минимизация заполнения главных строк мультипликаторов заложена в самой структуре прямых методов. При этом отсутствует необходимость передачи информации (базис, план и оптимальное значение целевой функции) на второй этап алгоритма и применения одного из способов устранения зацикливания для гарантии конечной сходимости.

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

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

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

Схема моделирования состоит в следующем. Из заданного временного ряда отбираются фрагменты, отвечающие определенным состояниям, например трендам с заданными углами наклона и дисперсиями. Из этих фрагментов составляются эталонные распределения состояний. Затем определяются эмпирические распределения длительностей пребывания системы в указанных состояниях и длительности времени перехода из состояния в состояние. В соответствии с этими эмпирическими распределениями строится вероятностная модель разладки и моделируются соответствующие траектории временного ряда.