Лекция 3. Методы графоаналитической оптимизации при решении инженерных задач

Следует поставить перед собой цель изыскать способ
решений всех задач ...одним и притом простым способом
Даламбер
С О Д Е Р Ж А Н И Е

Введение

1. Формализация задач оптимизации.

2. Реализация задач оптимизации на языке "Калькулятор".

Пример 1. Определить наикратчайшее расстояние от точки р3 до прямой р1-р2.
Пример 2. Из заданного набора вещественных чисел: 80.0, 40.0, 60.0, определить наименьшее число и построить график ЦФ.
Пример 3. Из множества  чисел определить наименьшее. Организовать цикл.
Пример 4. Из множества  чисел определить наименьшее и построить график зависимости величины числа от его номера.
3. Примеры формализации задач.
3.1. Общие задачи
Пример 5. Задача Герона. Определить на прямой p11-p12 такую точку p, чтобы сумма расстояний от нее до двух данных p1 и  p2 была минимальной.
Пример 6. Определить наикратчайшее расстояние между двумя отрезками прямых.
Пример 7. О геодезической линии. Задача 1. Определить наикратчайшее расстояние от точки на  стене комнаты до точки на потолке.
Пример 8. О геодезической линии. Задача 2. На поверхности определить наикратчайшее расстояние  от одной точки до другой.
Пример 9. Определить на плоскости xy такую точку p, чтобы сумма расстояний от нее до трех данных p1, p2 и p3 точек была минимальной.
Пример 10. Задача о прожекторе. Найти такую форму зеркала, чтобы все лучи идущие от источника, отражались по направлению оси x.
3.2. Задачи на принадлежность
3.3. Задачи на пересечение
Примеры 11-14.
Пример 15. Пересечение прямой и плоскости
Пример 15d. Пересечение 2-х плоскостей в 4-мерном пространстве.
3.4. Метрические задачи
3.5. Задачи на компромисс (требование на равенство)
5. Проектирование новых форм с помощью задач оптимизации
Пример 21. Задать объект ЦФ вида: F(x,y)=|p-pc|-R

В в е д е н и е

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

Найти простой алгоритм решения той или иной задачи остается актуальной проблемой.
В этом плане привлекательными являются  численные методы. Множество задач решается из условия на максимум/минимум.  Решения таких задач искали: Евклид, Архимед, Аполлоний, Герон, Тарталья, Торричелли, Иоган и Якоб Бернулли, Ньютон, Ферма, Эйлер и многие другие. Нахождение решений стимулировало создание таких теорий как дифференциальное и вариационное исчисление, оптимальное управление, которые сложны к применению их на практике. Стоит необходимость разработки простых алгоритмов, не требующих глубоких математических знаний. В основу решения оптимизационных задач можно положить простую идею: для наилучшего решения надо перебрать все возможные решения, сравнить их между собой и выбрать из них наилучшее.

При такой реализации главной является формализация (алгоритмизация) на языке ЭВМ понятий: что перебрать, как перебрать и как выбрать. Чаще всего перебираются одномерные или многомерные величины (вектора, массивы), связанные между собой известными законами физики или экономики.

1. Формализация задач оптимизации.

При решении численных задач в графической интерпретации важно выделить пять этапов:
1) формирование цели (ЦФ),
2) структуризация области существования ЦФ,
3) вычисление и определение мах/min ЦФ,
4) построение графика ЦФ.
5) графочисленный анализ задачи и получение результата.

1. ЦФ - это число (или совокупность чисел), выражающее: расстояние, время и другие величины в зависимости от каких-либо переменных величин, например, координат местоположения, трудозатрат, расхода топлива и т.п., и представляют вектор, у которого координаты - переменные величины.
Примеры формирования ЦФ:
 - найти минимальное расстояние s от точки р3 до прямой р1-р2
  s=|p-p2|->min,
 - найти минимальное расстояние s от точки р4 до плоскости p1-p3
  s=|p-p2|-> min,
 - найти минимальный пройденный путь из суммы возможных.
  s=|p1-p|+|p2-p1|+......|pn-pn-1| -> min  и т.д.

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

3. Расчет max/min ЦФ выполняют c помощью циклов, в которых при изменении какого-либо параметра вычисляется новое значение ЦФ, сравнивается с предыдущим и, если оно меньше, заносится в соответствующий регистр. Например, на языке “Калькулятор” это выглядит так: s < s99 ? s99=s, т.е. если s меньше s99, то s присваивается (заносится) в регистр s99. Сначала s99 задается заведомо большим числом в случае поиска минимума и заведомо меньшее в случае поиска максимума.

