Промежуточные вычислении 11 страница

d) Минимизировать z = 5х_х + 4х₂

при ограничениях

Зх, + 2х₂>5, 2х_х + 3х₂>7, х_х, х₂ > 0 и целые.

е) Максимизировать z = 5х_х + 7х₂ при ограничениях

2х_х +х₂< 13, 6х_х + 9х₂<41, х,, ж₂>Оицелые.

Глава 9. Целочисленное линейное программирование

3. Решите задачи из предыдущего упражнения, предполагая, что на перемен­ную Xj не налагается условие целочисленности.

4. Покажите графически, что следующая задача ЦЛП не имеет допустимых ре­шений, а затем проверьте этот результат с помощью метода ветвей и границ.

Максимизировать z = 2х₁ + х₂

при ограничениях

10х, + 10х₂ < 9, 10х, + 5х₂> 1, х_р х₂ > 0 и целые.

5. Решите следующую задачу методом ветвей и границ. Максимизировать z = 18х, + 14х₂ + 8х₃ + 4х₄

при ограничениях

15х, + 12х₂ + 7х₃ + 4х₄ + х₅ < 37, х,, х₂, х₃, х₄, х₅ = 0 или 1.

9.2.2. Метод ветвей и границ в системе TORA

Модуль целочисленного программирования системы TORA позволяет интерак­тивно генерировать деревья подзадач в методе ветвей и границ. Чтобы воспользо­ваться этой возможностью, в выходном окне модуля целочисленного программиро­вания выберите опцию User-guided В&В (Учебный режим метода ветвей и границ). В этом окне представлена вся информация, необходимая для создания дерева подза­дач. На рис. 9.9 показан внешний вид окна, в котором представлен корень N10 де­рева подзадач, которое соответствует задаче ЛПО на рис. 9.6 (файл ch9ToraB&BEx9-2-l.txt). Каждый узел определяется двумя цифрами, перед кото­рыми стоит буква N. Левая цифра определяет строку таблицы, в которой находится узел, а правая цифра представляет порядковое значение в пределах той же строки. Например, обозначение N10 на рис. 9.9 указывает, что узел 0 расположен в строке 1 (это единственный узел в этой строке). В программе TORA может быть не более 10 подзадач в одной строке. Но помните, что в автоматическом режиме нет каких-либо ограничений на количество генерируемых подзадач.

Далее следует выбрать переменную ветвления, щелкнув на любом из узлов, поме­ченных "х?". Эти узлы выделены зеленым цветом. Если щелкнуть на записи одного узла над областью, где расположено дерево, появится соответствующее решение. Как показано на рис. 9.10, из решения для узла N10 видно, что х, = 3,75 и х₂ = 1,25. Так­же следует обратить внимание на то, какие переменные ограничены целыми значе­ниями. Щелчок на любой из переменных приведет к автоматическому созданию двух подзадач, которые соответствуют выделенной переменной ветвления. На рис. 9.11 показан результат выбора х, в качестве переменной ветвления в узле N10. К дереву были добавлены узлы N20 (соответствует новому ограничению х, < 3) и N21 (соответствует новому ограничению х, > 4). В узле N20 получено целочисленное ре­шение, поэтому он считается прозондированным. Прозондированные узлы выделя­ются красным или пурпурным цветом. Пурпурный цвет используется тогда, когда в прозондированном узле была достигнута текущая нижняя граница значения целе­вой функции, что в данном случае произошло с узлом N20. Узел N21 пока не прозон­дирован. Поэтому щелчок на нем приведет к созданию следующих узлов в строке 3 дерева. Этот процесс продолжается до тех пор, пока не будут прозондированы все узлы (т.е. пока все они не будут выделены красным или пурпурным цветами).

9.2. Методы решения задач целочисленного программирования

Рис. 9.10. Выбор переменной ветвления

Глава 9. Целочисленное линейное программирование

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

Важно отметить, что в автоматическом режиме TORA выполняет последова­тельное решение подзадач по принципу "первым пришел — первым ушел". По­этому, вероятнее всего, поиск вручную может привести к более эффективному де­реву подзадач, поскольку пользователь может осуществить лучший выбор следующего зондируемого узла.

УПРАЖНЕНИЯ 9.2.2

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

Минимизировать у

при выполнении условий

2(ж,+ *, +... +*₁₆) + г/= 15. Все переменные двоичные.

9.2. Методы решения задач целочисленного программирования 421

Используя программу TORA в автоматическом режиме, ответьте на следую­щие вопросы.

