ОТ ПОПУЛЯРНОЙ МАТЕМАТИКИ К ПРОБЛЕМАМ ЛОГИКИ И МАТЕМАТИКИ
Вопросы для желающих стать миллионером и не только, думающих о методах
(с этими задачами сталкиваются инженеры, экономисты, менеджеры, специалисты по логистике, а можно задуматься математикам и когнитологам) { >>} Все виды заданий серии
Настоящие тесты, разработанные А.А. Борзых,
являются элементами учебно-методического комплекса в тренинговых программах ИНКЦентра. В апробации тестов участвуют слушатели семинаров
"Инновационно- консалтингового центра", РГСУ и участники клуба
"Математический склад ума и когнитология: задачи из жизни и их формализация"
.
Логистическая транспортная сеть коммивояжера
("прикладные задачи коммивояжера")
На рисунке вы видите не слишком сложную транспортную сеть (сама схема и числовые значения в ней - просто пример).
Расстояния между пунктами известны (показаны возле стрелок- путей).
Коммивояжер (разъездной торговец) , живущий в пункте #1, должен доехать на склад, находящийся в пункте #22 , где ему по ж/д поступают грузы, а затем
посетить все пункты, имеющиеся в этой сети (в данном случае #2,#3 и #4), и вернуться к исходному пункту #1 (домой).
В каком порядке коммивояжер должен посетить эти пункты, то есть как он проложит свой маршрут объезда сети из п.1 для выполнения задачи получения груза в п.2 и
дальнейшей доставки товаров по всем пунктам?
.
Те, кто сталкивался с подобными задачами в вузовском курсе математики или в популярных книгах, а так же на нашем сайте, отметят, что
эта задача похожа одновременно на задачу нахождения минимального маршрута между заданными точками сети
и на задачу коммивояжера по объезду всей сети.
Те, кто решал вышеуказанные задачи-предшественники, заметили, что, собствено говоря, решение таких задач сводится к выработке некоторого алгоритма перебора маршрутов, в котором при поиске оптимального
маршрута в общем случае учитывать и возможности петель в маршрутах (с которыми мы так часто сталкиваемся в жизни).
Итак, нужно выработать еще один алгоритм подбора.
Для начала, все-таки, найдите самый короткий маршрут объезда и найдите его длину!
Сколько же километров, по выбранному вами кратчайшему маршруту, проедет коммивояжер?
Настоящая WWW-страница создана 29 марта 2011 г. This page is opened at 29 March 2011.
, 
