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

4.3.1. Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного програм­мирования методом является метод ветвей и границ . Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере .

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

Пусть стоит задача:

где D - конечное множество.

Алгоритм является итеративным, и на каждой итерации про­исходит работа с некоторым подмножеством множества D . На­зовем это подмножество текущим и будем обозначать его как D ( q ) , где q - индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все множество D (D (1) =D ), и для него некоторым способом вычисляется значе­ние верхней оценки для целевой функции max f(x) ≤ ξ( D (1)). Стандартная итерация алгоритма состоит из следующих этапов:

1°. Если можно указать план x (q ) ∊D (q ) , для которого f(x (q ) ) ≤ξ( D (q )), то x (q ) =х* - решение задачи (4.29).

2°. Если такой план не найден, то область определения D (q ) некоторым образом разбивается на подмножества D 1 (q ) , D 2 (q ) , ..., D lq (q ) , удовлетворяющие условиям:

Для каждого подмножества находятся оценки сверху (вер­хние границы) для целевой функции ξD 1 ( q ) , ξD 2 ( q ) , ..., ξD l 1 ( q ) , уточняющие ранее полученную оценку ξD ( q ) , то есть ξD i ( q ) ≤ ξD ( q ) , i ∊1:l q . Возможно одно из двух:

2.1. Если существует такой план х ( q ) , что

то этот план оптимальный.

2.2. Если такой план не найден, то выбирается одно из мно­жеств D i ( q ) , i ∊1:l q (как правило, имеющее наибольшую оценку

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D 1 ( q +1) , D 2 ( q +1) ,..., D l ( q +1) ( q +1) , после чего процесс повторяется.

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

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

4.3.2. Решение ЦЗЛП методом ветвей и границ. Рас­смотрим применение алгоритма метода ветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D ( q ) обозначается подмножество множества допустимых планов за­дачи. Перед началом первой итерации (q = 1) в качестве теку­щего множества берется все множество D (D (1) = D ), после чего решается стандартная задача линейного программирования (D (1) , f ). Нетрудно заметить, что она является непрерывным аналогом

исходной задачи (4.2)-(4.3). Если найденный оптималь­ный план (1) содержит только целочисленные компоненты, то он является и оптимальным планом для (4.2)-(4.3): (1) = x* . В противном случае значение f ( (1)) становится оценкой (верх­ней границей) значения целевой функции на множестве D (1) , и мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.

1) Выбирается некоторая нецелочисленная компонента пла­на k ( q ) . Поскольку в оптимальном плане она должна быть це­лой, то можно наложить ограничения x k ≤ [ k ( q ) ] и x k ≥ [ k ( q ) ]+1. Таким образом, D ( q ) разбивается на подмножества

Графическая интерпретация такого разбиения множества D ( q ) приведена на рис. 4.4.

2) Решаются задачи линейного программирования

Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих множествах:

Если оптимальный план для одной из решенных задач удов­летворяет условию

и содержит только целые компоненты, то, значит, найдено ре­шение основной задачи (4.2)-(4.3). В противном случае среди всех концевых подмножеств , полученных как на предыду­щих (D i ( q )), так и на текущем (D 1 ( q ) , D 2 ( q )) этапе, выбирается об­ласть с наибольшей оценкой ξ(D i ( q )). Она становится текущим рассматриваемым подмножеством (D ( q +1)). Далее производится перенумерация концевых множеств и вычислительный процесс итеративно повторяется.

При решении задач (D 1 ( q ) , f ) и (D 2 ( q ) , f ) можно воспользовать­ся результатами решения предыдущей задачи (D ( q ) , f ). Рас­смотрим вариант организации вычислительного процесса на примере задачи ( 1 ( q ) , f ) (для ( 2 ( q ) , f ) он выглядит аналогично с точностью до знаков неравенств).

Предположим, что на последнем шаге решения задачи (D ( q ) , f ) был получен оптимальный базис β. Без ограничения общности можно считать, что он состоит из первых m столбцов матрицы задачи. Данное предположение делается исключитель­но для обеспечения наглядности дальнейшего изложения и оче­видно, что его выполнения можно всегда добиться за счет про­стой перенумерации векторов а j . По аналогии с предыдущим параграфом введем обозначения для элементов матрицы задачи (D ( q ) , f ) и ее вектора ограничений относительно базиса :

Тогда система ограничений задачи (D ( q ) , f ) может быть пред­ставлена как

а получаемая на ее основе система ограничений задачи ( 1 ( q ) , f ) как

где х n +1 ≥ 0 - фиктивная переменная, которой соответствует нулевой коэффициент в целевой функции, добавляемая для пре­образования неравенства в строгое равенство.