a) Сколько подзадач было решено прежде, чем было найдено оптимальное решение?

b) Сколько подзадач было решено прежде, чем была проверена оптималь­ность найденного решения?

2. Дана следующая задача ЦЛП.

Максимизировать z — 18х, + 14лс₂ + 8х₃ при выполнении условий

15х, + 12л;₂+ 7х₃ < 43,

x_lt х₂, х₃ — неотрицательные целые.

В системе TORA в режиме пошагового выполнения создайте дерево подза­дач с вычислением границ целевой функции и без такового. Как повлияет знание границ целевой функции на количество сгенерированных подзадач? Для сравнения всегда выбирайте переменную ветвления с наименьшим ин­дексом и зондируйте все задачи в текущей строке слева направо, затем пе­реходите на следующую строку.

3. Вернитесь к задаче из упражнения 2. Преобразуйте эту задачу в задачу ЦЛП с двоичными переменными, затем решите ее в программе TORA в автоматиче­ском режиме. Сравните размеры деревьев подзадач в каждом из упражнений.

4. В следующей задаче ЦЛП с двоичными переменными с помощью TORA сге­нерируйте дерево подзадач.

Максимизировать z = Зх, + 2х_г - 5х₃ - 2х₄ + Зх_ь

при выполнении условий

х, + х₂ + х₃ + 2x_i + х_ь < 4, 7ж, + Зх₃ - 4x_t + Зх₅ < 8, Их, - 6х₂ + Зх₄ - Зх₆ > 3, ж,, х₂, х₃, x_f, х_ь = О или 1.

5. Используя программу TORA в режиме пошагового выполнения, покажите, что следующая задача не имеет допустимого решения.

Максимизировать z = 2х, + х₂

при выполнении условий

10х, + НЦ, < 9, 10х, + 5х₂ > 1, x_v х₂ = 0 или 1.

6. С помощью TORA создайте дерево подзадач в методе ветвей и границ для сле­дующей частично-целочисленной задачи и найдите ее оптимальное решение.

Максимизировать z = х, + 2х₂ - Зх₃

при выполнении условий

Зх, + 4х₂ - х₃ < 10, 2jc, - Зх₂ + 4х₃ < 20, х,, х₂ неотрицательные целые, х₃>0.

Глава 9. Целочисленное линейное программирование

7. В системе TORA создайте дерево подзадач для следующей задачи, полагая, что выполняется только одно ограничение.

Максимизировать г = ж₁ + 2дг₂ - Здг₃

при выполнении условий

20х₁ + \Ьх₂- х₃<10, 12x, + 3x₂ + 4x₃<13, х„ х₂, х₃>0.

8. Преобразуйте представленную ниже задачу в частично-целочисленную, по­сле чего в системе TORA сгенерируйте для нее дерево подзадач. Каким будет оптимальное решение?

Максимизировать z = х_х + 2лг₂ + 5jc₃

при выполнении условий

\-х_х + \Ъх_г - Ъх_г\>\Ь, 2х₁+х₂ + х₃<10, х_1г х₂, х₃ > 0.

9.2.3. Метод отсекающих плоскостей

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

Пример 9.2.2

Продемонстрируем применение метода отсекающих плоскостей для решения сле­дующей задачи ЦЛП.

Максимизировать z = 7jc, + 10х₂

при ограничениях

+ Зх₂ < 6, Чх_л+х₃<ЗЬ, x_v х₂> 0 и целые.

Данный метод путем добавления отсечений (отсекающих плоскостей) преобразует пространство допустимых решений соответствующей задачи линейного программи­рования в выпуклый многогранник, вершина которого, соответствующая оптимуму, является целочисленной и представляет решение исходной задачи. На рис. 9.12 по­казан пример двух таких отсечений. Мы начинаем с оптимального решения непре­рывной задачи линейного программирования (х_х, х₂) = (4,5, 3,5) и z = 66,5. Затем прибавляем отсечение I, которое вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению (x_v х₂) = (4 у, 3) с z = 62. По­сле этого прибавляется отсечение II, которое вместе с отсечением I и исходными огра­ничениями приводит к оптимальному решению (jc,, х₂) — (4, 3) с z = 58. Последнее решение является полностью целочисленным, как и требуется.

9.2. Методы решения задач целочисленного программирования

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

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

Рис. 9.12. Последовательность построения отсечений

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

При дополнительных переменных х_ъ и х₄ для ограничений 1 и 2 оптимальная сим­плекс-таблица исходной задачи имеет следующий вид.

