Рассмотрим задачу дискретного программирования в общем виде:

Найти -вектор неизвестных, D- конечное

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

Идея метода состоит в разбиении D на непересекающиеся подмножества Di (эта процедура называется ветвлением) и вычислении верхней и нижней границ целевой функции на каждом из подмножеств. Нижнюю границу будем обозначать Н, а верхнюю Е. Соответственно Hi Eo, то это подмножество не содержит точку оптимума и может быть исключено из дальнейшего рассмотрения. Если верхняя граница Ei H заменяем Н на min Hi. Если Е=Н, то задача решена, иначе надо продолжить процедуру ветвления и вычисления верхней и нижней границ. При этом разбиению на очередном шаге могут подвергаться все или только некоторые подмножества до достижения равенства верхней и нижней границ, причём не на отдельном подмножестве, а для допустимой области в целом.

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

Схему динамического программирования при движении от начальной точке к конечной (рис. 5.1) можно представлять как процедуру ветвления.

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

Рис. 5.1.

Теперь подмножествами Di являются множества траекторий, каждая из которых проходит через соответствующую i-ую точку.

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

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

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

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

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ .

Общий план решения задачи коммивояжера

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

1. Построение матрицы с исходными данными.
2. Нахождение минимума по строкам.
3. Редукция строк.
4. Нахождение минимума по столбцам.
5. Редукция столбцов.
6. Вычисление оценок нулевых клеток.
7. Редукция матрицы.
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

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

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di ) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка .

4. Нахождение минимума по столбцам

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка .

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку ». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути , ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .

Общая длина пути: L = 30 .

Практическое применение задачи коммивояжера

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

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

Галяутдинов Р.Р.

© Копирование материала допустимо только при указании прямой гиперссылки на

Определения

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

Маршрутом в графе

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

Постановка задачи

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длинна (или цена) дуги (i , j ),

. Под маршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0 ÎZ , такой, что l (z 0)= minl (z ), z ÎZ .

Решение задачи

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

состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ (), φ(Z) ≤ φ ().

Сравнивая нижние границы φ (

) и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

Затем одно из подмножеств

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

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

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

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

Пример решения задачи коммивояжера методом ветвей и границ

Коммивояжер должен объездить 6городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

A	B	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

После их вычитания по строкам получим:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

После их вычитания по столбцам получим приведенную матрицу:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Найдем нижнюю границу φ (Z ) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Наибольшая степень Θ 14 = 10. Ветвление проводим по дуге (1, 4).

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

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

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

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

Здесь каждому ребру соответствует две дуги такого же веса.

«Жадный алгоритм» прежде всего включит в цикл ребро
, как имеющее минимальный вес. Включение этого ребра, как непосредственно легко проверить, необходимо ведет к гамильтонову циклу
веса 29. Оптимальный

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

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

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

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

Рассмотрим метод «ветвей и границ» на примере задачи коммивояжера. Пусть взвешенный орграф задан матрицей расстояний. Если некоторая дуга в графе отсутствует, то соответствующий элемент матрицы будем полагать равным ∞. Заметим, что если длины всех дуг, входящих в некоторую вершину, уменьшить на одно и то же число, то и длина оптимального гамильтонова цикла уменьшится на это же число. То же самое относится и к множеству выходящих дуг. Будем последовательно вычитать из строк и столбцов матрицы расстояний положительные числа так, чтобы элементы матрицы оставались неотрицательными. Так как длина оптимального гамильтонова цикла для графа с неотрицательной матрицей расстояний также неотрицательна, то сумма вычтенных количеств будет нижней границей для длины оптимального цикла исходного графа.

Рассмотрим пример. Пусть задан граф G с симметрической матрицей расстояний.

Значки « ∞ » на диагонали соответствуют отсутствию в графе петель – дуг, ведущих из вершины в эту же вершину. Получим, прежде всего, нижнюю границу для длины кратчайшего гамильтонового цикла. Из первой, второй, третьей и четвертой строк можно вычесть по единице, из пятой строки – два, а из пятого столбца можно вычесть ещё единицу. Это дает нижнюю границу 7, а матрица расстояний приобретает вид

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

из первой строки и второго столбца которой можно вычесть по единице, что увеличивает нижнюю границу на 2 и делает её равной 9.

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

Из её первой строки и первого столбца можно вычесть по единице, что приводит к матрице

Нижняя оценка здесь возрастает на 2 и также становится равной 9.

Нижняя оценка длины оптимального цикла остается неизменной.

Дуга (2,5) должна быть запрещена, как ведущая к появлению негамильтонова цикла, и матрица принимает вид

Нижняя оценка длины гамильтонова цикла остается, по – прежнему, равной 9.

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

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

Существует ли эффективный алгоритм для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

Является ли описанный метод « ветвей и границ» эффективным алгоритмом для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

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

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

Алгоритм решения:

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X 0 . Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и

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

Предполагая, что найденный оптимальный план X 0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X 0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:

Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:

• 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
• 2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
• 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.

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

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:

• 1. Находят решение задачи линейного программирования (1)-(3).
• 2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
• 3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
• 4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

целочисленный программирование задача коммивояжер ранец