Очевидно, что 1≤k≤m , т. к. небазисные компоненты опти­мального плана (m +1≤j≤n ) равны нулю, т. е. являются заведо­мо целочисленными. Тогда с учетом сделанных предположений о виде базиса можно записать:

Как видно из (4.39), в k -м столбце имеется всего два отлич­ных от нуля элемента: в k -й и (m +1)-й строках. Если вычесть из (m +1)-го уравнения k -e, то, учитывая, что [ά k ] – ά k =-{ά k }, по­лучим эквивалентную систему:

Проведенные преобразования системы ограничений D 1 ( q ) по­зволили явно выделить сопряженный базис, образуемый столб­цами с номерами 1,..., m , n +1, и соответствующий ему псевдо­план (ά 1 , ..., ά m , 0,...., 0, -{ά k }), т.е. для решения задачи (D 1 ( q ) , f ) может быть применен алгоритм двойственного симплекс-мето­да. Практически вычислительный процесс для данного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис. 4.5.

Для случая задачи (D 2 ( q ) , f ) преобразование симплекс-табли­цы, получаемое на базе аналогичных рассуждений, приведено на рис. 4.6.

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

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

КЛЮЧЕВЫЕ ПОНЯТИЯ

Ø Ø Задачи с неделимостями.

Ø Ø Экстремальные комбинаторные задачи.

Ø Ø Задачи с разрывными целевыми функциями.

Ø Ø Правильное отсечение.

Ø Ø Метод Гомори.

Ø Ø Методы ветвей и границ.

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.1. Какие основные проблемы возникают при решении дис­кретных задач?

4.2. Сформулируйте задачу о ранце.

4.3. Какие экономико-математические модели могут быть све­дены к задаче о коммивояжере?

4.4. Приведите пример моделей с разрывными целевыми функ­циями.

4.5. Какой принцип используется для построения правильно­го отсечения в методе Гомори?

4.6. Перечислите основные этапы, входящие в «большую» итерацию метода Гомори.

4.7. Какую роль играет алгоритм двойственного симплекс-ме­тода при решении целочисленной

линейной задачи мето­дом Гомори?

4.8. Перечислите принципиальные идеи, лежащие в основе ме­тодов ветвей и границ.

4.9. Как производится построение отсечения при решении це­лочисленной линейной задачи методом

ветвей и границ?

4.10. Опишите схему решения целочисленной задачи линейно­го программирования методом ветвей и

4.11. За счет каких преобразований удается построить сопря­женный базис при добавлении

отсекающего ограничения?

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найдем нижнюю границу φ (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).

Введение

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

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

Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, впервые, он был предложен Ленд и Дойг в 1960 г.

ветвь граница линейное программирование

Метод ветвей и границ

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

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

2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа. Вторая образуется путем добавления к задаче ЗЛП-0 ограничения. Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:

по возрастанию или убыванию индексов;

переменная представляет важное решение принимаемое в рамках данной задачи;

коэффициент в целевой функции при этой переменной существенно превосходит все остальные.

3. Задачи ЗЛП-1 и ЗЛП-2 решаются самостоятельно. Ветвь оканчивается, если область допустимых решений пуста, либо её оптимальное решение полностью целочисленное. В противном случае возникает необходимость ветвления с п.2, обозначая следующие номера задач ЗЛП в естественном порядке ЗЛП-3, ЗЛП-4.

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

Рассмотрим следующий пример. Максимизировать целевую функцию

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

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

1. Решим исходную задачу без учета требования целочисленности переменных.

Обозначим эту задачу линейного программирования ЗЛП-0.

На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.

Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений. Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.

Рисунок 1.1 Решение задачи ЗЛП-0

2. Решим задачу ЗЛП-1 графически.

На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке. Решение задачи нецелочисленное.

Рисунок 1.2 Решение задачи ЗЛП-1

3. Решим задачу ЗЛП-2 графически.

В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.

Рисунок 1.3 Решение задачи ЗЛП-2

Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и. В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.

Требуется решить следующую задачу:

max 2х 1 + х 2

5х 1 + 2х 2 10

3х 1 + 8х 2 13

Вначале решим эту задачу графически без ограниченийцелочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рисунок 4). Координаты точки оптимума можно найти, решив систему уравнений: 5х 1 + 2х 2 = 10 х 1 =27/17

3х 1 + 8х 2 = 13 х 2 =35/34

Х G = (27/17;35/34), z G =143/34

Рисунок 4 - Графическое решение задачи без ограничений целочиелейности

Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна z G (рис.5).

Рисунок 5 - Схема метода ветвей и границ

Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х 1 Z; [х 1 ] = = 1) и разобьем ОДП на две части следующим образом:

G 1 ={XG: х 1 1}

G 2 ={XG: х 1 2}

Это означает, что в область G 1 войдут все точки из G, у которых абсцисса не больше 1, а в G 2 - у которых она не меньше 2. Точки с дробными значениями абсциссы от 1 до 2 исключены из рассмотрения.

