Автор: Пользователь скрыл имя, 11 Марта 2013 в 11:59, курсовая работа
Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Проверим необходимое
и достаточное условие
∑a = 70 + 65 + 90 = 225
∑b = 50 + 65 + 65 + 15 + 30 = 225
50 |
65 |
65 |
15 |
30 | |
70 |
20 |
21 |
22[55] |
23[15] |
24 |
65 |
22[35] |
28 |
31 |
40 |
15[30] |
90 |
23[15] |
27[65] |
34[10] |
43 |
18 |
Сведем все вычисления в одну таблицу.
50 |
65 |
65 |
15 |
30 |
d1 |
d2 |
d3 |
d4 |
d5 | |
|
70 |
20 |
21 |
22[55] |
23[15] |
24 |
1 |
1 |
- |
- |
- |
65 |
22[35] |
28 |
31 |
40 |
15[30] |
7 |
7 |
7 |
6 |
- |
90 |
23[15] |
27[65] |
34[10] |
43 |
18 |
5 |
5 |
5 |
4 |
4 |
d1 |
2 |
6 |
9 |
17 |
3 |
|
|
|
|
|
d2 |
2 |
6 |
9 |
- |
3 |
|
|
|
|
|
d3 |
1 |
1 |
3 |
- |
3 |
|
|
|
|
|
d4 |
1 |
1 |
3 |
- |
- |
|
|
|
|
|
d5 |
0 |
0 |
0 |
- |
- |
|
|
|
|
|
В результате получен первый
опорный план, который является допустимым,
так как все грузы из баз
вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
2) Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=11 |
v2=15 |
v3=22 |
v4=23 |
v5=4 | |
u1=0 |
20 |
21 |
22[55] |
23[15] |
24 |
u2=11 |
22[35] |
28 |
31 |
40 |
15[30] |
u3=12 |
23[15] |
27[65] |
34[10] |
43 |
18 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (2;3): 31
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
50 |
65 |
65 |
15 |
30 | |
70 |
20 |
21 |
22[55] |
23[15] |
24 |
65 |
22[35] [-] |
28 |
31 [+] |
40 |
15[30] |
90 |
23[15] [+] |
27[65] |
34[10] [-] |
43 |
18 |
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х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 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=13 |
v2=17 |
v3=22 |
v4=23 |
v5=6 | |
u1=0 |
20 |
21 |
22[55] |
23[15] |
24 |
u2=9 |
22[25] |
28 |
31[10] |
40 |
15[30] |
u3=10 |
23[25] |
27[65] |
34 |
43 |
18 |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195.
ПОСТАНОВКА ЗАДАЧИ
Дано 3 поставщика:
, , Предложение
поставщика составляет 70 единиц,
i=1; поставщика составляет 65 единиц,
i=2; поставщика составляет 90 единиц,
i=3.
Дано 5 потребителей:
, , , , .Спрос потребителя составляет 50 единиц, j=1; потребителя составляет 65 единиц, j=2;потребителя составляет 65 единиц, j=3; потребителя составляет 55 единиц, j=4; потребителя составляет 30 единиц, j=5.
Дана стоимость перевозки:
единицы товара от 1 поставщика к 1 потребителю =20;
единицы товара от 1 поставщика к 2 потребителю =21;
единицы товара от 1 поставщика к 3 потребителю =22;
единицы товара от 1 поставщика к 4 потребителю =23;
единицы товара от 1 поставщика к 5 потребителю =24;
единицы товара от 2 поставщика к 1 потребителю =22;
единицы товара от 2 поставщика к 2 потребителю =28;
единицы товара от 2 поставщика к 3 потребителю =31;
единицы товара от 2 поставщика к 4 потребителю =40;
единицы товара от 2 поставщика к 5 потребителю =15;
единицы товара от 3 поставщика к 1 потребителю =23;
единицы товара от 3 поставщика к 2 потребителю =27;
единицы товара от 3 поставщика к 3 потребителю =34;
единицы товара от 3 поставщика к 4 потребителю =43;
единицы товара от 3 поставщика к 5 потребителю =18.
Требуется составить план
перевозок от каждого поставщика
к каждому потребителю с
Общая стоимость перевозок равна:
S==
Матрица транспортных расходов имеет вид:
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:
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[50] |
21[20] |
22 |
23 |
24 |
65 |
22 |
28[45] |
31[20] |
40 |
15 |
90 |
23 |
27 |
34[45] |
43[45] |
18 |
В результате получен первый
опорный план, который является допустимым,
так как все грузы из баз
вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Определяем оценку для каждой свободной клетки.
В свободную клетку (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[45] |
18 |
Оценка свободной клетки равна Δ13 = -2
Аналогично выполняем оценку для каждой свободной клетки:
Оценка свободной клетки равна Δ14 = -10
Оценка свободной клетки равна Δ15 = -9
Оценка свободной клетки равна Δ21 = -5
Оценка свободной клетки равна Δ24 = 0
Оценка свободной клетки равна Δ25 = -25
Оценка свободной клетки равна Δ31 = -7
Оценка свободной клетки равна Δ32 = -4
Оценка свободной клетки равна Δ35 = -25
Оценка свободной клетки равна Δ41 = 13
Оценка свободной клетки равна Δ42 = 12
Оценка свободной клетки равна Δ43 = 9.
Опорный план является неоптимальным, поскольку имеются отрицательны оценки клеток равные: (-25).
Поскольку имеются оценки клеток с одинаковыми по величине значениями, то для перехода к лучшему плану практически может быть занята любая клетка из этих двух.
Однако, если придерживаться принципа достижения наибольшего снижения целевой функции за один очередной переход, то в данном случае надо проанализировать, каково будет это общее снижение при занятии поставкой каждой клетки.