Автор: Пользователь скрыл имя, 14 Мая 2013 в 01:41, лабораторная работа
В данной лабораторной работе была решена транспортная задача по критерию времени. Решение производилось двумя способами: методом северо-западного угла и методом минимального элемента. Конечный результат при решении задачи двумя методами полностью совпал, что может говорить о правильности расчетов.
Если сравнивать два метода между собой, то стоит отметить, что для нахождения оптимального варианта методу северо-западного угла понадобилось 5 итераций, а методу минимального элемента всего 3. При этом максимальное значение времени без оптимизации у метода северо-западного угла составило 28, а у метода минимального элемента – 27. В результате оптимизации получен план, у которого максимально значение времени составляет 12.
|
|
|
|
| |||||||||||
|
5 |
15 |
3 1 |
6 8 |
10 | ||||||||||
|
23 |
8 7 |
13 |
27 |
12 4 | ||||||||||
|
30 |
1 2 |
5 12 |
24 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
T(X6) = max {3, 6, 8, 12, 1, 5, 8, 9} = 12
С помощью оставшихся не вычеркнутых клеток разгрузить клетку (2,5) не удаётся, т.е. план оптимальный.
Решение методом минимального элемента
Начальный план взят из лабораторной работы «Транспортная задача»
|
|
|
|
| |||||||||||
|
5 |
15 |
3 9 |
6 |
10 | ||||||||||
|
23 |
8 |
13 |
27 7 |
12 4 | ||||||||||
|
30 |
1 9 |
5 4 |
24 1 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
T(X1) = max {3, 27, 12, 1, 5, 24, 8, 9} =27
|
|
|
|
| |||||||||||
|
5 |
15 |
3- 9 |
6+ |
10 | ||||||||||
|
23 |
8 |
13+ |
27- 7 |
12 4 | ||||||||||
|
30 |
1 9 |
5 4 |
24 1 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
|
|
|
|
| |||||||||||
|
5 |
15 |
3 2 |
6 7 |
10 | ||||||||||
|
23 |
8 |
13 7 |
27 |
12 4 | ||||||||||
|
30 |
1 9 |
5 4 |
24 1 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
T(X2) = max {3, 6, 13, 12, 1, 5, 24, 8, 9} =24
|
|
|
|
| |||||||||||
|
5 |
15 |
3- 2 |
6+ 7 |
10 | ||||||||||
|
23 |
8 |
13 7 |
27 |
12 4 | ||||||||||
|
30 |
1 9 |
5+ 4 |
24- 1 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
|
|
|
|
| |||||||||||
|
5 |
15 |
3 1 |
6 8 |
10 | ||||||||||
|
23 |
8 |
13 7 |
27 |
12 4 | ||||||||||
|
30 |
1 9 |
5 5 |
24 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
T(X3) = max {3, 6, 13, 12, 1, 5, 8, 9} =13
|
|
|
|
| |||||||||||
|
5 |
15 |
3 1 |
6 8 |
10 | ||||||||||
|
23 |
8+ |
13- 7 |
27 |
12 4 | ||||||||||
|
30 |
1- 9 |
5+ 5 |
24 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
|
|
|
|
| |||||||||||
|
5 |
15 |
3 1 |
6 8 |
10 | ||||||||||
|
23 |
8 7 |
13 |
27 |
12 4 | ||||||||||
|
30 |
1 2 |
5 12 |
24 |
25 | ||||||||||
|
8 8 |
26 |
7 |
28 |
9 8 |
T(X4) = max {3, 6, 8, 12, 1, 5, 8, 9} = 12
С помощью оставшихся не вычеркнутых клеток разгрузить клетку (2,5) не удаётся, т.е. план оптимальный.
Выводы
В данной лабораторной работе была решена транспортная задача по критерию времени. Решение производилось двумя способами: методом северо-западного угла и методом минимального элемента. Конечный результат при решении задачи двумя методами полностью совпал, что может говорить о правильности расчетов.
Если сравнивать два метода между собой, то стоит отметить, что для нахождения оптимального варианта методу северо-западного угла понадобилось 5 итераций, а методу минимального элемента всего 3. При этом максимальное значение времени без оптимизации у метода северо-западного угла составило 28, а у метода минимального элемента – 27. В результате оптимизации получен план, у которого максимально значение времени составляет 12.