Некоторый однородный продукт, сосредоточенный у трех поставщиков А1, А2, А3 в количестве а1, а2, а3 тонн соответственно, необходимо доставить потребителям В1, В2, В3, В4, В5 в количестве b1, b2, b3, b4, b5 тонн. Стоимость Cij перевозки тонны груза от i-го поставщика j-му потребителю задана матрицей D. Составить план перевозок, имеющий минимальную стоимость и позволяющий вывести все грузы и полностью удовлетворить потребности.
ai
bi
150 50 200 150 150
100 2 10 8 8 5
250 9 17 15 14 11
350 10 20 15 20 13
Решение
Результат решения в ТП Excel:
Подготовим таблицу и заполним ее исходными данными: Стоимости перевозки тонны продукта (D), Ресурсы (а) и Потребности (b);
с помощью функции СУММ найдем суммы ресурсов (ячейка D12) и потребностей (G14);
подготовим таблицу оптимальных перевозок. Диапазон G09:G21 заполним начальными значениями — нулями;
с помощью функции СУММ найдем суммы перевозок по потребителям (C22:G22) и поставщиками (Н19:Н21);
в ячейку H16 ввести выражение стоимости оптимального плана перевозок;
Запустим инструментальное средство Поиск решения (меню Сервис/Поиск Решения) и введем необходимые параметры: адрес целевой ячейки, изменяемые ячейки и ограничения.
В результате было получено решение:
Т.е. имеем:
Первый поставщик перевозит по 50 тонн второму и четвертому потребителям;
Второй поставщик перевозит 100 тонн четвертому потребителю и 150 тонн пятому;
Третий поставщик перевозит 150 тонн первому потребителю и 200 тонн третьему потребителю.
Стоимость перевозки при этом составит 8450 ден.ед.
Исходный опорный план методом наименьшей стоимости
Данная транспортная задача является закрытой т.к. запасы равны потребностям 100+250+350=150+50+200+150+150=700
Найдем исходный опорный план, методом наименьшей стоимости. Наименьшая стоимость равна 2 – выбираем для нее минимальное число из ресурса и потребности данной ячейки min(100, 150)=100
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9 17 15 14 11 250
350 10 20 15 20 13 350
остаток 50 50 200 150 150
Далее наименьшая стоимость равна 8, но для данной цены уже нет ресурсов. Следующая цена 9 – выбираем для нее минимальное число из ресурса и остатков потребности данной ячейки min(100, 150)=100
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9
50 17 15 14 11 200
350 10 20 15 20 13 350
остаток 0 50 200 150 150
Следующая цена 11
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9
50 17 15 14 11
150 50
350 10 20 15 20 13 350
остаток 0 50 200 150 0
Следующая цена 14
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9
50 17 15 14
50 11
150 0
350 10 20 15 20 13 350
остаток 0 50 200 100 0
Следующая цена 15
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9
50 17 15 14
50 11
150 0
350 10 20 15
200 20 13 150
остаток 0 50 0 100 0
Следующая цена 20:
ai
bi остаток
150 50 200 150 150
100 2
100 10 8 8 5 0
250 9
50 17 15 14
50 11
150 0
350 10 20
50 15
200 20
100 13 0
остаток 0 0 0 0 0
В результате получили опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7
. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x)=2*100+9*50+14*50+11*150+20*50+15*200+20*100=9000
Последовательность шагов нахождения оптимального плана методом потенциала.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 2; 0 + v1 = 2; v1 = 2u2 + v1 = 9; 2 + u2 = 9; u2 = 7
u2 + v4 = 14; 7 + v4 = 14; v4 = 7u3 + v4 = 20; 7 + u3 = 20; u3 = 13
u3 + v2 = 20; 13 + v2 = 20; v2 = 7u3 + v3 = 15; 13 + v3 = 15; v3 = 2
u2 + v5 = 11; 7 + v5 = 11; v5 = 4
v1=2 v2=7 v3=2 v4=7 v5=4
u1=0 2 [100] 10 8 8 5
u2=7 9 [50] 17 15 14 [50] 11 [150]
u3=13 10 20 [50] 15 [200] 20 [100] 13
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 13 + 2 > 10; ∆31 = 13 + 2 - 10 = 5 > 0
(3;5): 13 + 4 > 13; ∆35 = 13 + 4 - 13 = 4 > 0max(5,4) = 5
Выбираем максимальную оценку свободной клетки (3;1): 10
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 2[100] 10 8 8 5 100
2 9[50][-] 17 15 14[50][+] 11[150] 250
3 10[+] 20[50] 15[200] 20[100][-] 13 350
Потребности 150 50 200 150 150
Цикл приведен в таблице (3,1 → 3,4 → 2,4 → 2,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 B5 Запасы
A1 2[100] 10 8 8 5 100
A2 9 17 15 14[100] 11[150] 250
A3 10[50] 20[50] 15[200] 20[50] 13 350
Потребности 150 50 200 150 150
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 2; 0 + v1 = 2; v1 = 2u3 + v1 = 10; 2 + u3 = 10; u3 = 8u3 + v2 = 20; 8 + v2 = 20; v2 = 12u3 + v3 = 15; 8 + v3 = 15; v3 = 7u3 + v4 = 20; 8 + v4 = 20; v4 = 12u2 + v4 = 14; 12 + u2 = 14; u2 = 2u2 + v5 = 11; 2 + v5 = 11; v5 = 9
v1=2 v2=12 v3=7 v4=12 v5=9
u1=0 2[100] 10 8 8 5
u2=2 9 17 15 14[100] 11[150]
u3=8 10[50] 20[50] 15[200] 20[50] 13
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 12 > 10; ∆12 = 0 + 12 - 10 = 2 > 0
(1;4): 0 + 12 > 8; ∆14 = 0 + 12 - 8 = 4 > 0
(1;5): 0 + 9 > 5; ∆15 = 0 + 9 - 5 = 4 > 0
(3;5): 8 + 9 > 13; ∆35 = 8 + 9 - 13 = 4 > 0max(2,4,4,4) = 4
Выбираем максимальную оценку свободной клетки (1;4): 8
Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 2[100][-] 10 8 8[+] 5 100
2 9 17 15 14[100] 11[150] 250
3 10[50][+] 20[50] 15[200] 20[50][-] 13 350
Потребности 150 50 200 150 150
Цикл приведен в таблице (1,4 → 1,1 → 3,1 → 3,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
