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

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых 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