Экономико математические методы маркетингового исследования (стр. 3 из 5)

Величины

и используются для сужения области поиска решения ЗДП. А именно если выполняется условие (2).

(2) означает, что

на множестве функция не достигает своего максимума, следовательно в дальнейшем подмножество можно не рассматривать при решении задачи.

Предположим (2) выполнено для

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

Выбираем следующее для разбиения подмножество из условия:

(4)

Пусть

разбивается на , переобозначим

Для каждого из этих подмножеств вычисляем:

(5)

Проверяем условие (5).

Пусть условие (5) выполняется для

(6).

Нужно скорректировать два подмножества

и

В дальнейшем будем рассматривать только те подмножества, которые на графе являются висячими вершинами, т.е. нерассмотренные.

Дальнейший процесс решения задачи можно построить двумя способами.

Граф:

Первый способ:

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

, например:

Пусть это будет

и производим разбиение.

Дальнейший процесс будет проходить также.

При этом способе можно достаточно быстро получить подмножество

, содержащее всего один план задачи

, то - претендент на оптимальный план. Запоминаем на графе на ветке, приводящей к ставим конец и корректируется величина , т.е. .

увеличена, следовательно нужно рассмотреть все нерассмотренные подмножества.

Далее продолжаем процесс решения задачи также.

Второй способ:

Выбирается множество для разбиения из всех висячих вершин, ещё нерассмотренных.

Выбирать способ решения задачи нужно в зависимости от конкретной задачи. При любом способе решения процесс продолжаем до тех пор пока не будет выполнено следующее условие:

для любого (висячие вершины).

Решением задачи будет тот план, который дал последнее значение величине

.

Для решения конкретной ЗДП необходимо строить алгоритм метода ветвей и границ, согласно приведенной схеме. При этом нужно решить следующие проблемы:

1) как найти

;

2) по какому принципу проводить разбиение множества;

3) как вычислить

.

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

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

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

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

Как найти

?

Для нахождения

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

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

Процесс вычитания из каждого элемента i-ой строки матрицы

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

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

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

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

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

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

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

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

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

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

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

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

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

:

1.

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

2. желательно выбрать

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