Примеры решений Метод Гомори Симплекс-метод Метод Фогеля Транспортная задача Задача о назначениях Распределительный метод Метод потенциалов Задача коммивояжера Открытые и закрытые задачи

Решение транспортной задачи методом северо-западного угла

Имеются три пункта отправления А1, А2, А3 однородного груза и пять пунктов В1, В2, В3, В4, В5 его назначения. На пунктах А1, А2, А3 груз находится в количестве а1, а2, а3 тонн соответственно. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Расстояние в сотнях километров между пунктами отправления и назначения приведены в матрице D.
Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными. Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах; 2) для решения задачи использовать методы северо-западного угла и потенциалов.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов. Требуется найти оптимальный план перевозок.

1 2 3 4 5 6 Запасы
1 6 6 8 5 4 3 130
2 2 4 3 9 8 5 55
3 3 5 7 9 6 11 80
4 3 5 4 4 2 1 65
5 2 5 6 3 2 8 135
Потребности 130 75 65 60 75 60

Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 130 + 55 + 80 + 65 + 135 = 465
∑ b = 130 + 75 + 65 + 60 + 75 + 60 = 465
Условие баланса соблюдается. Запасы равны потребностям.
Занесем исходные данные в распределительную таблицу.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4 3 130
2 2 4 3 9 8 5 55
3 3 5 7 9 6 11 80
4 3 5 4 4 2 1 65
5 2 5 6 3 2 8 135
Потребности 130 75 65 60 75 60

1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

