Транспортная задача

                                        ФГБОУ ВПО

                     Дальневосточный государственный

                        университет путей сообщения

 

 

 

                                  

                                                                         

 

 

                                                                             Кафедра:

                                                                      «Строительное производство»

 

 

 

 

 

 

 

 

 

 

 

                           ТРАНСПОРТНАЯ ЗАДАЧА

 

 

 

 

 

 

 

 

 

 

 

 

      Выполнил: Панасевич К.В.

       Проверил: Клыков М.С.

 

 

 

 

 

 

 

 

 

 

 

                                       г. Хабаровск

                                               2012

Транспортная задача.

 

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

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	6	7	Запасы
1	8	5	1	10	7	4	1	150
2	9	3	2	8	6	4	20	240
3	5	9	4	2	11	15	8	60
4	18	7	3	8	6	9	4	290
5	13	6	18	19	12	4	9	70
6	12	3	5	6	2	9	14	470
Потребности	100	50	70	130	30	190	260

 

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

∑a = 150 + 240 + 60 + 290 + 70 + 470 = 1280

∑b = 100 + 50 + 70 + 130 + 30 + 190 + 260 = 830

Занесем исходные данные в  распределительную таблицу.

	1	2	3	4	5	6	7	8	Запасы
1	8	5	1	10	7	4	1	0	150
2	9	3	2	8	6	4	20	0	240
3	5	9	4	2	11	15	8	0	60
4	18	7	3	8	6	9	4	0	290
5	13	6	18	19	12	4	9	0	70
6	12	3	5	6	2	9	14	0	470
Потребности	100	50	70	130	30	190	260	450

 

Этап I. Поиск первого опорного плана.

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

	1	2	3	4	5	6	7	8	Запасы
1	8[100]	5[50]	1	10	7	4	1	0	150
2	9	3	2[70]	8[130]	6[30]	4[10]	20	0	240
3	5	9	4	2	11	15[60]	8	0	60
4	18	7	3	8	6	9[120]	4[170]	0	290
5	13	6	18	19	12	4	9[70]	0	70
6	12	3	5	6	2	9	14[20]	0[450]	470
Потребности	100	50	70	130	30	190	260	450

 

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

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

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

	1	2	3	4	5	6	7	8	Запасы
1	8[100]	5[50]	1	10	7	4	1	0	150
2	9	3	2[70]	8[130]	6[30]	4[10]	20	0	240
3	5	9	4	2	11	15[60]	8	0	60
4	18	7	3	8	6	9[120]	4[170]	0	290
5	13	6	18	19	12	4	9[70]	0	70
6	12	3	5	6	2	9	14[20]	0[450]	470
Потребности	100	50	70	130	30	190	260	450

 

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

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

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

	1	2	3	4	5	6	7	8	Запасы
1	8[80]	5	1[70]	10	7	4	1	0	150
2	9[20]	3[50]	2	8[130]	6[30]	4[10]	20	0	240
3	5	9	4	2	11	15[60]	8	0	60
4	18	7	3	8	6	9[120]	4[170]	0	290
5	13	6	18	19	12	4	9[70]	0	70
6	12	3	5	6	2	9	14[20]	0[450]	470
Потребности	100	50	70	130	30	190	260	450

 

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

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

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

Этап II. Улучшение опорного плана.

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

	v1=8	v2=2	v3=1	v4=7	v5=5	v6=3	v7=-2	v8=-16
u1=0	8[80]	5	1[70]	10	7	4	1	0
u2=1	9[20]	3[50]	2	8[130]	6[30]	4[10]	20	0
u3=12	5	9	4	2	11	15[60]	8	0
u4=6	18	7	3	8	6	9[120]	4[170]	0
u5=11	13	6	18	19	12	4	9[70]	0
u6=16	12	3	5	6	2	9	14[20]	0[450]

 

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

 

 

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

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

	1	2	3	4	5	6	7	8	Запасы
1	8[80]	5	1[70]	10	7	4	1	0	150
2	9[20]	3[50]	2	8[130]	6[30][-]	4[10][+]	20	0	240
3	5	9	4	2	11	15[60]	8	0	60
4	18	7	3	8	6	9[120][-]	4[170][+]	0	290
5	13	6	18	19	12	4	9[70]	0	70
6	12	3	5	6	2[+]	9	14[20][-]	0[450]	470
Потребности	100	50	70	130	30	190	260	450

 

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

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

	1	2	3	4	5	6	7	8	Запасы
1	8[80]	5	1[70]	10	7	4	1	0	150
2	9[20]	3[50]	2	8[130]	6[10]	4[30]	20	0	240
3	5	9	4	2	11	15[60]	8	0	60
4	18	7	3	8	6	9[100]	4[190]	0	290
5	13	6	18	19	12	4	9[70]	0	70
6	12	3	5	6	2[20]	9	14	0[450]	470
Потребности	100	50	70	130	30	190	260	450