Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Побудова моделі

Читайте также:
  1. OSI Эталондық моделі
  2. Бейбітшілік моделі. Рим клубы
  3. Визначення та моделі стилю керівництва.
  4. Внутрішня побудова фінансової системи України.
  5. Дослідження залишків побудованої моделі на адекватність
  6. ЕКОЛОГІЧНІ МОДЕЛІ
  7. Захист прав на винаходи, корисні моделі і промислові зразки
  8. Лекція 4. Моделі представництва інтересів.
  9. Лінійні регресійні моделі в програмах обробки ЕТ
  10. Математичні моделі, вимоги до математичних моделей та їх класифікація

Задача чітко поставлена, тепер потрібно сформулювати для неї математичну модель. Це дуже важливий крок у процесі розв’язання і його треба добре обміркувати. Вибір моделі істотно впливає на розв'язання інших етапів, оскільки усе, що ви пропустите зараз, доведеться робити потім, перериваючи роботу і повертаючи назад.

Як ви можете здогадатися, неможливо запропонувати набір правил, що автоматизують стадію моделювання. Вибір моделі більше справа мистецтва, ніж науки і, ймовірно, ця тенденція збережеться. Це один з безлічі випадків, коли необхідне застосування творчих здібностей людини. А найкращий спосіб придбати досвід у моделюванні – вивчення вдалих моделей. Але, і в цій справі існують кілька корисних керуючих принципів.

Приступаючи до розробки моделі, варто задати, принаймні, два основних питання:

1. Які математичні структури більше всього підходять для задачі?

2. Чи існують вирішені задачі?

Друге питання, можливо, саме корисне у всій математиці. У контексті моделювання воно часто дає відповідь на перше питання. Дійсно, більшість розв'язуваних у математиці задач, як правило, являють собою модифікації уже вирішених. Більшість з нас просто не мають талант Ньютона, Ейнштейна чи Гауса, і для просування вперед нам доводиться керуватися накопиченим досвідом.

Спочатку розглянемо перше питання. Ми повинні математично описати, що нам відомо, і що хочемо знайти. На вибір відповідної структури будуть впливати такі фактори, як:

· обмеженість наших знань відносно невеликою кількістю структур;

· зручність представлення;

· простота обчислень;

· корисність різних операцій, зв'язаних з розглянутою структурою.

Зробивши пробний вибір математичної структури, задачу варто переформулювати в термінах відповідних математичних об'єктів. Це буде одна з можливих моделей, якщо ми можемо позитивно відповісти на наступні питання:

1. Чи уся важлива інформація добре описана математичними об'єктами?

2. Чи існує математична величина, що асоціюється із шуканим результатом?

3. Чи виявили ми які-небудь корисні відносини між об'єктами моделі?

4. Чи зручно працювати з моделлю?

У переважній більшості випадків доцільним на даному етапі є застосування декомпозиції задачі.

Принцип декомпозиції – один із широко застосовуваних прийомів до технології програмування. Він полягає в тому, що складна задача розбивається на підзадачі поменше (а ті – на ще більш дрібні і т.д.). Це дає можливість надалі складати алгоритми для розв'язання задачі вроздріб, що значно полегшує роботу.

Приклад [ ]:

Повертаємося до задачі комівояжера. Починаємо з постановки задачі, заданої наприкінці приклада.

Чи вирішували ми коли-небудь подібні задачі? З математичного боку, ймовірніше за все, ні. Однак усі ми зіштовхувалися з задачами вибору шляху за картами доріг чи у лабіринтах. Чи можемо ми перейти до зручного представлення нашої задачі у виді карти?

Очевидно, потрібно взяти лист паперу і нанести на нього ряд точок, що відповідають кожному місту. Щоб не ускладнювати собі задачу, ми не будемо зображувати точки так, щоб відстань між кожною парою точок, що відповідають містам i і j, було пропорційно вартості проїзду Cij. Розташуємо точки будь-яким зручним способом, з'єднаємо точки i і j лініями і проставимо на них «ваги» Cij.

Схема, що ми тільки що зобразили, - це окремий випадок відомого в математиці графа, чи сітки. У загальному випадку сітка – це безліч точок (на площині) разом з лініями, що з'єднують усі чи деякі пари точок; над лініями також можуть бути проставлені ваги.

Припустимо також, що вартість проїзду з i в j дорівнює вартості проїзду з j в i, хоча це і необов'язково.

Що ми шукаємо в задачі? У термінах теорії графів список міст (який ми раніше описали) визначає замкнутий цикл, що починається з базового міста і повертається туди ж після проходження всіх міст по одному разу. Такий цикл відповідає спрямованому руху олівця уздовж ліній сітки, що починається і закінчується в одній і тій же точці. Обхід такого роду назвемо туром. Вартість туру визначається як сума ваг усіх пройдених ребер. Задача буде вирішена, якщо ми зможемо знайти тур з мінімальною вартістю.

Розглянута задача відома в літературі як задача комівояжера; вона стала якоюсь мірою класичною. Це один з найбільш відомих прикладів задач, що дуже легко поставити і промоделювати, але дуже важко вирішити.




Дата добавления: 2015-01-30; просмотров: 25 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав