Экономико математические методы маркетингового исследования (стр. 4 из 5)
Это приведет к возможному нахождению гамельктонова цикла, а, следовательно, к коррекции величины
.Чтобы выбрать дугу
необходимо иметь матрицу 
, следовательно, прежде всего рассмотрим как можно получить, зная , матрицы соответствующие 
и 
. 
:1) т. к.
входит в любой гамельктоновый цикл из множества y, Поэтому вычеркиваем k – строку и l-столбец в матрице , т. к. больше не можем въезжать в город l и выезжать из города k.2) Из всех дуг уже зафиксированных для множества y составляем связный путь, который обязательно включает в себя последнюю зафиксированную дугу
. Этот связный путь может состоять из одной дуги . Полагаем, что в матрице 
, где m – конец, а p – начало, т.е. запрещаем подциклы.3) Приводим
, в результате получим с 
– константа приведения. 
1) в матрице
полагаем, что , т.е. запрещаем.2) В результате получаем
, приводим , получаем и 
1) просматривая все нулевые элементы
, и для каждого такого элемента рассчитываем величину 
– сумма минимального элемента i-ой строки и минимального элемента j-го столбца матрицы , исключая сам нулевой элемент. 
.2)
выбираем из условия 
для всех 
можно не получать, а сразу получать 
.Если же в процессе решения задачи придется разбивать
, а соответствующей матрицы нет, то её нужно восстановить из исходной матрицы. для любого X из исходной матрицы 
:Пусть вершина X такова, что для неё уже зафиксированы
.Шаг 1: для каждой фиксированной дуги
для каждой .Шаг 2: для каждой фиксированной дуги
составляет связный путь, который содержит обязательную дугу ; и запрещает переезд из 
в 
, т.е. 
, где m– коней и p – начало.Шаг 3: для каждой запрещенной дуги
полагаем, что 
В результате получаем матрицу
, приводим её и получаем .Связной путь должен содержать последнюю зафиксированную дугу.
Пример
Фирма «Турал Арбуз Корпорейшен» проводит исследование для более удачного расположения нового склада для товара, который они должны поставлять в 4 магазина. Одним из критериев выбора стала своевременная поставка товара в кротчайшие сроки (обговорено в контрактах). Т.е. получается задача о коммивояжере. Водитель должен побывать на каждой точке с утра и вернуться на склад. Продается три склада, нужно выбрать один из них (цены одинаковы). Важнейшим критерием является минимальный срок проезда через все магазины и возвращение опять на склад. Известно время, за которое водитель может доехать с одной торговой точки до другой и время проезда до склада. Сначала находим минимальное время пути, затрачиваемое водителем с первого склада.
Дана матрица затрачиваемого времени при переезде из точки i в j.
Приведение матрицы
по строкам: 
Приведение матрицы по столбцам:
Выбираем
: 
Получаем матрицу
Связной путь (2,3), следовательно
Начинаем 2-ую итерацию
Связной путь:
3-я итерация.
Нам нужно восстановить
из 
– связной путь 
, 
Приводим по строкам:
