2.7 Нахождение опорного плана транспортной задачи методом наименьшего элемента

Используя метод наименьшего элемента, построим первый опорный план транспортной задачи (Табл. 2.7.1).

Таблица 2.7.1

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100]	10	15	14	4[50]	150
A2	3	7[20]	12	5[150]	8	170
A3	21	18[70]	6[160]	13	16[30]	260
Потребности	100	90	160	150	80	580

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

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

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

(x) = 2*100 + 4*50 + 7*20 + 5*150 + 18*70 + 6*160 + 16*30 = 3990

2.8 Решение транспортной задачи методом потенциалов

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.1

	v1=2	v2=10	v3=15	v4=22	v5=25
u1=0	2[100]	10[50]	15	14	4
u2=-3	3	7[40]	12[130]	5	8
u3=-9	21	18	6[30]	13[150]	16[80]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.1).

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

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

Таблица 2.8.2

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100]	10[50][-]	15	14	4[+]	150
A2	3	7[40][+]	12[130][-]	5	8	170
A3	21	18	6[30][+]	13[150]	16[80][-]	260
Потребности	100	90	160	150	80	580

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

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е.

у = min (1, 2) = 50

Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.3).

Таблица 2.8.3

Пункт направления	B1	B2	B3	B4	B5	Запасы
1	2[100]	10	15	14	4[50]	150
2	3	7[90]	12[80]	5	8	170
3	21	18	6[80]	13[150]	16[30]	260
Потребности	100	90	160	150	80	580

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.4

	v1=2	v2=-11	v3=-6	v4=1	v5=4
u1=0	2[100]	10	15	14	4[50]
u2=18	3	7[90]	12[80]	5	8
u3=12	21	18	6[80]	13[150]	16[30]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.4).

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

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

Таблица 2.8.5

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[100][-]	10	15	14	4[50][+]	150
A2	3[+]	7[90]	12[80][-]	5	8	170
A3	21	18	6[80][+]	13[150]	16[30][-]	260
Потребности	100	90	160	150	80

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

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

Таблица 2.8.6

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[70]	10	15	14	4[80]	150
A2	3[30]	7[90]	12[50]	5	8	170
A3	21	18	6[110]	13[150]	16	260
Потребности	100	90	160	150	80	580

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.7

	v1=2	v2=6	v3=11	v4=18	v5=4
u1=0	2[70]	10	15	14	4[80]
u2=1	3[30]	7[90]	12[50]	5	8
u3=-5	21	18	6[110]	13[150]	16

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij (Табл. 2.8.7).

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

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

Таблица 2.8.8

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[70]	10	15	14	4[80]	150
A 2	3[30]	7[90]	12[50][-]	5[+]	8	170
A 3	21	18	6[110][+]	13[150][-]	16	260
Потребности	100	90	160	150	80	580

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

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

Таблица 2.8.9

Пункт направления	B1	B2	B3	B4	B5	Запасы
A1	2[70]	10	15	14	4[80]	150
A2	3[30]	7[90]	12	5[50]	8	170
A3	21	18	6[160]	13[100]	16	260
Потребности	100	90	160	150	80	580

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Таблица 2.8.10

	v1=2	v2=6	v3=-3	v4=4	v5=4
u1=0	2[70]	10	15	14	4[80]
u2=1	3[30]	7[90]	12	5[50]	8
u3=9	21	18	6[160]	13[100]	16

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij(Табл. 2.8.10).

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

(x) = 2*70 + 4*80 + 3*30 + 7*90 + 5*50 + 6*160 + 13*100 = 3690