Контрольная работа по информатике. 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Выполнить вычисления  в системе компьютерной математики  Maple.

1) Запускаем программу Maple.

2) Составляем команду для вычисления:

Для вычисления производных в Maple имеются две команды:

прямого исполнения – diff(f,x), где f – функция, которую следует продифференцировать, x – имя переменной, по которой производится дифференцирование.

отложенного исполнения – Diff(f,x), где параметры команды такие же, как и в предыдущей. Действие этой команды сводится к аналитической записи производной в виде .

3) Вводим команду для вычисления:

4) Нажимаем клавишу Enter, получаем результат:

2.   Математические методы оптимизации.

Фармацевтической фирме необходимо осуществить доставку однородной фармацевтической продукции, находящейся на четырех складах А1, А2, А3, А4 в четыре торговые точки В1, В2, В3, В4.

Количество единиц продукции на каждом из складов А1, А2, А3, А4 соответственно равно а1, а2, а3, а4.

Потребности торговых точек В1, В2, В3, В4 в единицах продукции соответственно равны b1, b2, b3, b4.

Известны стоимости Cij доставки (транспортные расходы) единицы продукции со склада Аi в торговую точку Вj.

Со склада Аi (i = 1, 2, 3, 4) в торговую точку Вj (j = 1, 2, 3, 4) перевозится xij единиц продукции. Переменные xij не могут принимать отрицательных значений (xij > 0), так как перевозки осуществляются только в одном направлении: со складов в торговые точки.

Требуется составить математическую модель транспортной задачи, вычислить оптимальный план перевозок, т.е. найти такие значения объемов перевозок xij однородной фармацевтической продукции со складов Аi в торговые точки Вj, чтобы вывести всю продукцию со складов, удовлетворить потребности торговых точек и обеспечить минимальные транспортные расходы.

Решение задачи должно иметь пояснение и табличные иллюстрации. Решение необходимо осуществить двумя способами: методом «северо-западного угла» (достаточно провести 4-5 циклов) и применяя систему компьютерной математики Maple.

1) Метод «северо-западного угла».

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

	1	2	3	4	Запасы
1	5	3	2	6	180
2	9	4	4	4	120
3	1	2	3	5	80
4	3	2	1	8	120
Потребности	140	80	120	160

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 180 + 120 + 80 + 120 = 500

∑b = 140 + 80 + 120 + 160 = 500

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

 

	1	2	3	4	Запасы
1	5	3	2	6	180
2	9	4	4	4	120
3	1	2	3	5	80
4	3	2	1	8	120
Потребности	140	80	120	160

 

Этап I. Поиск первого опорного плана.

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

План начинается заполняться с верхнего левого угла.

Искомый элемент равен 5

Для этого элемента запасы равны 180, потребности 140. Поскольку минимальным является 140, то вычитаем его.

x11 = min(180,140) = 140.

5	3	2	6	180 - 140 = 40
x	4	4	4	120
x	2	3	5	80
x	2	1	8	120
140 - 140 = 0	80	120	160	0

 

Искомый элемент равен 3

Для этого элемента запасы равны 40, потребности 80. Поскольку минимальным является 40, то вычитаем его.

x12 = min(40,80) = 40.

 

5	3	x	x	40 - 40 = 0
x	4	4	4	120
x	2	3	5	80
x	2	1	8	120
0	80 - 40 = 40	120	160	0

 

Искомый элемент равен 4

Для этого элемента запасы равны 120, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x22 = min(120,40) = 40.

 

5	3	x	x	0
x	4	4	4	120 - 40 = 80
x	x	3	5	80
x	x	1	8	120
0	40 - 40 = 0	120	160	0

 

Искомый элемент равен 4

Для этого элемента запасы равны 80, потребности 120. Поскольку минимальным является 80, то вычитаем его.

x23 = min(80,120) = 80.

5	3	x	x	0
x	4	4	x	80 - 80 = 0
x	x	3	5	80
x	x	1	8	120
0	0	120 - 80 = 40	160	0

 

Искомый элемент равен 3

Для этого элемента запасы равны 80, потребности 40. Поскольку минимальным является 40, то вычитаем его.

