2016/2, стр. 121 - 142

ПРОГРАМНИ ЕКСПЕРИМЕНТИ СЪС ЗАДАЧИ ОТ ТИП HERON

Резюме: Задачата на Heron е древна математическа задача, която има точно и елегантно решение. В статията са формулирани задачи, които представляват обобщение на задачата на Heron, но за които не са известни точни математически решения. Тези задачи имат практическо приложение и за тях са представени приближени решения чрез програми на C++ и MATLAB.

Ключови думи: Heron type problems, Generalized Heron problems

1. Задачата на Heron

Отправна точка в тази статия е следната древна задача.

Основна задача. Дадени са права \(l\) и две точки \(A\) и \(B\), разположени от една и съща страна на \(l\). Да се намери точка \(M\) от правата \(l\), за която сборът от разстоянията от \(A\) и B до M е минимален (Hadamard, 1962).

Задачата се среща и в разнообразни забавни формулировки. Тя има кратко и красиво решение.

Решение

Разглеждаме фиг. 1, на която \(l\) е дадената права, а A и B са точките, които са разположени от едната є страна. Построяваме т. A', симетрична на A по отношение на правата \(l\), а с M означаваме пресеч-ната точка на \(l\) и BA'. Нека \(\mathrm{M}_{1}\) е произволна точка върху \(l\), различна от т. М.

Тъй като \(\mathrm{MA}^{\prime}=\mathrm{MA}\) и \(\mathrm{M}_{1} \mathrm{~A}^{\prime}=\mathrm{M}_{1} \mathrm{~A}\), следва, че:

\(\mathrm{BM}_{1}+\mathrm{M}_{1} \mathrm{~A}=\mathrm{BM}_{1}+\mathrm{M}_{1} \mathrm{~A}^{\prime} \gt \mathrm{BA}^{\prime}=\mathrm{BM}+\mathrm{MA}^{\prime}=\mathrm{BM}+\mathrm{MA}\)

С това исканата точка M е построена и тя е единствена.

В (Hadamard, 1962) под номер 14 е дадена задача (задачата за билярда), която има различна формулировка от задачата на Heron, но практически решението е същото: Дадени са права xy и две точки \(A\) и \(B\), които са от една и съща страна на правата. Да се намери точка M върху правата, за която \(\boxtimes A M x=\boxtimes B M y\).

В тази задача косвено се илюстрира закон от физиката, съгласно който ъгълът, под който пада светлинен лъч върху равнинна повърхност, е равен на ъгъла, под който лъчът се отразява.

