Задачи модели и ЭВМ

59

Задачи, модели и ЭВМ

Кандидат физико-математических наук
А. Г. ГЕИН,
А. К. КОВАЛЬДЖИ,
кандидат физико-математических наук
М. В. САПИР

Наверняка все читатели «Кванта» знают, что ЭВМ обладает фантастической скоростью счета, освобождая нас от громозdkих и утомительных вычислений. В то же время вы постоянно слышите о том, что ЭВМ использует для произвольания пододы и управления производством, для рисования мультфильмов и розыска представников, т. е. для решения задач, с вычислениями как будто и не связанных. Как же это удается? Ведь здесь явное противоречие! И действительно — противоречие. Преддолевать его бывают весы не просто. О том, как применять ЭВМ для решения невычислительных задач, поедет речь в цикле статей, который начинается в этом номере «Кванта».

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

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

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

60

в райисполкоме и вам поручено решить эту задачу, воспользовавшись услугами ЭВМ. Что для этого нужно? Прежде всего надо помнить: ЭВМ не может ничего другого, кроме как выполнять ваши инструкции, алгоритмы, и то если они сормулированы на понятном ей языке. А для составления алгоритма нужно знать, что дано, что требуется получить, как связанные исходные данные и результаты, а также какие команды можно использовать. Иначе говоря, задача должна быть четко сормулирована.

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

Постановки задач

Это только в школьных задачах сразу ясно, что дано и что требуется получить. В жизни все сложнее. Опыт буквально кричит о том, как трудно правильно поставить задачу: не перепростить и не пересложить, не упустить важных исходных данных и не включить лишних, сорзмерить железное свозможным.

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

Или еще задача: составить расписание уроков в школе. Каковы исходные данные для этой задачи? Это зависит, конечно, от требований, предъявляемых к расписанию. Потребовать, чтобы два разных урока не проискодили в одно и то же время в одном классе? Тогда исходных данных будет немного: список учебных предметов для классов классов в каждой параллели. При этом, правда, может служиться так, что одному классу предмета изучать только математику, другому — только географию, а учитель литературы вряд ли будет доволен, если ему поручат вести уроки физики. Попробуйте сами четко сормулировать задачу составления школьного расписания. Думаем, что после этого вы будете с сочувствием относиться к нелегкому труду завуча, который решает эту задачу каждые полгода.

Эти двух примеров, наверное, достаточно, чтобы понять: постановка задачи — важная часть (иногда говорят — половина) ее решения. Ставя задачу, надо сормулировать те предположения, которые позволят в море информации об изучаемом объекте выдить исходные данные, определить, что будет служить результат и какова связь между исходными данными и результатом. Все это — предположения, исходные данные, результаты и связи между ними — называют моделью задачи.

Далеко не всегда заранее ясно, какие свойства объекта оказывается существенным для решения задачи. Вот, скажем, старинная задача.

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

Формализуем задачу. Сразу можно сормулировать следующие предположения: удар топора — прямолинейный разрез, подкова — некоторая дуга, части подковы после удара оста-

61

ются на месте и не деформируют. Значит, надо нарисовать дуг и рассечь ее двумя прямыми. Мы четко поставили задачу, и нетрудно убедиться, что больше пяты части не получится (рис. 2).

Одноко в книжке Е. И. Игнатева «В царстве смекалки» (М., Наука, 1982) в подобной задаче требуется разрубить подкову на шесть части и приведен другой рисунок (рис. 3; хорошего, когда есть ответ!). Оказывается, мы слищом абстрагировались и не учили, что у подковы есть еще и ширина. Итак, в нашей модели надо предположение, что подкова — дуга, заменить на такое: подкова — половина колыца.

Одноко, продолжая в том жедуxe, можно сообщить, что у подковы есть еще и толщина (рис. 4), а тогда уdar toropa — плоский разрез. На сколько части можно разбить подкову, если учеть толщину? У нас получилось 7 части.

Уражение 1. Двумя уdarami toropa разрубите подкову на 7 части.

А может быть, в действительности ответ еще больше? ЧERO бы еще учеть? Конечно же, дырки! Ведь у подковы есть дырки для гвоздей (рис. 5). В успех трудно поверить, но получается 11 части!

