II. Постановка и решение транспортной задачи

Фирма "Х" производит поставку продуктов питания для школ со складов А1,А2,А3,А4 в школы 1, 2, 3, 4 в количестве 190,250,210,300 единиц продуктов питания.

При заданных стоимостях перевозок составьте оптимальный план перевозок? Рассчитайте минимальные транспортные затраты на транспортировку продуктов питания в школы?

Стоимость доставки единицы груза из каждого склада в школы задана таблицей тарифов.

	Школа 1	Школа 2	Школа 3	Школа 4	Запасы
Склад A1	2	5	4	5	150
Склад A2	3	3	3	6	90
Склад А3	5	1	2	7	290
Склад А4	6	4	1	4	300
Потребности	190	250	210	300

2.1.Решение

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

Общий запас продуктов питания на складе составляет:

∑_а = 150+90+290+300= 830 у.е.,

а общая потребность школ в продуктах питания составляет:

∑_b = 190+250+210+300 = 950 у.е.

Из этого следует, что задача является открытой (несбалансированной). Для решения этой задачи мы вводим фиктивного поставщика (ФП).

ФП= "Потребности - Запасы"; ФП=950 у.е. - 830 у.е.; ФП=120 у.е.

Составляем матрицу, в строке ФП транспортные расходы равны 0.

	Школа 1	Школа 2	Школа 3	Школа 4	Запасы
Склад A1	2	5	4	5	150
Склад A2	3	3	3	6	90
Склад А3	5	1	2	7	290
Склад А4	6	4	1	4	300
Склад А5	0	0	0	0	120
Потребности	190	250	210	300

Строим опорный план:

	Школа 1	Школа 2	Школа 3	Школа 4	Запасы
Склад A1	2 150	5 0	4 0	5 0	150
Склад A2	3 40	3 50	3 0	6 0	90
Склад А3	5 0	1 200	2 90	7 0	290
Склад А4	6 0	4 0	1 120	4 180	300
Склад А5	0 0	0 0	0 0	0 120	120
Потребности	190	250	210	300

Посчитаем число занятых клеток по формуле:

m+n-1, где m - количество складов, а n - количество школ;

5+4-1=8, следовательно, опорный план является невырожденным.

	Школа 1	Школа 2	Школа 3	Школа 4	Запасы
Склад A1	2 150				150
Склад A2	3 40	3 50			90
Склад А3		1 200	2 90		290
Склад А4			1 120	4 180	300
Склад А5				0 120	120
Потребности	190	250	210	300

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

F(x)=2*150+3*40+3*50+1*200+2*90+1*120+4*180+0*120;

F(x)=300+120+150+120+180+120+720;

F(x)=1790;

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i и v_j по занятым клеткам в таблице, в которых U_i+V_j=C_ij.

Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек путем переноса только тех ячеек p_ij, которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми.

Кроме того, введем вспомогательный столбец, в который занесем значения U₁…U_n (U – это же m – число складов) и вспомогательную строку, в которую занесем значения неизвестных V₁…V_n (v – это же n – число потребителей).

Эти переменные должны удовлетворять линейную систему уравнений:

U_i+V_j=A_ij

Предположим, что U₁=0, тогда:

1. V₁=U₁+A_1,1; V₁=0+2; V₁=2;

2. U₂=V₁-A_2,1; U₂=2-3; U₂=-1;

3. V₂=U₂+A_2,2; V₂=-1+3; V₂=2;

4. U₃=V₂-A_3,2; U₃=2-1; U₃=1;

5. V₃=U₃+A_3,2; V₃=1+2; V₃=3;

6. U₄=V₃-A_4,3; U₄=3-1; U₄=2;

7. V₄=U₄+A_4,4; V₄=2+4; V₄=6;

8. U₅=V₄-A_5,4; U₅=6-0; U₅=6;

Составляем рабочую таблицу затрат:

	Школа 1	Школа 2	Школа 3	Школа 4	Ui
Склад A1	2				0
Склад A2	3	3			-1
Склад А3		1	2		1
Склад А4			1	4	2
Склад А5				0	6
Vj	2	2	3	6

Переносим данные опорного плана в ячейки А_1,1 - А_5,4.

	Школа 1	Школа 2	Школа 3	Школа 4	Ui
Склад A1	2 150	5 0	4 0	5 0	0
Склад A2	3 40	3 50	3 0	6 0	-1
Склад А3	5 0	1 200	2 90	7 0	1
Склад А4	6 0	4 0	1 120	4 180	2
Склад А5	0 0	0 0	0 0	0 120	6
Vj	2	2	3	6

Составляем матрицу затрат С_i,j по формуле: C_i,j=U_i+A_i,j-V_j.

С_i,j=

Из всех отрицательных чисел выбираем наибольшее по модулю, так как воздействие этого числа на затраты является максимальным. В нашем случае это число находится в ячейке А_1,4. Отметим в транспортной таблице ячейку А_1,4 знаком "+". Остальные занятые ячейки в этой строке знаком "–", таким образом, чтобы в каждой строке получился и "+", и "–", т.е. все помеченные клетки должны образовывать цикл.

Определяет минимум min из всех элементов, помеченных знаком "–", и выбирает одну ячейку, где этот минимум достигается. В нашем случае такой является А_2,2. Значение min при этом равно 50. В ячейку А_1,4 записываем значение min, ячейка А_2,2 остается пустой. В остальных ячейках, помеченных знаком "+" или "–" значение min либо складывается, либо вычитается.

Находим значения U_i и V_j. Результат заносим в новую таблицу.

	Школа 1	Школа 2	Школа 3	Школа 4	Ui
Склад A1	2 100	5 0	4 0	5 50	0
Склад A2	3 90	3 0	3 0	6 0	-1
Склад А3	5 0	1 250	2 40	7 0	0
Склад А4	6 0	4 0	1 170	4 130	1
Склад А5	0 0	0 0	0 0	0 120	5
Vj	2	1	2	5

Составляем матрицу затрат С_i,j.

С_i,j=

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

Находим F_min.

F_min= 2*100+5*50+3*90+1*250+2*40+1*170+4*130+0*120;

F_min= 200+250+270+250+80+170+520;

F_min=1740.