close

Вход

Забыли?

вход по аккаунту

Цветаева Марина Ивановна;pdf

код для вставкиСкачать
ПОНЯТИЕ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ. ЭЛЕМЕНТЫ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1. Моделирование как метод научного познания. Системный подход.
2. Этапы математического моделирования. Классификация
математических моделей.
3. Примеры линейных моделей. Математическая формулировка задачи
линейного программирования.
Моделирование как метод научного познания. Системный подход.
Слово "модель" происходит от латинского modus (копия, образ).
Моделирование - это замена некоторого исследуемого объекта А другим
объектом Б. При этом замещаемый объект А называется оригиналом или
объектом моделирования, а замещающий Б - моделью. Целью
моделирования являются получение, обработка, представление и
использование информации об объектах, которые взаимодействуют между
собой и внешней средой; а модель здесь выступает как средство познания
свойств и закономерности поведения объекта.
Простейшей моделью Земли, отображающей ее поверхность, является
глобус. Другой моделью такого рода является карта – бумажная или
электронная. Каждая модель обладает своими достоинствами и
недостатками. Мы предпочтем глобус, если важна визуализация без
искажений; для оценки обстановки в полевых условиях удобнее бумажная
карта, а для внесения оперативных изменений и получения дополнительной
информации – электронная карта.
Иначе говоря, выбор той или иной модели обусловлен целью моделирования.
При этом основным критерием выбора является адекватность модели, т.е.
совпадение основных характеристик модели и объекта моделирования в
отношении цели моделирования. Другим критерием является сложность
модели. На практике выбирают наиболее простую модель, позволяющую
достичь требуемого результата.
Основным принципом современного моделирования является системность
– любой объект можно представить в виде системы взаимодействующих и
взаимосвязанных элементов. Характеристиками системного подхода служат:
целостность, позволяющая рассматривать одновременно систему как
единое целое и в то же время как подсистему для вышестоящих уровней;
иерархичность строения, то есть подчинение элементов низшего уровня
элементам высшего уровня; структуризация, позволяющая описывать
процесс функционирования системы не столько свойствами её отдельных
элементов, сколько свойствами самой структуры.
Системный подход лежит в основе проектирования и работы
геоинформационных систем, обеспечивающих достоверной информацией
геодезистов, картографов и топографов.
Этапы математического моделирования. Классификация
математических моделей.
Перейдем к одному из наиболее универсальных видов моделирования –
математическому. Математическое моделирование - это процесс
построения и изучения математических моделей. Математическая модель
является приближенным представлением реальных объектов, процессов или
систем, выраженным в математических терминах и адекватно описывающим
существенные черты оригинала. Математические модели позволяют
количественно и визуально исследовать основные свойства объекта,
процесса или системы, его параметры, внутренние и внешние связи.
На этапе построения математической модели возникает задача выявить и
исключить из рассмотрения факторы, несущественно влияющие на конечный
результат: математическая модель эффективна, если содержит относительно
небольшое число переменных. Конечной целью этого этапа является
формулирование математической задачи, решение которой с необходимой
точностью осуществляется на следующем этапе. Заключительный этап
состоит в проверке адекватности найденного решения. На этом этапе модель
при необходимости модифицируется: происходит либо усложнение модели,
чтобы она была более адекватной действительности, либо ее упрощение ради
достижения практически приемлемого решения.
Поясним на примерах, как происходит отбор факторов, отражаемых в той
или иной математической модели.
Пример 1. Траекторией полета снаряда является баллистическая кривая –
линия, которую описывает при движении его центр масс. Предположим, что
сопротивление воздуха учитывается с помощью специальной поправки («на
ветер»). В таком случае математической моделью баллистической
траектории – в соответствии с первым законом Кеплера – будет дуга эллипса.
Следовательно, рассчитывая дальность полета и среднюю скорость снаряда,
придется вычислять сложный эллиптический интеграл.
Но если начальная скорость снаряда мала (по сравнению с первой
космической), то изменением ускорения свободного падения (как по
величине, так и по направлению) можно пренебречь. В этом случае – в
соответствии со вторым законом Ньютона – математической моделью
баллистической траектории будет дуга параболы. По этой модели дальность
полета и средняя скорость снаряда вычисляются без особого труда.
Наконец, если нас интересует лишь начальная фаза полета, в которой можно
пренебречь также изменением начальной скорости снаряда, то в качестве
математической модели баллистической траектории следует выбрать отрезок
прямой линии. Понятно, что такая модель в рассматриваемом случае
является простейшей.
Пример 2. В геодезии в качестве математической модели земной
поверхности рассматривают уровенную поверхность, которая в каждой
своей точке перпендикулярна отвесной линии. С учетом влияния
гравитационного поля Земли за уровенную поверхность принимают геоид,
относительно которого ведется отсчет высот над уровнем моря. Геоид не
имеет правильной геометрической формы. Поэтому, определяя
геодезические координаты точки, его заменяют референц-эллипсоидом. А в
качестве уровенной поверхности при определении географических координат
– для задач, решаемых в картографии - рассматривают сферу. Наконец, при
топографическом изучении незначительных по размеру территорий
изменение положения вертикальной линии можно вообще не учитывать, и в
данном случае уровенная поверхность будет плоской.
Определяя область математики, в рамках которой проводится исследование
математической модели, руководствуются схемой:
В детерминированных моделях предполагается отсутствие случайных
воздействий, поведение системы можно точно определить. При построении
детерминированных моделей обычно используются средства линейной и
векторной алгебры, аналитической и дифференциальной геометрии,
математического анализа. Стохастическая модель учитывает случайный
характер процессов в исследуемых объектах и системах, который
описывается методами теории вероятности и математической статистики.
Различают статические модели, которые описывают поведение системы в
фиксированный момент времени, и динамические - они отражают временные
изменения. Для статических и динамических моделей существенно
различаются не только методы исследования, но и возможности
визуализации.
По способу обработки входной информации модели обычно делятся на
непрерывные и дискретные. Исторически сложилось так, что потребность в
развитом математическом аппарате возникала, главным образом, при
построении непрерывных математических моделей. Но с появлением
компьютерной техники дискретные модели стали не менее востребованными.
Изучает такие модели специальная область математики - дискретная
математика.
.Примеры линейных моделей. Математическая формулировка задачи
линейного программирования.
Выделяя простейшие модели, рассмотренные в примерах 1,2 из предыдущего
параграфа, отметим их общую особенность – это линейные модели.
Действительно, прямая линия в пространстве задается линейными
параметрическими уравнениями x = x0 + l∙t , y = y0 + m∙t, z = z0 + n∙t (где
x0, y0, z0 - координаты начальной точки траектории; l, m, n – координаты
вектора начальной скорости снаряда). Положение плоскости в пространстве
также определяется линейным уравнением.
Более сложные модели из этих примеров (дуга параболы или эллипса; сфера
или эллипсоид вращения) нелинейны, поскольку описываются уравнениями
второй степени.
Зачастую при построении математической модели ищут компромисс,
выбирая между простой для изучения и последующего применения линейной
моделью и более адекватной (но трудной для исследования) нелинейной
моделью. Анализ нелинейной модели, в котором она (с определенными
допущениями) рассматривается как линейная называется линеаризацией.
Важность линейных моделей отражена в названиях некоторых
математических дисциплин: линейная алгебра, линейное программирование.
Последнее название появилось в результате не слишком удачного перевода
английского слова programming. Вариант «линейное планирование» точнее
соответствует смыслу основополагающей работы советского математика
Л.В.Канторовича, удостоенного за нее Нобелевской премии в области
экономики.
Задачи, для решения которых удобно применять методы линейного
программирования, возникают в самых разных областях деятельности, в том
числе и в быту.
Пример 3. Курсант позвал в гости четырех друзей, располагая 1000 руб. для
заказа на дом биг-маков (по цене 100 руб.) и колы (по цене 50 руб). По опыту
он знал, что один или два друга могут прийти с девушками, не предупредив
об этом заранее. Остававшихся от планируемого изначально заказа 250 руб.
(1000 - 5∙100 - 5∙50) хватало для дополнительного заказа 2 чизбургеров (по
цене 45 руб) и трех кол.
Но, поразмыслив, курсант понял, что девушка может обидеться, если ей
предложат чизбургер, а ее парню – биг-мак. И тогда он решил, что биг-мак и
кола достанутся лишь тем, кто пришел раньше других, а опоздавшие получат
чизбургеры и маленькую колу (по цене 35 руб).
Какое максимальное число биг-маков может заказать курсант в соответствии
с новым планом?
Решение. Обозначим через x1, x2, x3, x4 – количество заказанных биг-маков,
чизбургеров, колы и маленькой колы, соответственно. Все присутствующие
(из расчета на 7 человек) получают хотя бы один биг-мак или чизбургер, а
также колу или маленькую колу. Запишем в виде неравенств ограничения по
количеству: x1, x2, x3, x4 ≥ 0; x1 + x2 ≥ 7; x3 + x4 ≥ 7
Ограничение по общей стоимости: 100x1 + 45x2 + 50x3 + 35x4 ≤ 1000.
Критерий: x1 → max.
Построенная математическая модель - это целочисленная задача линейного
программирования. В данном случае найти ответ несложно. Минимальное
количество денег, потраченных на колу 50x3 + 35x4 с учетом ограничений
x3, x4 ≥ 0; x3 + x4 ≥ 7 достигается при x3 = 0; x4 = 7 - это 245 руб. Оставшихся
755 руб достаточно для покупки 7 биг-маков; в этом случае хватит денег,
чтобы заказать 3 колы и 4 маленьких колы.
В общем случае задачу линейного программирования можно
сформулировать так: найти наибольшее значение целевой функции
(1)
для значений,
удовлетворяющих системе ограничений
(2)
К записи (1), (2) приходят и в том случае, когда ищется минимальное
значение целевой функции, либо в системе ограничений имеются
неравенства разных знаков: для этого достаточно поменять знаки у
соответствующих коэффициентов при неизвестных. Например, ограничения
по количеству из примера 3 в виде (2) будут выглядеть так: -x1 - x2 ≤ - 7; -x3
– x4 ≤ - 7.
К построению математической модели вида (1), (2) сводятся многочисленные
задачи с экономическим или производственным содержанием. Некоторые из
них будут рассмотрены на практическом занятии.
В простейшем случае, когда число неизвестных равно 2, задачу (1), (2)
можно решить геометрически. Суть геометрического способа решения
вначале поясним на примере.
Пример 4. Решить задачу линейного программирования:
4 x1  5 x2  8,

