MMTS_Lectures_M

max ( min V(Xi , Ur )) .

Xi Ur

Критерий Гурвица основывается на следующем решающем правиле:

где kd – коэффициент доверия.

По критерию Гурвица предполагается, что среда находится с вероятностью kd в благоприятном состоянии и с вероятностью 1 – kd – в неблагоприятном. При kd = 0 получаем критерий Вальда, а при kd = 1

среды Ur относительно наилучшего решения в зависимости от стратегии Xi, определяемых

как max V ( Xi , Ur ) :

Xi

VS ( Xi , Ur ) = V (Xi , Ur )-max V ( Xi , Ur ) .

Xi

К рассчитанным сожалениям применяется решающее правило

max (min VS ( Xi , Ur )).

Xi Ur

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

Выбор одного из вышеуказанных критериев в качестве решающего производится принимающим решение.

Пример.

Необходимо найти оптимальное число машиномест на проектируемой автомобильной стоянке. К рассмотрению приняты 3 типовых проекта на 200, 250 и 300 машиномест. Ожидаемая прибыль V(Xi,Ur) в зависимости от числа мест Xi и состояния среды (числа занятых мест) Ur задана таблично. В этой же таблице приведены вероятности возможных состояний среды р(Ur).

Решение.

Критерий Вальда

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

Критерий Гурвица при Kd = 0.6

max (kd maxV(Xi , Ur)+(1-kd)minV(Xi , Ur))

Xi Ur Ur

=max (0.6 30+0.4(-15)дляx1 200;0.6 50+0.4(-35)дляx2 250;0.6 60+0.4(-55)дляx3 300).

Xi

max(12.0 дляx1 200;16.0 дляx2 250;14.0дляx3 300) 16.0(при x2 250).

Xi

и при Kd =1.0

max ( max V (Xi , Ur)) = 60.0 (x3 = 300).

Xi Ur

Критерий Лапласа

Критерий Сэвиджа

Результаты расчета сожалений по ранее приведенной формуле даны в таблице вторыми строками. Например, для 1-го столбца (Ur=150) сожаления определяются по выражению

Vs ( Xi , U1)= V ( Xi, U1) -max V (Xi , U1) =

Xi

V(Xi , U1 ) -max V (-15,-35,-55) = V(Xi , U1 ) +15.

Xi

По рассчитанным сожалениям поиск оптимального решения проводится следующим

= max(-30 для X1 ;-20 для X2;-40для X3) = -20(приX2 = 250).

Xi

Если известны вероятности состояния среды, то решение производится в условиях риска:

(0.1(-35)+0.120+0.6 50+0.2 50)дляX2; (0.1(-55)+0.1(-10)+0.6 45+0.2 60)для X3)= =38.5( при X 2 =250).

Для условий примера по большинству критериев наиболее эффективно строительство стоянки на 250 машиномест.

Пример компьютерной программы для принятия решений в условиях риска и неопределенности приведен в приложении 1.

1.5. Программное компьютерное обеспечение исследования транспортных систем

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

Операционные системы (ОС) – это набор программ, осуществляющих управление работой компьютера.

Функции ОС:

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

выполнение операций ввода-вывода с обработкой прерываний, запросов и распределением их между устройствами;

загрузка приложений в оперативную память (RAM/ОЗУ) и их выполнение, управление оперативной памятью, распределение ее между процессами, выделение виртуальной памяти; управление доступом к данным с обеспечением их защиты и ограничений на доступ; обработка исключительных условий во время выполнения задачи – ошибок, прерываний; функции по обеспечению организации сетей, использованию служебных программ,

выполнению сетевых операций.

Наибольшее распространение имеют семейства таких многозадачных многопользовательских ОС как Microsoft Windows, Mac OS и Linux.

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

Программирование может осуществляться в машинных кодах и на символьных языках. Наибольшее распространение получили следующие языки программирования: Ассемблер; Макроассемблер; Бейсик – варианты Quick, Turbo, Visual; Cobol (Кобол); Fortran(Фортран); Pascal (Паскаль); C (Си); Lisp (Лисп) – для машинной графики; Prolog (Пролог) – для обработки логической информации; объектноориентированная система

программирования Delphi (Делфи).

Для удобной работы с компьютером кроме ОС используются оболочки (FAR manager, Norton Commander, DOS Navigator, Volkov Commander, Total Commander и др.). Большинство

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

Прикладное программирование подразделяется на пакеты прикладных программ и программы пользователя.

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

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

Для интегрированных пакетов характерно следующее:

–совместимость записи данных, дающая возможность их вызова различными средствами для различных целей;

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

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

данных, графикой, создавать прикладные программы, поддерживать связь с другими компьютерами. Примерами таких пакетов являются Windows Office, Lotus и др.

К функционально ориентированным пакетам относятся средства работы с текстом, обработки электронных таблиц, организации баз данных, поддержки интерактивной графики, функционирования экспертных систем и т.п. Примерами являются пакеты машинной графики (AutoCAD, Компос), графические редакторы (Adobe PhotoShop, CorelDraw и др.), электронные таблицы и деловая графика (SuperCalc, Exсel, QuattroPro, Grapher), СУБД (Access, Clarion, Clipper, dBase, FoxBase, FoxPro, FoxGraph, Ingres, Paradox и

др.), редакционно-издательские системы (PageMaker, Ventura Publisher), анимационные (3D StudioMAX и др.), презентационные (PowerPoint).

Проблемно-ориентированные пакеты охватывают различные сферы применения: математика, экономика, транспорт, бухгалтерский учет и др. Для разнообразных задач математической статистики могут служить пакеты программ Statistica и "Олимп".

Программы Matlab, Gauss, Assyst, Eurica, Maple V, Mathematica, MathCad предназначены для решения задач матричной и векторной алгебры, векторного анализа, решения систем линейных и нелинейных уравнений. Некоторые из них позволяют выполнить преобразование математических выражений в символьной форме (упростить выражение или представить в другом виде), найти вид неопределенного интеграла.

Работа пользователя в пакетах производится с помощью "меню". Максимальное число альтернатив, содержащихся в "меню", различно. Обычно принимают равным 7±2 (7 – число по Миллеру).

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

При проектировании прикладных программ должны быть определены следующие характеристики:

1)состав исходного текста: 1.1) единый текст;

1.2) отдельные текстовые модули;

2)структура исполняемой программы:

2.1) единый модуль, полностью загружаемый в ОЗУ при запуске;

2.2) несколько сегментов, загружаемых в ОЗУ по мере необходимости; 2.3) резидентная часть, загружаемая в ОЗУ в начале сеанса, и одна или несколько

нерезидентных частей, загружаемых по мере необходимости; 3) Способ хранения данных на внешнем постоянном запоминающем устройстве (ВПЗУ): 3.1) все данные располагаются в одном файле; 3.2) данные распределены по нескольким файлам.

Состав исходного текста оказывает влияние на способ разработки программ, структура исполняемой программы – на требования к ОЗУ и быстродействие, способ хранения данных на ВПЗУ – на быстродействие при доступе к данным и характер использования внешней памяти.

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

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

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

Межмодульный информированный обмен может осуществляться через общие области ОЗУ и файлы на ВПЗУ. В случае необходимости обмена при разнесенном во времени исполнении программ или модулей применяется обмен через файлы на ВПЗУ.

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

2.ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

2.1.Детерминированные модели

2.1.1. Решение систем линейных уравнений

Исходный вид системы:

a1 1 x1 + ... + a1 i xi + ... + a1 p xp = b1

. . .

aj 1 x1 + ... + a j i xi + ... + a j p xp = bj

. . .

ap 1 x1 + ... + ap i xi + ... + ap p xp = bp

где aji – коэффициенты системы при неизвестных; bj – свободные члены. В свернутом виде система описывается следующим выражением:

p

ajixi bj ; j 1,p, i 1,p .

i 1

В матричном виде система имеет вид

А Х = В,

. . .

хp

Требуется найти значения Х, удовлетворяющие всем уравнениям системы.

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

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

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

Таким образом, на каждом этапе таких последовательных преобразований получаем понижение числа переменных (на последнем этапе до одной):

a1 1 x1 + ... + a1 i xi + ... + a1 p xp = b1 a'2 2 x1 + ... + a'2 i xi + ... + a'2 p xp =b'2

. . .

хр = b'р ,

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

Значение свободного члена для уравнения с одной переменной дает решение, например по переменной хр (хр=b'р), Затем из одного из уравнений системы предпоследнего этапа находится хр-1 и т.д., для 1-го этапа – x2 и из исходной системы – х1. Разновидность – метод Гаусса с выбором главного элемента.

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

По методу Крамера

X = A-1 B

или

xi = det Ai / det A ,

где А-1 – матрица, обратная матрице А;

Ai – матрица, полученная по матрице А с заменой в ней i- го столбца столбцом свободных

членов (aji = bj), j 1,p ;

det – детерминант (определитель) матрицы.

Если det A равен нулю, то система не определена. При значениях det A близких к нулю система слабо обусловлена.

2.1.2. Решение систем нелинейных уравнений

Задача состоит в нахождении корней следующей системы уравнений

fi(X) = 0 }, i 1,m ,

где X = { x1, x2,...,xm}.

Для решения могут применяться следующие методы:

-метод простых итераций;

-метод Зейделя, отличающийся от метода простых итераций тем, что текущие приближения к решению xi сразу подставляются в последующие уравнения;

-на основе методов поиска экстремума многомерных функций и др.

Метод простых итераций состоит в реализации вычислительного процесса по следующей формуле:

xi (k+1) = Fi(Xk),

где Fi(X) = fi(X) + xi =xi; i – номер переменной; k – номер итерации.

Итерации выполняются до тех пор, пока сохраняется хотя бы по одному из xi условие

abs ( xi(k+1) - xi(k) ) > E,

где Е – заданная точность.

Метод обеспечивает сходимость, если

Графическая интерпретация метода приведена на рисунке 2.1, а схема алгоритма на рисунке 2.2.

fi(X)+xi,

xi fi(X)+xi

xi

xрi xi

Рисунок 2.1 – Графическая интерпретация метода простых итераций (xрi – решение)

Решение на основе применения методов поиска экстремума (минимизации) многопараметрических функций основано на том, что формируются функции вида

где fi(X) = 0, i 1,m.

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

1

5

i1,m

11

Останов

Рисунок 2.2 – Схема алгоритма метода простых итераций

2.1.3. Численное интегрирование

Численное интегрирование – это вычисление значения определенного интеграла

b

S= f(x) dx = F(b)-F(a)

a

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

Такой интеграл численно равен площади фигуры, ограниченной ординатами в точках a и b, осью абсцисс и линией графика подинтегральной функции f(x) (рисунок 2.3).

Для численного интегрирования отрезок [a, b] разбивается на m частей, к каждой из которых применяется аппроксимация выбранной функцией (прямой, параболой, полиномом и т.п.).

Существует ряд методов численного интегрирования: прямоугольников, модифицированный прямоугольников, трапеций, Ньютона-Котеса (аппроксимация полиномом Лагранжа), Симпсона (аппроксимация параболой), Уэдлля (разбивка каждого из m отрезков на 6 частей), Чебышева (с неравномерным разбиением аргумента), Симпсона (кубатурная аппроксимация), Гаусса (кубатурная аппроксимация), Ромберга, Бодэ и др.

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

m

S= h f (x(i)),

i=1

где x(i) = a + (i-1) h или x(i) = a + i h; h = (b - a)/m.

Модернизированный метод прямоугольников отличается правилом выбора расчетных точек x(i):

x(i) = a + h/2 + ( i-1) h.

f(x)

S

a i=1 2 3 4 5 6 b x

Рисунок 2.3 – Графическая интерпретация численного интегрирования

По методу трапеций

m-1

S= h (f(x(0))/2 + f (x(i)) +f(x(m))/2) ,

i=1

где x(i) = a + i h.