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

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

	1	2	3	Запасы
1	5	3	6	40
2	2	1	2	17
3	7	4	8	23
Потребности	25	19	21

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

∑a = 40 + 17 + 23 = 80

∑b = 25 + 19 + 21 = 65

Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 15 (80—65). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

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

 

	1	2	3	4	Запасы
1	5	3	6	0	40
2	2	1	2	0	17
3	7	4	8	0	23
Потребности	25	19	21	15

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

 

 

	1	2	3	4	Запасы
1	5[25]	3[15]	6	0	40
2	2	1[4]	2[13]	0	17
3	7	4	8[8]	0[15]	23
Потребности	25	19	21	15

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

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

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

F(x) = 5*25 + 3*15 + 1*4 + 2*13 + 8*8 + 0*15  = 264

Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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 = 1; 3 + u2 = 1; u2 = -2

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

u3 + v3 = 8; 4 + u3 = 8; u3 = 4

u3 + v4 = 0; 4 + v4 = 0; v4 = -4

 

	v1=5	v2=3	v3=4	v4=-4
u1=0	5[25]	3[15]	6	0
u2=-2	2	1[4]	2[13]	0
u3=4	7	4	8[8]	0[15]

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

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

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

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

max(1,2,3) = 3

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

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

 

	1	2	3	4	Запасы
1	5[25]	3[15]	6	0	40
2	2	1[4] [-]	2[13] [+]	0	17
3	7	4 [+]	8[8] [-]	0[15]	23
Потребности	25	19	21	15

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

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

 

	1	2	3	4	Запасы
1	5[25]	3[15]	6	0	40
2	2	1	2[17]	0	17
3	7	4[4]	8[4]	0[15]	23
Потребности	25	19	21	15

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

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

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

u3 + v2 = 4; 3 + u3 = 4; u3 = 1

u3 + v3 = 8; 1 + v3 = 8; v3 = 7

u2 + v3 = 2; 7 + u2 = 2; u2 = -5

u3 + v4 = 0; 1 + v4 = 0; v4 = -1

 

	v1=5	v2=3	v3=7	v4=-1
u1=0	5[25]	3[15]	6	0
u2=-5	2	1	2[17]	0
u3=1	7	4[4]	8[4]	0[15]

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

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

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

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

 

	1	2	3	4	Запасы
1	5[25]	3[15][-]	6 [+]	0	40
2	2	1	2[17]	0	17
3	7	4[4] [+]	8[4] [-]	0[15]	23
Потребности	25	19	21	15

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

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

 

	1	2	3	4	Запасы
1	5[25]	3[11]	6[4]	0	40
2	2	1	2[17]	0	17
3	7	4[8]	8	0[15]	23
Потребности	25	19	21	15

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

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

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

u3 + v2 = 4; 3 + u3 = 4; u3 = 1

u3 + v4 = 0; 1 + v4 = 0; v4 = -1

u1 + v3 = 6; 0 + v3 = 6; v3 = 6

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

 

	v1=5	v2=3	v3=6	v4=-1
u1=0	5[25]	3[11]	6[4]	0
u2=-4	2	1	2[17]	0
u3=1	7	4[8]	8	0[15]

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