По-нататък за краткост точката M, която е решение на задачата на Heron, ще наричаме минималната точка за съответната права \(l\) и двете точки \(\mathrm{P}_{1}, \mathrm{P}_{2}\), а за самата задача и решението є ще използваме означението \(\mathrm{M}=\left(l ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\).

Може да се отбележи, че изискването в задачата на Heron двете точки да са от едната страна на правата, не е съществено. Когато точките са от различни страни, решението се вижда веднага и всъщност този случай подсказва за решението на основната задача.

Ако не се налагат ограничения за разположението на точките спрямо правата, тогава следва да се разгледат няколко случая. Те са представени в табл. 1, където с \(\mathrm{d}_{\text {мIN }}\) е означено минималното разстояние \(\mathrm{P}_{1} \mathrm{M}+\mathrm{MP}_{2}\).

Случаите от 2 до 6 са частни и тривиални, но не са безинтересни, когато решението се представя с компютърна програма. Въпреки това, за да не се утежнява програмният код, те няма да бъдат специално разглеждани в програмните решения на някои от задачите.

2. Задачата на Heron в координатна система

Разглеждаме задачата на Heron \(\mathrm{M}=\left(\mathrm{O} x ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\) в правоъгълна координатна система О \(x y\), в която правата \(l\) сьвпада с оста \(\mathrm{O} x\), а дадените точки \(\mathrm{P}_{1}\left(x_{1}, y_{1}\right)\) и \(\mathrm{P}_{2}\left(x_{2}, y_{2}\right)\), y2), са над оста \(\mathrm{O} x\), т.е. \(x_{1} \neq x_{2}, y_{1} \gt 0, y_{2} \gt 0\). Задача 1. Да се пресметнат координатите на минималната точка за \(\mathrm{M}=\left(\mathrm{O} x ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\)

Решение

Нека ортогоналните проекции на \(\mathrm{P}_{1}\) и \(\mathrm{P}_{2}\) върху \(\mathrm{O} x\) са точките \(\mathrm{A}_{1}\left(x_{1}, 0\right)\) и \(\mathrm{A}_{2}\left(x_{2}, 0\right)\), а \(\mathrm{M}(, 0)\) е търсената минимална точка (фиг. 2). От подобието на триъгълниците \(\mathrm{P}_{1} \mathrm{MA}_{1}\) и \(\mathrm{P}_{2} \mathrm{MA}_{2}\) следва, че \[ \cfrac{P_{1} A_{1}}{P_{2} A_{2}}=\cfrac{M A_{1}}{A_{2} M}=\cfrac{x_{M}-x_{1}}{x_{2}-x_{M}} \]

Така за стойността на координата \(x\) на т. M се получава:

(1) \[ x_{M}=\cfrac{x_{1} P_{2} A_{2}+x_{2} P_{1} A_{1}}{P_{2} A_{2}+P_{1} A_{1}} \]

Този резултат е обобщен в следващата задача.

Задача 2. Нека Oxy е правоъгълна координатна система, \(\mathrm{P}_{1}\left(x_{1}, y_{1}\right)\) и \(\mathrm{P}_{2}\left(x_{2}, y_{2}\right)\) са точки в равнината, \(\mathrm{a} l\) е права, минаваща през т. O и пресичаща \(\mathrm{O} x\) под ъгъл \(\alpha, 0 \leq \alpha \lt \cfrac{\pi}{2}\). Да се пресметнат координатите (\(x_{\mathrm{M}}, y_{\mathrm{M}}\) ) на минималната точка \(\mathrm{M}=\left(l ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\).

Решение

От съществено значение в тази задача е стойността на ъгъла \(\alpha\) (фиг. 3).

– Ако \(\alpha=∢ \mathrm{P}_{1} \mathrm{O} x\), тогава т. \(\mathrm{P}_{1}\) лежи върху правата \(l\) и това е случай 5 от табл. 1.

– Ако \(\alpha=∢ \mathrm{P}_{2} \mathrm{O} x\), тогава т. \(\mathrm{P}_{2}\) лежи върху правата \(l\) и това е случай 5 от табл. 1.

– Ако \(∢ \mathrm{P}_{1} \mathrm{O} x=∢ \mathrm{P}_{2} \mathrm{O} x\), това е случай 6 от табл. 1.

4 от– таб Акол. 1. правата \(P_{1} P_{2}\) пресича \(l\) под ъгъл \(\cfrac{\pi}{2}\), това съответства на случай 3 или

По-долу следва решението на задачата в общия случай (случай 1 от табл. 1).

Ортогоналната проекция на произволна точка P върху правата \(l\) с ъглов коефициент \(\operatorname{tg}(\alpha)\) е линейна трансформация, определена с матрицата:

\[ L=\left(\begin{array}{cc} \cos ^{2}(\alpha) & \sin (\alpha) \cos (\alpha) \\ \sin (\alpha) \cos (\alpha) & \sin ^{2}(\alpha) \end{array}\right) \]

Оттук следва, че за координатите на ортогоналната проекция \(\mathrm{A}_{1}\left(x_{1}^{\prime}, y_{1}^{\prime}\right)\) на т. \(P_{1}\) се получава:

\[ A_{1}\binom{x_{1}^{\prime}}{y_{1}^{\prime}}=L \times\binom{ x_{1}}{y_{1}}=\binom{\cos ^{2}(\alpha) x_{1}+\sin (\alpha) \cos (\alpha) y_{1}}{\sin (\alpha) \cos (\alpha) x_{1}+\sin ^{2}(\alpha) y_{1}} \]

Аналогично за координатите на т. \(\mathrm{A}_{2}\) се получава:

\[ A_{2}\binom{x_{2}^{\prime}}{y_{2}^{\prime}}=L \times\binom{ x_{2}}{y_{2}}=\binom{\cos ^{2}(\alpha) x_{2}+\sin (\alpha) \cos (\alpha) y_{2}}{\sin (\alpha) \cos (\alpha) x_{2}+\sin ^{2}(\alpha) y_{2}} \]

От подобието на триъгълниците \(\mathrm{A}_{2} \mathrm{~B}_{2} \mathrm{O}, \mathrm{MM}_{1} \mathrm{O}\) и \(\mathrm{A}_{1} \mathrm{~B}_{1} \mathrm{O}\) може да се запише:

\[ \cfrac{P_{1} A_{1}}{P_{2} A_{2}}=\cfrac{M A_{1}}{A_{2} M}=\cfrac{M_{1} \dot{B_{1}}}{B_{2} M_{1}}=\cfrac{x_{M}-x_{1}^{\prime}}{x_{2}^{\prime}-x_{M}} \]

Оттук за координатите (\(x_{\mathrm{M}}, y_{\mathrm{M}}\) ) на т. М, yM) на т. M, изразени с координатите (\(x^{\prime}{ }_{1}, y^{\prime}\) ) и \(\left(x_{2}^{\prime}, y_{2}^{\prime}\right)\) на ортогоналните проекции на т. \(P_{1}\) и т. \(P_{2}\) върху правата \(l\), се получава:

(3) \[ \begin{aligned} & x_{M}=\cfrac{x_{1}^{\prime} P_{2} A_{2}+x_{2}^{\prime} P_{1} A_{1}}{P_{2} A_{2}+P_{1} A_{1}} \\ & y_{M}=\operatorname{tg}(\alpha) x_{M}=\operatorname{tg}(\alpha) \cfrac{x_{1}^{\prime} P_{2} A_{2}+x_{2}^{\prime} P_{1} A_{1}}{P_{2} A_{2}+P_{1} A_{1}} \end{aligned} \]

Може да се отбележи, че специалният избор на правата \(l\) в тази и в следващите задачи не намалява общността на резултатите в тях.

Задача 3. В условията на задача 2 да се визуализира множеството от минимални точки \(\mathrm{M}(\alpha)=\left(l(\alpha) ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\) за \(0 \leq \alpha \lt \cfrac{\pi}{2}\).

Решение

Нека \(\alpha_{1}=∢ \mathrm{P}_{1} \mathrm{O} x\) и \(\alpha_{2}=∢ \mathrm{P}_{2} \mathrm{O} x\). Ясно е, че ако \(\alpha\) е в интервала \(\left[\min \left(\alpha_{1}, \alpha_{2}\right)\right.\), \(\left.\max \left(\alpha_{1}, \alpha_{2}\right)\right]\), α2)], тогава задачата се свежда до някой от частните случаи 2, 5 или 6 от табл. 1.

Всъщност решението на задачата изисква намиране и визуализиране на ГМТ със свойството на т. M. Координатите на точката M са пресметнати в задача 2. Остава графично да се визуализира множеството на точките M. Това е извършено с програмния код на функцията minPoints, написана на MATLAB.

Резултатите от четири изпълнения на функцията minPoints са показани на фигури 4а, 4б, 4в и 4г. Посочени са и координатите на точките \(\mathrm{P}_{1}\) и \(\mathrm{P}_{2}\).

3. Задачи от тип Heron

Задачата на Heron е прекрасен пример за оптимизационна геометрична задача, подходяща за изучаване още в училище. Задача, в която се търси точка от дадена права или в общия случай от изпъкнала крива, за която сумата от разстоянията 3 до няколко (две или повече) други точки е минимална, представлява обобщение на задачата на Heron и затова тук ще бъде наричана задача от тип Heron.

Следват примери на три задачи от тип Heron.

Задача 5. Структурата и организацията на пощенските услуги в една държава е следната (фиг.5). Територията на държавата е разделена на \(n(n \gt 2)\) отделни области. В рамките на всяка област има изградена областна пощенска станция (ОПС). Пощенските пратки (писма и колети) се събират и се разнасят до жителите на една и съща област чрез специализирани пощенски автомобили. Ако една пощенска пратка е адресирана до лице от друго селище в същата или друга област, тогава тя се изпраща до съответната ОПС. Областните станции комуникират помежду си чрез централна пощенска станция (ЦПС, т. нар. и хъб), в която ежедневно чрез хеликоптери се пренасят пощенските пратки от и до съответните ОПС, за които адресът на подателя и получателя са от различни области на държавата или евентуално от друга държава. За да се оптимизират разходите по транспортирането на пощенските пратки между ОПЦ и ЦПЦ, е необходимо да се избере място за хъб непосредствено до определена магистрала, така че сумата от разстоянията от всички ОПС до ЦПС да е минимална. Да се пресметнат координатите на новата ЦПС, ако се познават координатите на всяка ОПС и се приеме, че магистралата се описва с линейна функция.

Задача 6. В прав участък от линията на едно метро трябва да се проектира метростанция, която да облужва жителите на квартал, живеещи в \(n\) жилищни блока. Те са разположени от двете страни на линията в рамките на правоъгълна площ с дадени размери. Улиците, по които гражданите могат да се придвижват до линията на метрото, са успоредни и вертикални на линията на метрото. Трябва да се определи точката от линията на метрото, в която да се проектира и построи метростанцията, така че сумата от разстоянията, които живеещите в тези блокове ще изминават до станцията, да е минимална. За всеки блок се предполага, че е представен с координатите на една точка и се знае броят на живеещите в него.

Задача 7. Много от жителите на \(n\) селища \(\mathrm{T}_{1}, \mathrm{~T}_{2}, \ldots, \mathrm{~T}_{n}\) работят в град, до който се достига по магистрала. Най-краткият път от селище \(\mathrm{T}_{i}(i=1,2, \ldots, n)\) излиза на магистралата в точка \(\mathrm{A}_{i}\), а разстоянието \(\mathrm{T}_{i} \mathrm{~A}_{i}\) е \(k_{i}\) километра (фиг. 6). За да се намалят транспортните разходи и да се намали трафикът на автомобили по магистралата, една компания иска да инвестира в построяването на паркинг непосредствено до магистралата.

Всеки абонат на паркинга може да паркира колата си, с която идва от дома си, и да продължи с автобус до града или да се присъедини с други абонати, за да формират група за придвижване до града само с един автомобил. Да се определи точката M от магистралата, на която да се построи паркингът, така че сумарното разстояние от селищата до паркинга, което се изминава от абонатите, да бъде минимално. Предполага се, че броят за абонатите на паркинга от селище \(\mathrm{T}_{i}\) е \(\mathrm{c}_{i}, i=1,2, \ldots, n\).

Решенията на тези примерни задачи имат практическа стойност, но за тях не е лесно да се посочи точно решение по подобие на решението на задачата на Heron. Ето защо в подобни случаи полезни могат да бъдат приближени решения, които да бъдат напълно задоволителни за реални практически нужди.

4. Един експеримент: приближено решение на задачата на Heron

По-долу е представен експеримент, при който пресмятането на минималната точка и на съответното разстояние в задачата на Heron ще се извърши по два начина.

Задача 8. Разглежда се задачата \(\mathrm{M}=\left(\mathrm{O} x ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\), в която точките \(\mathrm{P}_{1}, \mathrm{P}_{2}\) са определени с координатите си \(\left(x_{1}, y_{1}\right)\) и \(\left(x_{2}, y_{2}\right)\). Да се напише програма за приближено пресмятане на минималната точка и съответното минимално разстояние, като резултатът се сравни със стойностите, получени от точния метод, представен в задача 1.

Решение

Приемаме разглеждането на тази задача като експеримент. С него ще може да се сравнят точното и приближеното решение за конкретни точки, чиито координати са случайни числа. Експериментът се базира на два съществени факта от решението на основната задача. Знае се, че задачата има решение и то е единствено.

Реализацията на експеримента е извършена с програмния модул Heron, написан на С++. Във функцията approx се генерира редица от равноотдалечени точки \(\mathrm{T}_{i}\left(t_{i}, 0\right)\) с дадена стъпка \(h, t_{0}=\min \left(x_{1}, x_{2}\right) \leq t_{i} \leq \max \left(x_{1}, x_{2}\right), t_{i}=t_{i-1}+h, i=1,2, \ldots\) За всяка от точките \(\mathrm{T}_{i}\) се пресмятат разстоянията є до дадените точки \(\mathrm{P}_{1}\) и \(\mathrm{P}_{2}\) и като резултат функцията връща минималната точка и съответното разстояние.

Програмата е структурирана като програмен модул в три файла: заглавен файл, файл за реализация на функциите и главна функция, с която е проведен експериментът. Преобразуването на модула в C++ клас е тривиално, но това не е направено, за да не се усложнява излишно програмният код.

За по-компактен запис на кода в заглавния файл Heron.h „точката“ е дефинирана като структура (Point) със съответен конструктор и функция, отпечатваща текущата стойност на точка. Функциите project и distPP са помощни за функцията approx. С първата се пресмята ортогоналната проекция на точка върху права, минаваща през началото на кординатната система и сключваща даден ъгъл с оста Ox. Втората функция пресмята разстоянието между две точки. С функцията heron се пресмятат стойностите на минималната точка съгласно (2) и (3) от задача 2.

Същинският експеримент се извършва в главната функция на програмата. В нея за всяка стъпка \(h,\left(h=10^{-s}, \mathrm{~s}=0,1,2, \ldots, 7\right)\) двете точки се генерират десет пъти със случайни координати (\(x, y\) ) в интервалите: \(1 \leq\) \(x \leq 100\) и \(0 \leq y \leq 50\). За всяка двойка точки се пресмятат приближените и „точните“ стойности на минималната точка и на съответното минимално разстояние.

По-долу са приведени резултатите от изпълнението на програмата само за стъпки \(h=10^{0}, 10^{-4}\) и \(10^{-6}\). Отпечатани са абсолютните и средните грешки от пресмятанията, както и времето за изпълнение на функцията за съответната стъпка (табл. 2).

Таблица 2. Извадка от резултатите на експеримента от задача 8

Вижда се, че резултатите, получени от итеративния метод за приближено пресмятане на минималната точка и съответното разстояние, са много добри. Това дава основание функцията approx да се обобщи за \(n\) точки. Нейният прототип ще съдържа масив от \(n\) точки:

double approx(Point pts[], int n, double h, Point& p)

Самата дефиниция на функцията approx в по-голямата си част ще остане същата. Единствено операторът mD = distPP(p1, Point(t, 0.0)) + distPP(p2, Point(t, 0.0));

трябва да се замени с оператора:

mD = sumDist(pts, n, p), където параметърът T съответства на текущата точка от правата, която е кадидат за минималната точка. Следва кодът на функцията sumDist:

Положителният резултат от този експеримент е добър повод да се пристъпи към втори експеримент, в който правата \(l\) ще бъде заменена с изпъкнала крива и по-конкретно с дъга от окръжност.

5. Втори експеримент

Разглеждаме задачата от тип Heron \(\mathrm{M}=\left(\mathrm{k} ; \mathrm{P}_{1}, \mathrm{P}_{2}\right)\), в която k е дъга от окръжност. Целта е експериментално да се провери една хипотеза, чиято идея се основава на метода на Heron, а именно, че ъгълите между \(\mathrm{P}_{1} \mathrm{M}\) и \(\mathrm{P}_{2} \mathrm{M}\) с допирателната на окръжността k в т. M са равни (физичен закон за отражението). За тази цел разглеждаме следната задача.

Задача 9. Дадена е окръжност с радиус \(r\) и център в началото на правоъгълна координатна система, \(\mathrm{k}(\mathrm{O}, r)\). Дадени са и две точки в първи квадрант, определени с координатите си , \(\mathrm{P}_{1}\left(x_{1}, y_{1}\right)\) и \(\mathrm{P}_{2}\left(x_{2}, y_{2}\right)\).

a) Да се намери точка \(\mathrm{M}\left(x_{M}, y_{M}\right)\) от дъгата на окръжността k в първи квадрант (\(x \gt 0\), \(y \gt 0\) ), за която сборът от разстоянията от M до \(\mathrm{P}_{1}\) и \(\mathrm{P}_{2}\) да е минимален (фиг. 7).

б) За точката M, определена в а), да се провери дали \(∢ \mathrm{P}_{1} \mathrm{ML}_{1}\) е равен на \(∢ \mathrm{P}_{2} \mathrm{ML}_{2}\) в случая, когато правата \(\mathrm{L}_{1} \mathrm{~L}_{2}\) е допирателна към окръжността k в т. M. В тази задача ролята на правата \(l\) от предишните задачи е поета от допирателната \(L_{1} L_{2}\) към окръжността в точка M (фиг. 7). Но тъй като \(\mathrm{OM} \perp \mathrm{L}_{1} \mathrm{~L}_{2}\), за да се докаже, че \(\nless \mathrm{P}_{1} \mathrm{ML}_{1}=∢ \mathrm{P}_{2} \mathrm{ML}_{2}\), е достатъчно да се докаже, че . \(∢ \varphi_{1}=∢ \varphi_{2}\)

