Главная Учебники - Разные Лекции (разные) - часть 34
Ташкентский институт инженеров железнодорожного транспорта Кафедра "Информатика и компьютерная графика" «Информатика» Выполнил:
студент группы ЕМ-477 Грачёв А. Принял
ассистент Ташкент 2008 Введение
Современное состояние вычислительной техники
Оперативная память (RAM, Random Access Memory, память произвольного доступа) - это энергозависимая среда, в которую загружаются и в которой находятся прикладные программы и данные в момент, пока вы с ними работаете. Когда вы заканчиваете работу, информация удаляется из оперативной памяти. Если необходимо обновление соответствующих дисковых данных, они перезаписываются. Это может происходить автоматически, но часто требует команды от пользователя. При выключении компьютера вся информация из оперативной памяти теряется. В связи с этим трудно недооценить все значение оперативной памяти. Однако до недавнего времени эта область компьютерной индустрии практически не развивалась (по сравнению с другими направлениями). Взять хотя бы видео, аудиоподсистемы, производительность процессоров и. т. д. Усовершенствования были, но они не соответствовали темпам развития других компонентов и касались лишь таких параметров, как время выборки, был добавлен кэш непосредственно на модуль памяти, конвейерное исполнение запроса, изменен управляющий сигнал вывода данных, но технология производства оставалась прежней, исчерпавшей свой ресурс. Память становилась узким местом компьютера, а, как известно, быстродействие всей системы определяется быстродействием самого медленного ее элемента. И вот несколько лет назад волна технологического бума докатилась и до оперативной памяти. Быстрое усовершенствование оперативной памяти позволило кроме ее усовершенствования, значительно снизить цену на нее. Но даже после падения цен, память системы, как правило, стоит вдвое дороже, чем системная плата. До обвального падения цен на память в середине 1996г. в течении многих лет цена одного мегабайта памяти держалась приблизительно на уровне 40 долларов. К концу 1996г. цена одного мегабайта памяти снизилась примерно до 4 долларов. Цены продолжали падать, и после главного обвального падения стоимость одного мегабайта не превышает доллара, или приблизительно 125 доларов за 128 Мбайт. Хотя память значительно подешевела, модернизировать приходится ее намного чаще, чем несколько лет назад. В настоящее время новые типы памяти разрабатываются намного быстрее, и вероятность того, что в новые компьютеры нельзя будет устанавливать память нового типа, как никогда велика. От количества установленной в компьютере оперативной памяти напрямую зависит возможность, какими программами вы сможете на нем работать. При недостаточном количестве оперативной памяти многие программы либо вовсе не будут работать, либо станут работать крайне медленно. Можно привести следующую приблизительную классифика-цию возможностей компьютера, в зависимости от объема оперативной памяти: 1 Мбайт и менее - на компьютере возможна работа только в среде DOS. Такие компьютеры можно использовать для корректировки текстов или ввода данных; 4 Мбайта - на компьютере возможна работа в среде DOS, Windows 3.1 и Windows for Workgroups. Работа в DOS вполне комфортна, а в Windows - нет: некоторые Windows-программы при таком объеме памяти не работают , а некоторые позволяют обрабатывать лишь небольшие и несложные документы. Одновременный запуск нескольких Windows-программ также может быть затруднен; 8 Мбайт - обеспечивается комфортная работа в среде Windows 3.1, Windows for Workgroups, при этом дальнейшее увеличение объема оперативной памяти уже практически не повышает быстродействие для большинства офисных приложений. Использование более новых операционных систем, как Windows 95 и OS/2 Warp, в принципе возможно, но работать они будут явно медленно; 16 Мбайт - обеспечивается комфортная работа в операционных системах Windows 95 и OS/2, причем дальнейшее увеличение объема оперативной памяти уже практически не повышает быстродействие при выполнении большинства офисных приложений. Возможно использование Windows NT, хотя ей не помешает добавить еще 8-16 Мбайт; 32 Мбайта и более - такой объем оперативной памяти может требоваться для серверов локальных сетей, компьютеров, используемых для обработки фотоизображений или видеофильмов, и в некоторых других приложениях. Полезен он может быть и для компьютеров, работающих под управлением ОС Windows NT. Всю память с произвольным доступом (RAM) можно разделить на два типа: 1. DRAM (динамическая RAM) 2. SRAM (статическая RAM). Причем независимо от типа оперативная память ЭВМ является адресной. Это значит, что каждой, хранимой в памяти единице информации ставится в соответствие специальное число, а именно адрес, определяющий место его хранения в памяти. В современных ЭВМ различных типов, как правило, минимальной адресуемой единицей информации является байт (8-ми разрядный код). Более крупные единицы информации - это слово и производные: двойное слово, полуслово и т. д. (образуется из целого числа байт). Обычно слово соответствует формату данных, наиболее часто встречающихся в данной машине в качестве операндов. Часто формат слова соответствует ширине выборке из основной памяти Существуют несколько методов организации оперативной памяти: 1) Метод строк/колонок (Row/column) . При данном методе адресации ОП, последняя представляет собой матрицу разделенную на строки и колонки. При обращении к ОП одна часть адреса определяет строку, а другая - колонку матрицы. Ячейка матрицы, оказавшаяся на пересечении выбранных строки и колонки считывается в память или обновляется ее содержимое. 2) Метод статических колонок (Static-column) . При данном методе адресации ОП информация, относящаяся к какой-либо программе, размещается в определенной колонке. Последующее обращение к данной программе происходит в ту же самую колонку. За счет статичности части адреса (ее не надо передавать по адресной шине) доступ к данным осуществляется быстрее. 3) Метод чередования адресов (Interleaved) , который впервые стал применяться в 386 моделях АТ компьютерах. Данный метод предполагает считывание (или запись) информации не по одному, а сразу по нескольким адресам: i, i+1, i+2 и т.д. Количество одновременно опрашиваемых адресов, по которым происходит считывание информации, определяет кратность чередования адресов, что соответствует количеству блоков ОП. На практике обычно используется 2-х или 4-х кратное чередование адресов, т.е. ОП делится на 2 или 4 блока.Запись информации в блоки осуществляется независимо друг от друга. Информация по адресу i хранится в первом блоке, по адресу i+1 - во втором блоке и т.д. Считываемая с блоков информация далее переписывается в кэш-память для последующей переработки. 4) Метод страничной организации (Page-mode) . При данном методе организации память адресуется не по байтам, а по границам страниц. Размер страницы обычно равен 1 или 2 Кбайта. Данный метод предполагает наличие в системе кэш-памяти емкостью не менее 128 Кб куда предварительно считываются требуемые страницы ОП для последующей переработки МП или другим устройством. Обновленная информация периодически из кэш-памяти сбрасывается в ОП. Последние два метода системной организации памяти предполагают обязательное наличие в системе сверх быстродействующей кэш-памяти для опережающего (read-ahaed) чтения в нее информации из ОП с последующей обработкой ее микропроцессором, что снижает время простоя последнего и повышает общую производительность системы. 1. Решение задач на языке TurboPascal. Задачи на массивы данных Массив
– упорядоченный конечный набор однотипных данных. У каждого элемента массива есть индекс (номер). Массив характеризуется именем, количеством измерений (может быть одномерным, двумерным и т.д.) и размером. Например, набор чисел: 2, 4, 6, 8, 10 можно рассматривать как массив А(5), состоящий из элементов: а1
=2, а2
=4, а3
=6, а4
=8, а5
=10. Четвертый элемент (индекс равен 4) этого массива равен 8. Тип массива обозначается зарезервированным словом ARRAY, после которого указывается диапазон изменения номеров элементов и (после слова OF) тип элементов массива. Общий вид описания одномерного массива в разделе VAR: V: ARRAY [N..M] OF T; где V – имя массива; N и M – нижний и верхний индексы массива; Т – тип массива. Например: M1: array [5..100] ofreal; {массив М1 действительных чисел с номерами от 5 до 100}; I: array [-1..5] ofinteger; {I – массив целых чисел с номерами от –1 до 5}; Один и тот же массив можно описать различными способами. Например, массив А, состоящий из 50 элементов, можно описать следующими способами: 1 способ: VAR A: ARRAY [1..50] OF REAL; 2 способ: CONST N=50; VAR A:=ARRAY [1..N] OF REAL; 3 способ: TYPE T=ARRAY [1..50] OF REAL; VARA:T; При третьем способе типу массива А дается имя T с помощью описания типа (после слова TYPE). Это описание типа помещается в программу перед совокупностью описания переменных (перед VAR). В программе элементы массивов вводятся и выводятся в цикле, организованном с помощью оператора FOR. Задача на двумерный массив Определить количество положительных и отрицательных элементов каждой строки матрицы В(7,6) и записать результаты в новые массивы С и D. program massiv; var i,j,p,o:integer; b:array[1..7, 1..6] of integer; c,d:array[1..7]of integer; begin writeln(‘Введите массив b(7,6)’); for i:=1 to 7 do for j:=1 to 6 do readln(b[i,j]); for i:=1 to 7 do begin p:=0; o:=0; for j:=1 to 6 do if b[i,j] >=0 then p:=p+1 else o:=o+1; c[j]:=p; d[j]:=o; end; for i:=1 to 7 do writeln(‘c[‘,i,’]=’,c[i], ‘d[‘,i,’]=’,d[i]); end. ввод: ответ: c[1]=4 d[1]=2 c[2]=4 d[2]=2 c[3]=5 d[3]=1 c[4]=4 d[4]=2 c[5]=3 d[5]=3 c[6]=5 d[6]=1 c[7]=3 d[3]=3 1.2. Построение графика функции в алфавитно-цифровом или графическом режиме
Пусть нужно вывести на алфавитно-цифровой экран монитора график функции y= f(x) в заданном диапазоне изменения аргумента х
от а до b с числом точек графика n (n£25). Перед выводом графика нужно напечатать вычисленные значения yi
в виде таблицы, также напечатать наибольшее и наименьшее значения функции f(x). Рассмотрим решение этой задачи на конкретном примере: Примем ширину поля графика w, равной 61 позиции. Отступим от левого края экрана на m= 10 позиций. Для вывода строки графика выделим символьный массив С, состоящий из (w+m) элементов, т.е. 71 элемента. Масштаб по оси х примем равным шагу h при перемещении на одну строку. Масштаб по оси y выберем таким, чтобы максимально использовать поле графика w. Для это необходимо вычислить ymax
= max {yi
} и ymin
= min{yi
} i
i
Определим масштаб my
по формуле: где ] [ - целая часть выражения; 0.5 добавлено для округления до ближайшего целого. Масштаб my
означает, что при каждом изменении значения функции на величину my
символ, изображающий точку на графике, смещается в очередную позицию по строке. По вычисленным значениям ymin
и my
определим номер позиции k, в которой изображается ось 0x
: Для определения номера l позиции в строке, в которой надо изобразить значение yi
,
воспользуемся формулой Для вывода собственно графика в цикле в очередной строке, соответствующей значениям аргумента xi
и функции yi
, выведем символ ‘I’ в позиции с номером k и символ ‘*’ в позиции с номером l
( при l
= k
в данной позиции следует выводить символ ‘*’). Схема алгоритма решения задачи имеет вид: Начало11
1
a, b, n w, m 12
Ck
=’I’ 2
Заполнение массива С 13
Заголовок пробелами 14
i = 1, n 3
h = ymax
=-105
15
ymin
=+105
x = a 16
Cl
= `*` 4
i = 1, n 17
печать массива C 5
yi
=
f(x) 6
yi
> ymax
нет
18
Cl
= ` ` да8
yi
< ymin
нет
7
ymax
=yi
да нет
19
k = l 9
ymin
= yi
да 20
Cl
= `I` 10
x = x + h конец Пояснения
. В блоке 2 символьный массив С заполняется пробелами. Блоки 3-10 организуют вычисление текущего значения функции yi
= f(xi
), запоминание вычисленных значений yi
в массиве y, состоящем из n элементов, вычисления наибольшего и наименьшего значений функции на заданном интервале изменения – аргумента x
. В блоках 11-12 вычисляется масштаб my
графика по оси y, номер k позиции в строке графика, соответствующий оси 0х
, и осуществляется присваивание k-тому элементу массива c
символа I. Вычисление номера l
в строке, соответствующей точке графика, занесение в l
-й элемент массива c
символа ‘*’ и печать символьного массива c
реализуется блоками 15-17; восстановление символьного массива c
в исходное состояние – блоками 18-20. Программа, реализующая схему алгоритма, имеет вид: PROGRAM GRAFIK; CONST W = 61; M = 10; VAR Y: ARRAY [1..25] OF REAL; C: ARRAY [1..71] OF CHAR; K, L, N, I, J: INTEGER; A, B, H, Y MAX, Y MIN, X, MY: REAL; BEGIN WRITELN (¢ВВЕДИТЕ A, B, N¢); READ (A, B , N); Y MAX = -1E4; YMIN:=+1E4; H: = (B-A)/N; X: = A; FOR I: = 1 TO N DO BEGIN Y[ I ]: = SIN(X)/X ; IF Y [I ] > Y MAX THEN Y MAX: = Y [I ]; IF Y [I ] < Y MIN THEN Y MIN: = Y [I ]; X: = X+H; END; MY:=ROUND((YMAX-YMIN)/W+0.5); K:=ROUND (ABS(YMIN)/MY+0.5)+M; C[K]:= ¢I ¢ ; WRITELN (¢ГРАФИКФУНКЦИИ Y=SIN(X)/X ¢); WRITELN (¢ …………………………………¢); FOR I:=1 TO N DO BEGIN L:=ROUND ((Y[ I ]- YMIN)/MY+0.5)+M; C[ L]: = ¢ *¢; FOR J: = 1 TO 71 DO WRITE (C[J]); END; END. ввод: a=0.1 b=2.5 n=40 2. Численные методы решения задач
2.1. Решение алгебраических и трансцендентных уравнений
К линейным уравнениям относятся алгебраические и трансцендентные уравнения. Уравнение называется алгебраическим, если функция f(x) представляет собой многочлен, какой-либо степени. f(x)=a0
xm
+a1
xm-1
+…+am-1
x+am
=0 m Если же в функцию f(x) входят одновременно разные элементарные функции, то такое уравнение называется трансцендентным
. f(x)=sinx+lnx=0 Такие уравнения решаются приближенными методами. Решение разбивается на 2 этапа: 1). Отделение корней, т.е. нахождение достаточно малой области, содержащий один корень. 2). Уточнение корня заданной степенью точности. Здесь известны следующие методы итераций, ньютона, хорды касательной половинного деления и т.д. Отделение корней.
Пусть решается уравнение f
(
x
)=
sinx
+
lnx
=0
. Отделение корней можно сделать 2-мя способами: графическим и алгебраическим. В графическом методе на координатной плоскости строится график функции и находится область пересечения функции с осью Х. В нашем случае удобно функцию разделить на 2 функции и на координатной плоскости построить оба графика, и найти область их пересечения. sinx=-lnx x [0;1] В алгебраическом методе отделения корней с некоторым шагом h просматривают достаточно большую область существования корня уравнений. Из математики известно, что непрерывная функция на небольшом отрезке содержит корень уравнения, если на концах отрезках функция f(x) имеет разные знаки. Уточнение корня по методу половинного деления.
Пусть решается уравнение f(x)=0 и функция f(x) непрерывна на отрезке [a,b] =[x1
,x2
]. Отрезок [a,b] содержит корень, т.е. f(a)*f(b)<0. Делим отрезок [a,b] пополам, т.е. выбираем начальное уравнение корня x= [b-a]< e =10-5
. Схема реализации алгоритма имеет вид: [a,b]=[x1
,x2
] e=10-5
Уточнение корня по методу Хорд
По методу Хорд выбирается произвольное начальное значение корня из отрезка [a,b] на котором корень существует xÎ[a,b]=[x1
,x2
]. Затем по методу Хорд корень уточняется. Найденное новое значение корня подставляется в правую часть уравнения и т.д. пока разность между двумя приближениями не станет меньше xn
+1
=
xn
-
Графический метод Хорд имеет вид: x
1
=a
x
1
=x2
x2
=x1
+h y1
=y2
ввод: 0.1,10,1e-4 ответ: х1=0.10000 х2=1.10000 Уточнение корней
a=x y=z begin if z=0 then goto 2; if y*z<0 then b:=x; begin a:=x; y:=f(b); end; if b-a>e then goto 10; 2:writeln('x=',x:8:5); readln; end. ввод: 0.1, 1.1, 1е-5 ответ: х=0.78111 М
етод хорд
y=f(x)/(f(b)-f(x))*(b-x) x:=y; if d>e then goto 10; y:=f(x); writeln('x=',x:8:5); end. ввод: 0.1, 1.1, 1е-5 ответ: х=0.78110 Проверка уравнения в ППП "Eureka"
Ввод: 2.2*
x
-
exp
(
x
*
ln
(2))=0
Ответ: X=0.78091254 Maximum error is 3.5465456e-7 2.2. Решение систем линейных уравнений методом итераций.
Метод итераций Гаусса-Зейделя
Метод последовательных приближений или итераций для больших n даёт сокращение времени решения на 20-30% по сравнению с точными методами. В методе итераций число действий пропорционально числу n2
, тогда как в точных методах n3
. Метод итераций особенно выгоден при решении систем, в которых много коэффициентов равно нулю. Рассмотрим метод на примере 3-х уравнений с тремя неизвестными. Дана система: a11
x1
+a12
x2
+a13
x3
=b1
a21
x1
+a22
x2
+a23
x3
=b2
a31
x1
+a32
x2
+a33
x3
=b3
Для сходимости метода итераций диагональные элементы системы должны быть преобладающие, т.е. |aii
|>>|aij
| Если это условие не выполняется, то делают элементарные преобразования системы. Например: x1
-6x2
=4 (2) 3x1
+x2
+x3
=-5 (1) 2x1
-8x3
=7 (3) 3x1
+x2
+x3
=-5 x1
-6x2
=4 2x1
-8x3
=7 Из 1-го уравнения преобразованной системы найдём х1
, из 2-го х2
из 3-го х3
. Получим: x1
=(b1
-a12
x2
-a13
x3
)/a11
x2
=(b2
-a21
x1
-a23
x3
)/a22
x3
=(b3
-a31
x1
-a32
x2
)/a33
Для удобства реализации алгоритма вычисляемое значение обозначим yi
. Получим: y1
=(b1
-a12
x2
-a13
x3
)/a11
y2
=(b2
-a21
x1
-a23
x3
)/a22
y3
=(b3
-a31
x1
-a32
x2
)/a33
Для нашего примера система примет вид: y1
=(-5-x2
-x3
)/3 y2
=(4-x1
)/(-6) y3
=(7-2x1
)/(-8) В качестве начального приближения для х1
;x2
;x3
, берётся 0 или 1. Подставляется в правую часть системы, получается новое значение xi
, которое снова подставляется в правую часть и т.д. Пока разность между приближениями не станет меньше d). program lin; var b1,d,x1,x2,x3,x4,e,y1,y2,y3,y4:real; begin x1:=0; x2:=0; x3:=0; x4:=0; e:=1e-5; repeat y1:=(-9-x2+x4)/4; y2:=(-y1+x3-3*x4)/2; y3:=(-7-x1+3*y2)/4; y4:=(2-3*x2+2*y3)/4; d:=sqrt(sqr(x1-y1)+sqr(x2-y2)+sqr(x3-y3)+sqr(x4-y4)); x1:=y1; x2:=y2; x3:=y3; x4:=y4; until d>E; b1:=x1+2*x2-x3-3*x4; writeln('x1= ',x1:8:5,' x2= ',x2:8:5, x1
=1; x2
=1; x3
=1; x4
=1; e=10-5
Проверка в ППП "Eureka"
4*x1+x2-x4=-9 x1-3*x2+4*x3=-7 3*x2-2*x3+4*x4=12 x1+2*x2-x3-3*x4=0 Ответ: Х1=-3.000000 Х2=4.000000 Х3=2.000000 X4=1.000000 Если функция f(x) непрерывна на отрезке [a,b] и известна ее первообразная F(x), то определенный интеграл от этой функции в пределах от а до b может быть вычислен по формуле Ньютона-Лейбница Как правило, выразить первообразную функцию удаётся не всегда, поэтому приходиться прибегать к приближённому интегрированию. Существует много численных методов: прямоугольников, трапеций, парабол или Симпсона и т.д. Метод прямоугольников
Из математики известно, что интеграл равен площади криволинейной трапеции, ограниченной кривой f(x) осью Х и ординатами в точках а и b. Для приближенного вычисления площади разобьём отрезок [а,b] на n части длинной h
=(
b
-
a
)/
n
.
В точках разбиения проведем ординаты до пересечения с кривой y=f(x), а концы ординат соединим прямоугольными отрезками, тогда площадь криволинейного приближенного прямоугольника можно считать равной площади фигуры ограниченной ломанной линией aABb. Площадь этой фигуры, которую обозначим через S, равна сумме площадей прямоугольников. S
=
h
(
y
0
+
y
1
+
y
2
+…+
yn
)
Таким образом, приближенное значение интеграла по формуле прямоугольников запишется в виде Точность метода с постоянным шагом h примерно e Метод трапеции
В этом методе начальные построения те же, только при вычислении площади криволинейной трапеции ординаты сверху соединяются ломаной линией. Получается множество прямоугольных трапеций. Площадь одной трапеции равна: S
тр
=
Отсюда: y = h.
Точность Е
Метод Симпсона (парабол)
В этом методе отрезок [a,в] разбивается на 2n
частей, длинной h= Расчетная формула имеет вид : у y0
= f(a), y1
= f(a+2h), y2
= f(a+2h)… y2n-1
= f(в-h) y2
n
= f(в). +1при i- нечётн. -1 при i- чётн. ci
= у end; y:=y*(b-a)/n; writeln('y=',y:8:5); readln; end. ОТВЕТ: y=0.28099 h=(b-a)/n x=a+h x:=x+h; end; y:=s*h; writeln('y=',y:8:5); readln; end. ОТВЕТ: y=0.28173 h=(b-a)/2n c:=1 x:=x+h c:=-c; if x<= b-h then goto 10; y:=s*h/3; writeln('y=',y:8:5); readln; end. ОТВЕТ: y= 0.27919 Решение интеграла в ППП "Eureka"
y=integ((sin(x^2+0.5)/cos(x^2+0.5))/(1+2*x^2),x,0.4,0.8) y=0.2823564 2.4 Методы решения дифференциальных уравнений
При использовании различных протекающих во времени процессах первым этапом является составление дифференциального уравнения,
описывающего процесс, а вторым – поиск решения этого уравнения. Дифференциальным уравнением называется равенство, связывающее значение аргумента, неизвестной функции некоторых ее производных. Наивысший порядок входящих в уравнение производных называется порядком дифференциального уравнения.
Рассмотрим уравнение вида: y=f(x,y) (1) Уравннение (1) имеет бесконечное множество решений (рис. 1) – через каждую точку плоскости проходит интегральная кривая. Чтобы выделить одну кривую, нужно указать точку плоскости, через которую проходит кривая, т.е. указать так называемые начальные уравнения (значения x=x0
и y=y0
) (2) Метод Эйлера
Одним из методов решения дифференциального уравнения (1) с начальным условием (2) является метод Эйлера. Будем рассматривать уравнение (1) на некотором отрезке [a,b]. Пусть отрезок поделен на n частей с шагом Обозначим X0
=a, X1
=X0
+h, X2
=X0
+2h,…, Xn
=X0
+nh=b. Обозначим искомые y(X1
),…y(Xn
) через y1
…yn
. Методика решения уравнения (1) с начальными условиями (2) связяна с разложением решения в ряд Тейлора в h-окрестности точки X0
. При отбрасывании членов ряда, содержащие производные второго и высшего порядков, получим где f(X,y) – правая часть уравнения (1). Таким образом, . При достаточно малой величине шага h метод Эйлера дает решения с большей точностью, т.к. погрешность близка к h2
(h<<1) на каждом шаге интегрирования. Метод Рунге-Кутта
Недостатком метода Эйлера является змедление вычислений при выборе малой величины шага h, задающей точность решения. Наиболее распространенным методом численного интегрирования дифференциальных уравнений служит метод Рунге-Кутта, обеспечивающий ускорение за счет большей точности вычислений на каждом шаге. Точность метода Рунге-Кутта оценивается величиной E≈h2
. Уточнение достигается за счет специального подбора координат четурех точек, в которых вычисляется первая производная f(x,y). Вместо первой производной h∙f(x,y) используемой в формуле Эйлера, вычисляется усредненная первая производная fi
. Формулы интегрирования по методу Рунге-Кутта имеют вид: где y’=(1-y2
)cos(x)+0.6y при х0
=0; xn
=1; у0=0; h=0.1 program eyler; label 100; const h=0.1; x0=0; xk=1; у0=0; х0=а; var h,y,x:real; i: integer; function f (x,y: real): real; begin f:= (1-y*y)*cos(x)+0.6*y; end; begin y:=y0; x:=x0; 100: y:=y+h*f(x,y); x:=x+h; writeln(‘ x=',x:5:1,' y=',y:8:5); if x<xk then goto 100; readln; end. x=0.1 y=0.1000 x=0.2 y=0.2045 x=0.3 y=0.3107 x=0.4 y=0.4156 x=0.5 y=0.5168 x=0.6 y=0.6121 x=0.7 y=0.7004 x=0.8 y=0.7814 x=0.9 y=0.8554 x=1.0 y=0.9234 при х0
=0; xn
=1; у0=0; h=0.1 program rungekutta; label 100; var x,p,x0,y0,xk,y,a,b,c,d,h:real; function f(x,y:real):real; begin f:= (1-y*y)*cos(x)+0.6*y; end; begin x0:= 0; xk:=1; y0:= 0; h:=0.1; x:=x0;y:=y0; 100: a:=h*f(x,y); b:=h*f(x+h/2,y+a/2); c:=h*f(x+h/2,y+b/2); d:=h*f(x+h,y+c); p:=(a+2*b+2*c+d)/6; y:=y+p; writeln('x=',x:8:1,'y=',y:8:5); if x<xk then goto 100; readln; end. ответ: x=0.1 y=0.1025 x=0.2 y=0.2082 x=0.3 y=0.3141 x=0.4 y=0.4173 x=0.5 y=0.5156 x=0.6 y=0.6076 x=0.7 y=0.6926 x=0.8 y=0.7705 x=0.9 y=0.8419 x=1.0 y=0.9081 3. Оптимизационные модели
3.1. Решение транспортной задачи
Транспортная задача является частным случаем общей задачи линейного программирования. В линейном программировании функция цели и система ограничений заданна линейно. Транспортная задача может быть решена основным методом линейного программирования – симплекс метода
, но для неё разработаны более удобные и эффективные методы, в частности метод потенциала
. Алгоритм транспортной задачи был впервые применён для рационализации перевозов груза, поэтому получил название транспортная задача
. Постановка задачи
Имеется m отправителей и n потребителей однородного груза. Запасы грухов у отправителей – ai
, потребность в грузе у получателей – bj
. Известна стоимость Сij
перевозки единицы от каждого отправителя до каждого получателя. Требуется определить оптимальную схему перевозки груза от отправителей к получателям так, чиобы суммарные транспортные расходы были min. Обычно условие задачи записывается в виде таблицы: Запасы ai
С11
X11
С12
X12
С1n
X1n
С2
1
X21
С22
X22
С2n
X2n
Сm1
Xm1
Сm2
Xm2
Сmn
Xmn
Потребность bj
xij
– количество груза, перевозимого от ai
отправителя к bj
потребителю. При решении транспортной задачи должны выполняться 4 условия: 1. Все запасы грузов должны быть вывезены, т.е. 2. Все потребности в грузе должны быть удовлетворены, т.е. 3. Суммарные транспортные затарты должны быть min
, т.е. F=C11
∙X11
+ C12
∙X12
+…+ Cmn
∙Xmn
® min или Существуют следующие методы решения задач: 1 Метод приближением условно оптимальными планами. 2 Метод потенциалов. 3 Метод рент. 4 Метод Филкерсона и т.д. Расстановка поставок методом двойного предпочтения 1 итерация 5 4 2 45 2 45 3 80 6 3 1 15 1 10 2 90 3 7 0 0 -3 0 135 0 Fmin
=90+90+240+15+10+180=625 2 итерация 5 4 2 90 2 3 35 6 3 -1 1 60 1 55 2 45 3 7 0 0 45 0 90 0 Fmin
=180+105+60+55+90=490 Конечная таблица
|