4. График ЦФ обычно строится в том же цикле, где определяется min/max ЦФ. Ординатами одномерной ЦФ будут ее значения, а абсциссой - координата х местоположения точки на прямой или ее безразмерный параметр s.

5. Графочисленный анализ задачи и получение результата подразумевает дополнительные исследования - типа получения точки при минимуме ЦФ и т.д.
 

2. Реализация задач оптимизации на языке "Калькулятор"

Пример 1. Определить наикратчайшее (или наперед заданное) расстояние от точки р3 до прямой р1-р2.
Требуется найти на прямой р1 - p2 такую точку p, которая бы обеспечивала  минимальное расстояние от р3 до прямой р1-р2.
Формально можно написать:
s=|p1-p| -> min.                    (1)
Запись (1) и будет целью (ЦФ).
В (1) неизвестной переменной является точка р, которую можно вычислять по формуле:
p=(1.-s)*p1+s*p2                 (2)
Однако и здесь точка вычисляется неоднозначно, а в диапазоне изменяющегося параметра s
0. < s < 1,
что нам и подходит, т.к. мы собираемся вычислять всевозможные варианты отрезков от точки р3 до прямой р1-р2 и из них уже выбрать минимальной длины.
Что же будет областью ограничений?
Во-первых, диапазон всевозможных положений точки р:
р1 < p < p2,
или покомпонентно:
x1 < x < x2,
y1 < y < y2,
во-вторых диапазон параметра s
0. < s < 1.
График ЦФ можно строить, как в зависимости от положения точки (ее координат по x или y), так и от безразмерного параметра s.
 
Выделим следующие моменты:

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

2) Вычисления точек на области ограничений, ЦФ, сравнения ее с эталоном и выбора наименьшего значения ее.

3) Построения графика ЦФ.

4) Определения положения искомой точки р, в которой ЦФ имеет минимум.

Итак в рассматриваемом примере:
1) Формируем МК tpim0.mac, в которой задаем точки: р1, р2, р3, строим отрезок р1-р2 , а также задаем эталон s99 для сравнения (уже в МК tprim.mac) первой вычисляемой длины.

tprim0.mac -           МК задания исходных данных
print$on                                   $ включить печать в протокол mgd.log
: p1=20.,10. p2=130.,50.  p3= 60.,80.  $ задание точек списком
otrezok: p101=p1 p102=p2     $ построение отрезка р1-р2
tprim : s=0.  s99=100.             $ обращение к циклу и задание s99
 

prim.mac - МК вычисления минимума и построения графика ЦФ.
s > 1. ? exit    $ условие выхода из МК
p=(1.-s)*p1+s*p2                           $ вычисление точки
okr: p100=p s100=2.5                    $ изображение точек р
otrezok : p101=p  p102=p3            $ построение отрезков р3-р
s11=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y))  $ вычисление длин перебираемых отрезков
s11 < s99 ?  s99=s11                      $ сравнения и выбор min будет равно 52 мм
otrezok : p101=p103  p102=x, s11 $ построение графика ЦФ
р103=р102                                      $ конец идет в начало следующего отрезка
n50= s99*1000.                               $ искусственно s99 переводим в целое
$ n50 <>  52000 ? exit                     $ при достижении минимума, выход
tprim : s=s+0.05                              $ обращение на себя с увеличением s
 

МК  tprim.mac, образуя рекурсивный цикл, выполняет следующие действия:
1) вычисление и перебор точек на прямой,
2) изображение перебираемых точек,
3) изображение отрезков от перебираемых точек р до р3,
3) вычисление длин перебираемых отрезков (в s11),
4) сравнение длин перебираемых отрезков и выбор из них наименьшей длины,
5) построение графика ЦФ
6)  определения положения искомой точки р, в которой ЦФ имеет минимум.

Пункт 6 достигается двумя путями:

1) вначале определяется минимум (при первом запуске МК), а затем ставится условие (при достижении минимума выйти), что в текущем регистре p и будут лежать искомые координаты точки,

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

Рассмотрим перечисленные пункты в МК:

1) организация цикла:

test1.mac - имя МК
s > 1. ? exit             $ условие выхода из МК
tprim : s=s+0.1      $ обращение на себя с увеличением s

