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

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

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

Определяем оценку для  каждой свободной клетки.

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

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

Оценка свободной клетки равна Δ₁₁ = 9

Аналогично выполняем  оценку для каждой свободной клетки:

Оценка свободной клетки равна Δ₁₂ = 6

Оценка свободной клетки равна Δ₁₅ = 20

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

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

Оценка свободной клетки равна Δ₂₄ = 6

Оценка свободной клетки равна Δ₃₄ = 8

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

Оценка свободной клетки равна Δ₄₁ = 11

Оценка свободной клетки равна Δ₄₂ = 7

Оценка свободной клетки равна Δ₄₄ = -1

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

Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток равные: (-2).

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

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

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

Аналогично определяем минимальные  затраты:

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

В результате получаем новый  опорный план:

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

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

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

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

 

 

 

 

 

МЕТОД ФОГЕЛЯ

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

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

	50	65	65	55	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 + 55 + 30 = 265

Построим первый опорный  план транспортной задачи. Для каждой строки и столбца таблицы условий  найдем разности между двумя минимальными тарифами, записанными в данной строе  или столбце, и поместим их в соответствующем  дополнительном столбце или строке.

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

Сведем все вычисления в одну таблицу

	50	65	65	55	30	d1	d2	d3	d4	d5
70	20	21	22[15]	23[55]	24	1	1	-	-	-
65	22[35]	28	31	40	15[30]	7	7	7	6	-
90	23[15]	27[65]	34[10]	43	18	5	5	5	4	4
d1	2	6	9	17	3
d2	2	6	9	-	3
d3	1	1	3	-	3
d4	1	1	3	-	-
d5	0	0	0	-	-

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

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

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

	v1=11	v2=15	v3=22	v4=23	v5=4
u1=0	20	21	22[15]	23[55]	24
u2=11	22[35]	28	31	40	15[30]
u3=12	23[15]	27[65]	34[10]	43	18

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

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

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

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

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

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

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

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

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

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

	50	65	65	55	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