Решение транспортной задачи

Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.

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

 

1

2

3

4

Запасы

1

6

3

7

1

10

2

5

12

10

4

29

3

16

8

2

9

39

4

5

11

10

3

49

5

0

0

0

0

34

Потребности

19

35

42

65

 

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

 ∑a = 10 + 29 + 39 + 49 + 34 = 161

 ∑b = 19 + 35 + 42 + 65 = 161

 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

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

 

1

2

3

4

Запасы

1

6

3

7

1

10

2

5

12

10

4

29

3

16

8

2

9

39

4

5

11

10

3

49

5

0

0

0

0

34

Потребности

19

35

42

65

 

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

 План начинается заполняться с верхнего левого угла.

 Искомый элемент равен 6

 Для этого элемента запасы равны 10, потребности 19. Поскольку минимальным является 10, то вычитаем его.

 x11 = min(10,19) = 10.

6

x

x

x

10 - 10 = 0

5

12

10

4

29

16

8

2

9

39

5

11

10

3

49

0

0

0

0

34

19 - 10 = 9

35

42

65

0

 

 Искомый элемент равен 5

 Для этого элемента запасы равны 29, потребности 9. Поскольку минимальным является 9, то вычитаем его.

 x21 = min(29,9) = 9.

6

x

x

x

0

5

12

10

4

29 - 9 = 20

x

8

2

9

39

x

11

10

3

49

0

0

0

0

34

9 - 9 = 0

35

42

65

0

 

 Искомый элемент равен 12

 Для этого элемента запасы равны 20, потребности 35. Поскольку минимальным является 20, то вычитаем его.

 x22 = min(20,35) = 20.

6

x

x

x

0

5

12

x

x

20 - 20 = 0

x

8

2

9

39

x

11

10

3

49

0

0

0

0

34

0

35 - 20 = 15

42

65

0

 

 Искомый элемент равен 8

 Для этого элемента запасы равны 39, потребности 15. Поскольку минимальным является 15, то вычитаем его.

 x32 = min(39,15) = 15.

6

x

x

x

0

5

12

x

x

0

x

8

2

9

39 - 15 = 24

x

x

10

3

49

0

0

0

0

34

0

15 - 15 = 0

42

65

0

 

 Искомый элемент равен 2

 Для этого элемента запасы равны 24, потребности 42. Поскольку минимальным является 24, то вычитаем его.

 x33 = min(24,42) = 24.

6

x

x

x

0

5

12

x

x

0

x

8

2

x

24 - 24 = 0

x

x

10

3

49

0

0

0

0

34

0

0

42 - 24 = 18

65

0

 

 Искомый элемент равен 10

 Для этого элемента запасы равны 49, потребности 18. Поскольку минимальным является 18, то вычитаем его.

 x43 = min(49,18) = 18.

6

x

x

x

0

5

12

x

x

0

x

8

2

x

0

x

x

10

3

49 - 18 = 31

0

0

0

0

34

0

0

18 - 18 = 0

65

0

 

 Искомый элемент равен 3

 Для этого элемента запасы равны 31, потребности 65. Поскольку минимальным является 31, то вычитаем его.

 x44 = min(31,65) = 31.

6

x

x

x

0

5

12

x

x

0

x

8

2

x

0

x

x

10

3

31 - 31 = 0

0

0

0

0

34

0

0

0

65 - 31 = 34

0

 

 Искомый элемент равен 0

 Для этого элемента запасы равны 34, потребности 34. Поскольку минимальным является 34, то вычитаем его.

 x54 = min(34,34) = 34.

6

x

x

x

0

5

12

x

x

0

x

8

2

x

0

x

x

10

3

0

0

0

0

0

34 - 34 = 0

0

0

0

34 - 34 = 0

0

 

 

1

2

3

4

Запасы

1

6[10]

3

7

1

10

2

5[9]

12[20]

10

4

29

3

16

8[15]

2[24]

9

39

4

5

11

10[18]

3[31]

49

5

0

0

0

0[34]

34

Потребности

19

35

42

65

 

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

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

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

 F(x) = 6*10 + 5*9 + 12*20 + 8*15 + 2*24 + 10*18 + 3*31 + 0*34  = 786

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v1 = 6; 0 + v1 = 6; v1 = 6

 u2 + v2 = 12; -1 + v2 = 12; v2 = 13

 u3 + v3 = 2; -5 + v3 = 2; v3 = 7

 u4 + v4 = 3; 3 + v4 = 3; v4 = 0

 

v1=6

v2=13

v3=7

v4=0

u1=0

6[10]

3

7

1

u2=-1

5[9]

12[20]