Уражение 2. Двумя уdarami toropa разрубите подкову на 11 части.

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

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

Уражение 3. Докажите, что подкову, изобравенную на рисунке 6, нельзя разрубить двумя уdarami toropa на большие число части, чем подкову на рисунке 5.

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

Рис. 2.
Рис. 3.
Рис. 4.
Рис. 5.
Рис. 6.

62

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

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

Итак, составить хорошо модель задачи — дело непростое. Далее решать эту задачу представить вам самим. А если задачу надо будет объяснить компьютеру? В этом случае придется учитывать «способности» ЭВМ, а точнее — возможности того языка, на котором вы будете с ней обяснять. Если ваша ЭВМ имеет только вычислить, то, высказывая представления об объекте, нужно позаботиться о том, чтобы исходные данные и результаты были числами, а связи между ними — математически соответствия. Выполнить такой «перевод» задачи на язык математики, вы получите модель, которую обещано называть математической моделью.

Mathematical models

Теперь мы можем вернуть к нашей задаче о станции. Начнем, естественно, с построения математической модели. Прежде всего высказываем представления. Будем считать, что участок дороги, проходящий по территории района, прямолинен, в любом месте участка можно построить станцию и соединить ее прямолинейными дорогами с каждым населенным пунктом $A_1$, $A_2$, …, $A_n$.

Теперь надо уяснить слов «наибольшее удобное расположение станции». Как это понimatь? Если стремиться к экономии средства на строительство дорог, то станцию надо расположить так, чтобы суммарнаялина дорогог, соединяющих станцию с населенными пунктами, была наименьшей. Если же стремиться к максимальной справедливости, то место для станции естественного выбрать так, чтобы наиболее из расстояний от нее до населенных пунктов было как можно меньше. Например, если в самом дальней от станции населенном пункте заболеет человек, то его надо доставить на станцию за само короткое время.

Мы за справедливость, как и поэтому избегем второй принцип.

Уражение 4. а) Покажите, что эти два причины приводят к различным результатам.

6. Как должны быть расположены два населенных пункта, чтобы эти причины дали одинаковые результаты?

Задача на исследование. Решить упражнение 4 б в случае произвольного числа населенных пунктов.

Предположения сделаны, определим, что будет исходными данными, а что — результатом в нашей математической модели. К счастью (а точнее — намеренно), предположения таковы, что мы легко можем перевести нашу задачу на язык чисел. Для этого нарисуем оси координат на карте района так, чтобы ось абсцисс проходила по интересущему насучкту железной дороги, а начало координат совпадало с его левым концом. Используем данными, конечно, являются число $n$ населенных пунктов, их координаты $(a_1; b_1), (a_2; b_2), ..., (a_n; b_n)$ илина $S$ участва железной дороги, пропелασшей по району. Результат — абсцисса точки, где надо строить станцию (рис. 7).

Остается найти соответствия между населенными данными и результатом.

63

Возьем любую точку на отрезке, изображаемем железную дорогу. Пусть $t$ — ее абсцисса. Через $Z$ обозначим максимальное из расстояний между этой точкой и каждой из насееленных пунктов:

$$Z = \max \left\{ \sqrt{(t-a_1)^2 + b_1^2}, \right. \\ \sqrt{(t-a_2)^2 + b_2^2} ; \dots ; \sqrt{(t-a_n)^2 + b_n^2} \}.$$

Ясно, что $Z$ — функция от $t$. Чтобы определить, где построить станцию, надо узнать, при каком $t$ из отрезка [0; $S$] функция $Z(t)$ принимает наименьшее значение.

Как видите, исходную задачу о станции мы заменили математической задачей: найти точку минимума некоторой функции. Эта задача и является математической моделью.

Как же найти точку минимума? Желательно могут, конечно, попытаться взять произвольную функцию $Z(t)$ и приравнять ее к нулю. Им предстоит предположить немало трудностей: функцию $Z(t)$ нельзя задать простой формулой, да и произвольная от нее, скорее всего, существует не во всех точках. Попробуем представить себе график функции $Z(t)$.

У разнение 5. Выберите произвольную координаты нескольких деревьев, а также длину отрезка железной дороги, и с помощью компьютера или микрокалькуляртора построите (по точкам) график функции $Z(t)$.