МК test1.mac организует рекурсию - вызов самой себя. Первая строка в ней - условия выхода, вторая - обращение к себе самой, причем s увеличивается на шаг 0.05. МК проработает десять раз и закончит свою работу. Никаких вычислений и построений в ней не будет происходить.

2) вычисление точек р на прямой, изображение их окружностями и соединение их отрезками с р3:

tprim.mac - МК вычисления минимума и построения графика ЦФ.
s > 1. ? exit                                     $ условие выхода из МК
p=(1.-s)*p1+s*p2                           $ вычисление точки
okr: p100=p s100=2.5                    $ изображение точек р
otrezok : p101=p  p102=p3            $ построение отрезков р3-р
tprim : s=s+0.05                             $ обращение на себя с увеличением s

3) вычисление точек на прямой и вычисление расстояний от точки р до р3:

tprim.mac - МК вычисления минимума и построения графика ЦФ.
s > 1. ? exit    $ условие выхода из МК
p=(1.-s)*p1+s*p2                           $ вычисление точки
s11=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y))  $ вычисление длин перебираемых отрезков
tprim : s=s+0.05                              $ обращение на себя с увеличением s

4) сравнение вычисляемых расстояний и выбор из них минимальное.
Выполняется одной командной строкой:
s11 < s99 ?  s99=s11                      $ сравнить и выбрать,
которая читается так: если число в регистре s11 меньше чем в регистре s99, то в регистр s99 кладем это число. Вспомните, если горошина в левой руке (s11) меньше, чем в правой (s99), то ее взять в правую.

5) построение графика ЦФ выполняется отрезками прямых, причем предыдущая текущая точка, вычисленная на предыдущем шаге рекурсия  - начало отрезка, текущая точка р - конец отрезка.
Что значит текущая точка графика ЦФ?
Во-первых, ЦФ функция задается  ординатой - той величиной, которую мы ищем (перебираем). В данном случае - это длины отрезков от р3 до р, вычисляемые в s11, которые и будет ординатой ЦФ. Во-вторых, абсциссой - независимой переменной в зависимости от чего мы строим график ЦФ. Этим параметром может быть любая координата текущей точки р:  x или y, или независимый параметр s. Для наглядности - чтобы график ЦФ строить над прямой р1-р2 в качестве абсциссы выбираем переменную х. Таким образом, текущая точка (конец отрезка ЦФ) будет: р102=х, s11.
Текущая точка в следующем шаге должна быть началом отрезка в графике ЦФ, поэтому текущую точку (после того как она выполнила свою задачу), переприсваеваем в какую-то третью (нейтральную) точку, чтобы из нее потом на следующем шаге взять координаты и положить в начало отрезка. Все вышесказанное записывается двум строками:

otrezok : p101=p103  p102=x, s11               $ построение графика ЦФ
р103=р102                                                      $ конец идет в начало следующего отрезка

6) И наконец, еще две строчки - для определения точки р* в какой достигнут минимум:

n50= s99*1000.                               $ искусственно s99 переводим в целое
$ n50 <>  52000 ? exit                     $ при достижении минимума, выход,

При рекурсивном цикле приходится сначала вычислять минимальное расстояние (в s99), а потом переводить это число в целое и ставить условие: при достижении этого числа из МК выйти. И только в этом случае, мы можем  зафиксировать искомую точку р*. График ЦФ в этом случае оборвется на минимуме, что будет также хорошим контролем, что все правильно сделано. Почему вещественное число переводим в целое? Все дело в округлениях - на печать машина выдает вещественные значения с округлениями, а в памяти машины - нет, вот и получается, что сравнения в следующем сеансе запуска МК происходят уже не с теми числами.
 
 
 

Однако есть второй вариант организации расчета - 2-х цикловый, и такой проблемы уже нет. Здесь в первом цикле считаем только минимум, после чего запоминаем его в нейтральном регистре, например:  s190=s99, и далее во втором цикле, выполняя те же вычисления и сравнения, ставим уcловие: s11 <> s190 ? exit. Все происходит за один запуск МК. Вот текст МК такой организации:

tprim0.mac МК задания исходных данных
print$on                               $ включить печать в протокол mgd.log
: p1=20.,10. p2=130.,50.  p3= 60.,80.
s90=$sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)) $ - ордината для первой точки графика ЦФ
otrezok: p101=p1 p102=p2 $ построение отрезка р1-р2
okr: p100=p3 s100=4.0       $ точка р3
s99=1000.                            $ эталон
tprim: s=0. p105=x1,s90      $ обращение к первому циклу и вычисление  s99
s190=s99                              $ запоминаем s99  в s190
s99=10000.                          $ опять задаем эталон
tprim2: s=0. p105=x1,s90    $ обращение ко второму циклу и вычисление искомой точки р

