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

Д.А. Силантьев,

препод. каф. ИГ, silantevda@gmail.com,

А.В. Толок,

д.т.н., зав. каф. ИГ,

МГТУ «Станкин», г. Москва

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

The majority of economic tasks is based on the optimization settings creating group of methods of mathematical optimization. These methods in combination with opportunities of the modern computer equipment allow to decide rather broad spectrum of application-oriented tasks. At the heart of the solution of each optimization task the problem of its correct setting expressed in the description of boundary conditions and the law of target dependence lies. In operation some principles of creation of optimization tasks on the basis of the R-functional simulation and their decision by a graded-index method using computer and graphic approach are considered.

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

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

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

Задачей R-функционального моделирования, в этом случае, является получение такого аналитического описания поверхности, форма которой имеет экстремальные точки в координатах решения поставленной оптимизационной задачи.

Таким образом, систему ограничений области решений можно рассматривать как множество предикатных функций w₁, w₂,…., w_n для некоторого пространства Rⁿ. Область допустимых решений w можно организовать как пересечение предикатных функций

(1)

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

(2)

При этом внутренняя область значений обнуляется, а внешняя область получает более выраженную область с отрицательными значениями. Окончательный вид функции F_w можно записать так:

(3)

Где F – целевая функция, w₀ – обнуленная область допустимых значений. Знак ± определяется поиском максимума или минимума функции F_w соответственно.

В ходе работы предлагается принципы построения и решения поставленной задачи оптимизации градиентным методом с использованием образов моделей (М-образов). М-образы [3] представляют собой изображение выбранной локальной дифференциальной характеристики поверхности геометрического объекта, представленного аналитической функцией. В работе [5] излагается градиентный метод, базирующийся на применении М-образов как информационной основы. Этот метод использует локальные геометрические характеристики, представленные М-образами для определения направления дальнейшего движения.

Рассмотрим простой пример задачи с тремя переменными и его решения на основе компьютерно-графического способа.

Зададим систему неравенств (4):

(4)

Требуется минимизировать целевую функцию (5):

(5)

На рисунке 1 представлена геометрическая модель, заданная системой неравенств (4).

а б

рис.1. а) геометрическая модель, б) визуальный результат решения примера компьютерно-графическим способом

Как видно из рисунка 1а, система линейных неравенств (4) образует выпуклый многогранник, задающий область допустимых значений (ОДЗ). Данная ОДЗ является, согласно теории R-функций, пересечением полупространств, на которые делится пространство каждой из указанных плоскостей.

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

Точность определения решения задачи этим способом зависит от точности представления воксельных М-образов, формирующих геометрическую модель. Такое уточнение требует временных затрат, но позволяет варьировать точностью решения задачи. Представленные на рисунке 2 результаты расчета были произведены на двухъядерном персональном компьютере с глубиной рекурсии – 8. Расчет длился порядка 30 минут.

рис. 2. Результат решения примера компьютерно-графическим способом

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

Мы неслучайно в первую очередь разбирали принципы решения задач математического программирования, в которых требуется найти экстремум целевой функции. Теперь, рассмотрим обратную задачу линейного и нелинейного программирования. Определим целевую функцию для решения некоторых математических задач. Данная задача рассматривалась в работе [6].

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

(6)

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

(7)

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

а б

рис. 3. а) геометрическая модель системы ограничения, б) организация решения системы (7) компьютерно-графическим способом

Такая прямая (8) получается путем нормирования коэффициентов и в системе линейных уравнений (7) и их сложения при соответствующих аргументах:

(8)

Пример решения системы 2-х линейных уравнений (9) с целевой функцией (10) показан на рисунке 4.

(9)

(10)

рис. 4. Организация решения системы (9) компьютерно-графическим способом.

Рассуждая таким же образом, зададим целевую функцию (11) для системы линейных уравнений (6), задающих три плоскости:

(11)

Пример решения системы 3-х линейных уравнений (12) с целевой функцией (13) показан на рисунке 5.

(12)

(13)

рис. 5. Организация решения системы (12) компьютерно-графическим способом

Следует отметить, что данный способ (8) и (11) для решения СЛАУ с двумя и тремя переменными интересен своей универсальностью. Для двумерного и многомерного случая целевая функция является своего рода локатором, указывающим направление для определения решения.

Ради интереса, рассмотрим принцип решения подобных задач на примере пересечения двух окружностей (14), показанных на рисунке 6а:

