Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


Итерация 1. На каждой итерации матрица должна быть приведена по строкам и столбцам. В результате приведения определяется нижняя граница стоимости маршрута при прохождении определенного числа городов.


Приведение матрицы по строкам (аналогично осуществляется приведение по столбцам) заключается в отыскании минимального элемента в каждой строке (столбце) и вычитании этого элемента из каждого элемента своей строки (столбца). Минимальные элементы строк (столбцов) называют константами приведения. Сумма констант приведения по строкам и столбцам будем обозначать h1 и h2 соответственно. Сумма констант приведения по строкам и столбцам есть нижняя оценка стоимости маршрута:


h = h1 + h2.    (31)


Осуществим приведение начальной матрицы по строкам и столбцам и вычислим константу приведения.


Приведем матрицу по строкам. Для этого в каждой строке определим минимальный элемент и вычтем его из каждого элемента своей строки:


1


2


3


4


5


6


hi


1


x


31


40


25


47


12


12


2


22


x


44


26


20


22


20


3


37


17


x


43


11


55


11


4


11


35


9


x


40


26


9


5


50


4


11


34


x


36


4


6


18


7


28


25


26


x


7


1


2


3


4


5

Скачать в pdf «Экстремальные модели менеджмента и экономики»