Решение 3D-задач математического программирования на основе воксельных М-образов в системе РАНОК

А.В. Толок,

в.н.с., д.т.н., проф.,

ИПУ РАН, atol@ipu.rssi.ru , г. Москва

Область применения графических образов-моделей (М-образов) выходит далеко за рамки построения реалистичного изображения аналитически заданной функции [1]. Примером тому являются наработки в области решения оптимизационных задач градиентным методом с применением воксельных М-образов [2-4]. Работа в этом направлении показала целесообразность развития такого подхода как одного из способов переноса на компьютерную платформу графического метода решения задач по оптимизации. В данной работе предлагается рассмотреть технологию решения трёхмерных задач математического программирования (МП) в системе РАНОК на примере линейной задачи, рассмотренной в [5]. Алгоритм решения взятого примера является параллельным аналогом «симплекс-метода». Он послужит тестом не только показателей результата, но и технологической сложности процесса решения подобных задач.

Рассмотрим постановку задачи линейного программирования

при ограничениях

(1)

и при условии .

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

рис.1. Многогранник допустимых решений

(2)

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

, (3)

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

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

Полученный результат является точкой , где .

Рассмотрим технологию решения такой задачи в системе РАНОК. Эта система не применяет ни численных, ни аналитических вычислений, используя в основе описания модели математический аппарат -функций [1] и градиентный алгоритм с использованием воксельных М-образов исследуемой модели. Аналитическая модель используется лишь на этапе определения значения .

Описание линейной модели (1) происходит в отдельных окнах системы как показано на рисунке 2.

рис.2. Пример описания задачи линейного программирования в системе РАНОК

рис.3. Этап работы задачи градиентного метода в системе РАНОК

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

Градиентный метод в системе РАНОК работает на воксельных графических М-образах и позволяет задавать, как одиночную траекторию градиента, так и заданное множество траекторий. В данном случае градиентное движение к максимальному значению осуществляется из каждой точки созданной воксельной графической модели функции для определения всех возможных экстремальных точек. В результате определяется массив точек остановки градиентного движения и выбирается точка с максимальным значением . На этом этапе выдаётся информация в табличном виде, результат представляется в первой строке, отсортированной по возрастанию значения (рис.4).

рис.4. Результат решения примера в системе РАНОК при малом уточнении модели

Если сравнивать результат на сходимость, то следует учесть специфику построения графических М-образов исследуемой модели. При этом применяется рекурсивный алгоритм уточнения области определения исследуемой модели, требующий временных затрат, но позволяющий варьировать точностью исследования. При конструировании системы РАНОК изначально предполагалось избегать технических ограничений, часто влияющих на идеологию построения современных систем. Система РАНОК сразу идеологически ориентируется на «идеальную компьютерную комплектацию». Представленные результаты расчёта были произведены на двухядерном персональном компьютере с глубиной рекурсии - 8. Расчёт длился порядка 6-ти часов. Очевидно, что при такой постановке уточнение значения результата даёт увеличение времени расчета для каждого уровня погружения рекурсии примерно в восемь раз. Несмотря на это можно говорить о пользе применения таких систем. Во-первых, снижается вероятность ошибки, присущая ручным расчётам. Во-вторых, не всегда требуется числовая точность решения, поскольку сама оптимизационная постановка, как правило, приближённая. В третьих применение кластерных технологий позволяет снять временные и технические проблемы, позволяя уточнять результат не меняя технологии решения.

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

рис.5. Визуализация решения примера в системе РАНОК

Следует отметить, что работа с воксельными образами требует временных затрат и часто, на доступной компьютерной технике, выражается десятком часов расчёта. Но это время связано не столько со сложностью исследуемой модели, сколько с физическим уровнем обработки информации. Это позволяет без потерь наращивать условия в постановке задач до бесконечности и усложнять порядок описания целевой функции. В отличие от человека, система РАНОК способна решать такие задачи. В этом преимущество данного подхода.

Литература

1. Максименко-Шейко К. В., Мацевитый А. М., Толок А. В., Шейко Т. И. R-функции и обратная задача аналитической геометрии в трехмерном пространстве // Ежемесячный теоретический и прикладной научно-технический журнал(с приложением), ISSN 1684-6400.– М.: «Новые технологии», 2007, Вып.10. – С.23-32

2. Толок А.В. Автоматизированная система аналитического проектирования в моделировании сложных экономических процессов // КОГНИТИВНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ РАЗВИТИЕМ СИТУАЦИЙ (CASC’2007) / Труды VIIМеждународной конференции / Под. ред. З.К. Авдеевой, С.В. Ковриги. – М.: Институт проблем управления РАН, 2007. – С. 173-176.

3. Плоский В.О., Толок О.В., Бондар О.А. Візуально-геометричне дослідження систем засобами ПК "РАНОК" // Прац  ТДАУ / Вип. 4, Т.40. Прикладна геометрія, 2008р., М.: ТДАУ, с.10-16

4. Плоский В.А., Толок А.В., Бондарь Е.А. / Исследование метода аппроксимации преобразований средствами системы "РАНОК" // Геометричне та компютерне модлювання, Вип. 21, / Харків, 2008, с.30-37

5. Барский А.Б. Параллельные информационные технологии: Учебное пособие / А.Б. Барский. - М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 503 с.: ил.