В зависимост от разположението на точките спрямо окръжността могат да се разгледат множество частни случаи (табл. 3).

На фиг. 7 е представен общият случай 7, който се има предвид при решението на задачата. Ще бъде използван опитът от задача 8 и координатите на минималната точка ще се пресметнат с приближение. Това се реализира с функцията approxK. Тя е твърде сходна с функцията approxL, но има един допълнителен параметър \(r\)– радиус на окръжността.

И тази функция, както и функцията approxL, може да се обобщи и броят на точките да е целочислен параметър \(n, n \gt 2\), а операторът mD = distPP(p1, p) + distPP(p, p2);

трябва да се замени с обръщение към функцията sumDist:

mD = sumDist(pts, n, p)

С функцията checkH се проверява дали ъглите са равни. Точността, с която се извършва проверката (сравняването на реалните числа), е определена от параметъра eps.

Алгоритъмът, заложен в кода на функцията checkH, използва зависимостите между ъглите на две пресичащи се прави с ъглови коефициенти съответно m1 и m2. Тогава за ъгъла между тях, изразен чрез ъглите θ1 и θ2, се получава:

\(\begin{aligned} & \theta=\theta_{2}-\theta_{1} \text { или } \theta=\pi-\left(\theta_{2}-\theta_{1}\right) . \\ & \operatorname{tg}(\theta)=\operatorname{tg}\left(\theta_{2}-\theta_{1}\right)=\cfrac{\operatorname{tg}\left(\theta_{2}\right)-\operatorname{tg}\left(\theta_{1}\right)}{1+\operatorname{tg}\left(\theta_{2}\right) \operatorname{tg}\left(\theta_{1}\right)}=\cfrac{m_{2}-m_{1}}{1+m_{1} m_{2}} \end{aligned}\)

В нашия случай трябва да се пресметнат ъгловите коефициенти \(m, m_{1}\) и \(m_{2}\) на правите \(\mathrm{OM}, \mathrm{P}_{1}\) М и \(\mathrm{P}_{2}\) М и съответно те са:

\(m=\cfrac{y_{M}}{x_{M}}, \quad m_{1}=\cfrac{y_{M}-y_{1}}{x_{M}-x_{1}}, \quad m_{2}=\cfrac{y_{M}-y_{2}}{x_{M}-x_{2}} \)

Следва кодът на функцията. По-долу следва главната функция на програмата.

Програмата е изпълнена многократно и резултатите на три от тях са дадени в табл. 4.

Таблица 4. Извадка от резултатите на експеримента от задача 9

Дотук всичко беше само експеримент върху една хипотеза. Резултатът от експеримента е отличен. Сега е ред хипотезата да се преформулира като теорема и да се докаже или... опровергае.

REFERENCES

Hadamard, J. (1962). Lectii de geometrie elementara. Geometrie plana, Editia a doua. Traducere din limba franceza completata cu resolvarile problemelor. Bucuresti: Editura tehnica.