Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Главная > Реферат >Математика

Сохрани ссылку на реферат в одной из сетей:

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

b1

b2

b3

b 4

b5

Запасы

a1

13

9

15

3

18

53

a2

7

8

6

10

9

17

a3

16

4

10

11

29

30

Потребности

20

20

20

13

27

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

∑ a = 53 + 17 + 30 = 100

∑ b = 20 + 20 + 20 + 13 + 27 = 100

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

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

1

2

3

4

5

Запасы

1

13

9

15

3

18

53

2

7

8

6

10

9

17

3

16

4

10

11

29

30

Потребности

20

20

20

13

27

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

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

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

13

9

15

3

18

33

x

8

6

10

9

17

x

4

10

11

29

30

0

20

20

13

27

0

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

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

13

9

15

3

18

13

x

x

6

10

9

17

x

x

10

11

29

30

0

0

20

13

27

0

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

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

13

9

15

x

x

0

x

x

6

10

9

17

x

x

10

11

29

30

0

0

7

13

27

0

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

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

13

9

15

x

x

0

x

x

6

10

9

10

x

x

x

11

29

30

0

0

0

13

27

0

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

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

13

9

15

x

x

0

x

x

6

10

x

0

x

x

x

11

29

30

0

0

0

3

27

0

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

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

13

9

15

x

x

0

x

x

6

10

x

0

x

x

x

11

29

27

0

0

0

0

27

0

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

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

13

9

15

x

x

0

x

x

6

10

x

0

x

x

x

11

29

0

0

0

0

0

0

0

1

2

3

4

5

Запасы

1

13[20]

9[20]

15[13]

3

18

53

2

7

8

6[7]

10[10]

9

17

3

16

4

10

11[3]

29[27]

30

Потребности

20

20

20

13

27

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

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

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u2 + v4 = 10; -9 + v4 = 10; v4 = 19

u3 + v4 = 11; 19 + u3 = 11; u3 = -8

u3 + v5 = 29; -8 + v5 = 29; v5 = 37

v1=13

v2=9

v3=15

v4=19

v5=37

u1=0

13[20]

9[20]

15[13]

3

18

u2=-9

7

8

6[7]

10[10]

9

u3=-8

16

4

10

11[3]

29[27]

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

(1;4): 0 + 19 > 3; ∆14 = 0 + 19 - 3 = 16

(1;5): 0 + 37 > 18; ∆15 = 0 + 37 - 18 = 19

(2;5): -9 + 37 > 9; ∆25 = -9 + 37 - 9 = 19

max(16,19,19) = 19

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

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

1

2

3

4

5

Запасы

1

13[20]

9[20]

15[13][-]

3

18[+]

53

2

7

8

6[7][+]

10[10][-]

9

17

3

16

4

10

11[3][+]

29[27][-]

30

Потребности

20

20

20

13

27

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

1

2

3

4

5

Запасы

1

13[20]

9[20]

15[3]

3

18[10]

53

2

7

8

6[17]

10

9

17

3

16

4

10

11[13]

29[17]

30

Потребности

20

20

20

13

27

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

u3 + v5 = 29; 18 + u3 = 29; u3 = 11

u3 + v4 = 11; 11 + v4 = 11; v4 = 0

v1=13

v2=9

v3=15

v4=0

v5=18

u1=0

13[20]

9[20]

15[3]

3

18[10]

u2=-9

7

8

6[17]

10

9

u3=11

16

4

10

11[13]

29[17]

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

(3;1): 11 + 13 > 16; ∆31 = 11 + 13 - 16 = 8

(3;2): 11 + 9 > 4; ∆32 = 11 + 9 - 4 = 16

(3;3): 11 + 15 > 10; ∆33 = 11 + 15 - 10 = 16

max(8,16,16) = 16

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

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

1

2

3

4

5

Запасы

1

13[20]

9[20][-]

15[3]

3

18[10][+]

53

2

7

8

6[17]

10

9

17

3

16

4[+]

10

11[13]

29[17][-]

30

Потребности

20

20

20

13

27

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

1

2

3

4

5

Запасы

1

13[20]

9[3]

15[3]

3

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[17]

10

11[13]

29

30

