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

Скрипт, примеры МК
 
С О Д Е Р Ж А Н И Е
Введение
1. Движение объектов в зависимости от скорости по заданному пути.
Пример 1. Задача о пешеходе. Определить маршрут движения путника по скошенному и нескошенному лугам так, чтобы маршрут пешехода был оптимальным.
Пример 2. Задача Снеллиуса. Определить траекторию движения луча света по двум разным средам.
Пример 3. Задача о брахистохроне. Найти кривую наискорейшего спуска.
2. Выбор энергосберегающего (или безопасного) движения судна на основе спутниковой информации.
Пример 4. Определить движения судна, если известно, что часть пути оно может идти по течению воды.
3. Движение в заданном направлении в зависимости от расстояния, направления и времени
Пример 5. Запущенной ракетой сбить самолет (мишень).
Пример 6. Определить на каком наикратчайшем расстоянии пройдут два судна (pi, и pj), при их движении в пересекающихся маршрутах.
Пример 7. Определить на каком расстоянии пройдут суда, при их движении в пересекающихся маршрутах, если первое судно, пытаясь уйти от столкновения, все время сворачивает на заданный угол.
 

В в е д е н и е

Многие законы природы, связанные с распространением света, электричества, жидкости, газа и т.п. можно вывести на основе понятий минимизации. Так, например, принцип Ферма гласит: в неоднородной среде свет распространяется по такой траектории, что время, затрачиваемое им на преодоление пути от одной точки до другой, минимально.

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

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


1. Движение объектов в зависимости от скорости по задаваемым отрезкам

Из физики известно, что скорость определяется, как расстояние поделенное на время.
v=s/t,
откуда время будет: расстояние поделенное на скорость:
t=s/v.
Используя данные определения, рассмотрим серию примеров.

Пример 1. Определить маршрут движения путника по скошенному и нескошенному лугам из точки p1 в точку p2 так, чтобы маршрут его движения был оптимальным. Скорость движения по скошенному лугу равна v1, по нескошенному - v2. Что минимизировать? Расстояние или время? Конечно, время.
1. Анализ:
Исходя из формул определяющих взаимосвязь скорости, времени и расстояния, определяем, что время неизвестно и его удобно выбрать в качестве минимизирующего параметра.

2. Алгоритмизация: время движения путника по лугу 1 и лугу 2 определяется:

t1=s1/v1=|p1-p|/v1
t2=s2/t1=|p2-p|/v2
Откуда общее время:
t=t1+t2=|p1-p|/v1+|p2-p|/v2
где p можно выразить по формуле
p=(1.-s)*p11+s*p12
0 < s < 1.

2. Формирование цели (ЦФ):

t=t1+t2 -> min
или
t=t1+t2=|p1-p|/v1+|p2-p|/v2 -> min,

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



Пример 2. Задача Снеллиуса. Определить траекторию движения луча света из точки p1, в точку p2, по двум разным средам, если известно, что скорость распространения света в верхней среде v1, а в нижней - v2

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

Итак формализация задачи.
1) Задание исходных данных: начальная р1 и конечные р2 точки движения луча.
2) Задание границы сред: р11-р12
3) Формирование цели (целевой функции):
Опять минимизируем время:
t=t1+t2 -> min
или
t=t1+t2=|p1-p|/v1+|p2-p|/v2 -> min,
где p
p=(1.-s)*p11+s*p12
Ограничения: 0 < s < 1.
Таким образом задача свелась к задаче о пешеходе по скошенному и не скошенному лугу.


