Дискретно-непрерывная математика (стр. 53 )

f(σп) — это и есть рекорд. Фиксируем σп - рекордный план. 9. Для найденных σ′k+1 и σ′′k+1 (если они допустимы) формулируем вспомогательную задачу (0≤χi ≤1, с учетом уже найденных χi, i≤k+l, уже определенных σk+1), находим ∆(σk+1). 10. Решение закончено: рекордный план и есть оптимальный вариант загрузки рюкзака, а рекорд f - значение функции-критерия для этого плана.

Блок «формулирование вспомогательной задачи для σk» означает следующее.

Обозначим для σk

Вспомогательная задача для σk . Найти хі(i > k) такие, что 0 ≤ xі≤ 1,

и при этом

(5.81)

достигает максимума.

Рис. 5.39 представляет конечный результат построения порфириана по схеме решения задачи о рюкзаке (см. рис. 5.38) и данных, представленных табл. 5.17.

Рис. 5.39. К решению задачи о рюкзаке.

Возле вершины записаны с(х)/с'(х), где с'(х) вычисляется по формуле (5.81), но хi выбираются из x только целые.

Таблица 5.17

К задаче о рюкзаке

3. Решение задачи бродячего торговца методом ветвей и границ. Отметим: вспомогательная задача в методе ветвей и границ формулируется путем отказа от некоторых ограничений или послаблением каких-то ограничений (в задаче о рюкзаке — отказом от дискретности хі).

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

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

Пусть

Такое представление упрощает представление способа вычисления значения функции-критерия для решения

(5.82)

где аij — расстояние между пунктами i и j (заданное матрицей — таблицей расстояний).

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

Вот от этого-это ограничения мы теперь и откажемся.

Нетрудно видеть, что в оговоренном случае задача превращается в задачу о назначении, где нужно найти максимум (4.110) при условиях, что для любого i найдется такое j, что хі=1; для каждого хij найдется такое i, что хij = 1. Это можно записать и иначе:

(5.83)

для любых i и j.

Задача о назначении дает соединения городов (в случае задачи бродячего торговца), вообще говоря, отдельными несвязанными круговыми маршрутами.

Таким образом, формальное решение задачи бродячего торговца по схеме «ветвей и границ» можно свести к решению задачи о назначении.

Так что, прежде всего, желательно научиться решать задачу о назначениях.

Задача о назначениях в свою очередь также может быть решена по схеме «ветвей и границ».

Для этого выполним сначала следующие преобразования.

Утверждение 1. Решение задачи о назначениях не изменится, если каждое аij в i-й строке уменьшить на то же число ∆і.

Утверждение 2. Решение задачи о назначениях не изменится, если каждое аij в j-м столбце уменьшить на то же число δj.

Вычтем теперь из матрицы аij величины ∆i и δj так, чтобы в каждой строке и каждом столбце образовались так называемые нулевые элементы или просто «нули».

Для этого возьмем i-ю строку, найдем в ней максимальное аij и положим ∆i - равным этому максимальному аij. Затем во вновь образованной матрице = аij — ∆i возьмем j-й столбец и положим δj - равным максимальному элементу в столбце. Перейдем теперь к матрице = аij— ∆i — δj. В ней в каждых строке и столбце теперь есть = 0 — это и есть «нулевые элементы», а все аij ≤0. (Мы рассматривали задачу о назначении как задачу максимизации, так ее и решаем, хотя, как вспомогательная для задачи бродячего торговца, задача о назначении есть задача минимизации - там выбирается минимальное аij).

Легко видеть, что, например, табл. 5.2 преобразуется к такому виду (табл. 5.18) ∆1=5, ∆2 = ∆3= 4, δ1 = δ3 = 0, δ2 = —1.

Таблица 5.18

Будем строить теперь порфириан для задачи о назначениях (рис. 5.40 воспроизводит решение для условий, заданных табл. 5.18).

Рис. 5.40. Решение задачи о назначении методом «ветвей и границ»

Множество возможных решений сначала разобьем (в зависимости от того, чему равно i1). Возле каждой вершины i1 запишем соответствующее b(i1)= (и = i1). Ветвление будем производить для той вершины ik, для которой b (ik) максимально.

Вообще, пусть полученыа вершины, соответствующие σk. Возможны три случая:

а) среди них нет ни одного σп;

б) получены σп, но найдется некоторый σk (k < п), что b(σk) > F(σп) для всех σп;

в) нет такого σk.

В случае в) решение закончено и максимальное F(σп) есть экстремум, в случаях а) и б) разветвлению подвергается элемент с максимальным b(σk), b(σk+1)= b(σk) +. (Если он не один, то самый «нижний» и самый левый среди «нижних».)

Упражнение. Постройте блок-схему описанного алгоритма.

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

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

Нетрудно показать справедливость утверждений 1 и 2 и для задачи бродячего торговца. Табл. 5.19 представляет матрицу табл. 5.15 после переобразований вида = аij— ∆і — δj, где ∆1 = ∆6 = 2,

∆ 2 = ∆ 5 = 4, ∆3 = 5, ∆ 4 = 6, δ1 = δ2 = δ3 = δ5= δ6 = 0, δ 4 = 1.

Таблица 5.19

Матрица

Будем строить решение задачи бродячего торговца как порфириан, производя ветвления и отсеивание вариантов по следующим правилам. По-прежнему считаем, что путешествие начинается с пункта 1, так что все множество возможных вариантов отождествляется с множеством, где σ1 = l ; примем, что b(σ1) = 0.

Пусть построена какая-то часть порфириана, все конечные вершины которого, как известно, можно отождествить с некоторыми маршрутами σk = i1, i2,…,ik— множество этих маршрутов обозначим через Р.

Ветвление некоторого σk означает построение σk+1=(σk, j), где j не входит в М (σk), и соответствующих вершин в порфириане. При этом

Выбор σk для ветвления или остановов решения определяется следующим. Если в Р содержатся σп, вычислим для них

Нетрудно понять, что вследствие выполненного преобразования матрицы в матрицу , длина F(σп) полного пути l, i1,.....,in, 1, т. е. (σп, 1) будет равна