Готовая транспортная задача по Методам оптимизации

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

    1    2    3    4    5    Запасы
1    20    5    27    10    26    15
2    7    17    18    21    28    25
3    27    21    9    23    26    5
4    1    13    17    23    7    15
Потребности    7    8    13    12    20    

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 15 + 25 + 5 + 15 = 60
∑b = 7 + 8 + 13 + 12 + 20 = 60
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

    1    2    3    4    5    Запасы
1    20    5    27    10    26    15
2    7    17    18    21    28    25
3    27    21    9    23    26    5
4    1    13    17    23    7    15
Потребности    7    8    13    12    20    

Используя метод северо-западного угла, построим первый опорный план транспортной задачи.План начинается заполняться с верхнего левого угла.

    1    2    3    4    5    Запасы
1    20[7]    5[8]    27    10    26    15
2    7    17    18[13]    21[12]    28    25
3    27    21    9    23    26[5]    5
4    1    13    17    23    7[15]    15
Потребности    7    8    13    12    20    
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. 
Значение целевой функции для этого опорного плана равно:
F(x) = 20*7 + 5*8 + 18*13 + 21*12 + 26*5 + 7*15 = 901

Строим новый план.
    1    2    3    4    5    Запасы
1    20[7]    5[8]    27    10    26    15
2    7    17    18[13]    21[12]    28    25
3    27    21    9    23    26[5]    5
4    1    13    17    23    7[15]    15
Потребности    7    8    13    12    20    

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 20*7 + 5*8 + 18*13 + 21*12 + 26*5 + 7*15 = 901

Строим новый план.

    1    2    3    4    5    Запасы
1    20[2]    5    27[13]    10    26    15
2    7[5]    17[8]    18    21[12]    28    25
3    27    21    9    23    26[5]    5
4    1    13    17    23    7[15]    15
Потребности    7    8    13    12    20    

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 20*2 + 27*13 + 7*5 + 17*8 + 21*12 + 26*5 + 7*15 = 1049
Строим новый план.

    1    2    3    4    5    Запасы
1    20[3]    5    27    10[12]    26    15
2    7[4]    17[8]    18[13]    21    28    25
3    27    21    9    23    26[5]    5
4    1    13    17    23    7[15]    15
Потребности    7    8    13    12    20    

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Значение целевой функции для этого опорного плана равно:
F(x) = 20*3 + 10*12 + 7*4 + 17*8 + 18*13 + 26*5 + 7*15 = 813 

Строим новый план.
    1    2    3    4    5    Запасы
1    20    5    27    10    26[15]    15
2    7[7]    17[8]    18[10]    21    28    25
3    27    21    9[3]    23[2]    26    5
4    1    13    17    23[10]    7[5]    15
Потребности    7    8    13    12    20    

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 26*15 + 7*7 + 17*8 + 18*10 + 9*3 + 23*2 + 23*10 + 7*5 = 1093

Используя метод минимального элемента, построим первый опорный план транспортной задачи.

    1    2    3    4    5    Запасы
1    20    5[8]    27    10[7]    26    15
2    7    17    18[8]    21[5]    28[12]    25
3    27    21    9[5]    23    26    5
4    1[7]    13    17    23    7[8]    15
Потребности    7    8    13    12    20    

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 5*8 + 10*7 + 18*8 + 21*5 + 28*12 + 9*5 + 1*7 + 7*8 = 803

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
    v1=11    v2=5    v3=7    v4=10    v5=17
u1=0    20    5[8]    27    10[7]    26
u2=11    7    17    18[8]    21[5]    28[12]
u3=2    27    21    9[5]    23    26
u4=-10    1[7]    13    17    23    7[8]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;1): 11 + 11 > 7; ∆21 = 11 + 11 - 7 = 15
Выбираем максимальную оценку свободной клетки (2;1): 7
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
    1    2    3    4    5    Запасы
1    20    5[8]    27    10[7]    26    15
2    7[+]    17    18[8]    21[5]    28[12][-]    25
3    27    21    9[5]    23    26    5
4    1[7][-]    13    17    23    7[8][+]    15
Потребности    7    8    13    12    20    

Цикл приведен в таблице (2,1 → 2,5 → 4,5 → 4,1).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

    1    2    3    4    5    Запасы
1    20    5[8]    27    10[7]    26    15
2    7[7]    17    18[8]    21[5]    28[5]    25
3    27    21    9[5]    23    26    5
4    1    13    17    23    7[15]    15
Потребности    7    8    13    12    20    

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

    v1=-4    v2=5    v3=7    v4=10    v5=17
u1=0    20    5[8]    27    10[7]    26
u2=11    7[7]    17    18[8]    21[5]    28[5]
u3=2    27    21    9[5]    23    26
u4=-10    1    13    17    23    7[15]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Минимальные затраты составят: 
F(x) = 5*8 + 10*7 + 7*7 + 18*8 + 21*5 + 28*5 + 9*5 + 7*15 = 698