tprim.mac - МК вычисления минимума и построения графика ЦФ.
s > 1. ? exit    $ условие выхода из МК
p=(1.-s)*p1+s*p2                           $ вычисление точки
okr: p100=p s100=2.5                    $ изображение точек р
otrezok : p101=p  p102=p3            $ построение отрезков р3-р
s11=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y))  $ вычисление длин перебираемых отрезков
s11 < s99 ?  s99=s11                      $ сравнения и выбор min будет равно 52 мм
tprim : s=s+0.05                              $ обращение на себя с увеличением s
 

tprim2.mac - МК построения графика ЦФ и определения текущей (искомой точки).
s > 1. ? exit                                      $ условие выхода из МК
p=(1.-s)*p1+s*p2                            $ вычисление точки
s11=$sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y))  $ вычисление длин перебираемых отрезков
otrezok : p101=p103  p102=x, s11  $ построение графика ЦФ
р103=р102                                      $ конец идет в начало следующего отрезка
s11 <> s190 ? exit    $ условие выхода из МК при достижении min, вычисленного в tprim.mac
tprim2 : s=s+0.05                            $ обращение на себя с увеличением s

Таким образом, все вычисления можно выполнять в одном цикле, но в этом случае добавляется одна новая МК: сначала вычисляется  минимум расстояния, а затем во второй (запускается с той же головной МК tprim0.mac), происходят те же вычисления, но добавляется построение графика ЦФ и условия выхода при достижении минимума, полученного в предыдущей МК, выйти. График ЦФ получиться оборванный в точке минимума. Если необходимо получить полный график, условие выхода надо закомментировать и запустить МК снова.

Даны два варианта решения задачи. Какой лучше? На вкус. Мы же, в целях экономии места, будем чаще использовать первый вариант.


В плане лучшего понимания проблем оптимизации рассмотрим более простой пример.
 
 Пример 2. Из заданного набора вещественных чисел: 80.0, 40.0, 60.0, определить наименьшее число и построить график зависимости величины числа от его номера.
: s1=80. s2=40. s3= 60.  s99=200.
Алгоритм решения основан на переборе, сравнении и выборе.
Сначала эталон (s99) задаем заведомо большим (s99=200.) числом из заданных.
Далее берем s1 и сравниваем с s99. Если число в s1 меньше числа в s99, то число из s1 помещаем в регистр s99 (переприсваиваем).
Потом берем второе число в s2, также сравниваем с новым числом в s99, и, если оно меньше, меняем его на меньшее (в противном случае присвоение не выполняется) и так до тех пор, пока не переберем все числа.
В итоге окажется, что наименьшее число находится в регистре s99.

Выполним вышесказанное на языке "Калькулятор".

s1 < s99 ? s99=s1
s2 < s99 ? s99=s2
s3 < s99 ? s3=s3
$  в итоге s99 будет наименьшее число 40.

Строим график зависимости значения числа от его номера.
Для наглядности номера чисел (значения абсцисс по оси х графика ЦФ) берем в масштабе 20:1
Вот как будут выглядеть командные строки:
otrezok: p101=1.0*20.0, s1  p102=2.0*20.0,s2
otrezok: p101=2.0*20.0, s2  p102=3.0*20.0,s3
 

Пример 3. Из заданного набора двадцати вещественных чисел определить наименьшее число.

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

hisd.mac - имя МК
: s1=70. s2=50. s3= 80. s4=60. s5=10.  s6=20. s7=5.  s8=70. s9=90.
: s10=35.  s11=15.  s12=76. s13=54. s14=76. s15=125. s16=165.
: s17=66. s18=105. s19=39. s20=84.
hisc :  s99=200. n=1  $ вызов второй МК hisc.mac

hisc.mac  - имя МК  цикла
n > 20 ? exit                 $   условие выхода
sn < s99 ?  s99=sn       $   сравнить и выбрать меньшее ( в s99)
hisc : n=n+1                 $   рекурсия - вызов МК самой себя

Результат (наименьшее число) будет в s99.


Пример 4.   Из того же набора  чисел (пример 3) определить наименьшее и построить график зависимости величины числа от его номера, найти номер числа.

В качестве переменной величины (вдоль оси х) выберем номера чисел (от 1 до 20). Аргументами (по оси y) будут значения чисел s1-s20. В качестве первоначальной точки выберем точку с координатами по х, например, по х ( х103=0.), по y (y103=s99).

