Лекции_по_дисциплине

Компьютерное моделирование

Program Tock;

Uses Crt, Graph; Var I, J: Integer; Z, P, X, H, Y: Integer; Begin

X: =320; Y: =240; H: =10; P: =4; Detect Graph (I, J);

InitGraph (I, J,‟‟);

Set Color (15); Line (10,312,630,312); Randomize; Repeat

Z: =Random (8); If Z>=P Then X: =X+H Else X: =X-H; Set Color (Green); Circle (X, Y, 10); Delay (200);

Set Color (0); Circle (X, Y, 10)

Until KeyPressed or (X>=640) or (X<=0); Close Graph End.

В программе шаг является постоянным, но никто не мешает нам сделать его переменным, выбирая шаг из интервала [0,Hmax] случайным образом. Для этого зададим максимально возможный шаг Hmax и в цикле определим

H:=Random(Hmax).

Рассмотрим, как происходит Броуновское движение, известное из курса физики. Если след движения точки не стирать, то на экране можно будет наблюдать траекторию такого движения. Для того чтобы описать движение n частиц, необходимо завести два массива координат точек и организовать их движение.

Программа: Броуновское движение

Program Gaz; Uses Crt, Graph;

Var I, J, HxMax, HyMax, Hx, Hy, N, I: Integer;

X, Y: Array [0…500] Of Integer; P1, P2, Z1, Z2: Real;

Begin N: =100;

For I: =1 to N Do Begin X [I]:= 320; Y [I]:= 240 End; HxMax: =10; P1:=0.5; P2:=0.5; HyMax: = 10;

Detect Graph (I, J); InitGraph (I, J,‟‟); Set Color (15);

Randomize; RectAngle (100,100,540,380);

For I: =1 to N Do PutPixel (X [I], Y [I], White); Delay (200); For I: =1 to N Do PutPixel (X [I], Y [I], 0);

Repeat

For me: =1 To N Do Begin

Z1:=Random; Z2:=Random;

Hx: =Random (HxMax); Hy: =Random (HyMax);

If Z1<P1 Then X [I]:=X [I] +Hx Else X [I]:=X [I]-Hx;

If Z2<P2 Then Y [I]:=Y [I] +Hy Else Y [I]:=Y [I]-Hy; If X [I] <=110 Then X [I]:=X [I] +2*(110-X [I]);

If X [I]>=530 Then X [I]:=X [I]-2*(-530+X [I]);

If Y [I] <=110 Then Y [I]:=Y [I] +2*(110-Y [I]); If Y [I]>=530 Then Y [I]:=Y [I] +2*(Y [I]-370); PutPixel (X [I], Y [I], 15)

End: Delay (100);

101

Тарова Инна Николаевна

For I: =1 to N Do PutPixel (X [I], Y [I], 0) Until KeyPressed; Close Graph

End.

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

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

1.Метод статистического моделирования: решение краевых задач ма-

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

2.Метод имитационного моделирования: моделирование систем массо-

вого обслуживания, задачи АСУ, АСУП, АСУТП, задачи защиты информации, моделирование сложных игровых ситуаций и динамических систем.

3.Метод стохастической аппроксимации: рекуррентные алгоритмы решения задач статистического оценивания.

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

5.Другие методы: вероятностные методы распознавания образов, модели адаптации, обучения, самообучения.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Какие случайные события называются достоверными? невозможными? Несовместными? Противоположными?

2.Дайте классическое определение вероятности случайного события.

3.Что такое дискретная случайная величина? Непрерывная?

4.Что такое математическое ожидание и дисперсия случайной величины?

5.Сформулируйте один из методов генерации последовательности псевдослучайных чисел.

6.Как формулируются задачи теории массового обслуживания?

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

8.Придумайте модель случайного блуждания точки в заданном лабиринте.

102

Компьютерное моделирование

9.Рассчитайте модель автобусного маршрута с n остановками.

103

ЛЕКЦИИ по дисциплине: «Компьютерное моделирование» Физико-математический факультет, 10 семестр, всего 33 часа

ЛЕКЦИЯ 7. КОМПЬЮТЕРНОЕ МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ЭКОНОМИКЕ

7.1. ЛИНЕЙНОЕ, НЕЛИНЕЙНОЕ И ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЯ

