1. Решение задач на языке Turbo Pascal.

Задачи на массивы данных

Массив – упорядоченный конечный набор однотипных данных.

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

Например, набор чисел: 2, 4, 6, 8, 10 можно рассматривать как массив А(5), состоящий из элементов: а₁=2, а₂=4, а₃=6, а₄=8, а₅=10. Четвертый элемент (индекс равен 4) этого массива равен 8.

Тип массива обозначается зарезервированным словом ARRAY, после которого указывается диапазон изменения номеров элементов и (после слова OF) тип элементов массива.

Общий вид описания одномерного массива в разделе VAR:

V: ARRAY [N..M] OF T;

где V – имя массива; N и M – нижний и верхний индексы массива; Т – тип массива.

Например:

M1: array [5..100] of real; {массив М1 действительных чисел с номерами от 5 до 100};

I: array [-1..5] of integer; {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;

VAR A:T;

При третьем способе типу массива А дается имя T с помощью описания типа (после слова TYPE). Это описание типа помещается в программу перед совокупностью описания переменных (перед VAR).

В программе элементы массивов вводятся и выводятся в цикле, организованном с помощью оператора FOR.

Задача на двумерный массив

начало

ввод b_i,j

i=1,7

p=0 o=0

b_i,j>=0

вывод массивов c(7), d(7)

конец

Да

Нет

j=1,6

j=1,6

i=1,7

p=p+1

o=o+1

c_j=p d_j=o

Определить количество положительных и отрицательных элементов каждой строки матрицы В(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). Перед выводом графика нужно напечатать вычисленные значения y_i в виде таблицы, также напечатать наибольшее и наименьшее значения функции f(x).

Рассмотрим решение этой задачи на конкретном примере:

. Число точек графика равно 20.

Примем ширину поля графика w, равной 61 позиции. Отступим от левого края экрана на m= 10 позиций. Для вывода строки графика выделим символьный массив С, состоящий из (w+m) элементов, т.е. 71 элемента. Масштаб по оси х примем равным шагу h при перемещении на одну строку. Масштаб по оси y выберем таким, чтобы максимально использовать поле графика w. Для это необходимо вычислить

y_max = max {y_i} и y_min = min{y_i}

i i

Определим масштаб m_y по формуле:

где ] [ - целая часть выражения; 0.5 добавлено для округления до ближайшего целого.

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

По вычисленным значениям y_min и m_y определим номер позиции k, в которой изображается ось 0_x :

Для определения номера l позиции в строке, в которой надо изобразить значение y_i, воспользуемся формулой

.

Для вывода собственно графика в цикле в очередной строке, соответствующей значениям аргумента x_i и функции y_i, выведем символ ‘I’ в позиции с номером k и символ ‘*’ в позиции с номером l ( при l= k в данной позиции следует выводить символ ‘*’).

Схема алгоритма решения задачи имеет вид:

Начало ¹¹

¹ a, b, n

w, m ¹²

C_k =’I’

² Заполнение

массива С ¹³ Заголовок

пробелами

¹⁴ i = 1, n

³ h =

y_max=-10^{5 15}

y_min =+10⁵

x = a

¹⁶C_l = `*`

⁴ i = 1, n ₁₇ печать

массива C

⁵ y_{i =} f(x)

₆ y_i> y_max ^{нет 18} C_l = ` `

да ⁸ y_i< y_min ^нет

⁷ y_max=y_i да ^нет ₁₉ k = l

⁹ y_min= y_i да

²⁰ C_l = `I`

¹⁰ x = x + h конец

Пояснения. В блоке 2 символьный массив С заполняется пробелами. Блоки 3-10 организуют вычисление текущего значения функции y_i = f(x_i), запоминание вычисленных значений y_i в массиве y, состоящем из n элементов, вычисления наибольшего и наименьшего значений функции на заданном интервале изменения – аргумента x. В блоках 11-12 вычисляется масштаб m_y графика по оси 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;

FOR I:=1 TO 71 DO C [ I ]: =  ;

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]);

WRITELN ( );

C[ L]: =  ;

IF K =L THEN C [ L ]:= I;

