Автор работы: Пользователь скрыл имя, 24 Сентября 2013 в 12:10, курсовая работа
Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений 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] |
<span class="Text_0020body__Char" style=" fon |