10

4

u3=-5

16

8[15]

2[24]

9

u4=3

5

11

10[18]

3[31]

u5=0

0

0

0

0[34]

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

 (1;2): 0 + 13 > 3; ∆12 = 0 + 13 - 3 = 10

 (4;1): 3 + 6 > 5; ∆41 = 3 + 6 - 5 = 4

 (4;2): 3 + 13 > 11; ∆42 = 3 + 13 - 11 = 5

 (5;1): 0 + 6 > 0; ∆51 = 0 + 6 - 0 = 6

 (5;2): 0 + 13 > 0; ∆52 = 0 + 13 - 0 = 13

 (5;3): 0 + 7 > 0; ∆53 = 0 + 7 - 0 = 7

 max(10,4,5,6,13,7) = 13

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

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

 

1

2

3

4

Запасы

1

6[10]

3

7

1

10

2

5[9]

12[20]

10

4

29

3

16

8[15][-]

2[24][+]

9

39

4

5

11

10[18][-]

3[31][+]

49

5

0

0[+]

0

0[34][-]

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6[10]

3

7

1

10

2

5[9]

12[20]

10

4

29

3

16

8

2[39]

9

39

4

5

11

10[3]

3[46]

49

5

0

0[15]

0

0[19]

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v1 = 6; 0 + v1 = 6; v1 = 6

 u2 + v2 = 12; -1 + v2 = 12; v2 = 13

 u5 + v4 = 0; -13 + v4 = 0; v4 = 13

 u4 + v3 = 10; -10 + v3 = 10; v3 = 20

 

v1=6

v2=13

v3=20

v4=13

u1=0

6[10]

3

7

1

u2=-1

5[9]

12[20]

10

4

u3=-18

16

8

2[39]

9

u4=-10

5

11

10[3]

3[46]

u5=-13

0

0[15]

0

0[19]

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

 (1;2): 0 + 13 > 3; ∆12 = 0 + 13 - 3 = 10

 (1;3): 0 + 20 > 7; ∆13 = 0 + 20 - 7 = 13

 (1;4): 0 + 13 > 1; ∆14 = 0 + 13 - 1 = 12

 (2;3): -1 + 20 > 10; ∆23 = -1 + 20 - 10 = 9

 (2;4): -1 + 13 > 4; ∆24 = -1 + 13 - 4 = 8

 (5;3): -13 + 20 > 0; ∆53 = -13 + 20 - 0 = 7

 max(10,13,12,9,8,7) = 13

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

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

 

1

2

3

4

Запасы

1

6[10][-]

3

7[+]

1

10

2

5[9][+]

12[20][-]

10

4

29

3

16

8

2[39]

9

39

4

5

11

10[3][-]

3[46][+]

49

5

0

0[15][+]

0

0[19][-]

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6[7]

3

7[3]

1

10

2

5[12]

12[17]

10

4

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[18]

0

0[16]

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v1 = 6; 0 + v1 = 6; v1 = 6

 u2 + v2 = 12; -1 + v2 = 12; v2 = 13

 u5 + v4 = 0; -13 + v4 = 0; v4 = 13

 u1 + v3 = 7; 0 + v3 = 7; v3 = 7

 

v1=6

v2=13

v3=7

v4=13

u1=0

6[7]

3

7[3]

1

u2=-1

5[12]

12[17]

10

4

u3=-5

16

8

2[39]

9

u4=-10

5

11

10

3[49]

u5=-13

0

0[18]

0

0[16]

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

 (1;2): 0 + 13 > 3; ∆12 = 0 + 13 - 3 = 10

 (1;4): 0 + 13 > 1; ∆14 = 0 + 13 - 1 = 12

 (2;4): -1 + 13 > 4; ∆24 = -1 + 13 - 4 = 8

 max(10,12,8) = 12

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

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

 

1

2

3

4

Запасы

1

6[7][-]

3

7[3]

1[+]

10

2

5[12][+]

12[17][-]

10

4

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[18][+]

0

0[16][-]

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6

3

7[3]

1[7]

10

2

5[19]

12[10]

10

4

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[25]

0

0[9]

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v3 = 7; 0 + v3 = 7; v3 = 7

 u1 + v4 = 1; 0 + v4 = 1; v4 = 1

 u5 + v2 = 0; -1 + v2 = 0; v2 = 1

 u2 + v1 = 5; 11 + v1 = 5; v1 = -6

 

v1=-6

v2=1

v3=7

v4=1

u1=0

6

3

7[3]

1[7]

u2=11

5[19]

12[10]

10

4

u3=-5

16

8

2[39]

9

u4=2

5

11

10

