Методы решения задач математического моделирования

курсовая работа

2.8 Решение транспортной задачи методом потенциалов

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

"right">Таблица 2.8.1

v1=2

v2=10

v3=15

v4=22

v5=25

u1=0

2[100]

10[50]

15

14

4

u2=-3

3

7[40]

12[130]

5

8

u3=-9

21

18

6[30]

13[150]

16[80]

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

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

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

"right">Таблица 2.8.2

Пункт направления

B1

B2

B3

B4

B5

Запасы

A1

2[100]

10[50][-]

15

14

4[+]

150

A2

3

7[40][+]

12[130][-]

5

8

170

A3

21

18

6[30][+]

13[150]

16[80][-]

260

Потребности

100

90

160

150

80

580

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

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е.

у = min (1, 2) = 50

Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план (Табл. 2.8.3).

"right">Таблица 2.8.3

Пункт направления

B1

B2

B3

B4

B5

Запасы

1

2[100]

10

15

14

4[50]

150

2

3

7[90]

12[80]

5

8

170

3

21

18

6[80]

13[150]

16[30]

260

Потребности

100

90

160

150

80

580

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

"right">Таблица 2.8.4

v1=2

v2=-11

v3=-6

v4=1

v5=4

u1=0

2[100]

10

15

14

4[50]

u2=18

3

7[90]

12[80]

5

8

u3=12

21

18

6[80]

13[150]

16[30]

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

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

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

"right">Таблица 2.8.5

Пункт направления

B1

B2

B3

B4

B5

Запасы

A1

2[100][-]

10

15

14

4[50][+]

150

A2

3[+]

7[90]

12[80][-]

5

8

170

A3

21

18

6[80][+]

13[150]

16[30][-]

260

Потребности

100

90

160

150

80

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

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

"right">Таблица 2.8.6

Пункт направления

B1

B2

B3

B4

B5

Запасы

A1

2[70]

10

15

14

4[80]

150

A2

3[30]

7[90]

12[50]

5

8

170

A3

21

18

6[110]

13[150]

16

260

Потребности

100

90

160

150

80

580

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

"right">Таблица 2.8.7

v1=2

v2=6

v3=11

v4=18

v5=4

u1=0

2[70]

10

15

14

4[80]

u2=1

3[30]

7[90]

12[50]

5

8

u3=-5

21

18

6[110]

13[150]

16

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

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

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

"right">Таблица 2.8.8

Пункт направления

B1

B2

B3

B4

B5

Запасы

A1

2[70]

10

15

14

4[80]

150

A 2

3[30]

7[90]

12[50][-]

5[+]

8

170

A 3

21

18

6[110][+]

13[150][-]

16

260

Потребности

100

90

160

150

80

580

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

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

"right">Таблица 2.8.9

Пункт направления

B1

B2

B3

B4

B5

Запасы

A1

2[70]

10

15

14

4[80]

150

A2

3[30]

7[90]

12

5[50]

8

170

A3

21

18

6[160]

13[100]

16

260

Потребности

100

90

160

150

80

580

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

"right">Таблица 2.8.10

v1=2

v2=6

v3=-3

v4=4

v5=4

u1=0

2[70]

10

15

14

4[80]

u2=1

3[30]

7[90]

12

5[50]

8

u3=9

21

18

6[160]

13[100]

16

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

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

F(x) = 2*70 + 4*80 + 3*30 + 7*90 + 5*50 + 6*160 + 13*100 = 3690

Делись добром ;)