Базис	Х1	хг	хз	Xi	Решение
z			63/22	31/22	66,5
хг			7/22	1/22	3,5
Х1			-1/22	3/22	4,5

Оптимальным непрерывным решением является jc₁ = 4,5, jc₂ = 3,5, х_г = 0, x_t = О иг = 66,5. Целочисленное отсечение получается в предположении, что все пере­менные задачи являются целочисленными. Поскольку коэффициенты исходной целевой функции являются целочисленными, то и значение г, соответствующее целочисленному решению, должно быть целочисленным.

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

z-уравнение: z + ||x₃+|±х₄ = 66^, ^..-уравнение: х_г+^х_г +^*₄ =³^-^-уравнение: -^х, =4^.

Глава 9. Целочисленное линейное программирование

Так как в этом примере г, х_х и х₂ должны быть целочисленными и все они на дан­ный момент имеют дробные значения в оптимальной симплекс-таблице, любое из трех уравнений можно использовать в качестве производящей строки для построе­ния отсечения. Выберем (произвольно) для этой цели z-уравнение.

^Z+ 22 ^ХЪ ⁺ 22*4 ⁼ ^2 (^пР^{ОИЗВОДЯ1}Ч^ая z-строка).

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

5 2

И)-

Разложение коэффициентов производящей z-строки приводит к следующему уравнению.

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

_z+ 2_V*₄-66 = l-g*3-£*₄.

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

i-lir -S-r =1 2 22 3 22 4 2

:_х __z._x =jl_(1£_x +±_х) • - ' " \22*3 ⁺ 22 4/'

Поскольку х₃, x_t > О, выражение в скобках является неотрицательным. Поэтому величина т^_тгх_э -£*₄. будучи целочисленной, не может превышать 1/2. Следова­тельно, необходимое условие целочисленности можно записать следующим образом.

--2-х <0 2 22 3 22 4-^и'

Это и есть дробное отсечение, порожденное z-строкой. Нетрудно убедиться, что ранее найденное оптимальное непрерывное решение х_х = 4,5, х₂ = 3,5, х₃ = О, х₄ = 0 не удов­летворяет отсечению. Действительно, так как x_a = x_t = О, отсечение не удовлетворяет­ся (оно приводит к неравенству 1/2 <0). Следовательно, если мы присоединим отсе­чение к конечной симплекс-таблице, то оптимальное решение новой симплекс-таблицы будет "двигаться" в направлении выполнения ограничения целочисленности. Можно таким же образом построить отсечение, исходя из производящей л^-строки или лг₂-строки. Рассмотрим сначала jCj-строку. Имеем

^Xl~22^X3 ⁺ 22^ХА ^{= 4} 2 (^пР^оизв°Д^яЩ^ая *f строка). Операция разложения приводит к уравнению

v(-¹⁺iM⁰⁺£h=K)-

Соответствующим отсечением является

21.. 3... 1

9.2. Методы решения задач целочисленного программирования

Аналогично

