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

 

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

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

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

 

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

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

u3 + v1 = 1; 3 + v1 = 1; v1 = -2

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

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

 

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

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

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

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

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

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

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

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

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

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

 

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

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

 

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

 

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

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

u4 + v2 = 2; 3 + u4 = 2; u4 = -1

u4 + v1 = 3; -1 + v1 = 3; v1 = 4

u3 + v1 = 1; 4 + u3 = 1; u3 = -3

u3 + v4 = 5; -3 + v4 = 5; v4 = 8

u2 + v4 = 4; 8 + u2 = 4; u2 = -4

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

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

 

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

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

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

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

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

 

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

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

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

 

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

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

u4 + v2 = 2; 3 + u4 = 2; u4 = -1

u4 + v1 = 3; -1 + v1 = 3; v1 = 4

u3 + v1 = 1; 4 + u3 = 1; u3 = -3

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

u1 + v4 = 6; 0 + v4 = 6; v4 = 6

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

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

 

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

Минимальные затраты составят:

F(x) = 3*20 + 2*120 + 6*40 + 4*120 + 1*80 + 3*60 + 2*60  = 1400

2) Решение с помошью системы компьютерной математики Maple.

- Запускаем Maple:

- Делаем рестарт. Создаём пустую матрицу (4,4):

> restart;

> x:=matrix(4,4);

- Создаём матрицу тарифов:

> c:=matrix([[5,3,2,6],[9,4,4,4],[1,2,3,5],[3,2,1,8]]);

- Вычисляем сумму последовательностей:

> F:=sum((sum(c[i,j]*x[i,j],i=1..4),j=1..4));

- Подключаем пакет Simplex:

> with(simplex);

- Оптимизируем задачу симплекс-методом, используя функцию minimize:

>minimize(F,{sum(x[1,j],j=1..4)=180,sum(x[2,j],j=1..4)=120,sum(x[3,j],j=1..4)=80,sum(x[4,j],j=1..4)=120,sum(x[i,1],i=1..4)=140,sum(x[i,2],i=1..4)=80,sum(x[i,3],i=1..4)=120,sum(x[i,4],i=1..4)=160},NONNEGATIVE);

- Выводим результат в  виде матрицы:

> V:=matrix([[0,20,120,40],[0,0,0,120],[80,0,0,0],[60,60,0,0]]);

- Получаем минимальную  стоимость перевозок с помощью  функции add:

> Z:=add(add(c[i,j]*V[i,j],i=1..4),j=1..4);

 

3. Выполнение статистических расчетов с применением табличного процессора Excel.

Создадим и заполним таблицу со следующими столбцами.

N – номер по порядку;

Xi – значение;

(Xi – M) – вспомогательная колонка;

(Xi – M)^2 – колонка для вычисления дисперсии.

Посчитаем сумму значений.

Найдем объем выборки с помощью функции СЧЁТ(B2:B21), подсчитывающей численные значения в диапазоне B2:B21.

 

Просуммировав значения Xi, можем найти среднее: разделим сумму на количество значений.

Приведем таблицу с формулами:

В ячейке G2 посчитано среднее значение, которое затем используется в колонке (Xi – M). $G$2 – абсолютная ссылка.

Полученные значения:

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

Применяя мастер функций Excel, заполняем вторую строку в следующей таблице. В ней заданы границы интервала, Fi – количество значений, попавших в i-ый интервал, Pi – эмпирическая вероятность, Xc – середины интервалов. Значение в ячейки I3 приравнивается к значению J2 (нижняя граница следующего интервала равна верхней границе предыдущего интервала). Следующие строки заполняются копированием с применением маркера автозаполнения. В нижней строке подсчитывается сумма по столбцам.

По полученным данным можно построить гистограмму. Для этого выделяем столбец со значениями Pi, выбираем закладку Вставка – Гистограмма – Гистограмма с группировкой. Щелкнув правой клавишей мыши по построенной гистограмме, выберем Выбрать данные – Подписи горизонтальной оси – Изменить – в качестве диапазона подписей оси выберем диапазон значений Xc (N2:N6).

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

Применим пакет «Описательная статистика». Для этого выберем вкладку Данные – Анализ данных – Описательная статистика – в качестве входного интервала зададим диапазон значений Xi, поставим галочку в пункте Итоговая  статистика.