Все выпуски

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

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

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

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

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

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

Эффективность производственного процесса непосредственно зависит от качества управления технологией, которая, в свою очередь, опирается на точность и оперативность обработки контрольно- измерительной информации. Разработка математических методов исследования системных связей и закономерностей функционирования и построение математических моделей с учетом структурных особенностей объекта исследований, а также написание программных продуктов для реализации данных методов являются актуальными задачами. Практика показала, что список параметров, имеющих место при исследовании сложного объекта современного производства, варьируется от нескольких десятков до нескольких сот наименований, причем степень воздействия каждого из факторов в начальный момент не ясна. Приступать к работе по непосредственному определению модели в этих условиях нельзя — объем требуемой информации может оказаться слишком велик, причем бóльшая часть работы по сбору этой информации будет проделана впустую из-за того, что степень влияния на параметры оптимизации большинства факторов из первоначального списка окажется пренебрежимо малой. Поэтому необходимым этапом при определении модели сложного объекта является работа по сокращению размерности факторного пространства. Большинство промышленных производств являются групповыми иерархическими процессами массового и крупносерийного производства, характеризующимися сотнями факторов. (Для примера реализации математических методов и апробации построенных моделей в основу были взяты данные Молдавского металлургического завода.) С целью исследования системных связей и закономерностей функционирования таких сложных объектов обычно выбираются несколько информативных параметров и осуществляется их выборочный контроль. В данной статье описывается последовательность приведения исходных показателей технологического процесса выплавки стали к виду, пригодному для построения математической модели с целью прогнозирования, внедрения новых видов стали и создание основы для разработки системы автоматизированного управления качеством продукции. В процессе преобразования выделяются следующие этапы: сбор и анализ исходных данных, построение таблицы слабокоррелированных параметров, сокращение факторного пространства с помощью корреляционных плеяд и метода весовых коэффициентов. Полученные результаты позволяют оптимизировать процесс построения модели многофакторного процесса.