Материал: Основы математического моделирования. методические указания к выполнению контрольной работы для студентов направления Машиностроение. Бырдин А.П., Костина Т.И

2. Аппроксимируем таблично заданную функцию y f (x) квадратичной

Предварительно вычисляем:

6

xk 0,5 1 1,5 2 2,5 3 10,5,

k1 6

xk2 0,25 1 2,25 4 6,25 9 22,75,

k1 6

xk3 0,125 1 3,375 8 15,625 27 55,125,

k1 6

xk4 0,0625 1 5,0625 16 39,0625 81 142,1875,

k1 6

yk 0,31 0,82 1,29 1,85 2,51 3,02 9,8,

k 1

6

xkyk 0,5 0,31 1 0,82 1,5 1,29 2 1,85 2,5 2,51 3 3,02 21,94.

k 1

6

xk2yk 0,25 0,31 1 0,82 2,25 1,29 4 1,85 6,25 2,51 9 3,02 54,0675.

k 1

Получим систему уравнений вида

6A0 10,5A1 22,75A2 9,8;

10,5A0 22,75A1 55,125A2 21,94;

22,75A0 55,125A1 142,1875A2 54,0675.

Решая эту систему, находим A0, A1 и A2: A0 0,08, A1 0,74, A2 0,07.

Искомый многочлен y 0,08x2 0,74x 0,07.

21

Задача №2

Задание. Найти численное решение линейной краевой задачи для дифференциального уравнения 2-го порядка конечно-разностным методом, используя аппроксимацию производных второго порядка и шаг h 0,1.

Решение. Метод конечных разностей.

Разбив отрезок [2;2,3] на части с шагом h 0,1, получим четыре узловые точки с абсциссами x0 2; x1 2,1; x2 2,2; x3 2,3. Две точки x0 2 и x3 2,3 являются граничными, а две другие – внутренними. Данное уравнение во внутренних точках заменим конечно-разностным уравнением:

y3 2.15.

22

Подставив значение y3 в третье уравнение, получим для определения остальных неизвестных систему

Решая эту систему уравнений, получим

Задача №3

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

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

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

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

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

23

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

При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, или явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и непланарные графы. Планарный граф— это граф, который можно изобразить на рисунке (плоскости) без пересечения ребер (простейшие — треугольник или пара связанных вершин), иначе граф непланарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода ребер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих ребер и содержит одну корневую вершину, в которую нет входящего ребра.

Производственная задача, сводимая к задаче поиска пути на графе, возникает при выборе технологических маршрутов обработки деталей в гибкой производственной системе (ГПС).

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

Решение. Пусть O1,O2,...,On – последовательность операций, а C1,C2,...,Cm– станки ГПС. Построим орграф с вершинами s,t и вершинами для каждой операции Oi и каждого станка Ci , который может ее выполнить. Вер-

24

шины соединим дугами s ui,1, vi,n t, ui, j vi, j, vi, j uk, j 1 для всех до-

Рис. 1. Пример допустимых назначений операций на станки

Таблица 5 Допустимые назначения операций на станки

Рассмотрим пример построения орграфа при n 4, m 5. Допустимые назначения операций на станки определены ребрами двудольного графа на рис. 1 или в табл. 5, а время выполнения операций подходящими станками и время транспортировки представлены в табл. 6. Клетки, соответствующие недопустимым назначениям операции на станки, заполнены 0. Для удобства построения графа изобразим таблицу, где столбцы – это операции, а строки – станки. Начинаем построение из вершины «s», далее операция первая может быть выполнена на станке первом или четвертым, ставим в соответствующих ячейках направленный отрезок - дугу, затем соединяем вершину «s» с вершинами u11 и u4,1, считая время затраченное от старта до начала выполнения операции равное

0. После этого для вершины v11 есть три пути, так вторая операция может быть выполнена на трех станках, соединяем дугами данные варианты. Аналогично для вершины v4,1. Продолжая такой алгоритм приходим в финишную вершину t. На рис. 2 изображен соответствующий орграф.

25