Предметная область моделирования

Предметная область моделирования

 

Построение модели

 

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

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

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

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

Процесс оптимизации в таких моделях сводится к нахождению таких положительных значений неизвестных х₁*…*х_n, которые удовлетворяются условию ограничений и доставляют экстремум с целевой функции.

Задача, в которой целевая функция и условия ограничений заданы линейными функциями, называется задачей линейного программирования (ЗЛП).

Общая задача линейного программирования имеет несколько форм записи:

Векторная форма записи. Минимизировать линейную функцию Z = СХ при ограничениях А₁х₁ + А₂x₂ +… + А_Nx_N = А_о, X 0, где С = (с₁, с₂,…, с_N); Х = (х₁, х₂,…, х_N); СХ - скалярное произведение; векторы A₁, A₂,…, A_N, A₀ состоят соответственно из коэффициентов при неизвестных и свободных членах.

Матричная форма записи. Минимизировать линейную функцию, Z = СХ при ограничениях АХ = А₀, Х 0, где С = (с₁, с₂,…, с_N) - матрица-cтрока; А = (а_ij) - матрица системы; Х - матрица-столбец, А₀ - матрица-столбец.

Запись с помощью знаков суммирования. Минимизировать линейную функцию Z = С_jх_j при ограничениях:

Определение 1. Планом или допустимым решением задачи линейного программирования называется Х = (х₁, х₂,…, х_N).

Определение 2. План Х = (х₁, х₂,…, х_N) называется опорным, если векторы А (i = 1, 2,…, N), входящие в разложение (1.4) с положительными коэффициентами х, являются линейно независимыми. Так как векторы А являются N-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать М.

Определение 3. Опорный план называется невырожденным, если он содержит М положительных компонент, в противном случае опорный план называется вырожденным.

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

Для решений уравнений линейного программирования применяют симплексный метод. Решение оформляется в виде таблицы. Переход к другой таблице называется итерацией.

Существует несколько модификаций симплексного метода. Метод последовательного улучшения опорного плана - применяется к тем задачам линейного программирования, когда выполнены следующие условия:

Правая часть системы ограничений состоит из неотрицательных чисел, т.е. P₀ > 0

Канонический вид системы содержит полный набор базисных векторов.

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

Найти минимальное значение линейной функции:

 

(1.2.1)   Z = С₁х₁+С₂х₂+… +С_Nx_N

 

при ограничениях:

a₁₁x₁ + a₂₂x₂ +… + a_1NХ_N b₁

a₂₁x₁ + a₂₂x₂ +… + a_2NХ_N b₂

(1.2.2)   ……………_M1x₁ + a_M2x₂ +… + a_MNХ_N b_M

(1.2.3)   x_j 0 (j = 1, 2,…, n)

 

Совокупность чисел х₁, х₂,…, х_N, удовлетворяющих ограничениям (1.2.2) и (1.2.3), называется решением. Если система неравенств (1.2.2) при условии (1.2.3) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х₁Ох₂ совместную систему линейных неравенств

 

a₁₁x₁ + a₂₂x₂ b₁

a₂₁x₁ + a₂₂x₂ b₂

……._M1x₁ + a_M2x₂ b_M

x₁ 0, x₂ 0

 

Это все равно, что в системе (1.2.2) - (1.2.3) положить N=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой

a_i1x₁ + a_i2x₂ = b_i,(i = 1, 2,…, m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х = 0, х = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы.

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

Если в системе ограничений (1.2.2) - (1.2.3) n = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i,(i = 1, 2,…, n), а условия неотрицательности - полупространства с граничными плоскостями соответственно х_j = 0 (j = 1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью. Пусть в системе ограничений (1.2.2) - (1.2.3) n 3; тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью a_i1x₁ + a_i2x₂ + a_iNx_N = b_i (i = 1, 2,…, m), а условия неотрицательности - полупространства с граничными гиперплоскостями х_j 0 (j = 1, 2,…, n).

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

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

 

Расчет модели

 

Постановка задачи

 

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

Программа должна работать на IBM совместных персональных компьютерах. Если говорить о типе процессоров им должен быть Pentium 1 и выше, а объем запоминающего устройства 16 Мб. Тип видеоадаптера - SVGA.

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

Пусть установлены возможные варианты транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10. Все 10 пунктов можно отнести к пяти зонам (этапам). На линиях, соединяющих пункты, поставлено время проезда между соседними пунктами (рис. 1).

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

 

Рисунок 1

 

Анализ результатов расчета

 

Анализ результатов данной задачи приводит к тому, что оптимальный путь найден и удовлетворяет условию задачи. Эта задача была решена с помощью языка программирования Delphi 7.0 это значит. Сравнивая результат, полученный в программе и результат, полученный при решении вручную, оказываются одинаковы. Но для решения данной задачи в программе требуется несколько секунд, а для решения в ручную, намного больше времени.

 

Заключение

 

Цель курсового проекта - освоить и реализовать программу для нахождения кратчайшего пути в транспортной сети из маршрутов, соединяющих исходный пункт 1 с конечным пунктом 10.

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

Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

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

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

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

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

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой: CnH2n+2 Молекула каждого предельного углеводорода представляет собой дерево.

Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т.е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех. Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.

Графы и физика

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

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

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

 

Список литературы

 

1. Гольштейн, Е.Г. Линейное программирование./ Гольштейн, Е.Г., Юдин, Д.Б. Теория, методы и приложения. - М., Наука, 1969. - с. 424

2. Грешилов, А.А. Прикладные задачи математического программирования: учебное пособие для ВУЗов./ Грешилов, А.А. - М., Логос, 2006. - с. 286

3. Зайченко, Ю.П. Исследование операций./ Зайченко, Ю.П. - 2-е издание, перер. и доп. - Киев, Высшая школа, 1979. - с. 392

4. Таха. Введение в исследование операций./ Таха, Хэмди, А. - 6-е изд. - М., Изд. дом «Вильямс», 2001. - с. 912

5. Абанская А.В. Экономико-математическое моделирование - 2004. - 123 c.

.  Гасс С. Линейное программирование - 2000. - 167 c.

.  Дрогобыцкий И.Н. Экономико-математическое моделирование - 2006. - 88 c.

.  Аверилл М. Лоу Имитационное моделирование - 2005. - 155 c.

.  Колесов В.М. Моделирование систем. Объектно-ориентированный подход - 2006. - 199 c.

10. Колемаев В.А. Экономико-математическое моделирование - 2005. - 66 с.

Предметная область моделирования