X Международная студенческая научная конференция Студенческий научный форум - 2018

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

Рис 1. Графическая иллюстрация задачи с одним препятствием.

Формула, полученная при решении задачи с одним препятствием, имеет вид:

Изменим условие задачи, добавив второе препятствие. Найдем кратчайший путь от точки О с координатами (x_о; y_о) до точки Fc координатами (x_F;y₀) и докажем, что именно этот путь является оптимальным в условиях данной задачи (рис 2, 3).

Рис 2. Условная местность, рассматриваемая для задачи

Рис 3. Графическая интерпретация

За начальную координату примем точку выхода – точку О. Её координата расположена правее точки М – точки пересечения касательной к двум окружностям с осью ОХ, иначе задача сводится к решению задачи с одним препятствием. Определим кратчайшее расстояние и построим его в системе моделирования «Компас», путь выделен зелёной линией (рис 4).

Рис 4. Построение кратчайшего пути в пакете «Компас»

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

I этап. Найдем кратчайший путь на данном участке (рис 5).

 

Рис 5. Зависимость длины ОВ от угла ï

 

Введём следующие обозначения:

1.  
   •  
     Система координат Oxy,

     О – точка начала отсчета,

     В – точка пересечения первой касательной и окружности,

     С – точка пересечения касательной к двум окружностям и малой окружности,

     a- расстояние от начала отсчета до точки начала окружности,

     b= r – радиус малой окружности,

     Угол «α» - угол HLC,

     Угол «μ» - угол BLC,

     Угол «ï» - угол B’ОL.

Кратчайшим расстоянием между двумя точками на плоскости является соединяющий их отрезок прямой. В данной задаче OL не изменяется. Таким образом, при уменьшении угла путь сокращается. Будем уменьшать угол ï, пока OB не коснется окружности (рис 5).

Исходя из этого можно сделать вывод о том, что кратчайшим расстоянием от точки О до окружности является касательная ОВ. Тогда по теореме Пифагора:

, то есть .

А кратчайшим расстоянием от точки В до С будет путь по дуге, так какпуть по сторонам центрального угла, опирающегося на данную дугу будет всегда больше пути по самой дуге. Тогда длина дуги BC определяется по формуле:, для всех , где измеряется в радианах. [4]

Обозначим через угол CLH.Тогда длина дуги BC определяется по формуле:,

Следовательно, путь, состоящий из отрезка ОВ и дуги ВС, является оптимальным в рассматриваемом случае.

Рис 6. Схематичная модель первого этапа решения задачи

Аналогично данному способу можно доказать, что наикратчайшим путем от Dк Fявляется дуга DEи отрезок EF.

IIэтап. Докажем, что кратчайшим путем от одной окружности к другой является касательная к двум этим окружностям – отрезок СD.

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

Проиллюстрируем данное утверждение на примере движения по сторонам треугольника. Путь по его стороне – с – будет короче, чем путь a+b (неравенство треугольника).

Применим неравенство треугольника для данной задачи (рис. 7). Расстояние между двумя окружностями – касательная (рис. 8).

 

Рис 7. Иллюстрация свойства неравенства треугольника для нахождения кратчайшего пути

 

 

Рис 8. Касательная к обеим окружностям

 

Для удобства нахождения пути и наглядности введём дополнительное построение: CD=LV, CD || LV. Тогда найдем LV (рис 9).

Выразим общий вид кратчайшего пути при помощи математических преобразований.

Выразим СD через длины отрезков, проведя дополнительные построения; при этом:

b = r – радиус малой окружности.

с – расстояние от малой окружности до большой

d = R – радиус большой окружности

DR = R, поэтому VR= R-r

Рис 9. Схематичная модель второго этапа решения задачи

CD=LV, CD || LV. Тогда найдем LV.

LR= b + c + d. RV= R-r.

По теореме Пифагора:

.

То есть .

III этап. Необходимые обозначения:

d –радиус большой окружности,

f –расстояние от конца большой окружности до конечной точки пути,

α– угол между перпендикуляром, выходящим из центра окружности и DR,

β – угол между перпендикуляром к касательной (т.е. радиусом) и отрезком, лежащим на оси Ox,

E– точка пересечения второй касательной и большой окружности,

F – точка конца пути,

R – центр большой окружности,

Q – точка конца большой окружности.

Докажем, что: путь по дуге DE и отрезку EFбудет кратчайшим.

Доказательство (аналогично первому этапу):

Путь по дуге будет всегда короче, чем по сторонам центрального угла, на которые она опирается.

Кратчайшим расстоянием между двумя точками на плоскости является соединяющий их отрезок прямой.

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

(из теоремы Пифагора)

Выразим общий вид наикратчайшего пути от точки D к F.

Рис10.Схематичная модель третьего этапа решения задачи

Найдем дугу DE в радианах:, тогда

Найдем EF: треугольник ERF – прямоугольный => по теореме Пифагора , то есть

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

Длину всего пути обозначим за S.

Рис11. Итоговая модель кратчайшего пути

Получим математическую модель пути:

Следовательно, путь, состоящий из трёх отрезков OB, CD, EF и двух дуг ᴗ BC,DE является более коротким, чем все остальные.

Теперь рассмотрим частный случай: между двумя населенными пунктами находятся труднопроходимые участки местности (рис. 12). Расстояния a, b, c, d, f – нам известны, либо их можно получить путем измерений, проведенных на географической карте.

Рис 12. Построение кратчайшего пути между двумя пунктами

Пустьr = 10, R = 25, OL=15, LR=50, RF=50.

Рис 13.Числовые значения известных расстояний на рисунке

Представим задачу с помощью математической модели и решим её с использованием ранее выведенной формулы:

После проведения несложных математических вычислений находим кратчайшее расстояние между двумя пунктами в обход непроходимых препятствий.

Тогда, подставив заданные значения в полученную нами формулу общего пути, получим: S=140

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

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

Список литературы:

Акулич И. Л. Математическое программирование в примерах и задачах: учеб.пособие/ И. Л. Акулич. – СПб: Лань, 2011 г. - 352 с.

Завьялова Т. В. Методы принятия управленческих решений: учеб.пособие/ Т. В. Завьялова, И. Н. Пирогова, Е. Г. Филиппова, - Екатеринбург: Изд-во УрГУПС, 2014 г. – 89 с.

Моисеева Л. Т. Методы математического моделирования процессов в машиностроении: учеб пособие/ Л. Т. Моисеева. – Курск, 2008 г. – 46 с.

Код для цитирования: Скопировать