Урок 3. Метод графочисленной оптимизации

Содержание

Теоретические положения.

Упражнение 1 В диалоге системы "Вектор" из 3-х заданных чисел выбрать наименьшее.
Упражнение 2. Не выходя из системы "Вектор (упр.1) построить график целевой функции (ЦФ) зависимости значения числа от его номера.
Упражнение 3. Написать МК вычисления наименьшего числа их 20-ти заданных. В "Вектор" МК показать (в соответствующем регистре) наименьшее число.
Упражнение 4. Модернизировав предыдущие МК, построить ЦФ зависимости значений чисел от их номера.
Контрольные вопросы
Упражнение 5. Определить наикратчайшее расстояние от p3 до отрезка p1-p2. Построить график ЦФ зависимости расстояний от положения точки р (её компаненты х).
Контрольные вопросы
Упражнение 6. Определить расстояние от точки до косой плоскости.
Упражнение 7 (пример). Определить расстояние от точки до сферы.

Самостоятельно.
Задача 1.
Задача 2.
Задача 3.


Теоретические положения:

Метод графочисленной оптимизации состоит из этапов:

1) Формирование целевой функции (ЦФ).
2) Определение области существования ЦФ.
3) Определение мах/min ЦФ.
4) Построение графика ЦФ.

1. Формирование ЦФ:
Найти расстояние s от точки р3 до т. р на прямой р1-р2, так чтобы:
s=|p3-p|->min, где р=(1.-s)*p1+s*p2

Найти минимальное расстояние s от точки р4 до плоскости p1-p3
s=|p4-p|-> min и т.д.

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

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

4. Построение графика ЦФ. График ЦФ обычно строится в том же цикле, где определяется min/max ЦФ. Ор-динатами ЦФ будут ее значения, а абсциссой - координата местоположения точки на прямой или ее безразмерный параметр s.
Упражнение 3.1. Из набора вещественных чисел: 80.0, 40.0, 60.0, определить наи-меньшее число и построить график величины числа от его номера.

Алгоритм решения основан: на переборе, сравнении и выборе.

Эталон (s99) задаем заведомо большим (s99=200.) любого числа из заданных. Сравниваем s1 с s99. Если число в s1 меньше числа в s99, то число из s1 помещаем в регистр s99 (переприсваиваем). Берем второе число в s2, также сравниваем с новым числом в s99, и, если оно меньше, меняем его на меньшее (в противном случае присвоение не выполняется) и так до тех пор, пока не переберем все числа. Наименьшее число будет находится в s99.


Упражнение 1. В системе "Вектор" в графическом диалоге из 3-х заданных чисел выбрать наименьшее.
: s1=80. s2=40. s3= 60.  s98=0. s99=200. $ - задание чисел списком (двоеточие)
s1 < s99 ? s99=s1 $ если число в s1 меньше чем в s99, то s99=s1
s2 < s99 ? s99=s2 $ действие выполняется как и в предыдущей строке
s3 < s99 ? s99=s3 $ действие не выполняется, так как s3 больше s99
В итоге в s99 будет лежать наименьшее число равное 40.


 
Упражнение 2. Не выходя из системы "Вектор построить график (ЦФ) зависимости значения числа от его номера. 
 
 

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


Упражнение 3. Написать (в текстовом редакторе) МК вычисления наименьшего числа их 20-ти заданных. В "Вектор" МК запустить их и показать (в соответствующем регистре) наименьшее число.

Решение. Ниже даны две МК: исходных данных и МК цикла, выполняющей перебор, сравнение и выбор.

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
n > 20 ? exit
sn < s99 ?  s99=sn  $ наименьшее число будет в s99;
$ sn <>  5. ? exit      $ при достижении мин, выйти. Так определим n.
hisc : n=n+1  $ рекурсия



 
Упражнение 4. Модернизировав МК  hisd.mac и hisс.mac построить график зависимости значений чисел от их номера. 
 

