Решите транспортную задачу линейного программирования
.pdf
Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥
Решите транспортную задачу линейного программирования
Имеются три пункта поставки однородного груза А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=550b=100+180+40+120+110=550a=b.
Суммарная потребность груза равна запасам груза у поставщиков. Следовательно, задача является закрытой.
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке A2B1 и равен 4. Запасы поставщика A2 составляют 200 ед. Потребность потребителя B1 составляет 100 ед. От поставщика A2 к потребителю B1 будем доставлять 100 ед.Мы полностью исчерпали потребности потребителя B1. Вычеркиваем столбец 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.
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
. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 8*110 + 5*40 + 4*100 + 12*70 + 10*30 + 4*120 + 5*80 = 3500 Найдем оптимальное решение( метод потенциалов) Проверим оптимальность опорного плана
. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
v1=0 v2=8 v3=5 v4=5 v5=6 Запасы
u1=0 15 8[110][+] 5[40][-] 21 15 150
u2=4 4[100] 12[70][-] 7[+] 8 10[30] 200
u3=-1 11 20 13 4[120] 5[80] 200
Потребности 100 180 40 120 110
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (2;3): 4 + 5 > 7; ∆23 = 4 + 5 - 7 = 2 > 0 (2;4): 4 + 5 > 8; ∆24 = 4 + 5 - 8 = 1 > 0 max(2,1) = 2 Выбираем максимальную оценку свободной клетки (2;3): 7 Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,3 → 2,2 → 1,2 → 1,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е