Методы принятия управленческих решений

	50	65	65	15	30
70	20	21	22[55]	23[15]	24
65	22[25] [+]	28	31[10]	40	15[30] [-]
90	23[25] [-]	27[65]	34	43	18 [+]

 

Оценка свободной клетки равна Δ₃₅ = 2.

Из приведенного расчета  видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции  Fx невозможно, поскольку она достигла минимального значения.

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

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

22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65  = 5195

 

 

 

 

МЕТОД МИНИМАЛЬНОЙ  СТОИМОСТИ

МЕТОД ПОТЕНЦИАЛОВ

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

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

	50	65	65	15	30
70	20	21	22	23	24
65	22	28	31	40	15
90	23	27	34	43	18

 

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

∑a = 70 + 65 + 90 = 225

∑b = 50 + 65 + 65 + 15 + 30 = 225

1. Построим первый опорный план транспортной задачи.

	50	65	65	15	30
70	20[50]	21[20]	22	23	24
65	22	28	31[35]	40	15[30]
90	23	27[45]	34[30]	43[15]	18

 

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

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

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

	v1=20	v2=21	v3=28	v4=37	v5=12
u1=0	20[50]	21[20]	22	23	24
u2=3	22	28	31[35]	40	15[30]
u3=6	23	27[45]	34[30]	43[15]	18

 

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

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

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

	50	65	65	15	30
70	20[50]	21[20] [-]	22	23 [+]	24
65	22	28	31[35]	40	15[30]
90	23	27[45] [+]	34[30]	43[15] [-]	18

 

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

	50	65	65	15	30
70	20[50]	21[5]	22	23[15]	24
65	22	28	31[35]	40	15[30]
90	23	27[60]	34[30]	43	18

 

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

	v1=20	v2=21	v3=28	v4=23	v5=12
u1=0	20[50]	21[5]	22	23[15]	24
u2=3	22	28	31[35]	40	15[30]
u3=6	23	27[60]	34[30]	43	18

 

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

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

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

	50	65	65	15	30
70	20[50]	21[5] [-]	22 [+]	23[15]	24
65	22	28	31[35]	40	15[30]
90	23	27[60] [+]	34[30] [-]	43	18

 

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

	50	65	65	15	30
70	20[50]	21	22[5]	23[15]	24
65	22	28	31[35]	40	15[30]
90	23	27[65]	34[25]	43	18

 

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

	v1=20	v2=15	v3=22	v4=23	v5=6
u1=0	20[50]	21	22[5]	23[15]	24
u2=9	22	28	31[35]	40	15[30]
u3=12	23	27[65]	34[25]	43	18

 

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

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

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

	50	65	65	15	30
70	20[50] [-]	21	22[5] [+]	23[15]	24
65	22	28	31[35]	40	15[30]
90	23 [+]	27[65]	34[25] [-]	43	18

 

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

	50	65	65	15	30
70	20[25]	21	22[30]	23[15]	24
65	22	28	31[35]	40	15[30]
90	23[25]	27[65]	34	43	18

 

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

	v1=20	v2=24	v3=22	v4=23	v5=6
u1=0	20[25]	21	22[30]	23[15]	24
u2=9	22	28	31[35]	40	15[30]
u3=3	23[25]	27[65]	34	43	18

 

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

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

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

	50	65	65	15	30
70	20[25] [-]	21	22[30] [+]	23[15]	24
65	22 [+]	28	31[35] [-]	40	15[30]
90	23[25]	27[65]	34	43	18