hisrisd.mac   - имя МК задания данных - все также как в hisd.mac, за исключением, задается еще первоначальная точка р103 для графика ЦФ, минимального числа в нейтральном регистре s190 и обращение ко второму циклу - фиксации номера искомого числа.
: s1=70. s2=50. s3= 80. s4=60. s5=10.  s6=20. s7=5.  s8=70. s9=90.
: s10=35.  s11=15.  s12=76. s13=54. s14=76. s15=125. s16=165.
: s17=66. s18=105. s19=39. s20=84.
hisrisc :  s99=200. n=1
s190=s99
hisrisc :  s99=200. n=1   p103=0.0,s99
 

hisrisc.mac   - имя МК  1-цикла
n > 20 ? exit                     $   условие выхода
sn < s99 ?  s99=sn            $   сравнить и выбрать меньшее ( в s99)
hisrisc : n=n+1                 $   рекурсия - вызов МК самой себя

hisrisc2.mac - имя МК  1-цикла
n > 20 ? exit                      $   условие выхода
tprin : p101= p103  x102=n*10 y102=sn   $ построения отрезка прямой у которого вторая точка - точка ЦФ
p103=p102                       $ переприсвоение конца отрезка в начало будущего
sn <> s190 ? exit              $ условие выхода при достижении минимального числа
hisrisc2 : n=n+1               $ рекурсия
 
 
Рис. График (для наглядности масштаб по х увеличен в 10) зависимости значений чисел от их номера. Число под номером 7 является наименьшим.


3. Примеры формализации задач

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

3.1. Общие задачи

Пример 5. Задача Герона. Определить на прямой p11-p12 такую точку p, чтобы сумма расстояний от нее до двух данных p1 и  p2 точек была минимальной.
Формализация.
Целевая функция:
s10 = |p1-p|+|p2-p|  -> min,
где
p =(1-s)*p11+s*p12
при ограничениях
0 < s < 1


Пример 6. Определить наикратчайшее расстояние между двумя отрезками прямых (в частном случае - точку пересечения двух отрезков прямых), у которых начала и концы имеют одинаковые координаты по х.
Формализация.
Целевая функция;
yj-yi -> min,
где
yi=y1+(y2-y1)*(x2-x)/(x2-x1)
yj=y3+(y4-y3)*(x4-x)/(x4-x3)
при ограничениях
x1 < x < x2


Пример 7. О геодезической линии. Задача 1. Определить наикратчайшее расстояние s10 от заданной точки p1 на одной из вертикальных стен комнаты до точки p2  на потолке, прокладывая путь только по плоскостям стен и потолка.
Целевая функция
s10=|p1-p|+|p-p2| -> min,
где
pi=(1-s)*p11+s*p12
при ограничениях
0 < s < 1


Пример 8. О геодезической линии. Задача 2. На поверхности определить наикратчайшее расстояние s10 от точки p1  до точки p2.
Целевая функция
s10=|p1-p|+|p-p2| -> min,
где
pi= - формула линии на поверхности, в нашем примере это прямая
pi=(1.-s)*p21+s*p22
при ограничениях
0 < s < 1


Пример 9. Определить на плоскости xy такую точку p, чтобы сумма расстояний от нее до трех данных p1, p2 и p3 точек была минимальной.
Формализация.
Целевая функция:
s1+s2+s3 = |p1-p|+|p2-p|+|p3-p| -> min
где
p=(1-u)*p13+u*p23
p13=(1-v)*p1+v*p3
p23=(1-v)*p2+v*p3
при ограничениях
0 < u,v < 1


Пример 10. Задача о прожекторе. Найти такую форму зеркала, чтобы все лучи, идущие от источника (рис.), отражались по направлению оси x.

Формализация.
В каждой точке кривой зеркала при отражении выполняется условие:

Чтобы решить данное уравнение необходимо  выполнение тождества:

Целевая функция:

Ограничения:
угол альфа меняется от нуля до 2 пи.


3.2. Задачи на принадлежность

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

К таким задачам относятся задачи на принадлежность точки прямой, плоскости, поверхности, телу, гиперповерхности. Теорема 1. Геометрический образ меньшей размерности принадлежит геометрическому образу большей размерности в том случае, если ЦФ расстояния первого образа до второго в своем пределе стремится к нулю.