Нетрудно убедиться в том, что функция $Z(t)$ сначала убивает, а затем возрастает. Нам повезло: у нашей функции только одна точка минимума. Ее можно найти с любой точностью, воспользоваться следующим методом. Разобем отрезок [0; $S$] на равные части, длину каждой из них обозначим буквой $r$. Затем найдем значения $Z$ при $t=0, r, 2r, \dots$ и так далее до $t=S$. Выберем из этих значений наименьшее и возместить результата $t$, при котором оно достигается. Это значение $t$ будет отличаться от «истинного» результата не больше чем на $r$.

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

Следующая простота точности. Результат получается лишь приближению: чем меньше $r$, тем точнее. Впрочем, нет смысла гнаться за особой точностью — ведь в действительности и железная дорога не прямая, и координаты деревьев известны лишь приближенно, и Земля, как известно, не плоская, а самое главное — и станция, и деревни не являются точками.

Правда, использую геометрические построения, можно найти и «точное» решение.

Уражнение 6. На плоскости заданы $n$ точек и отрезок. Используя лишь циркуль и линейку, найти отрезке такую точку, чтобы наиболее из расстояний от нее до заданных точек было бы наименьшим.

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

Уражнение 7. Составьте математическую модель задачи о станции, основываясь на этом принципе.

Задча на исследование. На плоскости заданы $n$ точек и отрезок. Построить на отрезке такую точку, чтобы сумма расстояний от нее до заданных точек была бы наименьшей.

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

1. выделить предложения, на которых будет основана математическая модель;
2. определить, что считать исходными данных и результаты;
3. записать математические соответствия (формулы, уравнения, неравенства и т. д.), связывающие результаты с исходными данных.

Как видите, математическая модель всегда основана на некоторых принципах. Однако благодая замене

64

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

Модель построена. Что далее?

Созданием математической модели завершает первый этап решения задачи с помощью ЭВМ. Далее нужно написать соответствующий программу. Мы не будем рассказывать, как это делается — это зависит от возможности конкретной ЭВМ, реализованных на ней языков. Но затем надо убедиться, что модель соответствует реальному объекту. Такую уверенность можно обеспечить лишь в результате эксперимента. Проведяя вычисления на ЭВМ, необходимо проанализировать результаты. При этом может возникнуть необходимость уточнить математический модель, поскольку выяснить, что при ее разработке не были учтены какие-либо существенные свойства объекта. Уточнить модель, снова составляют программу, продолжать расчеты на ЭВМ и анализируют результаты. И опять может потребовать учтение модели. Так будет продолжаться до тех пор, пока анализ результатов не показет их соответствие изучаемому объекту.

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

Задание

1. Составьте математическая модель задачи о железнодорожной станции, руководствуясь компромиссным принципом: если $Z$ — расстояние от станции до наболее удаленного пункта, а $W$ — сумма расстояний до всех пунктов, то требуется сделать как можно меньше сумму $kZ+(1-k)W$, где $k$ — число из отрезка [0; 1] (степень компромисса).

2. Исследуйте задачу о железнодорожной станции для двух населенных пунктов, в одном из которых живет 1000 человек, в другом — 2000, руководствуясь таким принципом: общее число «человекокилометров», затрачиваемых населенением на путь до станции, должно быть наименьшим.

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

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

Завершите построение математической модели.

4. Школьник, не знающий теоремы Пифагора, составил следующее математическое модели для определения длины диагонали произвольного прямоугольного стола.

Предположения: поверхность стола считаем прямоугольником со стороны $a$ и $b$; длина диагонали $d$ приближено равна длине ломаной, изображенной на рисунке 8, если, конечно, ступеней у этой ломаной достаточно маленькие; при неограниченном увеличении числа ступеней величины диагонали получается с любой точностью. Тогда $d=a+b$ (деяствительно, длина ломаной в точности равна $a+b$ независяimo от того, сколько в ней ступенек).

Почему получился неверный результат: диагональ прямоугольника равна сумме его смежных сторон?

Темы вычислительных экспериментов (для программы)

Составьте программы, соответствующие расстояntenым в стате модели задачи о железнодорожной станции. Посмотрите, как изменяется место расположения станции при изменении числа $k$ в задаче 1 и при увеличении числа отрезков разбиения.