*₂ ⁺ z2^x3 ⁺ 22^Х4 ^{= 3} 2 (^пР^оизв°Д^ящая *₂"^стР^ока) записывается в виде

v(⁰⁺i)v(⁰⁺Ata⁼(³⁺2-)-

Следовательно, в данном случае отсечение имеет вид

——х ——х + — <0 22*3 22 4 ⁺ 2

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

Выбирая (произвольно) отсечение, порожденное д:₂-строкой, записываем его сле­дующим образом.

'22^ХЪ~72^Х4 ^{+ $}\⁼~2' ⁵1 ~° (^{отсечение}

Это ограничение добавляется в качестве дополнительного в оптимальную сим­плекс-таблицу задачи.

Базис	*i	х2	Хз	X»	Si	Решение
z			63/22	31/22		66,5
хг			7/22	1/22		3,5
Х1			-1/22	3/22		4,5
«1			-7/22	-1/22		-0,5

Таблица представляет оптимальное, но недопустимое решение. Для восстановле­ния допустимости решения применим двойственный симплекс-метод (см. раз­дел 4.4), что приведет к следующей симплекс-таблице.

Базис	Х1	хг	хз	Хл	S1	Решение
z
хг
Х1				1/7	-1/7	Ц
Хз				1/7	-22/7

Из-за дробных значений переменных jc, и х₃ последнее решение все еще нецелочис­ленное. Выберем лг,-строку в качестве производящей, т.е.

vKh+(-'+fh=K)-

Соответствующее отсечение имеет вид

~4^xa~7^s,^+s2⁼~i' ^s2~° (отсечение2).

426 Глава 9. Целочисленное линейное программирование

Присоединяя отсечение 2 к последней симплекс-таблице, получаем следующее.

базис	Хх	Хг	Хз	Ха	S1	s2	Решение
z
хг
хх				1/7	-1,7		ц
хз				1/7	-22/7
S2				-1/7	-6/7		-4/7
Применение двойственного таблице.	симплекс-метода	приводит к	следующей	симплекс-
Базис	xx	хг	хз	ха	Si	s2	Решение
z
хг
хх					-1
хз					-4
ха						-7

Оптимальное решение (jc, = 4, х_г = 3, г — 58), определяемое последней симплекс-таблицей, является целочисленным. То, что все элементы данной симплекс-таблицы являются целочисленными, не случайность. Это типичное явление при использовании дробных отсечений.

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

Важность этого продемонстрируем на следующем примере. Рассмотрим огра­ничение

1 13

х. +-х₂ <-,

¹ 3 ² 2

л:,, х_г> О и целые.

С точки зрения решения соответствующей задачи ЦЛП это ограничение преобразу­ется в уравнение путем введения неотрицательной дополнительной переменной s,, т.е.

1 13

¹ 3 - ¹ 2

Применение дробного отсечения предполагает, что ограничение имеет допусти­мое целочисленное решение по всем переменным, т.е. x_v х₂ и s,. Рассмотрев это уравнение, можем сказать, что оно может иметь допустимое целочисленное реше­ние переменных х_х и х₂ лишь в том случае, если переменная s, принимает нецело­численные значения. Следовательно, применение дробного отсечения приведет к недопустимому целочисленному решению, так как все переменные x_lt х₂ и s, не могут одновременно быть целочисленными. Тем не менее ограничение имеет до­пустимые целочисленные решения для рассматриваемых переменных х_: и х₂.

9.2. Методы решения задач целочисленного программирования 427 Есть две возможности исправить эту ситуацию.

1. Можно умножить все ограничения на соответствующую константу для уст­ранения дробей. Например, приведенное выше ограничение умножается на 6, что приводит к неравенству 6x_t + 2х₂ < 39. Любое целочисленное решение переменных х, и х₂ автоматически дает целочисленное значение дополни­тельной переменной. Однако этот тип преобразования применим лишь для простых ограничений, так как значения необходимых целочисленных коэф­фициентов в некоторых случаях могут быть чрезвычайно большими.

2. Можно использовать специальные отсечения, именуемые частично-целочисленными. Они ориентированы на решение задач, в которых лишь часть переменных должна принимать целочисленные значения, а остальные (включая дополнительные) остаются непрерывными. Детальное изложение таких отсечений в этой главе не рассматривается (см. [3]).

УПРАЖНЕНИЯ 9.2.3

1. В примере 9.2.2 покажите графически, может ли каждое из следующих ог­раничений служить в качестве правильного отсечения.

a) х, + 2х₂ < 10.

b) 2х, + л:₂ < 10.

c) Зх₂<10.

d) Зх₁+х₂<15.

2. В примере 9.2.2 покажите графически, как следующие два правильных отсе­чения могут привести к оптимальному целочисленному решению.

Отсечение I. х, + 2х₂ < 10.

Отсечение II. 3xj + х₂ < 15.

3. Запишите отсечения I и II в примере 9.2.2 через уравнения для переменных х, и х₂ и покажите, что они совпадают с отсечениями, которые графически показаны на рис. 9.12.

4. Покажите, что дробное отсечение не приводит к допустимому решению в приведенной ниже задаче, если не устранены все дроби в ограничении.

Максимизировать z = х_х + 2х₂

при ограничениях

1 13 ¹ 2 " 4 х,, х₂ > 0 и целые.

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

а) Максимизировать г = 4х, + 6х₂ + 2х_ъ

при ограничениях

4х,-4х₂<5,

-х, + 6х₂< 5,

-х, + х₂ + х₃< 5,

х,, х₂, х₃> 0 и целые.

Глава 9. Целочисленное линейное программирование

Ь) Максимизировать г = Зх, + х_г + 3jc₃ при ограничениях

~х_у + 2х₂ + х₃ < 4, 4лг₂ - Зх₃ < 2, х₁-3х₂ + 2х₃<3, x_v х₂, х₃ > 0 и целые.

9.2.4. Вычислительный взгляд на задачи ЦЛП