Пример 11. Точка p принадлежит прямой p1-p2 в том случае, если минимум ЦФ расстояния от точки p до прямой равен нулю
s = |p - p| ->  min ->  0 ,
где
p=(1-u)*p1+u*p2 .

Пример 12. Точка р4 принадлежит плоскости р1-р2-р3, если минимум ЦФ расстояния от точки до плоскости равен нулю:
s = |p4- p| -> min -> 0 ,
где
где
p=(1-u)*p13+u*p23
p13=(1-v)*p1+v*p3
p23=(1-v)*p2+v*p4

Пример 13.Точка принадлежит поверхности, заданной через  линии контура, например по Кунсу, если минимум ЦФ расстояния от точки до поверхности равен нулю:
s=|p1 - pi| -> min -> 0 ,
где
pi = (1-u)*pv0+u*pv1+(1-v)*pu0+v*pu1-
       (1-v)*(1-u)*p00+u*p01)+v*((1-u)*p10+u*p11)  (1).
В системе "Вектор" точки на поверхности в зависимости от u, v определяются автоматически и разбираться в формуле  (1) не обязательно.

Также можно рассмотреть принадлежность прямой плоскости, кривой поверхности и т.п.


3.3. Задачи на пересечение

К таким задачам относятся задачи на пересечение двух прямых, пересечение прямой и плоскости, пересечение кривой линии и плоскости, пересечение кривой линии и поверхности, пересечение двух плоскостей, пересечение плоскости и поверхности, пересечение двух поверхностей, тел и гиперповерхностей и т.д.

Теорема 2. Геометрический образ имеет область (точку, прямую, кривую, плоскость) пересечения с другим образом, если ЦФ расстояний первого образа до второго имеет значение, равное нулю.



Пример 14. Пересечение двух прямых:
s = |pi - pj| -> min ->  0 ,      (25)
где
pi = (1-u)*p1 + u*p2,
pj = (1-v)*p3 + v*p4.
0 < u,v < 1
Аналогично решаются задачи на пересечение двух кривых линий и на пересечение прямой линии с кривой линией.

Пример 15. Пересечение прямой и плоскости:
|pi - pj| -> min ->  0 ,        (26)
где
pi = (1-v)*((1-u)*p1 + u*p2) + v*p3,
pj = (1-t)*p10 + t*p11.
Здесь задача 3-х параметрическая - зависит от трех параметров u,v,t, и чтоб изобразить ЦФ необходимо 4-х мерное пространство (модель)
Решение задачи на языке "Калькулятор". Надо организовать три вложенных (обращение из внутри одного к другому) рекурсивных цикла, определить минимум расстояния, зафиксировать его и затем определить искомую точку. В начертательной геометрии данная задача является одной из основных, поэтому решим ее. Вот текст МК и изображение ЦФ.

date.mac
: p1=100.,0.,0. p2=0.,100.,0.  p3=0.,0.,100.
: p4 = 50.,50.,50. p5= 25., 25., 25.
otrezok: p101=p1 p102=p2
tperpr: s=0. s99=500. p9=x1,y1,s99

tperpr.mac
s3 > 1. ? exit
p45=(1.-s3)*p5+s3*p4
okr: p100=p45 s100=3.0
tper1: s=0.
n50 <> 216 ? exit
tperpr: s3=s3+0.05

tper1.mac
s > 1. ? exit
p91=(1.-s)*p1 + s*p3
p92=(1.-s)*p2 + s*p3
$ otrezok: p101=p91 p102=p92
tper2: s1=0.
n50 <> 216 ? exit
tper1: s=s+0.05

tper2.mac
s1 > 1. ? exit
p=(1.-s1)*p91+s1*p92
s11=$sqrt((x45-x)*(x45-x)+(y45-y)*(y45-y)+(z45-z)*(z45-z))
s11 < s99 ? s99=s11
otrezok: p101=p9 p102=x+150.,s11
p9=p102
n50=s99*100.
n50 <> 216 ? exit
tper2 : s1=s1+0.05

Рис. График ЦФ и искомой точки 

Искомая точка получилась с погрешностями, однако, если уменьшить шаги перебора на прямой и плоскости, сузить длину отрезка, и наконец, уменьшить область треугольника, то точность можно значительно повысить.
Аналогично решаются задачи на пересечение кривой линии с плоскостью. Кто-то скажет, зачем городить огород, если в начертательной геометрии есть приемы решения данной задачи, да и аналитические не сложны. Здесь да, а вот как решите задачу на пересечение двух плоскостей в четырехмерном пространстве (кстати, в общем случае пересекаются в точке) методами начертательной геометрии или аналитической? Сложно! А вот предложенным способом уже можно - добавить еще один цикл  к предыдущей задаче, и точки взять 4-мерные). Решим эту задачу.