3[49]

u5=-1

0

0[25]

0

0[9]

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

 (2;3): 11 + 7 > 10; ∆23 = 11 + 7 - 10 = 8

 (2;4): 11 + 1 > 4; ∆24 = 11 + 1 - 4 = 8

 (5;3): -1 + 7 > 0; ∆53 = -1 + 7 - 0 = 6

 max(8,8,6) = 8

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

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

 

1

2

3

4

Запасы

1

6

3

7[3][-]

1[7][+]

10

2

5[19]

12[10][-]

10[+]

4

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[25][+]

0

0[9][-]

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6

3

7

1[10]

10

2

5[19]

12[7]

10[3]

4

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[28]

0

0[6]

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v4 = 1; 0 + v4 = 1; v4 = 1

 u5 + v2 = 0; -1 + v2 = 0; v2 = 1

 u2 + v1 = 5; 11 + v1 = 5; v1 = -6

 u2 + v3 = 10; 11 + v3 = 10; v3 = -1

 

v1=-6

v2=1

v3=-1

v4=1

u1=0

6

3

7

1[10]

u2=11

5[19]

12[7]

10[3]

4

u3=3

16

8

2[39]

9

u4=2

5

11

10

3[49]

u5=-1

0

0[28]

0

0[6]

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

 (2;4): 11 + 1 > 4; ∆24 = 11 + 1 - 4 = 8

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

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

 

1

2

3

4

Запасы

1

6

3

7

1[10]

10

2

5[19]

12[7][-]

10[3]

4[+]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[28][+]

0

0[6][-]

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6

3

7

1[10]

10

2

5[19]

12[1]

10[3]

4[6]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[34]

0

0

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v4 = 1; 0 + v4 = 1; v4 = 1

 u2 + v1 = 5; 3 + v1 = 5; v1 = 2

 u2 + v2 = 12; 3 + v2 = 12; v2 = 9

 u2 + v3 = 10; 3 + v3 = 10; v3 = 7

 

v1=2

v2=9

v3=7

v4=1

u1=0

6

3

7

1[10]

u2=3

5[19]

12[1]

10[3]

4[6]

u3=-5

16

8

2[39]

9

u4=2

5

11

10

3[49]

u5=-9

0

0[34]

0

0

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

 (1;2): 0 + 9 > 3; ∆12 = 0 + 9 - 3 = 6

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

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

 

1

2

3

4

Запасы

1

6

3[+]

7

1[10][-]

10

2

5[19]

12[1][-]

10[3]

4[6][+]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[34]

0

0

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6

3[1]

7

1[9]

10

2

5[19]

12

10[3]

4[7]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[34]

0

0

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v2 = 3; 0 + v2 = 3; v2 = 3

 u1 + v4 = 1; 0 + v4 = 1; v4 = 1

 u2 + v1 = 5; 3 + v1 = 5; v1 = 2

 u2 + v3 = 10; 3 + v3 = 10; v3 = 7

 

v1=2

v2=3

v3=7

v4=1

u1=0

6

3[1]

7

1[9]

u2=3

5[19]

12

10[3]

4[7]

u3=-5

16

8

2[39]

9

u4=2

5

11

10

3[49]

u5=-3

0

0[34]

0

0

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

 (5;3): -3 + 7 > 0; ∆53 = -3 + 7 - 0 = 4

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

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

 

1

2

3

4

Запасы

1

6

3[1][+]

7

1[9][-]

10

2

5[19]

12

10[3][-]

4[7][+]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[34][-]

0[+]

0

34

Потребности

19

35

42

65

 

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

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

 

1

2

3

4

Запасы

1

6

3[4]

7

1[6]

10

2

5[19]

12

10

4[10]

29

3

16

8

2[39]

9

39

4

5

11

10

3[49]

49

5

0

0[31]

0[3]

0

34

Потребности

19

35

42

65

 

 4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

 u1 + v2 = 3; 0 + v2 = 3; v2 = 3

 u5 + v3 = 0; -3 + v3 = 0; v3 = 3

 u1 + v4 = 1; 0 + v4 = 1; v4 = 1

 u2 + v1 = 5; 3 + v1 = 5; v1 = 2

 

v1=2

v2=3

v3=3

v4=1

u1=0

6

3[4]

7

1[6]

u2=3

5[19]

12

10

4[10]

u3=-1

16

8

2[39]

9

u4=2

5

11

10

3[49]

u5=-3

0

0[31]

0[3]

0

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

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

 F(x) = 3*4 + 1*6 + 5*19 + 4*10 + 2*39 + 3*49 + 0*31 + 0*3  = 378

загрузка...