END;

END.

ввод:

a=0.1

b=2.5

n=40

2. Численные методы решения задач

2.1. Решение алгебраических и трансцендентных уравнений

К линейным уравнениям относятся алгебраические и трансцендентные уравнения. Уравнение называется алгебраическим, если функция f(x) представляет собой многочлен, какой-либо степени.

f(x)=a₀x^m+a₁x^m-1+…+a_m-1x+a_m=0

m3

Если же в функцию f(x) входят одновременно разные элементарные функции, то такое уравнение называется трансцендентным.

f(x)=sinx+lnx=0

Такие уравнения решаются приближенными методами. Решение разбивается на 2 этапа:

1). Отделение корней, т.е. нахождение достаточно малой области, содержащий один корень.

2). Уточнение корня заданной степенью точности.

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

Отделение корней.

Пусть решается уравнение f(x)=sinx+lnx=0. Отделение корней можно сделать 2-мя способами:

графическим и алгебраическим.

В графическом методе на координатной плоскости строится график функции и находится область пересечения функции с осью Х. В нашем случае удобно функцию разделить на 2 функции и на координатной плоскости построить оба графика, и найти область их пересечения.

sinx=-lnx

у

f₁(x)=sinx

f₂(x)=-lnx

x [0;1]

f₂(x)

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

f(x)

х

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

Уточнение корня по методу половинного деления.

Пусть решается уравнение f(x)=0 и функция f(x) непрерывна на отрезке [a,b] =[x₁,x₂].

Отрезок [a,b] содержит корень, т.е. f(a)*f(b)<0.

Делим отрезок [a,b] пополам, т.е. выбираем начальное уравнение корня x=, если f(x)=0, то х является корнем уравнения, если f(x) не равно нулю, то выбираем тот из отрезков [a,x] или [x,b], на концах которого функция f(x) имеет противоположные знаки. Выбранный отрезок снова делим пополам и проводим те же рассуждения. Процесс деления отрезков пополам продолжается до тех пор, пока длина отрезка на концах которого функция имеет разные знаки не станет < 

[b-a]<  =10^-5 .

у

х

b

x=

Схема реализации алгоритма имеет вид: [a,b]=[x₁,x₂] =10^-5

Уточнение корня по методу Хорд

По методу Хорд выбирается произвольное начальное значение корня из отрезка [a,b] на котором корень существует x[a,b]=[x₁,x₂].

Затем по методу Хорд корень уточняется. Найденное новое значение корня подставляется в правую часть уравнения и т.д. пока разность между двумя приближениями не станет меньше < =10^-5. Расчётная формула метода Хорд имеет вид:

x_n+1=x_n-(b-x).

Графический метод Хорд имеет вид:

у

х

начало

ввод a, b, h

program otd;

x₁=a

x₂ =x₁ + h

a,b,x1,x2,y1,y2,h,d:real;

y₁=f(x₁)

begin

y₂=f(x₂)

Нет

Да

вывод x,y

readln(a,b,h);

x₁=x₂

x₂=x₁+h

y₁=y₂

y1:=f(x1);

10: y2:=f(x2);

Да

x1:=x2;x2:=x1+h;

Нет

конец

readln;

end.

ввод:

0.1,10,1e-4

ответ:

х1=0.10000

х2=1.10000

Уточнение корней

ввод a, b, e

y=f(a)

x =(a+b)/2

label 2, 10;

z=f(x)

Да

Нет

Нет

f:= 2.2*x-exp(x*ln(2));

a=x

y=z

end;

begin

Да

b-a

Нет

вывод x

конец

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

Метод хорд

ввод x, , b

y=f(x)/(f(b)-f(x))*(b-x)

label 10;

d=|y-x|

x=y

begin

Да

Нет

y=f(x)

writeln(‘введите x,b,e’);

вывод x, y

10: y:=x-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% по сравнению с точными методами.

В методе итераций число действий пропорционально числу n², тогда как в точных методах n³.

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

Дана система:

a₁₁x₁+a₁₂x₂+a₁₃x₃=b₁

a₂₁x₁+a₂₂x₂+a₂₃x₃=b₂

