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

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Детерминисткие или стохастические

• Статические  или динамические

• Сосредоточенные  или распределённые системы 

• Дискретные или непрерывные

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

Жесткие и мягкие модели.

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

Гармонический осциллятор — пример так называемой «жёсткой» модели. Она получена в  результате сильной идеализации  реальной физической системы. Для решения  вопроса о её применимости необходимо понять, насколько существенными  являются факторы, которыми мы пренебрегли. Иными словами, нужно исследовать «мягкую» модель, получающуюся малым возмущением «жёсткой». Она может задаваться, например, следующим уравнением: mddx/ddt=-kx+ef(x,dx/dt)

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

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

Универсальность моделей.

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

Прямая и обратная задачи математического моделирования.

Традиционно выделяют два основных класса задач, связанных с математическими  моделями: прямые и обратные.

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

В простейшем случае (одно уравнение осциллятора, например) прямая задача очень проста и сводится к явному решению этого  уравнения.

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

Математическое  моделирование в  экологии.

Математическое  моделирование в экологии– достаточно обширная область исследования и  по выбору объектов моделирования, и  по набору методов, и по спектру решаемых задач.

Первые исследования по применению математического моделирования в экологии относятся к двадцатым -тридцатым годам XX - го столетия. Исключение составляет работа Ферхюльста, появившаяся задолго до того, как сама экология сформировалась в виде целостной науки. Наиболее широкое использование математические модели в экологии получили с развитием электронно-вычислительной техники и методологии моделирования в конце шестидесятых годов.

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

Развитие  математико-экологических моделей  можно проследить по эволюции тех  научных и прикладных вопросов, для  ответа на которые эти модели создавались. Вопросы эти усложнялись по мере развития экологии и совершенствования методики моделирования. Если вначале сами вопросы и результаты математического моделирования представляли отвлеченный теоретический интерес, то в дальнейшем они стали носить конкретный практический характер.

Первой математической моделью была модель Ферхюльста, она  описывала численность популяции, ее динамику.

Классическими можно считать работы Райли, занимавшегося  моделированием фитопланктона с  учетом влияния освещенности и температуры  на основные физиологические процессы.

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

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

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

Математические  модели открытых систем.

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

Многочисленные примеры систем, в которых из хаотических состояний возникают высокоупорядоченные пространственные, временные или пространственно-временные структуры, известны в физике (лазеры, кристаллизация) и в химии (реакция Белоусова-Жаботинского).

Удивительно сложные, высокоупорядоченные структуры от кристаллов до организмов биосферы конструируются без "архитекторов", измерений и чертежей. Сейчас исследователям ясно, что образование таких структур является следствием нелинейных динамических взаимодействий внутри систем на стадии формирования при наличии некоторых внешних условий, основным из которых является подвод потока энергии извне.

Пространственные  структуры, возникающие в открытых системах, И. Пригожин назвал диссипативными. Развито новое научное направление, названное Г. Хакеном (1980) синергетикой (наука о явлениях кооперативности), целью которого является точное количественное описание процессов развития и самоорганизации систем.

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

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

Берущая начало от работ А. Лотки (Lotka, 1925) и В. Вольтерры (1931) математическая экология накопила большой арсенал моделей исследования временных закономерностей, цикличностей в экосистемах. В последние годы развиваются модели и методы изучения пространственной структуры популяций и сообществ.

Основы анализа  пространственно-временных структур в биохимических системах заложены в работах А. Тьюринга и И. Пригожина.

Традиционным  объектом эколого-математического моделирования является фитопланктон, кинетические процессы роста которого хорошо изучены количественно, а причины наблюдаемого в природе пространственно-временного структурирования не вполне ясны.

Следует отметить, что математическое моделирование  не подменяет собой экспериментальные исследования, а, напротив, стимулирует накопление фактического материала, уточняет направление проводимых экспериментов.

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

Кроме этого, уравнения содержат количественные выражения принятых гипотез о специфических экологических процессах (рождаемости, смертности, питания).

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

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

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

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

Первая в  математической экологии работа, направленная на изучение пространственной неоднородности, принадлежит Дж. Скеламу (Skellam, 1951). Им исследованы процессы распределения планктона в природных и лабораторных условиях.  

Модели  и методы анализа  пространственно-временных  структур.

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