Поиск кратчайшего пути в графе.

Найти кратчайший путь из узла 1 в узел 10 на сети дорог показанной на рисунке 3.19. Затраты на отдельных участках сети показаны на дугах [8].

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

Рис. 3.19. Поиск кратчайшего пути в графе

Вычислительный метод можно представить в виде так называемого динамического рекуррентного соотношения: , где – стоимость, отвечающая стратегии минимальных затрат прохода до узла k; – то же до узла n, из которого до узла k один шаг (дуга); – затраты по дуге kn. Данное выражение означает, что на каждом этапе расчета должны быть вычислены все возможные значения стоимости, суммированием соответствующей стоимости для очередного шага пути (переезда из пункта n в пункт k), и стоимости, отвечающей оптимальной стратегии выбора пути к узлу n.

Вычисленные суммы следует сравнить между собой и выбрать такой путь, для которого значение этой суммы минимально – «оптимальная цепочка состоит из оптимальных звеньев».

В простейших случаях вычислительный процесс может быть реализован в форме таблицы (рис. 3.20). В задачах большой размерности используется вычислительная техника.

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

Шаг	Формулы	Расчет
	f10=min(c10,8+f8,c10,9+f9)	f10=min(1+17,4+13)=17 оптимальной стратегии соответствует путь в узел 10 (конец пути) из узла 9
	f8=min(c5,8+f5,c6,8+f6,c7,8+f7)	f8= min(8+10,3+14,7+12)=17, оптимальной стратегии соответствует путь в узел 8 из узла 6
	f9=min(c5,9+f5,c6,9+f6,c7,9+f7)	f9= min(5+10,4+14,1+12)=13, оптимальной стратегии соответствует путь в узел 9 из узла 7
	f5= min(c2,5+f2,c3,5+f3)	f5= min(10+2,5+5)=10, оптимальной стратегии соответствует путь в узел 5 из узла 3
	f6=min(c2,6+f2,c3,6+f3,c4,6+f4)	f6=min(12+2,10+5,15+1)=14, оптимальной стратегии соответствует путь в узел 6 из узла 2
	f7=min(c3,7+f3,c4,7+f4)	f7=min(7+5,13+1)=12, оптимальной стратегии соответствует путь в узел 7 из узла 3
	f2= c1,2	f2= 2
	f3= c1,3	f3= 5
	f4= c1,4	f4= 1

Рис. 3.20. Реализация метода динамического программирования в табличном виде

Оптимальное решение:

- оптимальный путь в конечный узел 10 идет из узла 9,

- оптимальный путь к узлу 9 идет из узла 7,

- оптимальный путь к узлу 7 идет из узла 3,

- в узел 3 можно попасть из начального узла 1 по единственному пути.

Кратчайший путь проходит через узлы 1-3-7-9-10.

Величина критерия равна 17.

4. ПРОБЛЕМЫ ПРОГРАММНЫХ РЕАЛИЗАЦИЙ

В вычислительной математике «методов нет, если понимать метод как совокупность инструкций, следуя которым можно решить задачи данного типа. В данной дисциплине рассматриваются не методы, а скорее подходы к решению поставленных прикладных задач, разработанные вплоть до мельчайших деталей и многократно опробованные» [1].

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

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

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

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

Созданию любого объекта предшествует его проектирование.

«Интеграция средств вычислительной техники и технических наук в некоторой системе, функционирующей на базе ЭВМ, приводит к автоматизации процессапроектирования в рамках автоматизированного проектирования (АПР)» [10].

Разработку программных АПР можно рассматривать как последовательность определенных действий:

- определение требований;

- составление спецификации (технического задания);

- проектирование логики (алгоритм);

- программирование (кодирование);

- тестирование;

- документирование.

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

Определение требований к программному средству обычно выносится за пределы собственно его проектирования (на предпроектную стадию).

Типичное распределение затрат на разработку программного обеспечения показано на рис. 4.1.а (США) и рис. 4.1.б (РФ) [10, 11].

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

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

При этом речь идет не об исправлении элементарных программных ошибок, для чего предусматривается этап тестирования (отладки).

Доработка программного обеспечения на этом этапе предполагает поиск и исправление ошибок двух типов:

- ошибки реализации - возникающие в процессе конструирования, составления спецификации (технического задания), при проектировании и запросе ресурсов;

- ошибки логики - отсутствие некоторых сегментов в потоке управления, ошибочные условия, ошибочные функции или отсутствие функций.

Рис. 4.1. Распределение затрат на разработку программного обеспечения.

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

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

Эффективность используемых средств АПР,и соответственно, используемых в них математических методов основывается исключительно на реализуемой стабильности получения результатов, не противоречащих здравому смыслу, то есть не имеющих явных резервов улучшения и однозначно воспринимаемых проектировщиком («лицом, принимающим решения») как рациональные. С математической точки зрения это оптимальные проектные решения.

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

СПИСОК ЛИТЕРАТУРЫ

1. Федоренко Р.П. Приближенное решение задач оптимального управления. – М.: Наука, 1978. – 488 с.

2. Малюх В.Н. Введение в современные САПР. Курс лекций. – М.: ДМК Пресс, 2012. – 192 с.

