Решите транспортную задачу линейного программирования
Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов потребления этого груза В1, В2, В3, В4, В5. На пунктах поставки Аi, i = находится груз соответственно в количествах а1, а2 и а3 тонн. В пункты потребления Вj, j = требуется доставить соответственно b1, b2, b3, b4 и b5 тонн груза. Расходы на перевозку единицы груза между пунктами поставки и пунктами потребления приведены в таблице.
Найти такой план закрепления потребителей за поставщиками однородного груза хij, i = ; j = , чтобы общие затраты по перевозкам
Вj
Ai В1
В2
В3 В4
В5 Запасы
А1
15 8 5 21 15 150
А2
4 12 7 8 10 200
А3 11 20 13 4 5 200
Потребности 100 180 40 120 110 550
Решение
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 150 + 200 + 200 = 550∑b = 100 + 180 + 40 + 120 + 110 = 550
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Отыскиваемый элемент равен c21=4. Для этого элемента запасы равны 200, потребности 100. Т.к. минимальным является 100, то вычитаем его.x21 = min(200,100) = 100.
x 8 5 21 15 150
4 12 7 8 10 200 - 100 = 100
x 20 13 4 5 200
100 - 100 = 0 180 40 120 110
Отыскиваемый элемент равен c34=4. Для этого элемента запасы равны 200, потребности 120. Т.к. минимальным является 120, то вычитаем его.x34 = min(200,120) = 120.
x 8 5 x 15 150
4 12 7 x 10 100
x 20 13 4 5 200 - 120 = 80
0 180 40 120 - 120 = 0 110
Отыскиваемый элемент равен c13=5. Для этого элемента запасы равны 150, потребности 40. Т.к. минимальным является 40, то вычитаем его.x13 = min(150,40) = 40.
x 8 5 x 15 150 - 40 = 110
4 12 x x 10 100
x 20 x 4 5 80
0 180 40 - 40 = 0 0 110
Отыскиваемый элемент равен c35=5. Для этого элемента запасы равны 80, потребности 110. Т.к. минимальным является 80, то вычитаем его.x35 = min(80,110) = 80.
x 8 5 x 15 110
4 12 x x 10 100
x x x 4 5 80 - 80 = 0
0 180 0 0 110 - 80 = 30
Отыскиваемый элемент равен c12=8. Для этого элемента запасы равны 110, потребности 180. Т.к. минимальным является 110, то вычитаем его.x12 = min(110,180) = 110.
x 8 5 x x 110 - 110 = 0
4 12 x x 10 100
x x x 4 5 0
0 180 - 110 = 70 0 0 30
Отыскиваемый элемент равен c25=10
. Для этого элемента запасы равны 100, потребности 30. Т.к. минимальным является 30, то вычитаем его.x25 = min(100,30) = 30.
x 8 5 x x 0
4 12 x x 10 100 - 30 = 70
x x x 4 5 0
0 70 0 0 30 - 30 = 0
Отыскиваемый элемент равен c22=12. Для этого элемента запасы равны 70, потребности 70. Т.к. минимальным является 70, то вычитаем его.x22 = min(70,70) = 70.
x 8 5 x x 0
4 12 x x 10 70 - 70 = 0
x x x 4 5 0
0 70 - 70 = 0 0 0 0
В результате получен первый опорный план, который является допустимым, так как все грузы из складов вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 15 8[110] 5[40] 21 15 150
A2 4[100] 12[70] 7 8 10[30] 200
A3 11 20 13 4[120] 5[80] 200
Потребности 100 180 40 120 110
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 8; 0 + v2 = 8; v2 = 8u2 + v2 = 12; 8 + u2 = 12; u2 = 4u2 + v1 = 4; 4 + v1 = 4; v1 = 0u2 + v5 = 10; 4 + v5 = 10; v5 = 6u3 + v5 = 5; 6 + u3 = 5; u3 = -1u3 + v4 = 4; -1 + v4 = 4; v4 = 5u1 + v3 = 5; 0 + v3 = 5; v3 = 5
v1=0 v2=8 v3=5 v4=5 v5=6
u1=0 15 8[110] 5[40] 21 15
u2=4 4[100] 12[70] 7 8 10[30]
u3=-1 11 20 13 4[120] 5[80]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 4 + 5 > 7; ∆23 = 4 + 5 - 7 = 2 > 0(2;4): 4 + 5 > 8; ∆24 = 4 + 5 - 8 = 1 > 0max(2,1) = 2
Выбираем максимальную оценку свободной клетки (2;3): 7
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 15 8[110][+] 5[40][-] 21 15 150
2 4[100] 12[70][-] 7[+] 8 10[30] 200
3 11 20 13 4[120] 5[80] 200
Потребности 100 180 40 120 110
Цикл приведен в таблице (2,3 → 2,2 → 1,2 → 1,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