В последние годы мы особенно отчетливо ощутили, что нет ничего важнее для общества, чем здоровая экономика. Научное исследование основ функционирования экономики - сложная и интересная деятельность. Математические методы в ней играют возрастающую с каждым десятилетием роль, а реализация возникающих при этом математических моделей и получение практически важных результатов невозможны без ЭВМ. Рассмотрим лишь один из разделов - оптимальное планирование. Внутри него несколько моделей: линейное, нелинейное и динамическое программирование.

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

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

Пример 1. На некотором предприятии могут выпускать изделия двух видов (например, мотоциклы и велосипеды). В силу ограниченности возможностей сборочного цеха в нем могут собирать за день либо 25 мотоциклов (если не собирать вообще велосипеды), либо 100 велосипедов (если не собирать вообще мотоциклы), либо какую-нибудь комбинацию тех и других, определяемую приемлемыми трудозатратами. Склад может принять не более 70 изделий любого вида в сутки. Известно, что мотоцикл стоит в 2 раза дороже велосипеда. Требуется найти такой план выпуска продукции, который обеспечил бы предприятию наибольшую выручку. Такого рода задачи возникают повседневно в огромном количестве, но в

Компьютерное моделирование

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

Обозначим число выпускаемых за день мотоциклов X, велосипедов - у. Пусть Т1 -время (в часах), уходящее на производство одного мотоцикла, а т2 - одного велосипеда. Из условия задачи следует, что T1x+T2y 24. Если завод работает круглосуточно, то, очевидно, при одновременном выпуске обоих изделий

Еще одно условие – ограниченная емкость склада: x+y 70.

Обозначим цену мотоцикла - а1, велосипеда – а2. По условию а1=2а2. Общая цена продукции: S=a1x+a2y=2a2x+a2y=a2 (2x+y). Поскольку а2 – заданная положительная величина, то наибольшего значения следует добиваться от величины f=2x+y. Учитывая все условия, имеем: среди неотрица-

4x y 100
тельных решений системы	найти такое, которое соответст-
x	y 70

вует максимуму функции f=2x+y. Решим задачу геометрически. Построим на плоскости область, соответствующую неравенствам и условию не отрицательности х и у, а также семейство прямых,. Удовлетворяющих уравнению f=2x+y=c (с разными с). Координаты точки Р(10, 60) – точки касания – искомый оптимальный план производства.

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

105

Тарова Инна Николаевна

Нелинейное программирование (планирование) – математические методы отыскания максимума или минимума функции при наличии ограничений в виде неравенств или уравнений. Минимизируемая (максимизируемая) функция представляет собой принятый критерий эффективности решения задачи, соответствующий поставленной цели. Он носит название целевой функции. Ограничения характеризуют имеющиеся возможности решения задачи. Целевая функция или хотя бы одно из ограничений нелинейные (т.е. на графиках изображаются непрямыми – кривыми – линиями). Существо решения задачи нелинейного программирования заключается в том, чтобы найти условия, обращающие целевую функцию в минимум или максимум.

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

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

Z1(x1, x2,...,xn) 0;

Z 2(x1, x2,...,xn) 0;

.................... (1.1) где Z1,Z2,…Zm – соответствующие функ-

Zm(x1, x2,...,xn) 0

при xi 0.

ции, характеризующие условие решения поставленной задачи (ограничения), Xi – искомые величины, содержащие решение задачи. Целевая функция задается в виде: y f (x1, x2,...xn) (1.2). Причем хотя бы одна из

функций Z1,Z2,…Zm – нелинейная.

Методами нелинейного программирования решаются задачи распределения неоднородных ресурсов. Пусть имеется m разнородных ресурсов, которые предлагается реализовать для бизнеса в n регионах страны. Известны оценочные возможности (вероятности) начать бизнес в j-том регионе (Рj), а также эффективности использования I-го ресурса в n-м регионе (Wij). Распределение ресурсов по регионам характеризуется так называемым параметром управления (Hij):

106

Компьютерное моделирование

	0, если	i тый	не	направляется	в	j тый	регион;	Не-
Hij
		i тый				j тый
1, если			ресурс	направляется	в		регион.

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

n		m
Pц была максимальной: Pц Pj 1 (1 HijWij) max .
j 1		i 1

n

Должно выполняться также ограничение Hij 1, i 1,2,..., m .

j 1

Это ограничение означает, что каждый из m ресурсов обязательно должен назначаться в какой-либо из регионов.

Динамическое программирование (планирование) служит для вы-

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