Пример 3. Задача о брахистохроне. Найти кривую наискорейшего спуска. На этапе анализа замечаем, что скорость движения падающих  тел зависит от времени падения. Можно в точке pi на горизонтали, разделяющей пространство на две части принять, что скорость в верхней части определена v1, а в нижней v2 и  свести к задаче движения по скошенному и нескошенному лугу.
Рассмотрим подробнее. Итак (рис.3) в вертикальной плоскости определить путь p1-pi-p2, спускаясь по которому под действием собственной тяжести, тело p1, начав двигаться из точи p1, достигнет точки p2 в кратчайшее время. Используя уравнение ускорения падающего тела под действием силы тяготения a=gt2 (зависящего от высоты) и упрощенно считая в произвольной точке pi(xi,yi) скорость движения над точкой будет v1=sqrt(2*g*yi), а под  точкой pi будет v2=sqrt(2*g*y2). Задача сводится к задаче о движении луча света в разных средах или к задаче движения путника по скошенному и не скошенному лугу.

Формализация.
Целевая функция
t=t1+t2=|p1-pi|/v1+|pi-p2/v2 -> min
где
pi=(1.-s)*|p11 + s*p12
Ограничения
0 < s < 1
 

Графическая интерпретация постановки и нахождения ЦФ в задаче о брахистохроне.

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

Ниже дана программа формирования ЦФ, написанная на языке C - формируется массив ЦФ.
Что-то подобное будет на языке Java Scrept (JS)

#include   <math.h>
#include  "geotyps3.h"
    main()
{
    point3 mthkp[11] [11]  ;
    point3 p;
    float u,v,s1,s2,t,t1,t2,v1,v2;
    int k,i,  nppry,npprx;
    point3
                     p11  = { 0., 20.0 },
                     p12  = { 60., 20.0 },
                     p1  =  { 0., 0.0 },
                     p2  =  { 50., 40.0 };
        v1=sqrt(2.*9.8*p11.y);
        v2=sqrt(2.*9.8*p2.y);
      /* Брахистохрона Бернулли */
     npprx=11;
     for ( k=0, u=0; k < npprx; k++, u +=1./(npprx-1)) {
           p.x = (1-u)*p11.x + u*p12.x ;
           p.y = (1-u)*p11.y + u*p12.y ;
         s1= sqrt((p1.x-p.x)*(p1.x-p.x)+(p1.y-p.y)*(p1.y-p.y));
         s2= sqrt((p2.x-p.x)*(p2.x-p.x)+(p2.y-p.y)*(p2.y-p.y));
         t1=s1/v1;
         t2=s2/v2;
         t=t1 + t2;
      mthkp [0] [k].x = p.x;
      mthkp [0] [k].z = t*10. ;
      mthkp [0] [k].y = p.y;
        }
         vectorcg( "line12", 1, npprx, mthkp );
return( 0 );
}
 

2. Выбор энергосберегающего (или безопасного) движения судна на основе спутниковой информации.

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

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

Рассмотрим конкретный пример.

Пример 4. Судно (рис.6) движется из пункта р1 в пункт р2. Со спутника получены данные о направлении потока воды (или ветра), не совпадающего с курсом судна. Капитан судна принимает решение часть пути двигаться по течению воды (р1-р11), а затем (в точке р ) повернуть в нужном направлении. Необходимо определить точку р поворота.

Итак, требуется определить маршрут движения судна из точки р1 в точку р2 из условия того, что часть пути судно может двигаться по течению воды (р1-p11). Известны скорость судна v1=12 миль/час, скорость течения v2=7 миль/час.

Формализация (алгоритмизация) задачи. Время движения судна по течению воды (р1-p)  и далее по прямой (р-p2) определяется:
t=s12/(v1+v2)+s11/v1
и должно стремиться к минимуму.
Время в зависимости от положения точки на прямой р1=р11 является ЦФ. Минимум ЦФ даст искомое минимальное значение времени движения судна.
Причем абсцисса минимального значения соответствует точке, где необходимо свернуть с потока. Длина части маршрута по течению s11 и части движения по прямой s12 вычисляется из соотношений:
s12 =| p-p1|,
s11 = |p2-p| ,
где точка р определяется по формуле:
p=(1-s)*p1 + s*p10 при изменении s от нуля до единицы.
Таким образом, задача сводится к простому перебору точек на прямой р1-р10, вычислению времени в каждом случае на прохождение маршрута,  сравнению их и выбору из них наименьшего.
 
 
На рис. показан графический результат моделирования данной задачи.
Время движения судна по течению воды и вне его равно 15.0866 часа, что значительно меньше, чем по прямой (t1=17.8924 час).

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