a₃₁x₁+a₃₂x₂+a₃₃x₃=b₃

Для сходимости метода итераций диагональные элементы системы должны быть преобладающие, т.е.

__

Если это условие не выполняется, то делают элементарные преобразования системы.

Например:

x₁-6x₂=4 (2)

3x₁+x₂+x₃=-5 (1)

2x₁-8x₃=7 (3)

3x₁+x₂+x₃=-5

x₁-6x₂=4

2x₁-8x₃=7

Из 1-го уравнения преобразованной системы найдём х₁, из 2-го х₂ из 3-го х₃. Получим:

x₁=(b₁-a₁₂x₂-a₁₃x₃)/a₁₁

x₂=(b₂-a₂₁x₁-a₂₃x₃)/a₂₂

x₃=(b₃-a₃₁x₁-a₃₂x₂)/a₃₃

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

y₁=(b₁-a₁₂x₂-a₁₃x₃)/a₁₁

y₂=(b₂-a₂₁x₁-a₂₃x₃)/a₂₂

y₃=(b₃-a₃₁x₁-a₃₂x₂)/a₃₃

Для нашего примера система примет вид:

y₁=(-5-x₂-x₃)/3

y₂=(4-x₁)/(-6)

y₃=(7-2x₁)/(-8)

В качестве начального приближения для х₁;x₂;x₃, берётся 0 или 1. Подставляется в правую часть системы, получается новое значение x_i, которое снова подставляется в правую часть и т.д. Пока разность между приближениями не станет меньше d).

<=10^-5

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,

начало

x₁=1; x₂=1; x₃=1; x₄=1;

e=10^-5

y1:=(-9-x2+x4)/4

y2:=(-y1+x3-3*x4)/2

y3:=(-7-x1+3*y2)/4

y4:=(2-3*x2+2*y3)/4

Нет

x₁=y₁; x₂=y₂; x₃=y₃; x₄=y₄

d>

x3= 1.99999

b1=x1+2*x2-x3-3*x4

b1= 0.000000

вывод x_1, x_2, x_3, x_4, b₁

конец

Проверка в ППП "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

2.3. Методы вычисления определённых интегралов

Если функция f(x) непрерывна на отрезке [a,b] и известна ее первообразная F(x), то определенный интеграл от этой функции в пределах от а до b может быть вычислен по формуле Ньютона-Лейбница

.

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

Метод прямоугольников

Из математики известно, что интеграл равен площади криволинейной трапеции, ограниченной кривой f(x) осью Х и ординатами в точках а и b.

Для приближенного вычисления площади разобьём отрезок [а,b] на n части длинной h =(b-a)/n.

В точках разбиения проведем ординаты до пересечения с кривой y=f(x), а концы ординат соединим прямоугольными отрезками, тогда площадь криволинейного приближенного прямоугольника можно считать равной площади фигуры ограниченной ломанной линией aABb. Площадь этой фигуры, которую обозначим через S, равна сумме площадей прямоугольников.

S=h(y₀+y₁+y₂+…+y_n)

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

Точность метода с постоянным шагом h примерно h.

Метод трапеции

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

х

у

a

в

h

Получается множество прямоугольных трапеций. Площадь одной трапеции равна:

S_тр=^.h

Отсюда: y^.h + ^.h + … +^.h =

= h ^. + f(a + h) +…+ f(в-h)=+

Точность Е h²

Метод Симпсона (парабол)

В этом методе отрезок [a,в] разбивается на 2_n частей, длинной h=и ординаты сверху соединяются кривой второго порядка (3 соседних точки).

a

у

h

Расчетная формула имеет вид :

у(y₀ + 4y₁+ 2y₂ + 4y₃ + …+ 4y_2n*1 + y_2n)

y₀= f(a), y₁= f(a+2h), y₂= f(a+2h)… y_2n-1= f(в-h)

y_2n= f(в).

+1при i- нечётн.

-1 при i- чётн.

c_i= , тогда формула примет вид:

у(f(a)+f(в)+(3+c_i))

начало

CONST a= 0.4 ; b= 1.2; n=100;