z = x1 + 2x2  max
при ограничениях 2 x1  x2  10,
 x  0, x  0.
2
 1
Решение.
1. Заменим в ограничениях знаки "" на знак равно, получим уравнения двух
прямых: L1 :  4 x1  5x2  8, L2 : 2 x1  x2  10.
Построим эти прямые в прямоугольной системе координат:
2. Выделим допустимую область точек на плоскости, координаты которых
удовлетворяют системе ограничений (на рисунке эта область 0ABC
закрашена): первому ограничению удовлетворяют точки на плоскости,
которые лежат ниже прямой L1, второму ограничению – ниже прямой L2,
третьему – точки, находящиеся правее оси Ox2, четвёртому – выше оси Ox1
3. Приравняв к нулю переменную z в целевой функции, получим равенство:
0 = x1 + 2x2, которому удовлетворяют координаты точек на прямой L3.
4. Значение целевой функции начинает возрастать, если перемещать прямую
L3 параллельно вверх, оставаясь в границах закрашенной области. В этом
движении последней допустимой точкой окажется точка B. В этой точке
достигается искомый максимум целевой функции.
5. Для нахождения координат точки В решаем систему уравнений:
4 x1  5 x2  8,

2 x1  x2  10,
Решение системы x1 = 3, x2 = 4 позволяет найти максимальное значение
целевой функции z = x1 + 2x2 = 3 + 8 = 11
В общем случае геометрического решения задачи (1), (2) вначале строят
допустимую область, затем прямую L0, соответствующую нулевому
значению целевой функции, и откладывают от точки O вектор,
перпендикулярный прямой (его координатами являются коэффициенты c1,
c2).
Перемещая прямую L0 в направлении построенного вектора до выхода из
допустимой области в точке А, находят максимальное значение целевой
функции. Двигаясь в противоположном направлении (до выхода из
допустимой области в точке B) – ее минимальное значение.
Подчеркнем, что при любом развитии событий искомое экстремальное
значение целевой функции достигается в одной из вершин многоугольника,
определяющего допустимую область. Поэтому при решении на компьютере
задачи линейного программирования в случае n = 2 проще вычислить
значения целевой функции во всех вершинах многоугольника, а затем
сравнить их по величине.
Если же решается задачи линейного программирования для n ≥ 3, то
допустимая область задается многогранником (в пространстве n измерений).
И общепринятый путь решения состоит в специально организованном
переборе вершин данного многогранника. Этот способ решения называется
симплекс-методом. Он реализован ы в виде специальных программ во всех
популярных компьютерных пакетах, включая Microsoft Office (специальная
надстройка для Excel) и Mathcad.
1/--страниц
Пожаловаться на содержимое документа