Математические основы решение задачи коммивояжера

Введение.

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

Элементы  математического моделирования  использовались с самого начала появления  точных наук, и не случайно, что некоторые  методы вычислений носят имена таких  корифеев науки, как Ньютон и Эйлер, а слово алгоритм происходит от имени средневекового арабского ученого Аль-Хорезми. Второе рождение этой методологии пришлось на конец 40х - начало 50х годов 20 века и было обусловлено по крайней мере двумя причинами. Первая из них - появление компьютеров, хотя и скромных по нынешним меркам, но тем не менее избавивших ученых от огромной по объему рутинной вычислительной работы. Вторая - беспецендентный социальный заказ - выполнение национальных программ СССР и США по созданию ракетно-ядерного щита, которые не могли быть реализованы традиционными методами. Математическое моделирование справилось с этой задачей: ядерные взрывы и полеты ракет и спутников были предварительно осуществлены в недрах ЭВМ с помощью математических моделей и лишь затем претворены на практике. Этот успех во многом определил дальнейшие достижения методологии, без применения которой в развитых странах ни один крупномасштабный технический, экологически или экономический проект теперь всерьез не рассматривается.

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

Вопрос математического  моделирования можно разбить  на три этапа:

• составление  модели

• построение алгоритма 

• создание программы 

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

Второй этап - разработка алгоритма для реализации модели на компьютере.

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

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

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

Математическая  модель — это модель, созданная  с помощью математических понятий.

Математическое  моделирование — процесс построения и изучения математических моделей. Все естественные и общественные науки, использующие математический аппарат, по сути занимаются математическим моделированием: заменяют реальный объект его моделью и затем изучают последнюю.

Никакое определение  не может в полном объёме охватить реально существующую деятельность по математическому моделированию. Несмотря на это, определения полезны тем, что в них делается попытка выделить наиболее существенные черты.

Определение модели по А. А. Ляпунову: Моделирование  — это опосредованное практическое или теоретическое исследование объекта, при котором непосредственно  изучается не сам интересующий нас объект, а некоторая вспомогательная искусственная или естественная система (модель):

- находящаяся  в некотором объективном соответствии  с познаваемым объектом;

- способная  замещать его в определенных  отношениях;

- дающая при  её исследовании, в конечном счете, информацию о самом моделируемом объекте.

Классификация моделей.

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

Содержательная  классификация моделей.

Тип 1: Гипотеза (такое могло  бы быть).

Эти модели «представляют  собой пробное описание явления, причем автор либо верит в его  возможность, либо считает даже его  истинным». Например, модель Солнечной системы по Птолемею и модель Коперника (усовершенствованная Кеплером), модель атома Резерфорда и модель Большого Взрыва.

Никакая гипотеза в науке не бывает доказана раз  и навсегда. Очень чётко это  сформулировал Ричард Фейнман:

«У нас  всегда есть возможность опровергнуть теорию, но, обратите внимание, мы никогда не можем доказать, что она правильна. Предположим, что вы выдвинули удачную гипотезу, рассчитали, к чему это ведет, и выяснили, что все ее следствия подтверждаются экспериментально. Значит ли это, что ваша теория правильна? Нет, просто-напросто это значит, что вам не удалось ее опровергнуть.»

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

Тип 2: Феноменологическая модель (ведем себя так, как если бы…)

Феноменологическая  модель содержит механизм для описания явления. Однако этот механизм недостаточно убедителен, не может быть достаточно подтверждён имеющимися данными или плохо согласуется с имеющимися теориями и накопленным знанием об объекте. Поэтому феноменологические модели имеют статус временных решений. Считается, что ответ всё ещё неизвестен и необходимо продолжить поиск «истинных механизмов». Например, модели теплорода и кварковую модель элементарных частиц.

Роль модели в исследовании может меняться со временем, может случиться так, что  новые данные и теории подтвердят феноменологические модели и те будут повышены до статуса гипотезы. Аналогично, новое знание может постепенно прийти в противоречие с моделями-гипотезами первого типа и те могут быть переведены во второй. Так, кварковая модель постепенно переходит в разряд гипотез; атомизм в физике возник как временное решение, но с ходом истории перешёл в первый тип. А вот модели эфира, проделали путь от типа 1 к типу 2, а сейчас находятся вне науки.

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

Тип 3: Приближение (что-то считаем очень  большим или очень  малым)

Если можно  построить уравнения, описывающие  исследуемую систему, то это не значит, что их можно решить даже с помощью  компьютера. Общепринятый прием в  этом случае — использование приближений (моделей типа 3). Среди них модели линейного отклика. Уравнения заменяются линейными. Стандартный пример — закон Ома.

Если мы используем модель идеального газа для описания достаточно разреженных газов, то это  — модель типа 3 (приближение). При более высоких плотностях газа тоже полезно представлять себе более простую ситуацию с идеальным газом для качественного понимания и оценок, но тогда это уже тип 4.

Тип 4: Упрощение (опустим  для ясности некоторые  детали)

В модели типа 4 отбрасываются детали, которые могут заметно и не всегда контролируемо повлиять на результат. Одни и те же уравнения могут служить моделью типа 3 (приближение) или 4 (опустим для ясности некоторые детали) — это зависит от явления, для изучения которого используется модель. Так, если модели линейного отклика применяются при отсутствии более сложных моделей (то есть не производится линеаризация нелинейных уравнений, а просто ищутся линейные уравнения, описывающие объект), то это уже феноменологические линейные модели, и относятся они к следующему типу 4 (все нелинейные детали «для ясности» опускаем).

Примеры: применение модели идеального газа к неидеальному, уравнение состояния Ван-дер-Ваальса, большинство моделей физики твердого тела, жидкостей и ядерной физики. Путь от микроописания к свойствам тел (или сред), состоящих из большого числа частиц, очень длинен. Приходится отбрасывать многие детали. Это приводит к моделям 4-го типа.

Тип 5: Эвристическая модель (количественного  подтверждения нет, но модель способствует более глубокому проникновению в суть дела)

Эвристическая модель сохраняет лишь качественное подобие реальности и даёт предсказания только «по порядку величины». Типичный пример — приближение средней  длины свободного пробега в кинетической теории. Она даёт простые формулы для коэффициентов вязкости, диффузии, теплопроводности, согласующиеся с реальностью по порядку величины.

Но при  построении новой физики далеко не сразу получается модель, дающая хотя бы качественное описание объекта —  модель пятого типа. В этом случае часто используют модель по аналогии, отражающую действительность хоть в какой-нибудь черте.

Тип 6: Аналогия (учтём только некоторые особенности)

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

Тип 7: Мысленный эксперимент (главное  состоит в опровержении возможности)

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

Тип 8: Демонстрация возможности (главное  — показать внутреннюю непротиворечивость возможности).

Это тоже мысленные  эксперименты с воображаемыми сущностями, демонстрирующие, что предполагаемое явление согласуется с базовыми принципам и внутренне непротиворечиво. В этом основное отличие от моделей типа 7, которые вскрывают скрытые противоречия. Один из самых знаменитых таких экспериментов — геометрия Лобачевского. Другой пример — массовое производство формально — кинетических моделей химических и биологических колебаний, автоволн и др.

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

Формальная  классификация моделей.

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

• Линейные или нелинейные модели