3. Движение в заданном направлении в зависимости от расстояния, направления и времени

В ряде задач движение перебираемых точек зависит не  от безразмерного параметра s (как это делалось в предыдущей задаче перебора точек на прямой р1-р11), а от конкретного расстояния или направления движения, определяемого чаще единичным вектором.

Движение от точки р1 по направлению единичного вектора p99 задается:

p=p1+s*p99,

где точка р определяется в зависимости от s - расстояния от р1.

В свою очередь, если отрезок задан двумя точками р1, р2, единичный вектор р99 вычисляется:

р99=(р2-р1)/|p2-p1|

А если известна скорость движения, можно получить движения точки в заданном направлении в зависимости от времени:

p =p1+v*t*p99,

где p99 - единичный вектор.

Пример 5. Из точки p1 в заданном направлении р2 движется мишень pi со скоростью v1. В направлении мишени в момент ее начала движения запущена самонаводящая ракета pj, вектор движения которой p10-pj направлен все время на мишень pi. Скорость движения ракеты v2 > скорости мишени.  Задача сбить мишень.

Формально задачу можно поставить так. Найти минимальное расстояние, между ракетой и мишенью и в какое время это произойдет. Скорость мишени и ракеты известны. Для начала определим единичный вектора для мишени и ракеты по их направлениям:

p99i=(p2-p1)/|p2-p1|
p99j=(p1-p10)/|p1-p10|
 
Значит за время ti они от стартовой точки согласно каждой своей скорости пройдут путь равный вектору
(время на скорость и единичный вектор)

pi=p1+t*v1*p99i
pj=p10+t*v2*p99j

За следующий промежуток времени направление движения мишени не изменится и поэтому его единичный вектор будет тот же, а единичные вектор направления ракеты будет вычисляться по формуле
pj=pj+t*v2*pi
 
Расстояние между ракетой и мишенью определяется:

s=|pj-pi| -> min

Минимум график зависимости расстояния между ракетой и мишенью от времени (или от положения токи pi, как дано на рисунке)  даст время,  в какой момент ракета настигнет мишень, а узнав время определим по формуле  pi=p1+t*v1*p99i и критическую точку.
 


 


Пример 6. Определить на каком наикратчайшем расстоянии пройдут два судна (pi, и pj), при их движении в пересекающихся маршрутах. Известны скорость первого судна (v1) и второго (v2). Направление движения судов определены векторами p1-p2   и p11-p12
Анализ и формализация задачи.
1. Необходимо смоделировать движение того и другого судна в зависимости от времени (переменный независимый параметр)
pi=p1+t*v1*p99i
pj=p10+t*v2*p99j
где:
p99i=(p2-p1)/|p2-p1|
 p99j=(p12-p11)/|p11-p12|
Ставим цель
F=sij=|pi-pj| -> min
Здесь, конечно ЦФ не стремится к минимуму, а просто мы ищем  минимум.
График ЦФ буде зависимостью расстояния от переменной времени.
 

Пример 7. Определить на каком наикратчайшем расстоянии пройдут два судна (pi, и pj), при их движении в пересекающихся маршрутах, если судно, пытаясь уйти от столкновения, все время сворачивает на заданный угол. Известны скорость первого судна (v1) и второго (v2).

Задача подобна задаче с мишенью, за исключением того, что судно pj движется не в направлении мишени (второго судна) а в направлении, определяемого углом сворота.
Формализация.
s= |pi-pj| -> min
pi=p1+t*v1*(p1-p2)/|p1-p2|
pj=p10+t*v2*(p10+dx)-p3)/|p10+dx)-p3|
где t - переменный параметр, dx - шаг приращения, а р3 - предыдущее ( в цикле) р10.
 
Так выглядит  ситуация движения судов и ЦФ примера 6.