Автор: Пользователь скрыл имя, 11 Марта 2013 в 11:59, курсовая работа
Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[20] |
22 |
23 |
24 |
65 |
22 |
28[45] |
31 |
40 |
15[20] |
90 |
23 |
27 |
34[65] |
43[25] |
18 |
20*50 + 21*20 + 28*45 + 15*20 + 34*65 + 43*25 = 6265
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 5) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[20] |
22 |
23 |
24 |
65 |
22 |
28[45] |
31[20] |
40 |
15 |
90 |
23 |
27 |
34[45] |
43[15] |
18[30] |
20*50 + 21*20 + 28*45 + 31*20 + 34*45 + 43*15 = 6015
Выбираем тот вариант, чья функция затрат будет минимальной Fx = 6015
Определяем оценку для каждой свободной клетки.
В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[20] [-] |
22 [+] |
23 |
24 |
65 |
22 |
28[45] [+] |
31[20] [-] |
40 |
15 |
90 |
23 |
27 |
34[45] |
43[15] |
18[30] |
Оценка свободной клетки равна Δ13 = -2
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ14 = -10
Оценка свободной клетки равна Δ15 = 16
Оценка свободной клетки равна Δ21 = -5
Оценка свободной клетки равна Δ24 = 0
Оценка свободной клетки равна Δ25 = 0
Оценка свободной клетки равна Δ31 = -7
Оценка свободной клетки равна Δ32 = -4
Оценка свободной клетки равна Δ41 = 13
Оценка свободной клетки равна Δ42 = 12
Оценка свободной клетки равна Δ43 = 9
Оценка свободной клетки равна Δ45 = 25.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток равные: (-10).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[5] |
22 |
23[15] |
24 |
65 |
22 |
28[60] |
31[5] |
40 |
15 |
90 |
23 |
27 |
34[60] |
43 |
18[30] |
20*50 + 21*5 + 23*15 + 28*60 + 31*5 + 34*60 = 5865
Определяем оценку для каждой свободной клетки.
В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[5] [-] |
22 [+] |
23[15] |
24 |
65 |
22 |
28[60] [+] |
31[5] [-] |
40 |
15 |
90 |
23 |
27 |
34[60] |
43 |
18[30] |
Оценка свободной клетки равна Δ13 = -2
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ15 = 16
Оценка свободной клетки равна Δ21 = -5
Оценка свободной клетки равна Δ24 = 10
Оценка свободной клетки равна Δ25 = 0
Оценка свободной клетки равна Δ31 = -7
Оценка свободной клетки равна Δ32 = -4
Оценка свободной клетки равна Δ34 = 10
Оценка свободной клетки равна Δ41 = 3
Оценка свободной клетки равна Δ42 = 2
Оценка свободной клетки равна Δ43 = -1
Оценка свободной клетки равна Δ45 = 15.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток равные: (-7).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
55 |
30 | |
70 |
20 |
21[55] |
22 |
23[15] |
24 |
65 |
22 |
28[10] |
31[55] |
40 |
15 |
90 |
23[50] |
27 |
34[10] |
43 |
18[30] |
21*55 + 23*15 + 28*10 + 31*55 + 23*50 + 34*10 = 5515
Определяем оценку для каждой свободной клетки.
В свободную клетку
(1;1) поставим знак «+», а в
остальных вершинах
50 |
65 |
65 |
55 |
30 | |
70 |
20 [+] |
21[55] [-] |
22 |
23[15] |
24 |
65 |
22 |
28[10] [+] |
31[55] [-] |
40 |
15 |
90 |
23[50] [-] |
27 |
34[10] [+] |
43 |
18[30] |
Оценка свободной клетки равна Δ11 = 7
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ13 = -2
Оценка свободной клетки равна Δ15 = 16
Оценка свободной клетки равна Δ21 = 2
Оценка свободной клетки равна Δ24 = 10
Оценка свободной клетки равна Δ25 = 0
Оценка свободной клетки равна Δ32 = -4
Оценка свободной клетки равна Δ34 = 10
Оценка свободной клетки равна Δ41 = 10
Оценка свободной клетки равна Δ42 = 2
Оценка свободной клетки равна Δ43 = -1
Оценка свободной клетки равна Δ45 = 15.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток равные: (-4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план
50 |
65 |
65 |
55 |
30 | |
70 |
20 |
21[55] |
22 |
23[15] |
24 |
65 |
22 |
28 |
31[65] |
40 |
15 |
90 |
23[50] |
27[10] |
34[0] |
43 |
18[30] |
21*55 + 23*15 + 31*65 + 23*50 + 27*10 = 5475
Аналогично определяем минимальные затраты:
21*55 + 23*15 + 31*65 + 23*50 + 27*10 + 18*30 = 5475
21*25 + 22*30 + 23*15 + 31*35 + 15*30 + 23*50 + 27*40 = 5295
22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 + 0*40 = 5195
Из приведенного расчета видно, что ни одна свободная клетка не имеет отрицательной оценки, следовательно, дальнейшее снижение целевой функции Fx невозможно, поскольку она достигла минимального значения.
Таким образом, последний опорный план является оптимальным.
Минимальные затраты составят:
22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
МЕТОД ПОТЕНЦИАЛОВ
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
50 |
65 |
65 |
55 |
30 | |
70 |
20 |
21 |
22 |
23 |
24 |
65 |
22 |
28 |
31 |
40 |
15 |
90 |
23 |
27 |
34 |
43 |
18 |
Проверим необходимое
и достаточное условие
∑a = 70 + 65 + 90 = 225
∑b = 50 + 65 + 65 + 55 + 30 = 265
Занесем исходные данные в распределительную таблицу.
50 |
65 |
65 |
55 |
30 | |
70 |
20 |
21 |
22 |
23 |
24 |
65 |
22 |
28 |
31 |
40 |
15 |
90 |
23 |
27 |
34 |
43 |
18 |
Построим первый опорный план транспортной задачи.
50 |
65 |
65 |
55 |
30 | |
70 |
20[50] |
21[20] |
22 |
23 |
24 |
65 |
22 |
28[45] |
31[20] |
40 |
15 |
90 |
23 |
27 |
34[45] |
43[45] |
18 |