Потребности

20

20

20

13

27

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v2 = 9; 0 + v2 = 9; v2 = 9

u3 + v2 = 4; 9 + u3 = 4; u3 = -5

u3 + v4 = 11; -5 + v4 = 11; v4 = 16

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=9

v3=15

v4=16

v5=18

u1=0

13[20]

9[3]

15[3]

3

18[27]

u2=-9

7

8

6[17]

10

9

u3=-5

16

4[17]

10

11[13]

29

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

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

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

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

1

2

3

4

5

Запасы

1

13[20]

9[3][-]

15[3]

3[+]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[17][+]

10

11[13][-]

29

30

Потребности

20

20

20

13

27

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

1

2

3

4

5

Запасы

1

13[20]

9

15[3]

3[3]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10

11[10]

29

30

Потребности

20

20

20

13

27

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v3 = 15; 0 + v3 = 15; v3 = 15

u2 + v3 = 6; 15 + u2 = 6; u2 = -9

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u3 + v4 = 11; 3 + u3 = 11; u3 = 8

u3 + v2 = 4; 8 + v2 = 4; v2 = -4

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=-4

v3=15

v4=3

v5=18

u1=0

13[20]

9

15[3]

3[3]

18[27]

u2=-9

7

8

6[17]

10

9

u3=8

16

4[20]

10

11[10]

29

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

(3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

(3;3): 8 + 15 > 10; ∆33 = 8 + 15 - 10 = 13

max(5,13) = 13

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

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

1

2

3

4

5

Запасы

1

13[20]

9

15[3][-]

3[3][+]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10[+]

11[10][-]

29

30

Потребности

20

20

20

13

27

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

1

2

3

4

5

Запасы

1

13[20]

9

15

3[6]

18[27]

53

2

7

8

6[17]

10

9

17

3

16

4[20]

10[3]

11[7]

29

30

Потребности

20

20

20

13

27

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u3 + v4 = 11; 3 + u3 = 11; u3 = 8

u3 + v2 = 4; 8 + v2 = 4; v2 = -4

u3 + v3 = 10; 8 + v3 = 10; v3 = 2

u2 + v3 = 6; 2 + u2 = 6; u2 = 4

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

v1=13

v2=-4

v3=2

v4=3

v5=18

u1=0

13[20]

9

15

3[6]

18[27]

u2=4

7

8

6[17]

10

9

u3=8

16

4[20]

10[3]

11[7]

29

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

(2;1): 4 + 13 > 7; ∆21 = 4 + 13 - 7 = 10

(2;5): 4 + 18 > 9; ∆25 = 4 + 18 - 9 = 13

(3;1): 8 + 13 > 16; ∆31 = 8 + 13 - 16 = 5

max(10,13,5) = 13

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

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

1

2

3

4

5

Запасы

1

13[20]

9

15

3[6][+]

18[27][-]

53

2

7

8

6[17][-]

10

9[+]

17

3

16

4[20]

10[3][+]

11[7][-]

29

30

Потребности

20

20

20

13

27

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

1

2

3

4

5

Запасы

1

13[20]

9

15

3[13]

18[20]

53

2

7

8

6[10]

10

9[7]

17

3

16

4[20]

10[10]

11

29

30

Потребности

20

20

20

13

27

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

u1 + v1 = 13; 0 + v1 = 13; v1 = 13

u1 + v4 = 3; 0 + v4 = 3; v4 = 3

u1 + v5 = 18; 0 + v5 = 18; v5 = 18

u2 + v5 = 9; 18 + u2 = 9; u2 = -9

u2 + v3 = 6; -9 + v3 = 6; v3 = 15

u3 + v3 = 10; 15 + u3 = 10; u3 = -5

u3 + v2 = 4; -5 + v2 = 4; v2 = 9

v1=13

v2=9

v3=15

v4=3

v5=18

u1=0

13[20]

9

15

3[13]

18[20]

u2=-9

7

8

6[10]

10

9[7]

u3=-5

16

4[20]

10[10]

11

29

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

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

F(x) = 13*20 + 3*13 + 18*20 + 6*10 + 9*7 + 4*20 + 10*10 = 962



Скачать работу

Похожие работы: