Задача об оптимальном месте для магазина

На рис. 3.16 помещен протокол решения задачи о поиске места для магазина на дачном участке. Критерий поиска — минимум суммы расстояний от магазина до всех остальных домиков. Их координаты X и y— случайные числа в интервале от 0 до 100 (наша задача— учебная). Магазин может быть либо встроен в один из домиков, либо стоять отдельно.

Рис. 3.16. Задача об оптимальном месте магазина в дачном поселке

На рис. 3.16 координаты встроенного магазина определяются перебором через функцию match (один из переводов с английского — "находить соответствие"). Затем эти координаты становятся первым приближением для уточнения местоположения отдельно стоящего магазина. Заканчивается расчет графической иллюстрацией— X-Y-графиком. Здесь главное— правильно отформатировать точки на графике: квадратики — дачи на участке, крестик — встроенный магазин и кружок — отдельно стоящий магазин.

Продолжением задачи о месте магазина среди дачных домиков является другая оптимизационная задача — задача коммивояжера (рис. 3.17).

Рис. 3.17. Задача коммивояжера

Эта задача сводится к нахождению порядка обхода всех дачных домиков по маршруту наименьшей длины. На рис. 3.17 задача коммивояжера решается с помощью функции anneal (отжиг), которая становится встроенной (но не описанной в диалоговом окне ввода встроенных функций) после подгрузки к Mathcad пакета Numerical Recipes. Парадокс задачи коммивояжера в том, что от многих точек (домиков — см. рис. 3.17) путь лежит не к ближайшей точке, а чуть ли не к самой дальней. На сайте книги дано раскрытие функции

anneal.

На сайте книги читатель найдет решение задачи коммивояжера встроенными средствами Mathcad по "жадному" и "муравьиному" алгоритмам.