ввод а, b, n

у=0; х=а

i=1,n

begin

y=y+f(x)

end;

x=x+(b-a)/n

y:=0; x:=a;

y=y*(b-a)/n

begin

вывод y

конец

end;

y:=y*(b-a)/n;

writeln('y=',y:8:5);

readln;

end.

ОТВЕТ:

y=0.28099

ввод а, b, n

у=0; х=а

h=(b-a)/n

x=a+h

var x,y,h,s:real;

s:=(f(a)+f(b))/2

xb-h

begin

s=s+f(x)

end;

x:=x+h

h:=(b-a)/n;

y:=s*h

s:=(f(a)+f(b))/2;

вывод y

begin

конец

x:=x+h;

end;

y:=s*h;

writeln('y=',y:8:5);

readln;

end.

ОТВЕТ:

y=0.28173

ввод а, b, n

h=(b-a)/2n

s:=f(a)+f(b)

CONST a= 0.4; b=0.8; n=100;

c:=1

x:=x+h

c,n: integer;

s:=s+(3+c)*f(x)

begin

x:=x+h

c=-c

begin

x<= b-h

s:=f(a)+f(b);

y:=s*h/3

x:=a+h;

вывод y

конец

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=x₀ и y=y₀) (2)

Рис. 1.

Метод Эйлера

Одним из методов решения дифференциального уравнения (1) с начальным условием (2) является метод Эйлера.

Будем рассматривать уравнение (1) на некотором отрезке [a,b]. Пусть отрезок поделен на n частей с шагом .

Обозначим X₀=a, X₁=X₀+h, X₂=X₀+2h,…, X_n=X₀+nh=b. Обозначим искомые y(X₁),…y(X_n) через y₁…y_n.

Методика решения уравнения (1) с начальными условиями (2) связяна с разложением решения в ряд Тейлора в h-окрестности точки X₀.

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

где f(X,y) – правая часть уравнения (1).

Таким образом,

.

При достаточно малой величине шага h метод Эйлера дает решения с большей точностью, т.к. погрешность близка к h² (h<<1) на каждом шаге интегрирования.

Метод Рунге-Кутта

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

Наиболее распространенным методом численного интегрирования дифференциальных уравнений служит метод Рунге-Кутта, обеспечивающий ускорение за счет большей точности вычислений на каждом шаге. Точность метода Рунге-Кутта оценивается величиной E≈h².

Уточнение достигается за счет специального подбора координат четурех точек, в которых вычисляется первая производная f(x,y). Вместо первой производной h∙f(x,y) используемой в формуле Эйлера, вычисляется усредненная первая производная f_i.

Формулы интегрирования по методу Рунге-Кутта имеют вид:

где

начало

ввод x0, xk, y0, h

x=x0, y=y0

x=x+h

y=y+f(x,y)*h

вывод x, y

конец

x

Да

Нет

h=(x_n – x₀)/n i=0,1,2,…n

y’=(1-y²)cos(x)+0.6y

при х₀=0; x_n=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

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

начало

ввод x0, xk, y0, h

x=x0, y=y0

x=x+h

y=y+f(x,y)*h

вывод x, y

конец

x

Да

Нет

y’=(1-y²)cos(x)+0.6y

при х₀=0; x_n=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

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 потребителей однородного груза. Запасы грухов у отправителей – a_i, потребность в грузе у получателей – b_j. Известна стоимость С_ij перевозки единицы от каждого отправителя до каждого получателя. Требуется определить оптимальную схему перевозки груза от отправителей к получателям так, чиобы суммарные транспортные расходы были min. Обычно условие задачи записывается в виде таблицы:

В1

В2

Вn

Запасы

a_i

А1

С₁₁

X₁₁

С₁₂

X₁₂

С_1n

X_1n

a₁

А2

С₂₁

X₂₁

С₂₂

X₂₂

С_2n

X_2n

a₂

Аm

С_m1

X_m1

С_m2

X_m2

С_mn

X_mn

a_m

Потребность

b_j

b₁

b₂

b_n

 a_i =  b_j

