В матрице L(k,r) следует запретить переезд из города k в город r т.е. lk,r=?, а все остальные элементы lij переносятся из матрицы L’’. Получим L(k,r) => привести т.е. осуществить переход от L(k,r) => L(k,r)’ => L(k,r)’’. Сумма приведенных констант, полученных в результате приведения ? hi+? Hj=?k,r
Оценка ?(D1(1))= ?(D(1))+ ? hi+? Hj=?( D(1))+?k,r
Найдем матрицу L(k,r), которая соответствует подмножеству D(1)2 а D(1)2 – множество всех путей К, в котором из города k путь лежит в город r => в матрице L(k,r) запрещен выезд из k-города в любой другой город кроме r, т.е. рассмотрим lk,j =? j?r. Это соответствует запрещению всех элементов k-ой строки, кроме lk,r, т.е. уравниваем их все ?. С другой стороны необходимо запретить приезд в r-й город из всех городов, кроме k, т.е. положим li,r =? i?k. Это соответствует тому, что все элементы r-го столбца, кроме элемента lk,r будут равны ?, т.е. матрицы исключаем r-й столбец, необходимо запретить обратный переезд из города r в k, т.е. lk,r=?.
Все остальные элементы в матрицу L(k,r) переносятся из матрицы L’’. Размерность L(k,r) уменьшена. После этого матрицу L(k,r) необходимо привести. Найдем сумму приведенных констант RN-1= ? hi+? Hj
Оценка ?(D2(1))= ?(D(1))+ RN-1.
Нахождение второй наиболее перспективной дуги
Поскольку путь К еще не найден, необходимо согласно методу ветвей и границ для дальнейшего разбиения выбрать подмножество с наименьшей оценкой. Пусть это будет подмножество D(1)2, т.е. ?( D(1)2)<?( D(1)1). (если оценки одинаковые, то выбираем любое). Подмножество D(1)2 бьем на два D(1,2)1 и D(1,2)2. Наиболее перспективную найдем вычислив ?ij для всех элементов L”(k,r) ???? max ?ij=?pq, тогда D(1,2)1 это множество всех путей К которые содержат дугу k,r и не содержат p,q. Ему соответствует матрица состояний L(k,r)(h,q). D(1,2)2 это множество всех путей К которое содержит две дуги k,r и p,q ему соответствует L(k,r)(h,q). Чтобы получить матрицу L(k,r)(h,q) надо положить lpq=?, а остальные переписываем из матрицы L”(k,r). После этого осуществляем переход L(k,r)(h,q) =>L’(k,r)(h,q) =>L”(k,r)(h,q). ?hi+?Hj=?pq и оценка ?(D(1,1)1)=?(D(1)2)+?pq. Чтобы получить L(k,r)(p,q) надо исключить p-строку и q-столбец, обратный переход lpq=?. И поскольку в пути К вошли две дуги (более одной) следует предусмотреть образование подконтура проходящего через число городов меньше чем N. Подконтур может образоваться в том случае, когда конец одной дуги совпадает с началом другой. Все остальные элементы переписываются и L’(k,r). Затем осуществляется переход от L(k,r)(p,q)=> L’(k,r)(p,q)=> L”(k,r)(p,q). Находим ?hi+?Hj=RN-2 и находим ?(D(1,2)2)=?(D(1)2)+RN-2.
И так как путь К еще не найден, то для дальнейшего разбиения выбираем подмножество с наименьшей оценкой: min(?(D(1)1), ?(D(1,2)1), ?(D(1,2)2), ?(D(1)2)). Тогда D(1)1 будем бить на два подмножества аналогично тому, как били D(1)2. Процесс разбиения прекращаем тогда когда на очередном этапе будет найдено подмножество с наименьшей оценкой, которой будет соответствовать матрица состояний размером 2х2. Из этой матрицы выписываем дуги недостающие в пути К – дуги соответствуют нулевым элементам. Это наименьшая оценка и равна длине кротчайшего пути К.
Задачи сводящиеся к задаче К
1) О переналадке станка: N партий деталей следует обработать на станке в заданное времена tij. Переналадка станка при переходе от обработки i-детали к j-детали. Эти времена образуют T=(tij)NN. Найти порядок обработки партий деталей при котором суммарное время переналадки станка будет min.
Замечание: время обработки парий деталей является постоянным и поэтому на суммарное min время обработки всех деталей не влияет.
Если вместо станка рассмотреть К. а вместо N партий деталей N-городов и в качестве матрицы расстояний L рассмотреть T, то получим задачу К, решив которую найдем последовательность обработки которая обеспечивает min суммарное время их обработки.
2) О переналадки поточной линии: на поточной линии необходимо разлить N видов сока. Задаются времена Tij переналадки (промывки) поточной линии при переходе от разлива i-сока к j-соку. Имеем матрицу T=(tij)NN. Найти последовательность разливки соков при которой суммарное время разлива будет минимальное (для этого суммарное время обработки линии должно быть min). Переход аналогично предыдущей задачи (поточная линия – К, N видов – N городов и T – L). Решив задачу К найдем оптимальную последовательность.