О Расшивке узких мест производства. Задача сводиться к нахождению объемов приобретения дополнительных ресурсов

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
B1 B2 B3 B4 Запасы
A1 4 2 2 6 50
A2 5 3 2 7 42
A3 1 4 3 2 42
Потребности 28 44 31 20
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 50 + 42 + 42 = 134∑b = 28 + 44 + 31 + 20 = 123
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 11 (134-123). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 Запасы
A1 4 2 2 6 0 50
A2 5 3 2 7 0 42
A3 1 4 3 2 0 42
Потребности 28 44 31 20 11
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Отыскиваемый элемент равен c31=1. Для этого элемента запасы равны 42, потребности 28. Т.к. минимальным является 28, то вычитаем его.x31 = min(42,28) = 28.
x 2 2 6 0 50
x 3 2 7 0 42
1 4 3 2 0 42 - 28 = 14
28 - 28 = 0 44 31 20 11
Отыскиваемый элемент равен c12=2. Для этого элемента запасы равны 50, потребности 44. Т.к. минимальным является 44, то вычитаем его.x12 = min(50,44) = 44.
x 2 2 6 0 50 - 44 = 6
x x 2 7 0 42
1 x 3 2 0 14
0 44 - 44 = 0 31 20 11
Отыскиваемый элемент равен c13=2. Для этого элемента запасы равны 6, потребности 31. Т.к. минимальным является 6, то вычитаем его.x13 = min(6,31) = 6.
x 2 2 x x 6 - 6 = 0
x x 2 7 0 42
1 x 3 2 0 14
0 0 31 - 6 = 25 20 11
Отыскиваемый элемент равен c23=2. Для этого элемента запасы равны 42, потребности 25 . Т.к. минимальным является 25, то вычитаем его.x23 = min(42,25) = 25.
x 2 2 x x 0
x x 2 7 0 42 - 25 = 17
1 x x 2 0 14
0 0 25 - 25 = 0 20 11
Отыскиваемый элемент равен c34=2. Для этого элемента запасы равны 14, потребности 20. Т.к. минимальным является 14, то вычитаем его.x34 = min(14,20) = 14.
x 2 2 x x 0
x x 2 7 0 17
1 x x 2 x 14 - 14 = 0
0 0 0 20 - 14 = 6 11
Отыскиваемый элемент равен c24=7. Для этого элемента запасы равны 17, потребности 6. Т.к. минимальным является 6, то вычитаем его.x24 = min(17,6) = 6.
x 2 2 x x 0
x x 2 7 0 17 - 6 = 11
1 x x 2 x 0
0 0 0 6 - 6 = 0 11
Отыскиваемый элемент равен c25=0. Для этого элемента запасы равны 11, потребности 11. Т.к. минимальным является 11, то вычитаем его.x25 = min(11,11) = 11.
x 2 2 x x 0
x x 2 7 0 11 - 11 = 0
1 x x 2 x 0
0 0 0 0 11 - 11 = 0
B1 B2 B3 B4 B5 Запасы
A1 4 2[44] 2[6] 6 0 50
A2 5 3 2[25] 7[6] 0[11] 42
A3 1[28] 4 3 2[14] 0 42
Потребности 28 44 31 20 11
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2∙44 + 2∙6 + 2∙25 + 7∙6 + 0∙11 + 1∙28 + 2∙14 = 248
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 2; 0 + v2 = 2; v2 = 2u1 + v3 = 2; 0 + v3 = 2; v3 = 2u2 + v3 = 2; 2 + u2 = 2; u2 = 0u2 + v4 = 7; 0 + v4 = 7; v4 = 7u3 + v4 = 2; 7 + u3 = 2; u3 = -5u3 + v1 = 1; -5 + v1 = 1; v1 = 6u2 + v5 = 0; 0 + v5 = 0; v5 = 0
v1=6 v2=2 v3=2 v4=7 v5=0
u1=0 4 2[44] 2[6] 6 0
u2=0 5 3 2[25] 7[6] 0[11]
u3=-5 1[28] 4 3 2[14] 0
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;1): 0 + 6 > 4; ∆11 = 0 + 6 - 4 = 2 > 0(1;4): 0 + 7 > 6; ∆14 = 0 + 7 - 6 = 1 > 0(2;1): 0 + 6 > 5; ∆21 = 0 + 6 - 5 = 1 > 0max(2,1,1) = 2Выбираем максимальную оценку свободной клетки (1;1): 4
Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 4[+] 2[44] 2[6][-] 6 0 50
2 5 3 2[25][+] 7[6][-] 0[11] 42
3 1[28][-] 4 3 2[14][+] 0 42
Потребности 28 44 31 20 11
Цикл приведен в таблице (1,1 → 1,3 → 2,3 → 2,4 → 3,4 → 3,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е