В клетках таблицы даны тарифы перевозок единицы груза из пункта в пункт .
Требуется составить план, обеспечивающий минимальные суммарные затраты на перевозку товаров при следующих ограничениях:
если спрос превосходит предложение, то полностью удовлетворить потребности пункта ; если же предложение превосходит спрос, то исчерпать полностью запасы пункта ;
заблокировать перевозки из в .
10.
Решение
B1 B2 B3 B4 B5 Запасы
A1 21 17 12 24 30 18
A2 6 1 9 90 9 18
A3 7 5 24 6 13 18
A4 29 22 21 5 7 18
Потребности 15 15 15 15 15
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 18 + 18 + 18 + 18 = 72 ∑b = 15 + 15 + 15 + 15 + 15 = 75 Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 3 (72—75). Тарифы перевозки единицы груза из базы ко всем потребителям полагаем равны нулю. Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 Запасы
A1 21 17 12 24 30 18
A2 6 1 9 90 9 18
A3 7 5 24 6 13 18
A4 29 22 21 5 7 18
A5 0 0 0 0 0 3
Потребности 15 15 15 15 15
Поиск первого опорного плана. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 21 17 12[15] 24 30[3] 18
A2 6[3] 1[15] 9 90 9 18
A3 7[12] 5 24 6 13[6] 18
A4 29 22 21 5[15] 7[3] 18
A5 0 0 0 0 0[3] 3
Потребности 15 15 15 15 15
Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 12*15 + 30*3 + 6*3 + 1*15 + 7*12 + 13*6 + 5*15 + 7*3 + 0*3 = 561 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 12; 0 + v3 = 12; v3 = 12 u1 + v5 = 30; 0 + v5 = 30; v5 = 30 u3 + v5 = 13; 30 + u3 = 13; u3 = -17 u3 + v1 = 7; -17 + v1 = 7; v1 = 24 u2 + v1 = 6; 24 + u2 = 6; u2 = -18 u2 + v2 = 1; -18 + v2 = 1; v2 = 19 u4 + v5 = 7; 30 + u4 = 7; u4 = -23 u4 + v4 = 5; -23 + v4 = 5; v4 = 28 u5 + v5 = 0; 30 + u5 = 0; u5 = -30
v1=24 v2=19 v3=12 v4=28 v5=30
u1=0 21 17 12[15] 24 30[3]
u2=-18 6[3] 1[15] 9 90 9
u3=-17 7[12] 5 24 6 13[6]
u4=-23 29 22 21 5[15] 7[3]
u5=-30 0 0 0 0 0[3]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (1;1): 0 + 24 > 21; ∆11 = 0 + 24 - 21 = 3 > 0 (1;2): 0 + 19 > 17; ∆12 = 0 + 19 - 17 = 2 > 0 (1;4): 0 + 28 > 24; ∆14 = 0 + 28 - 24 = 4 > 0 (2;5): -18 + 30 > 9; ∆25 = -18 + 30 - 9 = 3 > 0 (3;4): -17 + 28 > 6; ∆34 = -17 + 28 - 6 = 5 > 0 max(3,2,4,3,5) = 5 Выбираем максимальную оценку свободной клетки (3;4): 6 Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 21 17 12[15] 24 30[3] 18
2 6[3] 1[15] 9 90 9 18
3 7[12] 5 24 6[+] 13[6][-] 18
4 29 22 21 5[15][-] 7[3][+] 18
5 0 0 0 0 0[3] 3
Потребности 15 15 15 15 15
Цикл приведен в таблице (3,4 → 3,5 → 4,5 → 4,4). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
. у = min (3, 5) = 6. Прибавляем 6 к объемам грузов, стоящих в плюсовых клетках и вычитаем 6 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 B5 Запасы
A1 21 17 12[15] 24 30[3] 18
A2 6[3] 1[15] 9 90 9 18
A3 7[12] 5 24 6[6] 13 18
A4 29 22 21 5[9] 7[9] 18
A5 0 0 0 0 0[3] 3
Потребности 15 15 15 15 15
Проверим оптимальность опорного плана
Задать вопрос
на новый заказ в Автор24.