x_ij – количество груза, перевозимого от a_i отправителя к b_j потребителю.

При решении транспортной задачи должны выполняться 4 условия:

1. Все запасы грузов должны быть вывезены, т.е. i=1…m

2. Все потребности в грузе должны быть удовлетворены, т.е. j=1…n.

3. Суммарные транспортные затарты должны быть min, т.е.

F=C₁₁∙X₁₁+ C₁₂∙X₁₂+…+ C_mn∙X_mn  min

или

Существуют следующие методы решения задач:

1 Метод приближением условно оптимальными планами.

2 Метод потенциалов.

3 Метод рент.

4 Метод Филкерсона и т.д.

Расстановка поставок методом двойного предпочтения

1 итерация

В1

В2

В3

B4

U_j

А1

5

4

2

45

2

45

90

0

А2

3

80

6

3

1

15

95

-1

А3

1

10

2

90

3

7

100

-3

Фикт.

0

0

-3

0

135

0

135

-2

90

90

180

60

V_i

4

5

2

2

F_min=90+90+240+15+10+180=625

2 итерация

В1

В2

В3

B4

U_j

А1

5

4

2

90

2

90

0

А2

3

35

6

3

-1

1

60

95

2

А3

1

55

2

45

3

7

100

0

Фикт.

0

0

45

0

90

0

135

-2

90

90

180

60

V_i

1

2

2

-1

F_min=180+105+60+55+90=490

Конечная таблица

В1

В2

В3

B4

U_j

А1

5

4

2

90

2

90

0

А2

3

6

3

35

1

60

95

1

А3

1

90

2

10

3

7

100

0

Фикт.

0

0

80

0

55

0

135

-2

90

90

180

60

V_i

1

2

2

0

F_min=180+105+60+90+20=455

3.2. Расчёт сетевого графика

Сетевая модель называется сетевым графиком, на котором в определённом порядке показаны все операции по созданию объекта. Векторы или нити на графике – это выполняемые работы. Узлы – это события, т.е. момент начала или окончания ряда работ. Сетевой график в отличие от линейного даёт не только перечень работ, но и взаимосвязь между ними. На основе расчёта графика контролируется ход работ, основное внимание уделяется критическим работам, для остальных рассчитывается резерв времени. В основу построения сети закладывают три понятия: работа, событие, путь.

Основные расчётные параметры – ранние и поздние сроки начала и окончания работы, и резервы времени.

Рассмотрим фрагмент графика.

k

i-j- данная работа

t-j- время данной работы

h-i- предшествующая работа

j-k- последующая работа

t_kp- время критического пути

t_ij^PH- раннее начало данной работы

t_ij^PO- раннее окончание данной работы

t_ij^ПН- позднее начало работы

t_ij^НО- позднее окончание данной работы

R_ij- общий или полный резерв, времени работы

R_ij- частный резерв времени работы

Раннее начало исходных работ полагается равное нулю. T_1i^РН= 0

Раннее окончание любой работы равно сумме её раннего начала и продолжительности.

t_ij^PP= t_ij^PH+ t_ij

Раннее начало любой работы равно max раннему окончанию предшествующих работ.

t_ij^PH= max_h t_h^PO

max ранее окончание завершающих работ равно критическому времени

max_j t_jN^PO= t_кр.

Позднее окончание завершающих работ - равно критическому времени. Позднее окончание работ. Позднее начало любой работы равно разности её позднего окончания и продолжительности: t_ij^ПН = t_ij^НО - t_ij

Позднее окончание любой работы равно min- му позднему началу последующих работ:

t_ij^НО = min_k t_jk^ПН

Все параметры сетевого графика не отрицательны.

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

Полный резерв времени показывает насколько можно увеличить продолжительность данной работы не увеличивая t- критическое.

t_ij^пн- t_ij^рн

t_ij^по- t_ij^ро

K_ij=

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

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

r_ij= t_jk^рн- t_ij^ро

r_iN= t_кр- t_jN^ро

r_ij R_ij

Все расчёты записываются в таблицу - критический путь.

Решение

1-2-7-9-10-11-12

Ткрит = 46

1

5

11

7

3