На сегодняшний день, несмотря на 40 лет интенсивных исследований, не суще­ствует вычислительного алгоритма, приемлемого для решения всех разнообразных задач целочисленного программирования. Из представленных в этой главе двух ал­горитмов метод ветвей и границ считается более эффективным — практически все коммерческие программы, предназначенные для решения задач ЦЛП, используют этот метод. Метод отсекающих плоскостей более сложен и менее надежен, кроме того его реализация порождает серьезные проблемы, связанные с ошибками машинного округления. Было много попыток сделать этот метод эффективным для компьютер­ных вычислений, но они не увенчались большими успехами. В большинстве случаев метод отсекающих плоскостей используется как дополнительный метод при решении подзадач, генерируемых в процессе применения метода ветвей и границ.

Наиболее важным фактором, влияющим на процесс вычислений в целочисленном программировании, является количество целочисленных переменных. Существую­щие алгоритмы не решают задачу ЦЛП последовательно, т.е. не позволяют получать промежуточные целочисленные решения, отличные от оптимального, поэтому с вы­числительной точки зрения в задаче ЦЛП необходимо ограничиться по возможности меньшим числом переменных, принимающих целочисленные значения. Следую­щие советы могут оказаться полезными при решении практических задач.

1. Аппроксимировать целочисленные переменные непрерывными, где это воз­можно.

2. Сузить, насколько возможно, интервалы допустимых значений целочислен­ных переменных.

3. Избегать в модели ЦЛП использования нелинейных функций.

Уровень развития методов решения целочисленных задач не удовлетворяет тре­бованиям, которые диктуются их практической важностью. Маловероятно, что в целочисленном программировании будет получен новый теоретический прорыв. Представляется более вероятным, что новые технологические достижения в облас­ти компьютерной техники могут предложить новые пути повышения эффективно­сти алгоритмов решения задач ЦЛП.

9.3. ЗАДАЧА КОММИВОЯЖЕРА

Задачи такого типа известны под общим названием задача коммивояжера, в "классической" формулировке которой коммивояжер пытается определить кратчайший маршрут для одноразового посещения п городов. По существу, эта задача является задачей о назначениях с дополнительными ограничениями, кото­рые гарантируют исключение из оптимального решения неполных замкнутых маршрутов. (В задаче коммивояжера замкнутый маршрут, проходящий через

9.3. Задача коммивояжера

каждый пункт только один раз, называется циклом; цикл, проходящий через все пункты, называется полным, в противном случае — частичным или подциклом.) В задаче коммивояжера с п городами можно определить такие переменные:

|1,если город j достижим из города i, У [0, в противном случае.

Имея значения d_tj, расстояния от города i до города j (считается, что й_ц = °° при i=j), задачу коммивояжера можно формализовать следующим образом.

Минимизировать г = ХХ^Л

при ограничениях

2Х= 1,1=1,2, ■■■'^п<

7=1 и

х_ц = 0 или 1,

решение должно быть полным циклом.

Ограничения задачи, кроме последнего, определяют обычную задачу о назначе­ниях (см. раздел 5.4). В общем случае нет гарантии, что оптимальное решение за­дачи коммивояжера может быть получено путем решения соответствующей задачи о назначениях, т.е., что оптимальное решение задачи о назначениях образует пол­ный цикл. Более вероятно, что оно будет содержать частичные циклы, соединяю­щие вместе некоторые подмножества узлов сети. На рис. 9.13 показана задача коммивояжера, состоящая из 5-ти городов. Ребра, соединяющие узлы (города) се­ти, соответствуют дорогам с двухсторонним движением. На этом рисунке показано решение задачи коммивояжера и частичные циклы, соответствующие решению за­дачи о назначениях. Если задача о назначениях формирует полный цикл, то это бу­дет оптимальным решением задачи коммивояжера. Если оптимальное решение за­дачи о назначениях состоит из нескольких частичных циклов, то в эту задачу добавляются специальные ограничения, удаляющие решения с частичными цик­лами. Такие ограничения будут показаны далее в этом разделе.

Задача S-ти городов Решение задачи коммивояжера Решение задачи о назначениях (х₁₂ — Хх — x_w — x_4i — х₃₁ — 1) (х_и — х_п — x_ls — х_н — Х_Ч| — 1)

Рис. 9.13. Пример задачи коммивояжера для 5-ти городов

Глава 9. Целочисленное линейное программирование

Основные методы решения задачи коммивояжера построены на тех же основах, что и методы ветвей и границ и отсекающих плоскостей, рассмотренные в разде­ле 9.2. Прежде чем представлять эти методы, рассмотрим пример, демонстрирую­щий универсальность задачи коммивояжера для описания различных практиче­ских ситуаций (см. также упражнения 9.3.1).