2015-06-10
468
| П2 | ||||||
| П1 | ¥ | |||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ |
Во время приведения по строкам и столбцам мы условно уменьшили расстояние на величину, равную n= Сумма 1+Сумма 2=157+22=179 миль. Это значит, что какой бы маршрут не был избран, оценка его нижней границы критерия эффективности не может быть менее 179.
В матрице № 3 в ячейках с нулевыми значениями в правом верхнем углу записаны величины штрафов за не использование каждого нулевого элемента. Штраф определяется суммированием минимальных элементов, колонки и строки которых пересекаются в данной клетке. Например:
Р(2-П2)=0+9=9
Эта цифра показывает, сколько лишних миль мы пройдем, если не выберем данный маршрут. Каждый маршрут разбиваем на два подмножества и рассчитываем расценки затрат в каждом подмножестве. Например:
|
|
|
Из расчета видно, что если мы не будем следовать этим маршрутом, то пройдем дополнительно 9 миль.
Так как для нулевой клетки 4-5 штраф самый большой (23 мили) по сравнению с другими нулевыми клетками, то этот маршрут необходимо обязательно использовать. Аналитически это выполняется, если исключить из матрицы № 4 строку и колонку, содержащие эту ячейку. Одновременно надо запретить включать в дальнейшие решения путь 4-5, если такой путь еще остался в матрице после сокращения, то есть на пересечении строки и столбца 5-4 ставится знак ¥.
Произведем описанные действия и получим матрицу № 4. В полученной матрице в строке 4 отсутствуют нулевые значения, поэтому применим операцию приведения и получим матрицу № 5. Во время приведения мы еще условно уменьшили расстояние на 6 миль и общее уменьшение теперь составило 179+6=185 миль.