x33 = min(80,40) = 40.

 

 

 

 

5	3	x	x	0
x	4	4	x	0
x	x	3	5	80 - 40 = 40
x	x	x	8	120
0	0	40 - 40 = 0	160	0

 

Искомый элемент равен 5

Для этого элемента запасы равны 40, потребности 160. Поскольку минимальным является 40, то вычитаем его.

x34 = min(40,160) = 40.

5	3	x	x	0
x	4	4	x	0
x	x	3	5	40 - 40 = 0
x	x	x	8	120
0	0	0	160 - 40 = 120	0

 

Искомый элемент равен 8

Для этого элемента запасы равны 120, потребности 120. Поскольку минимальным является 120, то вычитаем его.

x44 = min(120,120) = 120.

5	3	x	x	0
x	4	4	x	0
x	x	3	5	0
x	x	x	8	120 - 120 = 0
0	0	0	120 - 120 = 0	0

 

 

	1	2	3	4	Запасы
1	5[140]	3[40]	2	6	180
2	9	4[40]	4[80]	4	120
3	1	2	3[40]	5[40]	80
4	3	2	1	8[120]	120
Потребности	140	80	120	160

 

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

2. Подсчитаем число занятых  клеток таблицы, их 7, а должно  быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 5*140 + 3*40 + 4*40 + 4*80 + 3*40 + 5*40 + 8*120  = 2580

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u1 + v2 = 3; 0 + v2 = 3; v2 = 3

u2 + v2 = 4; 3 + u2 = 4; u2 = 1

u2 + v3 = 4; 1 + v3 = 4; v3 = 3

u3 + v3 = 3; 3 + u3 = 3; u3 = 0

u3 + v4 = 5; 0 + v4 = 5; v4 = 5

u4 + v4 = 8; 5 + u4 = 8; u4 = 3

 

	v1=5	v2=3	v3=3	v4=5
u1=0	5[140]	3[40]	2	6
u2=1	9	4[40]	4[80]	4
u3=0	1	2	3[40]	5[40]
u4=3	3	2	1	8[120]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;3): 0 + 3 > 2; ∆13 = 0 + 3 - 2 = 1

(2;4): 1 + 5 > 4; ∆24 = 1 + 5 - 4 = 2

(3;1): 0 + 5 > 1; ∆31 = 0 + 5 - 1 = 4

(3;2): 0 + 3 > 2; ∆32 = 0 + 3 - 2 = 1

(4;1): 3 + 5 > 3; ∆41 = 3 + 5 - 3 = 5

(4;2): 3 + 3 > 2; ∆42 = 3 + 3 - 2 = 4

(4;3): 3 + 3 > 1; ∆43 = 3 + 3 - 1 = 5

max(1,2,4,1,5,4,5) = 5

Выбираем максимальную оценку свободной клетки (4;1): 3

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	5[140][-]	3[40][+]	2	6	180
2	9	4[40][-]	4[80][+]	4	120
3	1	2	3[40][-]	5[40][+]	80
4	3[+]	2	1	8[120][-]	120
Потребности	140	80	120	160

Цикл приведен в таблице (4,1 → 4,4 → 3,4 → 3,3 → 2,3 → 2,2 → 1,2 → 1,1).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	5[100]	3[80]	2	6	180
2	9	4[0]	4[120]	4	120
3	1	2	3	5[80]	80
4	3[40]	2	1	8[80]	120
Потребности	140	80	120	160

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u4 + v1 = 3; 5 + u4 = 3; u4 = -2

u4 + v4 = 8; -2 + v4 = 8; v4 = 10

u3 + v4 = 5; 10 + u3 = 5; u3 = -5

u1 + v2 = 3; 0 + v2 = 3; v2 = 3

u2 + v2 = 4; 3 + u2 = 4; u2 = 1

u2 + v3 = 4; 1 + v3 = 4; v3 = 3

 

	v1=5	v2=3	v3=3	v4=10
u1=0	5[100]	3[80]	2	6
u2=1	9	4[0]	4[120]	4
u3=-5	1	2	3	5[80]
u4=-2	3[40]	2	1	8[80]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;3): 0 + 3 > 2; ∆13 = 0 + 3 - 2 = 1

