Имитационные математические модели

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное учреждение высшего профессионального образования

«МАТИ» - Российский государственный технологический университет имени К.Э. Циолковского.

Кафедра «Испытания летательных аппаратов»

Курсовая работа

По курсу: «Математическое моделирование»

На тему: «Имитационные математические модели»

Москва 2014

Введение

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

К имитационному моделированию прибегают, когда:

1. дорого или невозможно экспериментировать на реальном объекте;

2. невозможно построить аналитическую модель: в системе есть время, причинные связи, последствие, нелинейности, стохастические (случайные) переменные;

3. необходимо сымитировать поведение системы во времени.

имитационный моделирование граф

1. Условия задачи

Исходные данные транспортной задачи в форме графа и в матричной форме

Рис. 1 Исходные данные транспортной задачи в форме графа

Рис. 2 Исходные данные транспортной задачи в матричной форме

2. Целевая функция и критерий оптимизации

Целевая функция:

Y = c₁₁ Ч-- x₁₁ +--c₁₂ Ч--x₁₂ + ... + c_ij Ч x_ij + ... + c_mn Ч--x_mn =.

Критерий оптимизации в транспортной задаче являются минимальные затраты на доставку всего груза потребителю, т.е. (Y min).

3. Построение опорного плана

Общий (или скорректированный) алгоритм построения опорного плана методом аппроксимации Фогеля

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

Алгоритм метода включает следующие основные этапы:

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

2) Поиск из всех разностей как по строкам, так и по столбцам, максимальной. Максимальная разность обводится рамкой.

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

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

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

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

6) Вычисление целевой функции опорного плана.

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

Основой алгоритмов этих методов является критерий оптимальности:

_ij = c_ij - z_ij >--_, где:

cij -затраты, связанные с доставкой одной единицы ресурса из i-го в j-ый пункт;

zij -расчетные затраты, связанные с доставкой одной единицы ресурса из i-го в j-ый пункт, для тех клеток опорного плана ресурсы в которые не распределены.

Если все _ij >--_, то данный план является оптимальным, если нет, то требуется его улучшение.

4. Построение опорного плана методом аппроксимации Фогеля

Опорный план перевозок

5. Расчет приведенных затрат

Y₀ =--c₁₁ Ч x₁₁ + c₂₁ Ч x₂₁ + c₂₂ Ч x₂₂ + c₂₃ Ч x₂₃ + c₃₃ Ч x₃₃ + c₄₃ Ч x₄₃ + c₅₂ Ч x₅₂

Замечание: Здесь и далее Y_i обозначает, что значение целевой функции относится к i-му шагу оптимизации. Опорный план _ Y₀.

6. Улучшение опорного плана

Общий (или скорректированный) алгоритм метода потенциалов

Пусть имеется матрица перевозок, соответствующая начальному решению: x_ij = - распределенные ресурсы (базисные переменные), x_ij =--_--для свободных переменных (ресурсы не распределены). Клетки соответствующие свободным ресурсам помечены звездочками.

В крайний правый столбец матрицы введем неизвестные u_i, а в нижнюю строку - неизвестные v_j. Эти n+m неизвестных должны для всех ( i, j ), соответствующих базисным переменным, удовлетворять линейной системе уравнений:

u_i + v_j = c_ij ,

Можно доказать, что эта система для всех базисных решений имеет треугольный вид, ее ранг равен n?m?1, и, следовательно, систему всегда можно решить следующим способом: на первом шаге полагают v_n ???. Если на k-ом шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения (14), т.к. значение другой неизвестной в этом уравнении уже известно. (Это верно до тех пор, пока не найдены все неизвестные). То, какую неизвестную можно найти на (k+1)-м шаге, определяют методом проб. Переменные u_i и v_j называются “потенциалами”.

1) Составим и решим систему уравнений.

Как было отмечено; уравнения составляются для клеток в которые распределены ресурсы.

2) Определим расчетные значения затрат zij для клеток, в которые ресурсы не распределены (со свободными переменными):

z_ij = u_i +--v_j ,

3) Вычислим разность заданных и расчетных затрат

_ij = c_ij - z_ij

Если все _ij 0, то исходный план является оптимальным и переходят к пункту 5, в противном случае переходят к построению нового плана.

_ab--=-----max к_ij --к,--_ij >--_.

Правило перераспределения следующее:

а) В клетку новой таблицы записывается число M.

б) Клетка остается пустой.

г) В остальных клетках, помеченных знаками “+” и “-”, число M вычитается из стоящего в клетки числа или складывается с ним, в соответствии со знаками.

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

Таким образом, получили новую матрицу - новый план.

Определим значение целевой функции, с учетом перераспределений в матрице.

Внимание: Уточнение матрицы проводится до тех пор, пока хотя бы одно значение _ij < 0.

Решение системы уравнений

г₁ = 0б тогда м₁ = 100б м₂ = 104б м₃ = 132б г₂ = 5б г₃ = -4б г₄ = -13 б г₅ = 51

Определим значения z_ij для клеток, в которые ресурсы не распределены:

Определим значения _ij и проверим условия оптимальности

Так как все _ij , решение в формировании нового плана не нуждается.

Граф оптимальной перевозки

Заключение

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

Список использованных источников

1. http://ru.wikipedia.org/ - Википедия - Свободная энциклопедия

2. Губарь Ю. Курс "Введение в математическое моделирование", Лекция 5: "Компьютерное имитационное моделирование. Статистическое имитационное моделирование" Интуит.ру

3. Строгалев В. П., Толкачева И. О. Имитационное моделирование. -- МГТУ им. Баумана, 2008

Размещено на Allbest.ru