Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Транспортна задача за критерієм часу

Міністерство освіти та науки, молоді та спорту України

Національний Технічний Університет України „КПІ”

Кафедра КЕОА

Звіт з лабораторної роботи

на тему: „Транспортна задача за критерієм часу”

Виконав:

студент V курсу

гр. ДКм-81 ФЕЛ

Кирпач Д.І.

Перевірив:

Яганов П.О.

Київ 2013

Решение методом северо-западного угла

Начальный план взят из лабораторной работы «Транспортная задача»

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

5 8

15 1

a₂=

8 8

13 3

a₃=

5 10

24 4

a₄=

28 4

9 12

T(X1) = max {5, 15, 8, 13, 5, 24, 28, 9} = 28

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

5- 8

15 1

a₂=

8 8

13 3

a₃=

5 10

24 4

a₄=

28- 4

9 12

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

5 4

15 1

6 4

a₂=

8 8

13 3

a₃=

5 10

24 4

a₄=

8 4

9 12

T(X2) = max {5, 15, 6, 8, 13, 10, 24, 8, 9} = 24

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

5- 4

15 1

6+ 4

a₂=

23+

8- 8

13 3

a₃=

5 10

24- 4

a₄=

8 4

9 12

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

15 1

6 8

a₂=

23 4

8 4

13 3

a₃=

1 4

5 10

a₄=

8 4

9 12

T(X3) = max {15, 6, 23, 8, 13, 1, 5, 8, 9} = 23

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

15 1

6 8

a₂=

23- 4

8 4

13 3

12+

a₃=

1 4

5 10

a₄=

8+ 4

9- 12

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

15 1

6 8

a₂=

8 4

13 3

12 4

a₃=

1 4

5 10

a₄=

8 8

9 8

T(X4) = max {15, 6, 8, 13, 12, 1, 5, 8, 9} = 15

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

15- 1

6 8

a₂=

8 4

13 3

12 4

a₃=

1+ 4

5- 10

a₄=

8 8

9 8

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

8 4

13 3

12 4

a₃=

1 5

5 9

a₄=

8 8

9 8

T(X5) = max {3, 6, 8, 13, 12, 1, 5, 8, 9} = 13

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

8+ 4

13- 3

12 4

a₃=

1- 5

5+ 9

a₄=

8 8

9 8

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

8 7

12 4

a₃=

1 2

5 12

a₄=

8 8

9 8

T(X6) = max {3, 6, 8, 12, 1, 5, 8, 9} = 12

С помощью оставшихся не вычеркнутых клеток разгрузить клетку (2,5) не удаётся, т.е. план оптимальный.

Решение методом минимального элемента

Начальный план взят из лабораторной работы «Транспортная задача»

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 9

a₂=

27 7

12 4

a₃=

1 9

5 4

24 1

a₄=

8 8

9 8

T(X1) = max {3, 27, 12, 1, 5, 24, 8, 9} =27

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3- 9

a₂=

13+

27- 7

12 4

a₃=

1 9

5 4

24 1

a₄=

8 8

9 8

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 2

6 7

a₂=

13 7

12 4

a₃=

1 9

5 4

24 1

a₄=

8 8

9 8

T(X2) = max {3, 6, 13, 12, 1, 5, 24, 8, 9} =24

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3- 2

6+ 7

a₂=

13 7

12 4

a₃=

1 9

5+ 4

24- 1

a₄=

8 8

9 8

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

13 7

12 4

a₃=

1 9

5 5

a₄=

8 8

9 8

T(X3) = max {3, 6, 13, 12, 1, 5, 8, 9} =13

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

13- 7

12 4

a₃=

1- 9

5+ 5

a₄=

8 8

9 8

b₁=

b₂=

b₃=

b₄=

b₅=

a₁=

3 1

6 8

a₂=

8 7

12 4

a₃=

1 2

5 12

a₄=

8 8

9 8

T(X4) = max {3, 6, 8, 12, 1, 5, 8, 9} = 12

С помощью оставшихся не вычеркнутых клеток разгрузить клетку (2,5) не удаётся, т.е. план оптимальный.

Выводы

В данной лабораторной работе была решена транспортная задача по критерию времени. Решение производилось двумя способами: методом северо-западного угла и методом минимального элемента. Конечный результат при решении задачи двумя методами полностью совпал, что может говорить о правильности расчетов.

Если сравнивать два метода между собой, то стоит отметить, что для нахождения оптимального варианта методу северо-западного угла понадобилось 5 итераций, а методу минимального элемента всего 3. При этом максимальное значение времени без оптимизации у метода северо-западного угла составило 28, а у метода минимального элемента – 27. В результате оптимизации получен план, у которого максимально значение времени составляет 12.