Решение задачи о комивояжере.

 – верхняя оценка оптимального значения

 – нижняя оценка функции цели  на множестве

- оптимальная

 

 

Как найти ?

Для нахождения  необходимо провести операцию приведения матрицы .

Определение:

Процесс вычитания из каждого элемента i-ой строки матрицы  минимального элемента этой строки называется приведением матрицы  по строке I, а минимальный элемент этой строки называется константой приведения. Аналогично процесс вычитания из каждого элемента j-ого столбца матрицы  называется приведением матрицы  по столбцам.

Приведенная матрица – это матрица, которая приведена и по всем строкам и столбцам.

 – суммарная константа приведения матрицы .

Критерий приведения – в каждой строке и столбце должны быть хотя бы один нуль.

Приведенная матрица –

t – произвольный гамельктоновый цикл.

 

 

На каждой итерации разбиваем множество на два подмножества.

Принцип разбиения:

X – произвольное множество, которое разбивается.

 – подмножества, на которые разбивается множество X .

На каждой итерации свои подмножества – . Разбиение проходит по дуге . Во множество  входят те гамельктоновы циклы из x, каждые из которых содержат дугу . Во множество  входят те гамельктоновы циклы из x, в которых запрещена дуга , т.е. запрещен переезд в город l.

 

Из таких соображений выбираем дугу :

1.  должно быть как можно меньше;

2. желательно выбрать , чтобы максимально возросла , следовательно, для дальнейшего разбиения выберем y.

Это приведет к возможному нахождению гамельктонова цикла, а, следовательно, к коррекции величины .

Чтобы выбрать дугу  необходимо иметь матрицу , следовательно, прежде всего рассмотрим как можно получить, зная , матрицы соответствующие  и .

Схема получения :

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-я итерация.

 

 

Нам нужно восстановить  из

 

 – связной путь ,

 

Приводим по строкам:

 

4-я итерация:

 

 

Связной путь:

 

 

Корректируем :

 

 

Ответ: оптимальный путь это –

 означает, что водитель будет затрачивать минимум как 62 единицы времени для проезда из первого склада во все нужные магазины один раз и для возвращения обратно на склад. Нужно уточнить, что время отгрузки здесь не считается.

	=58
			Z0=65

Граф задачи

 

После нахождения времени таких переездов со второго и третьего складов, нам останется только выбрать минимальное из них. Допустим, что  для второго склада и  для третьего. Тогда выгоднее взять второй склад.

 

 

Заключение

 

Для проведения маркетинговых исследований используется широкий спектр экономико-математических методов. Основные из них – это:

· Статистические методы обработки информации;

· Многомерные методы;

· Регрессионные и корреляционные методы;

· Имитационные методы;

· Методы статической теории принятия решений;

· Детерминированные методы исследования операций;

· Гибридные методы

Самыми распространенными из них являются методы математической статистики.

Трудность применения экономико-математических методов маркетинговых исследований заключается в том, что они требуют у персонала высокой квалификации и огромный блок соответствующих знаний, но в XXI веке эта трудность сводится лишь к соответствию рабочего места специалиста-маркетолога с современными технологиями. Т.е. оно должно обеспечивать оперативное удовлетворение информационных и вычислительных потребностей специалиста, дающего реально ощутимые результаты и не требующего при этом от пользователя специальных знаний по прикладному и системному программированию.

Также сложность заключается в том, что маркетинг исследует людское поведение, которое не может быть до конца изучено, соответственно математически просчитать что-либо связанное с этим очень сложно.

Но, несмотря на некоторые недостатки, все-таки с помощью математических методов намного проще найти оптимальное решение некоторых экономических задач.

Одна из таких задач разбиралась в моей курсовой работе. Как видно это занимает не очень много времени, но единственный недостаток этого то, что требуется достаточно много времени для того, чтобы разобраться в методе и алгоритме решения. Это конечно является существенным недостатком, но согласитесь, что просто рассуждениями или, следуя интуиции, решение находилось бы намного дольше и, скорее всего, не оптимальное.

Получается, что, несмотря на все недостатки математических методов они необходимы. Тем более что современные технологии позволяют существенно облегчить их применение на практике (с помощью персональных компьютеров, их программ и т.п.)