ГРАФОЧИСЛЕННЫЙ МЕТОД ВЕКТОРНОЙ ОПТИМИЗАЦИИ

 /два подхода реализации в системе “Вектор”/
Седых В.И., Болотов В.П.

 Методы расчетно-графического программирования, включающие традиционные методы оптимизации и средства графического анализа, позволяют представить решение многих задач геометрического моделирования по единой схеме:

1) формирование задачи с использованием аналогий из физики, механики или априорной информации о решаемой задаче;

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

3) решение и анализ ЦФ в графической системе "Вектор".

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

Так, например, задача "О почтовой посылке" (найти максимальный объем посылки при ограничениях на обхват и длину) формализуется как V=xyz и является трехмерной, решаемой в четырехмерном пространстве. Однако наложение ограничения x+2y+2z=C (плоскости, отсекающей по осям отрезки, равные C, C/2, C/2) дает возможность представить ее в параметрическом виде, и тогда ЦФ становится двумерной, для ее решения теперь достаточно трехмерного пространства.

Другой пример - задача Тартальи: найти максимум произведения двух чисел на их разность. ЦФ задачи определяется непосредственно из постановки задачи S=xy(x-y), задача является двумерной и уже на этом уровне вполне решаемой в системе "Вектор". Однако и в этом случае размерность можно понизить. Есть ограничение: два числа должны быть выбраны, например, от нуля до какого-то значения С, что позволяет записать ограничение уравнением прямой, отсекающей по осям x и y отрезки, равные С. Таким образом, задача Тартальи свелась к одномерной в той же постановке.

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

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

Формировать ЦФ можно двумя способами:

1) с помощью макрокоманд непосредственно в системе “Вектор”, используя один, два или более циклов в зависимости от размерности ЦФ, программируя при этом графики ЦФ, мах/min на них;

2) с помощью формирования массива ЦФ на языке Си и передачи его в систему “Вектор” по заранее определенному правилу. Анализ ЦФ (нахождение минимума/максимума ЦФ, построение различных проекций ЦФ, построение изолиний и т.д.) производится автоматически с помощью средств, предоставляемых системой.

Второй способ более профессионален: программирование осуществляется на языке высокого уровня (легче оперировать различными обозначениями переменных, организовывать циклы) и только для формирования массива точек. Недостаток его состоит в том, что такой подход требует для ПЭВМ транслятора с языка СИ и, соответственно, дополнительного объема оперативной и дисковой памяти, что на учебных ПЭВМ не всегда еше удается выполнить.

В учебном курсе “Основы инженерного творчества” за 1994-1996 гг. были апробированы оба подхода. Было выявлено, что первый подход - формирование ЦФ с помощью макрокоманд - требует опыта работы в системе “Вектор” на задачах общего плана, таких как геометрические построения, параметризация, организация рекурсивных циклов и т.д. И поэтому курсанты, прослушавшие курс “Основы вычислительной геометрии”, с такими задачами справлялись. В иных случаях, преподавателю приходилось макрокоманды на 80 % готовить заранее.

Если к системе графочисленной оптимизации “Вектор” подходить с позиций профессионального использования не только в учебном процессе, но и на практике, то надо безусловно применять и развивать второй подход. В плане такого развития требуется расширить возможность представления не только многомерных, но и больших массивов. Эти ограничения в системе “Вектор” сейчас можно обходить, сужая область ограничений, но для этого надо многократно переформировывать массив ЦФ, что не совсем удобно. Для решения проблемы массив точек надо не загружать в память системы (как это делается сейчас), а брать из файла, как это сделано в системе “Вектор” при моделировании поверхностей по линиям, заданным любым количеством двумерных точек формата .dxf.

Ниже показано решение задачи “О посылке обоими методами”. Причем, для первого метода массив ЦФ формируется без снижения размерности, для второго, учитывая, что решение лежит на плоскости р1-р3, размерность ЦФ уменьшена. Массив ЦФ, его максимум (помещается в s12), построение графика ЦФ (по отрезкам прямых) формируются с помощью МК на языке “Калькулятор” системы “Вектор”. При этом, чтобы графически зафиксировать положение МАХ, необходимо МК запускать два раза: при первом пуске зафиксировать (узнать) значение максимума ЦФ, при втором - по достижении этого значения выйти. Обрыв построения графика даст картину, в какой точке имеем максимум.
 
 Пример формирования массива задачи “О посылке” на языке СИ

#include   <math.h>
#include  "geotyps3.h"
#include  "point4.h"
    main()
{
    point4 mthkp[7][7] [7]  ;
    point3 mthkp2[21][21];
    float u,v,s,x,y,z,t;
    int k,i,j;
    int  nppry,npprx,npprt;
     point3             p1 = { 72.,0.,0.},
                        p2 = { 0., 36.,0.},
                        p3 = { 0.,0.,36.},
                        pc = {0.,0.,0.};
/* задача "О посылке": максимум объема - вариант на всем объеме ограничений */
     npprt=2;
     nppry=21;
     npprx=21;
     t=0.10;
for ( j=0,v=0; j < nppry; j++ ,v +=1./(nppry-1.)) {
     for ( k=0, u=0; k < npprx; k++, u +=1./(npprx-1)) {
            x=v*p1.x;
            y=(1.-v)*u*p2.y;
            z=(1.-v)*(1.-u)*p3.z;
            x=(1.-t)*x+t*pc.x;
            y=(1.-t)*y+t*pc.y;
            z=(1.-t)*z+t*pc.z;

           mthkp2 [j][k].x=x;
           mthkp2 [j][k].y=y;
           mthkp2 [j][k].z=x*y*z/100.;
          }
      }
vectorcg( "gips4", npprx, nppry, mthkp2);
return( 0 );
}

Пример организации циклов перебора точек, расчета максимума  и построения графика ЦФ
в задаче “О посылке” на языке “Калькулятор”

<dok0> МК задания исходных данных
: p1=72.,0.,0. p2=0.,36.,0.  p3=0.,0.,36.  p4=p3
tprin : p101=p1 p102=p3
tprin : p101=p2 p102=p4
$  print$on
 dok : s=0.   s12=0.  p105= x1, 0. s90=3429.22

<dok> МК перебора линий (прямых) в области ограничений
s > 1.001 ? exit
p91=(1.-s)*p1+s*p3
p92=(1.-s)*p2 +s*p4
tprin: p101=p91 p102=p92
dok1 : s1=0. p105=p91
n50<>3429215 ? exit   $ при вторм запуске МК
dok : s=s+0.1

<dok1> МК перебора точек на линий  в
области ограничений
s1 > 1.001 ? exit
p=(1.-s1)*p91+s1*p92
s11=x*y*z
tprin :  p101=p105  p102=x, y, s11/200.+z
s11 > s12 ?  s12=s11
n50=s12*1000.
: p125=p
n50<>3429215 ? exit   $ при вторм запуске МК
dok1 : s1=s1+0.1   p105=p102

<tprin> МК построения отрезка прямой
_Линии_общего_назначения
 _Отрезок_прямой____________________________
 _Начальная_точка___=_( x101    y101    z101
 _Кoнeчная_точка____=_( x102    y102    z102
 _Число_выводимых__точек_= 02
 _Визуализация__по_стандартным_проекциям_ n