(14)

а б

рис. 6. а) геометрическая модель, б) организация решения системы (14) компьютерно-графическим способом

Принцип решения таких задач схож с рассматриваемым выше случаем. Целевой функцией в данном случае является окружность (рис.5б). Запишем систему (14) в другом виде (15):

(15)

где .

Дело в том, что окружности образуются путем вращения прямой вокруг центра по закону . Данные прямые, образующие эти окружности являются касательными к ним и одновременно перпендикулярны прямой, связывающей центр системы координат с центром окружности. Прямая , где – нормированные коэффициенты системы уравнений типа (15),определяет положение целевой функции. Таким образом, задается возрастание положительных значений ЦФ (16) в требуемом направлении и определяется решение в виде точек пересечения заданных окружностей.

(16)

Пример решения системы уравнений пересечения двух бесконечных цилиндров (17) с целевой функцией (18) показан на рисунке 6.

(17)

(18)

рис. 6. Изображение решения системы (17) компьютерно-графическим способом.

Рассмотрим пример постановки системы нелинейных уравнений двух переменных на примере пересечения парабол(19), показанных на рисунке 7а:

(19)

Целевой функцией в данном случае является окружность (рис.7б). Преобразуем систему (19) в другой вид (20):

(20)

и сложив уравнения этой системы, получим данную целевую функцию (21):

(21)

а б

рис. 7. а) геометрическая модель, б) организация решения системы (19) компьютерно-графическим способом

Если же мы обратимся при решении системы к целевой функции, полученной также как и (8), (11), (16), то мы получим тот же результат, что и при использовании целевой функции типа (21).

Помимо решений задач математического программирования можно также рассмотреть некоторые задачи стереометрического направления и свести их к оптимизационным. Рассмотрим компьютерно-графический способ решения задачи по определению криволинейной поверхности сечения тела цилиндра в трехмерном пространстве [7].

Имеется цилиндр , разрезанный поверхностью . Определить площадь полученной поверхности.

Применяя аппарат R-функций, представим поверхность усечённого цилиндра следующими выражениями:

(22); (23); (24)

Эта поверхность представляет собой функцию ограничений, на которой допускается существование результирующих точек. Задачей целевой функции является распределение результирующих точек на секущей поверхности предикатной функции . Чтобы обеспечить собрать результирующие точки в полученном сегменте достаточно задать целевую функцию:

(25)

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

а. б. в.

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

а) ; б) ; в) .

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

Чтобы требуемая поверхность была определена, необходимо найти максимум целевой функции (25) при ограничениях (22), (23), (24). Графическое выделение области показано на рисунке 9.

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

рис. 9. Визуализация решения геометрической рис.10. Пример отображения окружности вокселями на глубине

постановки задачи. рекурсии равной 5.

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

Заключение

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

Литература

1. Толок А.В. Графические образы-модели в информационных технологиях // Прикладная информатика, №4(22), 2009, М.: “МаркетcДС”, С.31-40.

2. Рвачёв В.Л. Теория R-функций и некоторые её приложения. К.: Наукова думка, 1982.-552 с.

3. Толок А.В. Синтез компьютерных образов геометрических характеристик для оценки рельефа поверхности функции двух переменных // Збірник доповідей НАН України. Математика, природознавство, технічні науки. 2004. №4. С.63-69.

4. Толок А.В., Морозов Д.Н., Мыльцев А.М. Когнитивность М-образов в системе РАНОК // Техническая эстетика и дизайн. Научно-технический сборник. 2008. № 5. С. 140-144.

5. Толок А.В., Мыльцев А.М., Корогод В.Л. Алгоритм пространственного движения по градиенту на основе М-образов // Прикладная геометрия и инженерная графика. К: КНУСА. 2007. – Вып. 77., С. 85-90.

6. Григорьев С.Н., Толок А.В., Силантьев Д.А., Лоторевич Е.А., Пушкарёв С.А. Вопросы развития графических способов решения математических задач на компьютерной основе // Материалы 40-й междунар. конф. «Информационные технологии в науке, образовании, телекоммуникации и бизнесе (IT+S&E*12)». — Приложение к журналу Открытое образование. —С.66-71.

7. Григорьев С.Н., Толок А.В., Силантьев Д.А., Лоторевич Е.А., Пушкарёв С.А. Визуализация математического моделирования при определении рабочих поверхностей деталей // Технология машиностроения, 2013, №2—С.57-60.