Решение. Переменной величиной (вдоль оси х) выберем номера чисел (от 1 до 20). Аргументами (по оси y) будут значения чисел s1-s20. Первой точкой графика ЦФ выберем точку р103 с координатами (х103=0., y103=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  p103=0.0,s99
 
hisc.mac
n > 20 ? exit
sn < s99 ?  s99=sn
otrezok: p101= p103  x102=n*10 y102=sn
hisс : n=n+1   p103=p102
 
 
Упражнение 4.1. Определите номер минимального числа. Изобразите график ЦФ. 
 
Решение. Переменной величиной (вдоль оси х) выберем номера чисел (от 1 до 20). Аргументами (по оси y) будут значения чисел s1-s20. Первой точкой графика ЦФ выберем точку р103 с координатами (х103=0., y103=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  p103=0.0,s99
 
hisc.mac
n > 20 ? exit
sn < s99 ?  s99=sn
otrezok: p101= p103  x102=n*10 y102=sn
sn <> 5. ? exit
hisс : n=n+1   p103=p102


Вопросы:
Сколько раз отработает программа hisc?
Сколько раз строка sn < s99 ? s99=sn выполнит присвоение?
Что означает запись s99=sn? В каком регистре будет лежать минимальное число?
Как узнать номер минимального число?
Как найти максимальное число?
Что означает команда x102=n*10 ?
Как задается конец отрезка в МК otrezok?
Что от чего зависит при построении ЦФ?
4. Как определить номер минимального числа? Определить.



 
 
Упражнение 5. Определить наикратчайшее расстояние от p3 до отрезка p1-p2. Построить график ЦФ зависимости расстояний от точки р (её компаненты х)
 
 
 

Решение: переберем расстояния от заданной точки до множества точек на прямой, и то расстояние, которое будет наименьшим и будет решением. Перебор точ-ки р на прямой р1-р2 можно по формуле:

р= (1.-s)*p1+s*p2, где s изменяется  от 0. до 1.

Расстояние от точки p3 до точки р определяется:
s11 = |p3-p| или: s11=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y)).

Дадим решение задачи с помощью двух макрокоманд.

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

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

Графическая интерпретация задачи упр.5.
 

Вопросы.
1. Что означает перебрать, сравнить и выбрать?
2.  В каком регистре будет находится минимальное расстояние?
3.  Как определить точку до которой от р3 до прямой минимум?
4.  Что нужно сделать, чтобы строка $ n50 <>  52000 ? exit сработала?
5.  Откуда взялось число 52000 в строке: n50 <>  52000 ? exit?
6.  Строка otrezok : p101=p103  p102=x, s11 строит график ЦФ. Что является пе-ременным параметром, что аргументом?


Упражнение 6. Определить расстояние от точки до косой плоскости.

Решение. С помощью 3-х МК - задания данных и двух рекурсивных цикллов - перебора линий в плоскости и точек на линиях.

tplsk0.mac задание исходных данных
$ print$on
: p1=70.,0.,0. p2=0.,80.,0.  p3=0.,0.,0.
otrezok: p101=p1 p102=p2
otrezok: p101=p2 p102=p3
otrezok: p101=p3 p102=p1
p5=30.,30.,50.
tplsk: s=0.  s99=500. p9=x1,y1,s99

tplsk.mac  определение линий на плоскости
s > 1. ? exit
p91=(1.-s)*p1+s*p3   $ вычисление точек на границе слева
p92=(1.-s)*p2 +s*p3  $ вычисление точек справа
otrezok: p101=p91 p102=p92 $ изображаем перебираемые линии
tplsk1: s1=0.      $  на цикл вычисления точек на линиях
$ n50 <> s99min, переведенное в целом см. n50) 79 ? exit
tplsk : s=s+0.1   $ рекурсия

