Поиск

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

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

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

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

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

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



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

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