Имеются 3 пункта поставки однородного груза А1, А2, А3 и 4 пункта потребления этого

Имеются 3 пункта поставки однородного груза А1, А2, А3 и 4 пункта потребления этого груза В1, В2, В3, В4. На пунктах А(I=1,2,3) груз находится соответственно в количествах а1, а2, а3 условных единиц. В пункты В (J=1,2,3,4) требуется доставить соответственно bj единиц груза.Стоимость перевозки единицы груза (с учетом расстояний) из А, в В указана в таблице. Найти оптимальный план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальными. Пункты назнач. B1 B2 B3 B4 Запасы Пункты Отправ. A1 7 11 16 11 340 A2 12 15 17 21 280 A3 11 12 19 13 360 Потребности 390 280 130 180

∑a = 340 + 280 + 360 = 980 ∑b = 390 + 280 + 130 + 180 = 980 Суммарная потребность груза равна запасам груза у поставщиков. Следовательно, задача является закрытой.
Поиск первого опорного плана. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. 
Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 7. Запасы поставщика A1 составляют 340 ед. Потребность потребителя B1 составляет 390 ед. От поставщика A1 к потребителю B1 будем доставлять 340 ед.
Мы полностью исчерпали запасы поставщика А1. Вычеркиваем строку 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжая аналогичным образом рассуждения получим опорное решение:
B1 B2 B3 B4 Запасы
A1 7[340] 11 16 11 340
A2 12 15 17[130] 21[150] 280
A3 11[50] 12[280] 19 13[30] 360
Потребности 390 280 130 180
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6

. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 7*340 + 17*130 + 21*150 + 11*50 + 12*280 + 13*30 = 12040 Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 
v1=7 v2=8 v3=5 v4=9 Запасы
u1=0 7[340] 11 16 11 340
u2=12 12[+] 15 17[130] 21[150][-] 280
u3=4 11[50][-] 12[280] 19 13[30][+] 360
Потребности 390 280 130 180
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+ vj > cij (2;1): 12 + 7 > 12; ∆21 = 12 + 7 - 12 = 7 > 0 (2;2): 12 + 8 > 15; ∆22 = 12 + 8 - 15 = 5 > 0 max(7,5) = 7 Выбираем максимальную оценку свободной клетки (2;1): 12 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 
Цикл приведен в таблице (2,1 → 2,4 → 3,4 → 3,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е