1 2 3 4 5 6 Запасы
1 6[130] 6 8 5 4 3 130
2 2 4[55] 3 9 8 5 55
3 3 5[20] 7[60] 9 6 11 80
4 3 5 4[5] 4[60] 2 1 65
5 2 5 6 3 2[75] 8[60] 135
Потребности 130 75 65 60 75 60

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
1 2 3 4 5 6 Запасы
1 6[55] 6[75] 8 5 4 3 130
2 2[55] 4 3 9 8 5 55
3 3[20] 5 7[60] 9 6 11 80
4 3 5 4[5] 4[60] 2 1 65
5 2 5 6 3 2[75] 8[60] 135
Потребности 130 75 65 60 75 60

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
1 2 3 4 5 6 Запасы
1 6[65] 6 8[65] 5 4 3 130
2 2[55] 4 3 9 8 5 55
3 3[10] 5[70] 7 9 6 11 80
4 3 5[5] 4 4[60] 2 1 65
5 2 5 6 3 2[75] 8[60] 135
Потребности 130 75 65 60 75 60

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
1 2 3 4 5 6 Запасы
1 6[70] 6 8 5[60] 4 3 130
2 2[55] 4 3 9 8 5 55
3 3[5] 5[75] 7 9 6 11 80
4 3 5 4[65] 4 2 1 65
5 2 5 6 3 2[75] 8[60] 135
Потребности 130 75 65 60 75 60

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план.
1 2 3 4 5 6 Запасы
1 6[55] 6 8 5 4[75] 3 130
2 2[55] 4 3 9 8 5 55
3 3[20] 5[60] 7 9 6 11 80
4 3 5[15] 4[50] 4 2 1 65
5 2 5 6[15] 3[60] 2 8[60] 135
Потребности 130 75 65 60 75 60

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 6; 0 + v1 = 6; v1 = 6
u2 + v1 = 2; 6 + u2 = 2; u2 = -4
u3 + v1 = 3; 6 + u3 = 3; u3 = -3
u3 + v2 = 5; -3 + v2 = 5; v2 = 8
u4 + v2 = 5; 8 + u4 = 5; u4 = -3
u4 + v3 = 4; -3 + v3 = 4; v3 = 7
u5 + v3 = 6; 7 + u5 = 6; u5 = -1
u5 + v4 = 3; -1 + v4 = 3; v4 = 4
u5 + v6 = 8; -1 + v6 = 8; v6 = 9
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
v1=6 v2=8 v3=7 v4=4 v5=4 v6=9
u1=0 6[55] 6 8 5 4[75] 3
u2=-4 2[55] 4 3 9 8 5
u3=-3 3[20] 5[60] 7 9 6 11
u4=-3 3 5[15] 4[50] 4 2 1
u5=-1 2 5 6[15] 3[60] 2 8[60]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 8 > 6; ∆12 = 0 + 8 - 6 = 2
(1;6): 0 + 9 > 3; ∆16 = 0 + 9 - 3 = 6
(4;6): -3 + 9 > 1; ∆46 = -3 + 9 - 1 = 5
(5;1): -1 + 6 > 2; ∆51 = -1 + 6 - 2 = 3
(5;2): -1 + 8 > 5; ∆52 = -1 + 8 - 5 = 2
(5;5): -1 + 4 > 2; ∆55 = -1 + 4 - 2 = 1
Выбираем максимальную оценку свободной клетки (1;6): 3
Для этого в перспективную клетку (1;6) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6[55][-] 6 8 5 4[75] 3[+] 130
2 2[55] 4 3 9 8 5 55
3 3[20][+] 5[60][-] 7 9 6 11 80
4 3 5[15][+] 4[50][-] 4 2 1 65
5 2 5 6[15][+] 3[60] 2 8[60][-] 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6[5] 6 8 5 4[75] 3[50] 130
2 2[55] 4 3 9 8 5 55
3 3[70] 5[10] 7 9 6 11 80
4 3 5[65] 4 4 2 1 65
5 2 5 6[65] 3[60] 2 8[10] 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 6; 0 + v1 = 6; v1 = 6
u2 + v1 = 2; 6 + u2 = 2; u2 = -4
u3 + v1 = 3; 6 + u3 = 3; u3 = -3
u3 + v2 = 5; -3 + v2 = 5; v2 = 8
u4 + v2 = 5; 8 + u4 = 5; u4 = -3
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
u5 + v6 = 8; 3 + u5 = 8; u5 = 5
u5 + v3 = 6; 5 + v3 = 6; v3 = 1
u5 + v4 = 3; 5 + v4 = 3; v4 = -2
v1=6 v2=8 v3=1 v4=-2 v5=4 v6=3
u1=0 6[5] 6 8 5 4[75] 3[50]
u2=-4 2[55] 4 3 9 8 5
u3=-3 3[70] 5[10] 7 9 6 11
u4=-3 3 5[65] 4 4 2 1
u5=5 2 5 6[65] 3[60] 2 8[10]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 8 > 6; ∆12 = 0 + 8 - 6 = 2
(5;1): 5 + 6 > 2; ∆51 = 5 + 6 - 2 = 9
(5;2): 5 + 8 > 5; ∆52 = 5 + 8 - 5 = 8
(5;5): 5 + 4 > 2; ∆55 = 5 + 4 - 2 = 7
Выбираем максимальную оценку свободной клетки (5;1): 2
Для этого в перспективную клетку (5;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6[5][-] 6 8 5 4[75] 3[50][+] 130
2 2[55] 4 3 9 8 5 55
3 3[70] 5[10] 7 9 6 11 80
4 3 5[65] 4 4 2 1 65
5 2[+] 5 6[65] 3[60] 2 8[10][-] 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[75] 3[55] 130
2 2[55] 4 3 9 8 5 55
3 3[70] 5[10] 7 9 6 11 80
4 3 5[65] 4 4 2 1 65
5 2[5] 5 6[65] 3[60] 2 8[5] 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
u5 + v6 = 8; 3 + u5 = 8; u5 = 5
u5 + v1 = 2; 5 + v1 = 2; v1 = -3
u2 + v1 = 2; -3 + u2 = 2; u2 = 5
u3 + v1 = 3; -3 + u3 = 3; u3 = 6
u3 + v2 = 5; 6 + v2 = 5; v2 = -1
u4 + v2 = 5; -1 + u4 = 5; u4 = 6
u5 + v3 = 6; 5 + v3 = 6; v3 = 1
u5 + v4 = 3; 5 + v4 = 3; v4 = -2
v1=-3 v2=-1 v3=1 v4=-2 v5=4 v6=3
u1=0 6 6 8 5 4[75] 3[55]
u2=5 2[55] 4 3 9 8 5
u3=6 3[70] 5[10] 7 9 6 11
u4=6 3 5[65] 4 4 2 1
u5=5 2[5] 5 6[65] 3[60] 2 8[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 5 + 1 > 3; ∆23 = 5 + 1 - 3 = 3
(2;5): 5 + 4 > 8; ∆25 = 5 + 4 - 8 = 1
(2;6): 5 + 3 > 5; ∆26 = 5 + 3 - 5 = 3
(3;5): 6 + 4 > 6; ∆35 = 6 + 4 - 6 = 4
(4;3): 6 + 1 > 4; ∆43 = 6 + 1 - 4 = 3
(4;5): 6 + 4 > 2; ∆45 = 6 + 4 - 2 = 8
(4;6): 6 + 3 > 1; ∆46 = 6 + 3 - 1 = 8
(5;5): 5 + 4 > 2; ∆55 = 5 + 4 - 2 = 7
Выбираем максимальную оценку свободной клетки (4;5): 2
Для этого в перспективную клетку (4;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[75][-] 3[55][+] 130
2 2[55] 4 3 9 8 5 55
3 3[70][-] 5[10][+] 7 9 6 11 80
4 3 5[65][-] 4 4 2[+] 1 65
5 2[5][+] 5 6[65] 3[60] 2 8[5][-] 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 6) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[70] 3[60] 130
2 2[55] 4 3 9 8 5 55
3 3[65] 5[15] 7 9 6 11 80
4 3 5[60] 4 4 2[5] 1 65
5 2[10] 5 6[65] 3[60] 2 8 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u2 + v1 = 2; 5 + u2 = 2; u2 = -3
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v3 = 6; -3 + v3 = 6; v3 = 9
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
v1=5 v2=7 v3=9 v4=6 v5=4 v6=3
u1=0 6 6 8 5 4[70] 3[60]
u2=-3 2[55] 4 3 9 8 5
u3=-2 3[65] 5[15] 7 9 6 11
u4=-2 3 5[60] 4 4 2[5] 1
u5=-3 2[10] 5 6[65] 3[60] 2 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;3): 0 + 9 > 8; ∆13 = 0 + 9 - 8 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
(2;3): -3 + 9 > 3; ∆23 = -3 + 9 - 3 = 3
(4;3): -2 + 9 > 4; ∆43 = -2 + 9 - 4 = 3
Выбираем максимальную оценку свободной клетки (2;3): 3
Для этого в перспективную клетку (2;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[70] 3[60] 130
2 2[55][-] 4 3[+] 9 8 5 55
3 3[65] 5[15] 7 9 6 11 80
4 3 5[60] 4 4 2[5] 1 65
5 2[10][+] 5 6[65][-] 3[60] 2 8 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 55. Прибавляем 55 к объемам грузов, стоящих в плюсовых клетках и вычитаем 55 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[70] 3[60] 130
2 2 4 3[55] 9 8 5 55
3 3[65] 5[15] 7 9 6 11 80
4 3 5[60] 4 4 2[5] 1 65
5 2[65] 5 6[10] 3[60] 2 8 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v3 = 6; -3 + v3 = 6; v3 = 9
u2 + v3 = 3; 9 + u2 = 3; u2 = -6
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
v1=5 v2=7 v3=9 v4=6 v5=4 v6=3
u1=0 6 6 8 5 4[70] 3[60]
u2=-6 2 4 3[55] 9 8 5
u3=-2 3[65] 5[15] 7 9 6 11
u4=-2 3 5[60] 4 4 2[5] 1
u5=-3 2[65] 5 6[10] 3[60] 2 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;3): 0 + 9 > 8; ∆13 = 0 + 9 - 8 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
(4;3): -2 + 9 > 4; ∆43 = -2 + 9 - 4 = 3
Выбираем максимальную оценку свободной клетки (4;3): 4
Для этого в перспективную клетку (4;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[70] 3[60] 130
2 2 4 3[55] 9 8 5 55
3 3[65][-] 5[15][+] 7 9 6 11 80
4 3 5[60][-] 4[+] 4 2[5] 1 65
5 2[65][+] 5 6[10][-] 3[60] 2 8 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4[70] 3[60] 130
2 2 4 3[55] 9 8 5 55
3 3[55] 5[25] 7 9 6 11 80
4 3 5[50] 4[10] 4 2[5] 1 65
5 2[75] 5 6 3[60] 2 8 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v2 = 5; -2 + v2 = 5; v2 = 7
u3 + v2 = 5; 7 + u3 = 5; u3 = -2
u3 + v1 = 3; -2 + v1 = 3; v1 = 5
u5 + v1 = 2; 5 + u5 = 2; u5 = -3
u5 + v4 = 3; -3 + v4 = 3; v4 = 6
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u2 + v3 = 3; 6 + u2 = 3; u2 = -3
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
v1=5 v2=7 v3=6 v4=6 v5=4 v6=3
u1=0 6 6 8 5 4[70] 3[60]
u2=-3 2 4 3[55] 9 8 5
u3=-2 3[55] 5[25] 7 9 6 11
u4=-2 3 5[50] 4[10] 4 2[5] 1
u5=-3 2[75] 5 6 3[60] 2 8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 7 > 6; ∆12 = 0 + 7 - 6 = 1
(1;4): 0 + 6 > 5; ∆14 = 0 + 6 - 5 = 1
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
1 2 3 4 5 6 Запасы
1 6 6[+] 8 5 4[70][-] 3[60] 130
2 2 4 3[55] 9 8 5 55
3 3[55] 5[25] 7 9 6 11 80
4 3 5[50][-] 4[10] 4 2[5][+] 1 65
5 2[75] 5 6 3[60] 2 8 135
Потребности 130 75 65 60 75 60

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 2 3 4 5 6 Запасы
1 6 6[50] 8 5 4[20] 3[60] 130
2 2 4 3[55] 9 8 5 55
3 3[55] 5[25] 7 9 6 11 80
4 3 5 4[10] 4 2[55] 1 65
5 2[75] 5 6 3[60] 2 8 135
Потребности 130 75 65 60 75 60

4. Проверим оптимальность опорного плана. Найдем потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 6; 0 + v2 = 6; v2 = 6
u3 + v2 = 5; 6 + u3 = 5; u3 = -1
u3 + v1 = 3; -1 + v1 = 3; v1 = 4
u5 + v1 = 2; 4 + u5 = 2; u5 = -2
u5 + v4 = 3; -2 + v4 = 3; v4 = 5
u1 + v5 = 4; 0 + v5 = 4; v5 = 4
u4 + v5 = 2; 4 + u4 = 2; u4 = -2
u4 + v3 = 4; -2 + v3 = 4; v3 = 6
u2 + v3 = 3; 6 + u2 = 3; u2 = -3
u1 + v6 = 3; 0 + v6 = 3; v6 = 3
v1=4 v2=6 v3=6 v4=5 v5=4 v6=3
u1=0 6 6[50] 8 5 4[20] 3[60]
u2=-3 2 4 3[55] 9 8 5
u3=-1 3[55] 5[25] 7 9 6 11
u4=-2 3 5 4[10] 4 2[55] 1
u5=-2 2[75] 5 6 3[60] 2 8

Опорный план является оптимальным.
Затраты составят:
F(x) = 6*50 + 4*20 + 3*60 + 3*55 + 3*55 + 5*25 + 4*10 + 2*55 + 2*75 + 3*60  = 1495

Скачать в формате doc

Пример №2. Из трех пунктов хранения (или производства) требуется доставить однородный груз в пять пунктов потребления. Количество груза N в каждом пункте отправления, объемы потребления M, а также стоимости C перевозки единицы груза из пункта отправления A в пункт потребления B указаны в таблице.
Составить такой план перевозок, при котором общая стоимость была бы минимальной.
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов.
1 2 3 4 5 6 Запасы
1 6 6 8 5 4 3 130
2 2 4 3 - 8 5 55
3 3 5 7 - 6 11 80
4 3 5 4 4 2 1 65
5 2 5 6 3 2 8 135
Потребности 130 75 65 60 75 60

Решение получаем с помощью калькулятора. Максимальная стоимость в данной матрице тарифов равна 11. Поэтому вместо прочерков достаточно указать значение в 2 раза больше заданного. Например, 22 (2*11).

1 2 3 4 5 6 Запасы
1 6 6 8 5 4 3 130
2 2 4 3 22 8 5 55
3 3 5 7 22 6 11 80
4 3 5 4 4 2 1 65
5 2 5 6 3 2 8 135
Потребности 130 75 65 60 75 60

Пример №3.

Решение задачи методом северо–западного угла и потенциалов

Имеются три пункта отправления A 1 , A2, A 3 однородного груза  и пять пунктов B1,B2,B3,B4,B5 его назначения. На пунктах A1,A2, A3 груз находится в количестве a1, a2, a3 тонн соответственно. В пункты B1,B2,B3,B4,B5 требуется доставить соответственно b1,b2,b3,b4,b5 тонн груза. Расстояния в сотнях километров между пунктами отправления и назначения приведены в матрице D:
Пункты отправления Пункты назначения
B1 B2 B3 B4 B5
A1 d11 d12 d13 d14 d15
A2 d21 d22 d23 d24 d25
A3 d31 d32 d33 d34 d35


Найти такой план перевозок, при котором общие затраты на перевозку грузов будут минимальными.
Указания: 1) считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно–километрах; 2) для решения задачи использовать методы северо–западного угла и потенциалов.

Перейти к онлайн решению своей задачи

Метод Гомори
Метод Гомори
Метод Гомори. Решение задачи целочисленного программирования
Решить онлайн
Линейное программирование
Решение ЗЛП графическим методомГрафический метод решения ЗЛП
Решить онлайн
Курсовые на заказ