Пример 15d. Пересечение 2-х плоскостей в 4-мерном пространстве.
В общем случае пересечением будет точка.  Формализуем задачу.
pi-pj -> min -> 0
где pi, pj - 4-мерные вектора определяются
pi= (1-u)*p81+ u*p82,
где:
p81=(1-v)*p1+v*p3
p82=(1-v)*p2+v*p4
0 < u,v < 1
и
pj=(1-s)*p91+s*p92
где:
p91=(1-s1)*p1+s1*p3
p92=(1-s1)*p2+s1*p4
0  <  s, s1  < 1
В модуле Vectoru.exe системы "Вектор" можно работать с трехмерными векторами, поэтому придется использовать покомпонентную запись, например, вместо:
pi= (1-u)*p81+ u*p82,
задавать:
xi= (1-u)*x81+ u*x82,
yi= (1-u)*y81+ u*y82,
zi= (1-u)*z81+ u*z82,
ti = (1-u)*t81+ u*t82,
где t -  4-я координата задаваемых точек.

Решение задачи в систем "Вектор"

mernd.mac   - задание исходных 4-мерных точек (4-я координата в s )
:p1=100.,0.,0. s1=0.
:p2=0.,100.,0. s2=0.
:p3=0.,0.,100. s3=0.
:p4=0.,0.,0.   s4= 100.
:p10=10.,10.,10.  s10=10.
mern1: s11=0. s12=0. s21=0. s22=0. s99=500.

mern1.mac  - МК первого цикла - перебора линий на 1-й плоскости
s11 > 1. ? exit
p91=(1.-s11)*p1 + s11*p10   $ вычисление точек на границе слева
s91=(1.-s11)*s1 + s11*s10   $ вычисление точек на границе слева
p92=(1.-s11)*p2 + s11*p10   $ вычисление точек на границе слева
s92=(1.-s11)*s2 + s11*s10   $ вычисление точек на границе слева
mern2: s12=0.      $  на цикл вычисления точек на линиях
mern1: s11=s11+0.2   $ рекурсия

mern2.mac - МК перебора точек на 1-й плоскости
s12 > 1. ? exit    $  условие выхода из второго цикла
p7=(1.-s12)*p91+s12*p92    $  вычисление точек (x и y) на отрезках
s7=(1.-s12)*s91+s12*s92    $  вычисление точек (x и y) на отрезках
okr: p100=p7 s100=2.0
mern3: s21=0. s22=0.
mern2 : s12=s12+0.2     $ рекурсия и шаг (0.2)

mern3.mac - МК перебора линий на 2-й плоскости
s21 > 1. ? exit   $  условие выхода из 3-го цикла
p81=(1.-s21)*p3 + s21*p10   $ вычисление точек на границе слева
s81=(1.-s21)*s3 + s21*s10   $ вычисление точек на границе слева
p82=(1.-s21)*p4 + s21*p10   $ вычисление точек на границе слева
s82=(1.-s21)*s4 + s21*s10   $ вычисление точек на границе слева
mern4: s22=0.  $  на цикл вычисления точек на линиях
mern3: s21=s21+0.2   $ рекурсия

mern4.mac - МК перебора точек на 2-й плоскости и вычисление min
s22 > 1. ? exit    $  условие выхода из 4-го цикла
p8=(1.-s22)*p81+s22*p82    $  вычисление точек (x и y) на отрезках
s8=(1.-s22)*s81+s22*s82    $  вычисление точек (x и y) на отрезках
: s51=(x7-x8)*(x7-x8)        s52=(y7-y8)*(y7-y8)
: s53=(z7-z8)*(z7-z8)         s54=(s7-s8)*(s7-s8)
s101=$sqrt(s51+s52+s53+s54) $ длины отрезков между точками 2-х плоскостей
s101 < s99 ? s99=s101      $  выбор наименьшей длины в s99
okr: s100=1. p100=x7+150.,s101  $ график ЦФ изображаем точками
mern4: s22=s22+0.2     $ рекурсия и шаг (0.2)
 
 
Рис. Слева показан перебор точек на первой плоскости, справа - ЦФ зависимости расстояния между плоскостями.