управляемая операция (целенаправленное действие), распадающаяся (есте-

ственно или искусственно) на m шагов – этапов. На каждом шаге осуществляется распределение и перераспределение участвующих в операции с целью улучшения ее результата в целом. Эти распределения в динамическом программировании называются управлениями и обозначаются буквой U. Эффективность операции в целом оценивается тем же показателем, что и эффективность ее управления W(U). При этом W(U) зависит от всей совокупности управлений на каждом шаге операции: W=W (U)=W (U1,U2,…,Um). Управление, при котором показатель W достигает максимума, называется оптимальным управлением. Оптимальное управление обозначается буквой U. Оптимальное управление многошаговым процессом состоит из совокупности оптимальных шаговых управлений: U=(U1,U2,…,Um). Задача динамического программирования – определить оптимальное управление на каждом шаге Ui(I=1,2,…,m) и оптимальное управление всей операцией в целом. В большинстве практических задач принимается, что показатель эффективности операции W в целом пред-

ставляет собой сумму эффективности действий на всех этапах операции:

107

Тарова Инна Николаевна

m

W Wi , где Wi – эффективность операции на I-том шаге. При этом в

i 1

m

случае оптимального управления W max Wi . Существо решения за-

i 1

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

1) оптимизация производится методом последовательных приближений (итераций) в два круга; вначале от последнего шага операции к первому, а затем, наоборот – от первого к последнему; 2) на первом круге, идя от последующих шагов к предыдущим, находится условное оптимальное управление; условное оптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивали максимальную эффективность последующего шага, т.е. на каждом шаге имеется такое управление, которое обеспечивает оптимальное продолжение операции; этот принцип выбора управления называется принципом оптимальности; 3) так продолжается до первого шага, но т.к. первый шаг не имеет предыдущего, то полученное для него условное оптимальное управление теряет свой условный характер и становится просто оптимальным условием, которое мы ищем; 4) второй круг оптимизации начинается с первого шага, для которого оптимальное управление известно. Имея для всех шагов после него условные оптимальные управления, мы знаем, что необходимо делать на каждом последующем шаге. Это дает возможность последовательно переходить от условных к оптимальным управлениям для всех последующих шагов, что обеспечивает оптимальность операции в целом.

Пусть имеется m различных грузов, которые необходимо загрузить транспортное средство таким образом, чтобы общая ценность груза W была максимальной. Ценность груза является функцией от грузоподъемности транспортного средства: W=f(G). Известны массы грузов I-го типа Pi и их стоимости Ci. Необходимо загрузить транспортное средство таким обра-

зом,	чтобы	общая	ценность	груза	была	максимальной:
		m
W f (G) max XiCi ,			где Xi – число предметов груза I-го типа, за-

i 1

гружаемых в транспортное средство; Xi выступает в качестве управления (Ui=Xi). Ограничивающими условиями являются:

m

XiPi G, Xi 0,1,2,... . Первое условие требует, чтобы общая масса

i 1

108

Компьютерное моделирование

груза не превышала грузоподъемности транспортного средства, а второе

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

7.2. СИМПЛЕКС-МЕТОД

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

ний (7.1)

и требуется отыскать минимум линейной функции f=c1x1+c2x2+…+cnxn (7.2). Для отыскания произвольного опорного решения приведем (7.1) к виду, в котором некоторые r неизвестных выражены через остальные, а свободные члены неотрицательны (как это сделать - обсудим позднее):

(7.3)

Неизвестные X1,Х2,…,Xn - базисные неизвестные, набор {х1, х2, ..., хr} на-

зывается базисом, а остальные неизвестные (хг+1, хr+2,..., xn} - свободные. Подставляя (7.3) в (7.1), выразим функцию f через свободные неизвестные:

(7.4)

109

Тарова Инна Николаевна

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

Пример I .Дана система ограничений

Требуется минимизировать линейную функцию f= х2 - х3. В качестве свободных переменных выберем х2 и х3. Тогда данная система ограничений преобразуется к виду

Таким образом, базисное решение (3,0,0,1). Так как линейная функция уже записана в свободных неизвестных, то ее значение для данного базисного решения f=0. Для уменьшения этого значения можно уменьшить х2 или увеличить x3. Но х2 в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x3. Первое из уравнений имеет ограничение x3=1 (из условия X1 0), второе - не дает ограничений. Далее, берем x3 = 1, х2 не меняем и получаем новое допустимое решение (0,0,1,3), для которого f=-1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, х4). От предыдущей системы ограничений переходим к новой:

110