3. Дьяконов В. MathCad2001: учебный курс. – СПб.: Питер, 2003. – 621 с.

4. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1973, 360 с.

5. Банди Б. Методы оптимизации. Вводный курс. – М.: Радио и связь, 1988. – 128 с.

6. Струченков В.И. Методы оптимизации. Основы теории, задачи, обучающие комплексы. Учебное пособие. – М:. Издательство «Экзамен», 2005. – 256 с.

7. Стенбринк Петер А. Оптимизация транспортных сетей. – М.: Транспорт, 1981. – 320 с.

8. Оре Ойстин. Графы и их применение. Изд. 2-е, стереотипное. – М.: Едиториал УРСС, 2002. –168 с.

9. Вагнер Г. Основы исследования операций. В 3-х т. – М.: Мир, 1973.

10. Энкарначчо Ж., Шлехтендаль Э. Автоматизированное проектирование. Основные понятия и архитектура систем. – М.: Радио и связь, 1986.– 288 с.

11. Кудряшов И.А. и др. Программирование, отладка и решение задач на ЭВМ единой серии. – Л.: Энергоатомиздат, Ленингр.отд-ние, 1988. –208 с.

СОДЕРЖАНИЕ:

Введение. 3

1. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ 4

2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ.. 7

2.1. Моделирование случайных процессов. 8

2.1.1. Теория вероятностей, основные понятия и определения. 8

2.1.2. Математическая статистика. 12

2.2. Сортировка. 17

2.3. Интерполяция табличных зависимостей. 20

2.4. Аппроксимация. 22

2.4.1. Полиномиальная аппроксимация. 23

2.4.2. Линейная аппроксимация. 24

2.4.3. Метод наименьших квадратов для произвольной функции. 25

2.5. Сглаживание данных. 25

2.6. Экстраполяция данных (предсказание) 27

2.7. Численное дифференцирование. 27

2.8. Вычисление определенного интеграла. 28

2.9. Численное решение дифференциальных уравнений. 30

2.10. Моделирование рельефа местности. 37

2.11. Моделирование продольного профиля и плана при реконструкции железных дорог. 41

3. МАТЕМАТИЧЕСКИЕ МЕТОДЫ.. 48

3.1. Реализация численной модели на ЭВМ.. 48

3.2. Целевая функция. Ограничения. 50

3.3. Оптимизация без ограничений. 53

3.3.1. Прямой одномерный поиск. 53

3.3.2. Прямой многомерный поиск. 59

3.4. Оптимизация с ограничениями. 63

3.5. Линейное программирование. 66

3.6. Нелинейное программирование. 72

3.7. Многошаговые процессы на графах. 74

3.8. Динамическое программирование. 76

4. ПРОБЛЕМЫ ПРОГРАММНЫХ РЕАЛИЗАЦИЙ.. 81

СПИСОК ЛИТЕРАТУРЫ.. 85

Св. план 2012 г., поз.142

Виталий Алексеевич Бучкин

Екатерина Александровна Рыжик

МАТЕМАТИЧЕСКИЕ МОДЕЛИ

В ИНЖЕНЕРНЫХ РАСЧЕТАХ

Конспект лекций

[1]Киберне́тика (от др.- греч. κυβερνητική – «искусство управления») – наука об общих закономерностях процессов управления и передачи информации в различных системах, будь то машины, живые организмы или общество.

[2] CAD– Computer-Aided Design – дизайн (замысел, план, намерение, цель) с помощью компьютера – термин, используемый для обозначения широкого спектра компьютерных инструментов помогающих в осуществлении проектирования

[3] Леона́рдо Пиза́нский (около 1170 года – около 1250 года) — первый крупный математик средневековой Европы. Более известен под прозвищем Фибона́ччи. Исследовал ряд чисел, в котором каждое последующее число равно сумме двух предыдущих (1202). С его именем связано начало введения в Европе десятичной системы счисления и арабских цифр в бухгалтерский и вообще финансовый учет.

[4] Золотое сечение (золотая пропорция, деление в крайнем и среднем отношении) –деление непрерывной величины на две части в таком отношении, при котором меньшая часть так относится к большей, как большая ко всей величине. Деление отрезка в крайнем и среднем отношении впервые встречается у Евклида (ок. 300 лет до н. э.).

[5] Все методы математического программирования (линейного, нелинейного, динамического) были разработаны на заре «компьютерной эры», т.е. до массового применения вычислительной техники. Слово «programming» можно перевести на русский язык как «планирование», так они и назывались – динамическое планирование и т.п. Термин «планирование» был заменен на «программирование» позднее и вряд ли обосновано. Это математические методы, их можно программно реализовать, но непосредственно к написанию программного кода они отношения не имеют.

[6] Применение любого метода вычислительной математики приводят к получению приближенного решения, Однако, для одних методов достижимость и точность решения доступна оценке и управлению, для других – носит предположительный характер. Методы второго типа принято называть эвристическими от латинского Evrica– «отыскиваю», «открываю». Эвристические методы достаточно часто (в основном, при отсутствии альтернатив) применяются для решения прикладных задач. Например, все известные алгоритмы триангуляции Делоне (см. § 2.10) – эвристические, точного решения здесь пока не найдено.