Задача 3 Необходимо доставить однородный груз от трех филиалов фирмы пяти потребителям:

	Филиал 1	Филиал 2	Филиал 3
Предложение филиалов (ед.):	101	7	94
	потр.1	потр.2	потр.3	потр.4	потр.5
Спрос потребителей (ед.):	44	64	63	12	89

Известна матрица затрат на доставку единицы груза от каждого поставщика потребителю (руб.).

	потр.1	потр.2	потр.3	потр.4	потр.5
Поставщик 1	11	12	10	7	9
Поставщик 2	11	12	9	7	10
Поставщик 3	11	9	8	8	9

1. Составить ЭММ расчета оптимального плана перевозок.

2. Определить исходный опорный план методом северо-западного угла.

3. Найти оптимальный план перевозок методом потенциалов и указать соответствующие ему минимальные транспортные затраты.

Решение

Составим экономико-математическую модель методом минимального элемента:

Математическая модель транспортной задачи: F = ∑∑c_ijx_ij, (1) при условиях: ∑x_ij = a_i, i = 1,2,…, m, (2) ∑x_ij = b_j, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	Запасы
1	11	12	10	7	9	101
2	11	12	9	7	10	7
3	11	9	8	8	9	94
Потребности	44	64	63	12	89

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 101 + 7 + 94 = 202 ∑b = 44 + 64 + 63 + 12 + 89 = 272 Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	11	12	10	7	9	101
2	11	12	9	7	10	7
3	11	9	8	8	9	94
4	0	0	0	0	0	70
Потребности	44	64	63	12	89

Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	5	Запасы
1	11	12	10	7[12]	9[89]	101
2	11[7]	12	9	7	10	7
3	11	9[31]	8[63]	8	9	94
4	0[37]	0[33]	0	0	0	70
Потребности	44	64	63	12	89

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

	1	2	3	4	5	Запасы
1	11[7]	12	10	7[5]	9[89]	101
2	11	12	9	7[7]	10	7
3	11	9[31]	8[63]	8	9	94
4	0[37]	0[33]	0	0	0	70
Потребности	44	64	63	12	89

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

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

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

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

	v1=11	v2=11	v3=10	v4=7	v5=9
u1=0	11[7]	12	10	7[5]	9[89]
u2=0	11	12	9	7[7]	10
u3=-2	11	9[31]	8[63]	8	9
u4=-11	0[37]	0[33]	0	0	0

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

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

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

	1	2	3	4	5	Запасы
1	11[7][-]	12	10	7[5][+]	9[89]	101
2	11	12	9[+]	7[7][-]	10	7
3	11	9[31][+]	8[63][-]	8	9	94
4	0[37][+]	0[33][-]	0	0	0	70
Потребности	44	64	63	12	89

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

	1	2	3	4	5	Запасы
1	11[0]	12	10	7[12]	9[89]	101
2	11	12	9[7]	7	10	7
3	11	9[38]	8[56]	8	9	94
4	0[44]	0[26]	0	0	0	70
Потребности	44	64	63	12	89

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

	v1=11	v2=11	v3=10	v4=7	v5=9
u1=0	11[0]	12	10	7[12]	9[89]
u2=-1	11	12	9[7]	7	10
u3=-2	11	9[38]	8[56]	8	9
u4=-11	0[44]	0[26]	0	0	0

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

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

F(x) = 7*12 + 9*89 + 9*7 + 9*38 + 8*56 + 0*44 + 0*26 = 1738

Ответ: F(X)=1738