Изобразим эти области на графике (рисунок 6).

Из рисунка 6 видно, что G 2 представляет собой одну точку Х G 2 =(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2 =4).

План Х G 2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G 1 |. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G 1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G 1

Рисунок 6 - Разбиение множества на части

На G 1 точку оптимума можно найти, решив систему уравнений:

х 1 = 1 х 1 =1

3х 1 + 8х 2 = 13 х 2 =5/4

Х G 1 = (1; 5/4), z G =13/4

Оценка меньше 4, следовательно, решением задачи является Х * =Х G 2 =(2;0),z * =4.

3.4 Решение задачи целочисленного линейного программирования методом ветвей и границ с помощью ппп «Система деловых задач»

ЗЦЛП можно решить с помощью пакета прикладных программ “Quantitative Systems for Business” ("Система деловых задач") . Соответствующая программа запускается файлом intlprog.ехе. Она решает как частично, так и полностью целочисленные задачи линейного программирования с числом переменных и ограничений до 20, используя метод ветвей и границ. В том числе решаются и задачи с булевыми переменными (т.е. с переменными, которые могут принимать одно из двух значений - 0 или 1; как, например, в задаче о назначениях ). По умолчанию все переменные неотрицательны. Программа позволяет ввести целочисленные границы для переменных, не включая их в общее число ограничений. По умолчанию нижняя граница 0, а верхняя 32000. Если необходимо установить нецелочисленные границы, их вводят, как обычные ограничения.

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

Режим 2 (ввод новой задачи) включает три этапа. На первом этапе осуществляют ввод информации о размерности задачи, направлении экстремизации и именах переменных (по умолчанию XI, Х2,..., Хn).

На втором этапе необходимо определить, являются ли все переменные целочисленными, являются ли все переменные булевыми, и будут ли вводиться границы для переменных. При ответе «нет» на первый вопрос или «да» на третий, выводится таблица (рисунок 7):

Введите предел и границы для переменных

(По умолчанию значения нижней границы 0 и верхней границы 32000)

№ перем. Имя Предел (I/C) Нижняя гр. Верхняя гр.

1 X 1 <0 > <0 >

2 X 2 <0 > <0 >

Рисунок 7 - Определение пределов и границ

Установив I (integer) в столбце «Предел», на переменную накладывают ограничение целочисленности. В противном случае (С, continuous) -переменная может принимать и нецелые значения, т.е. является непрерывной.

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

На третьем этапе вводятся коэффициенты при переменных и знаки в ограничениях.

В меню решений имеется возможность исправить целочисленную погрешность (по умолчанию она 0,001).

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

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

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

При этом на каждой итерации выводится информация о текущих целочисленных границах (определяющих рассматриваемое подмножество), оптимальном плане нецелочисленной задачи, о том, является ли он целочисленным, о значении целевой функции (ЦФ) на нем и о величинах ZL или ZU. Для задачи на максимум выводится значение нижней границы ZL, а на минимум верхней ZU. До тех пор, пока не найдено какое-нибудь целое решение, ZL =-1*10 20 , а ZU = 1*10 20 .

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

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

Поясним это на примере (рис.8):

max 3х 1 + 2х 2

7х 1 + 5х 2 35

9х 1 + 4х 2 36

На первой итерации найдено нецелочисленное решение Х=(2,353; 3,706). Вся ОДП (множество G) разбивается на два подмножества - G 1 и G 2 следующим образом:

G 1 ={XG: х 1 3}

G 2 ={XG: х 1 2}.

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

На пятой итерации на подмножестве G 5 найдено целочисленное решение, которому соответствует значение целевой функции 12. На следующей итерации это значение присваивается величине ZL, которая до этого была равна -1*10 20 . Соответствующий план запоминается - он может оказаться оптимальным. Но на шестой итерации снова получен целочисленный план, целевая функция на котором равна 13 (больше 12) - ZL снова изменяется, запоминается новый план.

После этого, на седьмой итерации, переходят к рассмотрению подмножества G 2 , которое разбивают на G 7 и G 8 .

На тринадцатой итерации (подмножество G 14) снова найдено целочисленное решение Х=(0; 7), целевая функция на нем равна 14. Снова изменяется ZL и запоминается соответствующий план.

План, найденный на четырнадцатой итерации, также является целочисленным, но его не запоминают, так как 13<14 (ZL=14). План, найденный на пятнадцатой итерации, тоже, к сожалению, не запоминается, так как 1414, а программа ставит своей целью найти хотя бы одно решение.

Наличие других оптимальных планов здесь игнорируется.

Таким образом, решение Х=(0; 7) получено за 15 итераций.

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

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

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

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

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план 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) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

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