2015-06-30
804
Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений – нахождение оценок свободных клеток.
Теорема8. (признак оптимальности опорного решения). Если допустимое решение Х=(
), i=1,2,,…,m, j=1,2,…,n транспортной задачи является оптимальным, то существует потенциалы (числа) поставщиков 
, i=1,2,,…,m и потребителей 
, j=1,2,…,n, удовлетворяющие следующим условиям:
+ = 
при >0, (12)
+ 
при =0. (13)
Доказательство. Используем вторую теорему двойственности. Запишем математическую модель транспортной задачи
,
, i=1,2,,…,m,
, j=1,2,…,n,
0, i=1,2,,…,m, j=1,2,…,n.
составим математическую модель двойственной задачи. Обозначим через , i=1,2,,…,m переменные (оценки), соответствующие первым m уравнениям системы ограничений, и через , j=1,2,…,n переменные, соответствующие последним n уравнениям. Записываем
F(U, V)= 
, + , i=1,2,,…,m, j=1,2,…,n.
Каждое ограничение двойственной задачи содержит только две переменные, так как вектор-условие 
системы ограничений исходной задачи имеет только две отличные от нуля (равные единице) координаты,i-ю и (m+j)-ю. Условий неотрицательности двойственная задача не имеет, так как все ограничения в исходной задаче – равенства. По второй теореме двойственности, если при подстановке в систему ограничений двойственной задачи некоторое ограничение выполняется как строгое неравенство + < , то соответствующая координата оптимального решения исходной задачи равна нулю, т.е. =0. Если же оптимальным решением ограничение удовлетворяется как равенство + = , то соответствующая координата оптимального решения отлична от нуля, т.е. 
>0.
Группа равенств (12) + = при >0 используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например - + = или - = , если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).
Данная система уравнений имеет m+n неизвестных , i=1,2,,…,m и , j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.
Группа неравенств (13) + при =0 используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в виде 
= + - при =0. (14)
Числа называются оценками свободных клеток таблицы или векторов-условий транспортной задачи, не входящих в базис опорного решения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.
Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (k, l) таблицы, соответствующую max{ 
}= . Если 0, то решение оптимальное. Если же >0, то для соответствующей клетки (k, l) строят цикл и улучшают решение, перераспределяя груз 
= 
по этому циклу.
