Математическое моделирование. Талалаев Александр Александрович Группа 44411 Шифр i т52 Минск 2015 Теоретическая часть Вариант 2 Классификация моделей. Формы представления моделей задача

• Название: Талалаев Александр Александрович Группа 44411 Шифр i т52 Минск 2015 Теоретическая часть Вариант 2 Классификация моделей. Формы представления моделей задача
• Анкор: Математическое моделирование
• Дата: 17.05.2022
• Размер: 40.7 Kb.
• Имя файла: Математическое моделирование.docx
• Тип: Задача; #535440

Минский государственный высший

радиотехнический колледж


Математическое моделирование
Вариант № 17
Талалаев Александр Александрович
Группа 44411
Шифр I Т-52

Минск 2015

Теоретическая часть

Вариант 2

1.  Классификация моделей. Формы представления моделей.

2. Задача о минимальном остове и методы ее решения. Алгоритм Прима.
Практическая часть

Вариант 17
Транспортная задача.

a1=220 a2=400 a3=280

b1=160 b2=180 b3=170 b4=200 b5=190

C=

20 17 13 2 17 6 10 9 4 15 3 7 13 6 23

1. Классификация моделей. Формы представления моделей.

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

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

Классификация моделей и видов моделирования объектов и систем в соответствии с теорией подобия должна выделить в них наиболее общие признаки и свойства реальных систем. Ниже приведена одна из возможных классификаций.

Признаки классификации	Виды математических моделей
1. Принадлежность к иерархическому уровню	Модели микроуровня Модели макроуровня Модели метауровня
2. Характер взаимоотношений со средой	Открытые непрерывный обмен) Закрытые (слабая связь)
3. Характер отображаемых свойств объекта	Структурные Функциональные
4. Способ представления свойств объекта	Аналитические Алгоритмические Имитационные
5. Способ получения модели	Теоретические Эмпирические
6. Причинная обусловленность	Детерминированные Вероятностные
7. По отношению к времени	Динамические Статические
8. По типу уравнений	Линейные Нелинейные
9. По множеству значений переменных	Непрерывные Дискретные Дискретно-непрерывные
10. По назначению	Технические Экономические Социальные и т.д.

Формы представления моделей.

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

2. Задача о минимальном остове и методы ее решения. Алгоритм Прима.

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

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

Метод решения Алгоритм Прима.

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

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

Алгоритм Прима

Этот алгоритм назван в честь американского математика Роберта Прима (Robert Prim), который открыл этот алгоритм в 1957 г. Впрочем, ещё в 1930 г. этот алгоритм был открыт чешским математиком Войтеком Ярником (Vojtech Jarnik). Кроме того, Эдгар Дейкстра (Edsger Dijkstra) в 1959 г. также изобрёл этот алгоритм, независимо от них.

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

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

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

Решение

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

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

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

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

Вариант 17

Транспортная задача.

a1=220 a2=400 a3=280

b1=160 b2=180 b3=170 b4=200 b5=190

C=

20 17 13 2 17 6 10 9 4 15 3 7 13 6 23

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

	1	2	3	4	5	Запасы
1	20	17	13	2	17	220
2	6	10	9	4	15	400
3	3	7	13	6	23	280
Потребности	160	180	170	200	190

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 220 + 400 + 280 = 900

∑b = 160 + 180 + 170 + 200 + 190 = 900

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.
Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

	1	2	3	4	5	Запасы
1	20	17	13	2 [200]	17 [20]	220
2	6	10 [60]	9 [170]	4	15 [170]	400
3	3 [160]	7 [120]	13	6	23	280
Потребности	160	180	170	200	190

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

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 2*200 + 17*20 + 10*60 + 9*170 + 15*170 + 3*160 + 7*120  = 6740
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2

u₁ + v₅ = 17; 0 + v₅ = 17; v₅ = 17

u₂ + v₅ = 15; 17 + u₂ = 15; u₂ = -2

u₂ + v₂ = 10; -2 + v₂ = 10; v₂ = 12

u₃ + v₂ = 7; 12 + u₃ = 7; u₃ = -5

u₃ + v₁ = 3; -5 + v₁ = 3; v₁ = 8

u₂ + v₃ = 9; -2 + v₃ = 9; v₃ = 11

	v1=8	v2=12	v3=11	v4=2	v5=17
u1=0	20	17	13	2 [200]	17 [20]
u2=-2	6	10 [60]	9 [170]	4	15 [170]
u3=-5	3 [160]	7 [120]	13	6	23

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят:

F(x) = 2*200 + 17*20 + 10*60 + 9*170 + 15*170 + 3*160 + 7*120  = 6740

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 4-й магазин (200), в 5-й магазин (20)

Из 2-го склада необходимо груз направить в 2-й магазин (60), в 3-й магазин (170), в 5-й магазин (170)

Из 3-го склада необходимо груз направить в 1-й магазин (160), в 2-й магазин (120)


Литература:

Стариков, А. В. Экономико-математическое и компьютерное моделирование: учеб. пособие / А. В. Стариков, И. С. Кущева;
Фед. агентство по образованию, ГОУ ВПО «ВГЛТА». – Воронеж, 2008. - 132 с.

Кузнецов А. В. и др. Высшая математика: Мат. программир.: Учеб./ А. В. Кузнецов, В. А. Сакович, Н. И. Холод; Под общ. ред. А. В. Кузнецова.— Мн.: Выш. шк., 1994.— 286 с.

Большакова М.B. Линейное програмнрование: Учебно-метод. пособие к кон­трольной работе для студ. эконом, факультета /И.В. Большакова. М.В. Кураленко. - Мн.: БИТУ. 2004. - 148 с.

Талалаев А.А.

05.03.2015 года