Автор: Пользователь скрыл имя, 11 Марта 2013 в 11:59, курсовая работа
Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Опорный план является неоптимальным, поскольку имеются, отрицательны оценки клеток (1,4;) равные: (-14).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21[5] |
22 |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23 |
27[60] |
34[30] |
43 |
18 |
20*50 + 21*5 + 23*15 + 31*35 + 15*30 + 27*60 + 34*30 = 5625
3)Определяем оценку для каждой свободной клетки.
В свободную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21[5] [-] |
22 [+] |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23 |
27[60] [+] |
34[30] [-] |
43 |
18 |
Оценка свободной клетки равна Δ13 = -6.
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ15 = 12.
Оценка свободной клетки равна Δ21 = -1.
Оценка свободной клетки равна Δ22 = 4.
Оценка свободной клетки равна Δ24 = 14.
Оценка свободной клетки равна Δ31 = -3.
Оценка свободной клетки равна Δ34 = 14.
В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21[5] |
22 |
23[15] |
24 |
65 |
22 |
28 |
31[35] [+] |
40 |
15[30] [-] |
90 |
23 |
27[60] |
34[30] [-] |
43 |
18 [+] |
Оценка свободной клетки равна Δ35 = 0.
Опорный план является неоптимальным, поскольку имеются, отрицательны оценки клеток (1,3;) равные: (-6).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21 |
22[5] |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23 |
27[65] |
34[25] |
43 |
18 |
20*50 + 22*5 + 23*15 + 31*35 + 15*30 + 27*65 + 34*25 = 5595
4) Определяем оценку для каждой свободной клетки.
В свободную клетку
(1;2) поставим знак «+», а в
остальных вершинах
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21 [+] |
22[5] [-] |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23 |
27[65] [-] |
34[25] [+] |
43 |
18 |
Оценка свободной клетки равна Δ12 = 6.
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ15 = 18.
Оценка свободной клетки равна Δ21 = -7.
Оценка свободной клетки равна Δ22 = 4.
Оценка свободной клетки равна Δ24 = 8.
Оценка свободной клетки равна Δ31 = -9.
Оценка свободной клетки равна Δ34 = 8.
В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20[50] |
21 |
22[5] |
23[15] |
24 |
65 |
22 |
28 |
31[35] [+] |
40 |
15[30] [-] |
90 |
23 |
27[65] |
34[25] [-] |
43 |
18 [+] |
Оценка свободной клетки равна Δ35 = 0.
Опорный план является неоптимальным, поскольку имеются, отрицательны оценки клеток (3,1;) равные: (-9).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
15 |
30 | |
70 |
20[25] |
21 |
22[30] |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23[25] |
27[65] |
34 |
43 |
18 |
20*25 + 22*30 + 23*15 + 31*35 + 15*30 + 23*25 + 27*65 = 5370
5) Определяем оценку для каждой свободной клетки.
В свободную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20[25] [-] |
21 [+] |
22[30] |
23[15] |
24 |
65 |
22 |
28 |
31[35] |
40 |
15[30] |
90 |
23[25] [+] |
27[65] [-] |
34 |
43 |
18 |
Оценка свободной клетки равна Δ12 = -3.
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ15 = 18.
Оценка свободной клетки равна Δ21 = -7.
Оценка свободной клетки равна Δ22 = -5.
Оценка свободной клетки равна Δ24 = 8.
Оценка свободной клетки равна Δ33 = 9.
Оценка свободной клетки равна Δ34 = 17.
В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20[25] [+] |
21 |
22[30] [-] |
23[15] |
24 |
65 |
22 |
28 |
31[35] [+] |
40 |
15[30] [-] |
90 |
23[25] [-] |
27[65] |
34 |
43 |
18 [+] |
Оценка свободной клетки равна Δ35 = 9.
Опорный план является неоптимальным, поскольку имеются, отрицательны оценки клеток (2,1;) равные: (-7).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 25. Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем 25 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
50 |
65 |
65 |
15 |
30 | |
70 |
20 |
21 |
22[55] |
23[15] |
24 |
65 |
22[25] |
28 |
31[10] |
40 |
15[30] |
90 |
23[25] |
27[65] |
34 |
43 |
18 |
22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195
6) Определяем оценку для каждой свободной клетки.
В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20 [+] |
21 |
22[55] [-] |
23[15] |
24 |
65 |
22[25] [-] |
28 |
31[10] [+] |
40 |
15[30] |
90 |
23[25] |
27[65] |
34 |
43 |
18 |
Оценка свободной клетки равна Δ11 = 7.
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ12 = 4.
Оценка свободной клетки равна Δ15 = 18.
Оценка свободной клетки равна Δ22 = 2.
Оценка свободной клетки равна Δ24 = 8.
Оценка свободной клетки равна Δ33 = 2.
Оценка свободной клетки равна Δ34 = 10.
В свободную клетку (3;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».