Контрольная работа по «Моделирование транспортных процессов»

Искомый элемент равен 10 
Для этого элемента запасы равны 40, потребности 10. Поскольку минимальным является 10, то вычитаем его. 
x22 = min(40,10) = 10.

3	x	x	8	x	0
2	10	1	x	9	40 - 10 = 30
x	x	8	x	1	50
0	10 - 10 = 0	30	0	50	0

Искомый элемент равен 1 
Для этого элемента запасы равны 30, потребности 30. Поскольку минимальным является 30, то вычитаем его. 
x23 = min(30,30) = 30.

3	x	x	8	x	0
2	10	1	x	x	30 - 30 = 0
x	x	x	x	1	50
0	0	30 - 30 = 0	0	50	0

Искомый элемент равен 1 
Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его. 
x35 = min(50,50) = 50.

3	x	x	8	x			0
2	10	1	x	x			0
x	x	x	x	1			50 - 50 = 0
0	0	0	0	50 - 50 = 0			0
					1	2		3		4	5	Запасы
1					3[30]	11		6		8[70]	8	100
2					2[30]	10[10]		1[30]		5	9	70
3					6	3		8		6	1[50]	50
Потребности					60	10		30		70	50

2. Подсчитаем число занятых  клеток таблицы, их 6, а должно  быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.  
Строим новый план. 
Значение целевой функции для этого опорного плана равно: 
F(x) = 3*30 + 8*70 + 2*30 + 10*10 + 1*30 + 1*50 = 890 
Искомый элемент равен 8 
Для этого элемента запасы равны 100, потребности 50. Поскольку минимальным является 50, то вычитаем его. 
x15 = min(100,50) = 50.

3	11	6	8	8	100 - 50 = 50
2	10	1	5	x	70
6	3	8	6	x	50
60	10	30	70	50 - 50 = 0	0

Искомый элемент равен 3 
Для этого элемента запасы равны 50, потребности 60. Поскольку минимальным является 50, то вычитаем его. 
x11 = min(50,60) = 50.

3	x	x	x	8	50 - 50 = 0
2	10	1	5	x	70
6	3	8	6	x	50
60 - 50 = 10	10	30	70	0	0

Искомый элемент равен 2 
Для этого элемента запасы равны 70, потребности 10. Поскольку минимальным является 10, то вычитаем его. 
x21 = min(70,10) = 10.

3	x	x	x	8	0
2	10	1	5	x	70 - 10 = 60
x	3	8	6	x	50
10 - 10 = 0	10	30	70	0	0

Искомый элемент равен 10 
Для этого элемента запасы равны 60, потребности 10. Поскольку минимальным является 10, то вычитаем его. 
x22 = min(60,10) = 10.

3	x	x	x	8	0
2	10	1	5	x	60 - 10 = 50
x	x	8	6	x	50
0	10 - 10 = 0	30	70	0	0

Искомый элемент равен 1 
Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его. 
x23 = min(50,30) = 30.

3	x	x	x	8	0
2	10	1	5	x	50 - 30 = 20
x	x	x	6	x	50
0	0	30 - 30 = 0	70	0	0

Искомый элемент равен 5 
Для этого элемента запасы равны 20, потребности 70. Поскольку минимальным является 20, то вычитаем его. 
x24 = min(20,70) = 20.

3	x	x	x	8	0
2	10	1	5	x	20 - 20 = 0
x	x	x	6	x	50
0	0	0	70 - 20 = 50	0	0

Искомый элемент равен 6 
Для этого элемента запасы равны 50, потребности 50. Поскольку минимальным является 50, то вычитаем его. 
x34 = min(50,50) = 50.

3	x	x	x		8		0
2	10	1	5		x		0
x	x	x	6		x		50 - 50 = 0
0	0	0	50 - 50 = 0		0		0
				1		2		3		4	5	Запасы
1				3[50]		11		6		8	8[50]	100
2				2[10]		10[10]		1[30]		5[20]	9	70
3				6		3		8		6[50]	1	50
Потребности				60		10		30		70	50

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. 
Значение целевой функции для этого опорного плана равно: 
F(x) = 3*50 + 8*50 + 2*10 + 10*10 + 1*30 + 5*20 + 6*50 = 1100 
Этап II. Улучшение опорного плана. 
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 
u1 + v1 = 3; 0 + v1 = 3; v1 = 3 
u2 + v1 = 2; 3 + u2 = 2; u2 = -1 
u2 + v2 = 10; -1 + v2 = 10; v2 = 11 
u2 + v3 = 1; -1 + v3 = 1; v3 = 2 
u2 + v4 = 5; -1 + v4 = 5; v4 = 6 
u3 + v4 = 6; 6 + u3 = 6; u3 = 0 
u1 + v5 = 8; 0 + v5 = 8; v5 = 8

	v1=3	v2=11	v3=2	v4=6	v5=8
u1=0	3[50]	11	6	8	8[50]
u2=-1	2[10]	10[10]	1[30]	5[20]	9
u3=0	6	3	8	6[50]	1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij 
(3;2): 0 + 11 > 3; ∆32 = 0 + 11 - 3 = 8 
(3;5): 0 + 8 > 1; ∆35 = 0 + 8 - 1 = 7 
max(8,7) = 8 
Выбираем максимальную оценку свободной клетки (3;2): 3 
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[50]	11	6	8	8[50]	100
2	2[10]	10[10][-]	1[30]	5[20][+]	9	70
3	6	3[+]	8	6[50][-]	1	50
Потребности	60	10	30	70	50

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

	1	2	3	4	5	Запасы
1	3[50]	11	6	8	8[50]	100
2	2[10]	10	1[30]	5[30]	9	70
3	6	3[10]	8	6[40]	1	50
Потребности	60	10	30	70	50