Пример 16. Пересечение прямой линии и поверхности.
Рассмотрим пересечение поверхности однополостного гиперболоида, который определяется уравнением следующего вида:
xi = a* sin u *cos v,
yi = b* sin u * sin v,
zi = c* cos u,         (27)
где а, b, с - значения по осям, а u, v - некоторые переменные,
с прямой линией, заданной уравнением:
pj = (1-t)*p10 + t*p11.
Минимум ЦФ расстояний, равный нулю между этими двумя образами, и даст искомые две или одну (в случае касания) точки:
|pi-p1j| -> min ->  0 .
ЦФ будет зависеть от трех переменных u,v,t и может изображаться в 4-мерном пространстве.


Пример 17. Пересечение двух плоскостей.
|pi - pj| -> min -> 0
pi = (1-v)*((1-u)*p1 + u*p2) + v*p3
pj = (1-s)*((1-t)*p11 + t*p12) + s*p13

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



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


 

3.4. Метрические задачи

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

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

Пример 18. Определить наикратчайшее расстояние между двумя заданными прямыми линиями (рис. 33).

s = |pi-pj| -> min ,
где
pi = (1-u)*p1 + u*p2,
pj = (1-v)*p3 + v*p4.
Целевая функция является двумерной, ее изображение возможно в 4-мерном пространстве на массиве заданных трехмерных совпадающих образов.
Если ее рассмотреть как функцию от параметров u,v задача  будет двумерной и ее изображение возможно в трехмерном пространстве. Такое качество дает возможность изобразить ЦФ в 3-х мерной  системе координат.


3.5. Задачи на компромисс

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

Пример 19. Определить на прямой р1-р2 точку р таким образом, чтобы расстояния s1 и s2 от точек до прямой были одинаковыми.
s1=s2  или
s1-s2 -> 0
Решение. Для этого строим три целевых функций:
1) график f1 зависимости расстояний от точки p1 до прямой p1-p2;
2) график f2 зависимости расстояния от точки p2 до прямой и
3) график f пересечения ЦФ f1 и f2.
Как видим решение подобных задач вполне возможно графочисленными методами.

Пример 20. На плоскости найти точку р на одинаковом расстоянии от трех заданных  р1, р2, р3.
s1=s2=s3 или
|p1-p|=|p2-p|=|p3-p|

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

Можно привести еще множество подобных задач:

1. На прямой найти точку, удаленную от заданной плоскости на заданное расстояние.
2. На прямой найти точку, одинаково удаленную от двух заданных плоскостей.
3. В  плоскости определить точку, одинаково удаленную от трех заданных точек.
4. В плоскости определить точку, одинаково удаленную от трех взаимно параллельных или пересекающихся прямых.
5. Определить точку, удаленную на заданное расстояние от трех заданных пересекающихся плоскостей.
6. В плоскости определить точку, одинаково удаленную от трех заданных  пересекающихся плоскостей.


5. Проектирование новых форм с помощью задач оптимизации

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

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

"что перебрать и как перебрать" - (множество исходных данных описывается в виде одномерных или многомерных массивов (обычно точек), элементы которых необходимо перебрать;

"сравнить в массиве и выбрать из массива" - тот элемент, который отвечает тем или иным требованиям.

Этап "что перебрать" легко интерпретируется образами начертательной геометрии:
одномерный массив - это прямая или кривая линия,
двумерный массив - плоскость,
трехмерный массив - трехмерное тело,
4-мерный массив - 4-мерная фигура и т.д.,
Кроме того, геометрический образ имеет и сама ЦФ.

Пример 21. Задать объект ЦФ вида: F(x,y)=|p-pc|-R
|p-pc|=R - условия геометрического места точек окружности
Из условия что |p-pc| - модуль вектора, определяемого по формуле
|p-pc| = sqrt((x-xc)*(x-xc)+(y-yc)*(y-yc)) можно получить известное уравнение окружности.
Однако можно применить условие оптимизации:
F(x,y)=|p-pc|-R -> min,   (1)
где р - переменный параметр, изменяющийся в какой-то области (в угловых координатах).
В общем случае (1) это конус, однако если |p-pc|-R взять по модулю ||p-pc|-R|, то получим фигуру, полученную на рис. 1, где впадина фигуры образует окружность радиуса R.
В системе вектор изолинии можно получить автоматически, однако интересна сама ЦФ, которую можно комфорно или топологически преобразовывать в более замысловатые для проектирования  и дизайна. На рис. показана форма вида: F(x,y)=||p-pc|-R| (см. рис.).