tplsk1.mac  второй цикл - перебор расстояний от точки до плоскости
s1 > 1. ? exit    $  условие выхода из второго цикла
p=(1.-s1)*p91+s1*p92    $  вычисление точек (x и y) на отрезках
otrezok: p101=p p102=p5 $   соединяем вычисленные точки с точкой р5
s11=$sqrt((x5-x)*(x5-x)+(y5-y)*(y5-y)+(z5-z)*(z5-z)) $ длины
s11 < s99 ?  s99=s11      $  выбор наименьшей длины в s99
otrezok: p101=p9 p102=x,y,s11+0.  $ график ЦФ - длины от x и y
p9=p102   $  конец кладем в начало следующего отрезка
n50=s99*1000.  $  переводим s99min в целое
$ n50 <> s99min - переведенное в целое см. n50 ? exit $ условие выхода
tplsk1 : s1=s1+0.1     $ рекурсия и шаг (0.1)

Графическая интерпретация задачи упр.6.



Упражнение 7 (пример). Определить расстояния от точки до сферы.

tsfer0.mac - МК запуска МК определения расстояний от точки до сферы
ck   $  задание комплексного чертежа
$ tsferd : n=1  $ изображаем на горизонтальной проекции
 tsferd : n=2   $ фронтальной
 tsferd : n=3   $ профильной
 tsferd : n=5   $ диметрии

tsferd.mac  - МК данных от точки p2  до сферы
print$on      $
p2=0.,0.,0.   $  задаваемая точка
okr: p100=p2 s100=10.  $  изобразим  ее
: p1=50.,40.,40. s11=30.   $ данные для сферы
s99=1000.0   $ эталон сравнения - начальное значение
p3 = x1,s1   $ начало графика ЦФ - зависимости расстояния от р2 до сферы
tsferi: s1=0. s2=0.

tsferi.mac  - первый цикл от точки p2  до сферы
s1 > 6.29 ? exit   $ цикл перебора меридиан на сфере
tsferi2: s2=0. p3=p1  $ к циклу перебора точек на сфере и расстояний до р2
$ n50 <> s99min (n50) ? exit  $ условие выхода при достижении минимума
tsferi: s1=s1+0.5  $  условие выхода из второго цикла

tsferi2.mac  - МК второго цикла от точки p2  до сферы
s2 > 6.29 ? exit  $ условие выхода
x=x1+s11*cos(s1)*$sin(s2)  $  сфера см. матсправочник
y=y1+s11*$sin(s1)*$sin(s2) $
z=z1+s11*cos(s2)    $
$ okr : p100=p s100=2.0    $ точки (можно) отображаем окружностями
otrezok: p101=p p102=p2    $ соединяем перебираемые отрезки
s9=$sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y)) $ длины их
s9 < s99 ? s99=s9  $ выбор минимального
otrezok: p101=p3 p102=x,y,s9-100. $ график расстояний от x,y
p3=p102    $ конец в начало переводим
n50=s99*1000.   $ переводим s99 в целое
$ n50 <> 35038 ? exit  $ выход при s99min
tsferi2: s2=s2+0.5  $ рекурсия

Графическая интерпретация задачи упр.7.




Самостоятельно.


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




Задача 2. Определить наикратчайшее расстояние между двумя отрезками p11-p12 и р21-р22 прямых (в частном случае - точку пересечения двух отрезков).
Целевая функция: s=|pi-pj| -> min
Пусть начала и концы отрезков по х совпадают (х11=х21, х12=х22).
Тогда ЦФ: s=|yi-yj| -> min,    при     х11 < x <  x12
Ограничения:
yi(x)= y11+(y12-y11)*(x-x11)/(x12-x11)
yj(x)= y21+(y22-y21)*(x-x21)/(x22-x21)



Задача 3 (задача о геодезической линии). Определить наикратчайшее расстояние s от заданной точки p1 на одной из вертикальных стен комнаты до точки p2 на потолке, прокладывая путь только по плоскостям стен и потолка.

Целевая функция: s=|p1-p|+|p2-p| -> min
Ограничения: p=(1-u)*p11+u*p12, где 0. < u < 1.
p11-p12 - начальная и конечная точки на границе плоскостей.