(1;4): 0 + 10 > 6; ∆14 = 0 + 10 - 6 = 4

(2;4): 1 + 10 > 4; ∆24 = 1 + 10 - 4 = 7

max(1,4,7) = 7

Выбираем максимальную оценку свободной клетки (2;4): 4

Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	5[100][-]	3[80][+]	2	6	180
2	9	4[0][-]	4[120]	4[+]	120
3	1	2	3	5[80]	80
4	3[40][+]	2	1	8[80][-]	120
Потребности	140	80	120	160

 

Цикл приведен в таблице (2,4 → 2,2 → 1,2 → 1,1 → 4,1 → 4,4).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	5[100]	3[80]	2	6	180
2	9	4	4[120]	4[0]	120
3	1	2	3	5[80]	80
4	3[40]	2	1	8[80]	120
Потребности	140	80	120	160

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u4 + v1 = 3; 5 + u4 = 3; u4 = -2

u4 + v4 = 8; -2 + v4 = 8; v4 = 10

u2 + v4 = 4; 10 + u2 = 4; u2 = -6

u2 + v3 = 4; -6 + v3 = 4; v3 = 10

u3 + v4 = 5; 10 + u3 = 5; u3 = -5

u1 + v2 = 3; 0 + v2 = 3; v2 = 3

	v1=5	v2=3	v3=10	v4=10
u1=0	5[100]	3[80]	2	6
u2=-6	9	4	4[120]	4[0]
u3=-5	1	2	3	5[80]
u4=-2	3[40]	2	1	8[80]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;3): 0 + 10 > 2; ∆13 = 0 + 10 - 2 = 8

(1;4): 0 + 10 > 6; ∆14 = 0 + 10 - 6 = 4

(3;3): -5 + 10 > 3; ∆33 = -5 + 10 - 3 = 2

(4;3): -2 + 10 > 1; ∆43 = -2 + 10 - 1 = 7

max(8,4,2,7) = 8

Выбираем максимальную оценку свободной клетки (1;3): 2

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

	1	2	3	4	Запасы
1	5[100][-]	3[80]	2[+]	6	180
2	9	4	4[120][-]	4[0][+]	120
3	1	2	3	5[80]	80
4	3[40][+]	2	1	8[80][-]	120
Потребности	140	80	120	160

 

Цикл приведен в таблице (1,3 → 1,1 → 4,1 → 4,4 → 2,4 → 2,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	1	2	3	4	Запасы
1	5[20]	3[80]	2[80]	6	180
2	9	4	4[40]	4[80]	120
3	1	2	3	5[80]	80
4	3[120]	2	1	8	120
Потребности	140	80	120	160

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u4 + v1 = 3; 5 + u4 = 3; u4 = -2

u1 + v2 = 3; 0 + v2 = 3; v2 = 3

u1 + v3 = 2; 0 + v3 = 2; v3 = 2

u2 + v3 = 4; 2 + u2 = 4; u2 = 2

u2 + v4 = 4; 2 + v4 = 4; v4 = 2

u3 + v4 = 5; 2 + u3 = 5; u3 = 3

	v1=5	v2=3	v3=2	v4=2
u1=0	5[20]	3[80]	2[80]	6
u2=2	9	4	4[40]	4[80]
u3=3	1	2	3	5[80]
u4=-2	3[120]	2	1	8

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(2;2): 2 + 3 > 4; ∆22 = 2 + 3 - 4 = 1

(3;1): 3 + 5 > 1; ∆31 = 3 + 5 - 1 = 7

(3;2): 3 + 3 > 2; ∆32 = 3 + 3 - 2 = 4

(3;3): 3 + 2 > 3; ∆33 = 3 + 2 - 3 = 2

max(1,7,4,2) = 7

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	5[20][-]	3[80]	2[80][+]	6	180
2	9	4	4[40][-]	4[80][+]	120
3	1[+]	2	3	5[80][-]	80
4	3[120]	2	1	8	120
Потребности	140	80	120	160