8

4

6

10

12

3

5

4

2

8

5

3

8

1

9

3

9

2

4

7

6

9

10

10

20

3

15

7

11

8

Заключение

Современные офисные пакеты

ArjFolder 2.85

Бесплатный архиватор ArjFolder, созданный независимым французским программистом Рафаэлем Мунье, предназначен, как нетрудно догадаться по названию, для работы с ARJ-файлами. Фактически ArjFolder с помощью функций Проводника Windows 9x строит программную оболочку для DOS-утилиты Arj (эта вызываемая из командной строки утилита входит в состав дистрибутива; вообще говоря, она распространяется условно-бесплатно, так что называть ArjFolder бесплатным пакетом не совсем правильно). Дистрибутив ArjFolder представляет собой самораспаковывающийся EXE-модуль объемом 730 Кбайт. В ходе инсталляции пользователю предлагается установить ArjFolder вместе с утилитой Arj или без нее. Для полноценной работы с архивами следует выбрать первую возможность, в противном случае программа не сможет формировать и пополнять архивы, а ограничится только просмотром содержимого архивов и их распаковкой. После инсталляции архиватор встраивается в Проводник Windows 9x. В системном меню "Пуск| Программы" появляется раздел с программой настройки ArjFolder, предназначенной для управления привязкой архиватора к файлам распознаваемых им типов (программа позволяет создавать, пополнять и распаковывать ARJ-файлы, а также просматривать и распаковывать сжатые файлы и архивы в форматах ACE, ZIP, GZIP, TAR, CAB и RAR). Кроме того, в контекстное меню объектов Windows добавляется команда Add to Arj ("Включить в Arj-архив"). С ее помощью можно создавать или пополнять ARJ-архивы и самораспаковывающиеся EXE-файлы. В случае если с программой связан какой-нибудь из распознаваемых ею типов файлов, щелчок на таком файле вызывает двухпанельное окно, похожее на Проводник (к сожалению, это единственный и не очень удобный способ вызвать ArjFolder). Упакованные в архиве объекты изображаются в правой панели окна подобно содержимому обычной папки. Контекстные меню позволяют открывать, распаковывать, удалять или просматривать эти файлы. Добавлять файлы в ARJ-архив и распаковывать их можно с помощью перетаскивания, для остальных типов архивов перетаскиванием можно только распаковывать файлы. Из богатейшего ассортимента опций командной строки, предусмотренных в DOS-программе Arj, Windows-оболочка задействует лишь несколько основных, в частности возможность создавать многотомные архивы для записи на дискеты, защиту с помощью пароля, упаковку вложенных каталогов, упаковку скрытых и системных файлов (опции действуют при создании нового архива). К сожалению, интеграция архиватора с Windows недостаточно полна: если в программах типа ZIP Magic или WinRAR (да и в файловых оболочках типа DISCo Commander) архивы по своему "поведению" практически неотличимы от обычных каталогов, то оснащенный средствами ArjFolder Проводник в левой панели показывает вместо дерева дисков и каталогов только один архив, не имеющий контекстного меню, а в практически бесполезной строке адреса может содержаться только имя текущего архива. На панели инструментов при этом отсутствует кнопка перехода к родительскому каталогу, и, что самое неприятное, - в меню Файл нет команды Открыть. Все операции с архивами производятся в текстовом окне DOS, что тоже не очень удобно. Еще один недостаток - программа не показывает структуру упакованных каталогов, изображая содержимое архива в виде единого плоского списка (впрочем, это свойственно большинству рассмотренных программ). Следует также заметить, что отдельные элементы интерфейса (в целом англоязычного) остались не переведенными с французского (так, вместо привычного обозначения MB вы увидите Mo). Для пользователей Windows, имеющих дело с несложными ARJ-архивами и избегающих командных строк, данная программа может стать простым бесплатным решением, остальные, скорее всего, предпочтут что-нибудь более совершенное, например программу WinRAR с подключенным внешним модулем Arj.

Список используемой литературы:

1. Конспект лекций по информатике

2. Методические указания к лабораторным работам

3. Журнал «Мир ПК»

41