Целочисленное линейное программирование метод ветвей и границ. Задача коммивояжера - метод ветвей и границ. Теперь, собственно, об ошибках в той публикации
Лекция 6.
Градиентные методы решения задач нелинейного программирования.
Вопросы: 1. Общая характеристика методов.
2. Метод градиента.
3. Метод наискорейшего спуска.
4. Метод Франка-Фулфа.
5. Метод штрафных функций.
1. Общая характеристика методов.
Градиентные методы представляют собой приближенные (итерационные) методы решения задачи нелинейного программирования и позволяют решить практически любую задачу. Однако при этом определяется локальный экстремум. Поэтому целесообразно применять эти методы для решения задач выпуклого программирования, в которых каждый локальный экстремум является и глобальным. Процесс решения задачи состоит в том, что, начиная с некоторой точки х (начальной), осуществляется последовательный переход в направлении gradF(x), если определяется точка максимума, и –gradF(x) (антиградиента), если определяется точка минимума, до точки, являющейся решением задачи. При этом эта точка может оказаться как внутри области допустимых значений, так и на ее границе.
Градиентные методы можно разделить на два класса (группы). К первой группе относятся методы, в которых все исследуемые точки принадлежат допустимой области. К таким методам относятся: метод градиента, наискорейшего спуска, Франка-Вулфа и др. Ко второй группе относятся методы, в которых исследуемые точки могут и не принадлежать допустимой области. Общим из таких методов является метод штрафных функций. Все методы штрафных функций отличаются друг от друга способом определения «штрафа».
Основным понятием, используемым во всех градиентных методах, является понятие градиента функции, как направления наискорейшего возрастания функции.
При определении решения градиентными методами итерационный процесс продолжается до тех пор, пока:
Либо grad F(x*) = 0, (точное решение);
где
- две последовательные точки,
-
малое число, характеризующее точность
решения.
2. Метод градиента.
Представим человека, стоящего на склоне оврага, которому необходимо спуститься вниз (на дно). Наиболее естественным, кажется, направление в сторону наибольшей крутизны спуска, т.е. направление (-grad F(x)). Получаемая при этом стратегия, называемая градиентным методом , представляет собой последовательность шагов, каждый из которых содержит две операции:
а) определение направления наибольшей крутизны спуска (подъема);
б) перемещение в выбранном направлении на некоторый шаг.
Правильный выбор шага имеет существенное значение. Чем шаг меньше, тем точнее результат, но больше вычислений. Различные модификации градиентного метода и состоят в использовании различных способов определения шага. Если на каком-либо шаге значение F(x) не уменьшилось, это означает, что точку минимума «проскочили», в этом случае необходимо вернуться к предыдущей точке и уменьшить шаг, например, вдвое.
Схема решения.
принадлежащей допустимой области
3. Выбор шага h.
x (k+1)
= x (k)
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Замечание. Если grad F(x (k)) = 0, то решение будет точным.
Пример.
F(x) = -6x 1
+ 2x 1 2
– 2x 1 x 2
+ 2x 2 2
min,
x 1 +x 2
2,x 1
0, x 2
0,
= 0,1.
3. Метод наискорейшего спуска.
В отличие от метода градиента, в котором градиент определяют на каждом шаге, в методе наискорейшего спуска градиент находят в начальной точке и движение в найденном направлении продолжают одинаковыми шагами до тех пор, пока значение функции уменьшается (увеличивается). Если на каком-либо шаге F(x) возросло (уменьшилось), то движение в данном направлении прекращается, последний шаг снимается полностью или наполовину и вычисляется новое значение градиента и новое направление.
Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области,
и F(x 0), k = 0.
2. Определение grad F(x 0) или –gradF(x 0).
3. Выбор шага h.
4. Определение следующей точки по формуле
x (k+1)
= x (k)
h grad F(x (k)),
«+» - если max,
«-» - если min.
5. Определение F(x (k +1)) и:
Если
,
решение найдено;
Если нет:
а) при поиске min: - если F(x (k +1))
Если F(x (k +1))
>F(x (k))
– переход к п. 2; б) при поиске max: -
еслиF(x (k +1))
>F(x (k))
– переход к п. 4; Если F(x (k +1))
Замечания:
1. Если grad F(x (k))
= 0, то решение будет точным. 2. Преимуществом метода
наискорейшего спуска является его
простота и сокращение расчетов, так
как grad F(x) вычисляется не во всех точках,
что важно для задач большой
размерности. 3. Недостатком является то,
что шаги должны быть малыми, чтобы не пропустить точку оптимума. Пример.
F(x) = 3x 1
– 0,2x 1 2
+ x 2 -
0,2x 2 2
x 1
+ x 2
x 1
+ 2x 2
4. Метод Франка-Вулфа.
Метод используется для оптимизации
нелинейной целевой функции при линейных
ограничениях. В окрестности исследуемой
точки нелинейная целевая функция
заменяется линейной функцией и задача
сводится к последовательному решению
задач линейного программирования. Схема решения.
1. Определение х 0 = (х 1 ,x 2 ,…,x n),
принадлежащей допустимой области, и
F(x 0), k = 0. 2. Определение grad F(x (k)). 3. Строят функцию 4. Определение max(min)f(x) при
исходных ограничениях. Пусть это будет
точка z (k) . 5. Определение шага вычислений x (k +1) =x (k) +
6. Определение F(x (k +1))
и проверяют необходимость дальнейших
вычислений: Если
Если нет, то переход к п. 2. Пример.
F(x) = 4x 1
+ 10x 2
–x 1 2
–x 2 2
x 1
+x 2 x 2
5. Метод штрафных функций.
Пусть необходимо найти F(x 1 ,x 2 ,…,x n)
g i
(x 1 ,
x 2 ,…,x n)
Функции F и g i –
выпуклые или вогнутые. Идея метода штрафных функций
заключается в поиске оптимального
значения новой целевой функции Q(x) = F(x)
+ H(x), которая является суммой исходной
целевой функции и некоторой функции
H(x), определяемой системой ограничений
и называемой штрафной функцией. Штрафные
функции строят таким образом, чтобы
обеспечить либо быстрое возвращение в
допустимую область, либо невозможность
выходы из нее. Метод штрафных функций
сводит задачу на условный экстремум к
решению последовательности задач на
безусловный экстремум, что проще.
Существует множество способов построения
штрафной функции. Наиболее часто она
имеет вид: H(x) =
где
Примечание
: Чем меньше
Начинают решение с малых
Используя штрафную функцию,
последовательно переходят от одной
точки к другой до тех пор, пока не получат
приемлемое решение. Схема решения.
1. Определение начальную точку х 0 = (х 1 ,x 2 ,…,x n),
F(x 0) и k = 0. 2. Выбирают шаг вычислений h. 3. Определяют частные производные
4. Определяют координаты следующей точки
по формуле: x j (k +1) 5. Если x (k +1) а) если
б) если grad F(x (k +1))
= 0, то найдено точное решение. Если x (k +1) Пример.
F(x) = – x 1 2
– x 2 2
(x 1
-5) 2 +(x 2
-5) 2 Метод
градиентного спуска.
Направление
наискорейшего спуска соответствует
направлению наибольшего убывания
функции. Известно, что направление
наибольшего возрастания функции двух
переменных u = f(x, у) характеризуется ее
градиентом: где
e1, е2 - единичные векторы (орты) в
направлении координатных осей.
Следовательно, направление, противоположное
градиентному, укажет направление
наибольшего убывания функции. Методы,
основанные на выборе пути оптимизации
с помощью градиента, называются
градиентными.
Идея метода
градиентного спуска состоит в следующем.
Выбираем некоторую начальную точку вычисляем в ней градиент рассматриваемой
функции. Делаем шаг в направлении,
обратном градиентному: Процесс
продолжается до получения наименьшего
значения целевой функции. Строго говоря,
момент окончания поиска наступит тогда,
когда движение из полученной точки с
любым шагом приводит к возрастанию
значения целевой функции. Если минимум
функции достигается внутри рассматриваемой
области, то в этой точке градиент равен
нулю, что также может служить сигналом
об окончании процесса оптимизации. Метод
градиентного спуска обладает тем же
недостатком, что и метод покоординатного
спуска: при наличии оврагов на поверхности
сходимость метода очень медленная. В описанном
методе требуется вычислять на каждом
шаге оптимизации градиент целевой
функции f(х): Формулы
для частных производных можно получить
в явном виде лишь в том случае, когда
целевая функция задана аналитически.
В противном случае эти производные
вычисляются с помощью численного
дифференцирования: При
использовании градиентного спуска в
задачах оптимизации основной объем
вычислений приходится обычно на
вычисление градиента целевой функции
в каждой точке траектории спуска. Поэтому
целесообразно уменьшить количество
таких точек без ущерба для самого
решения. Это достигается в некоторых
методах, являющихся модификациями
градиентного спуска. Одним из них
является метод наискорейшего спуска.
Согласно этому методу, после определения
в начальной точке направления,
противоположного градиенту целевой
функции, решают одномерную задачу
оптимизации, минимизируя функцию вдоль
этого направления. А именно, минимизируется
функция: Для
минимизации
Метод
наискорейшего спуска для случая функции
двух переменных z = f(x,y).
Во-первых,
легко показать, что градиент функции
перпендикулярен касательной к линии
уровня в данной точке. Следовательно,
в градиентных методах спуск происходит
по нормали к линии уровня. Во-вторых, в
точке, в которой достигается минимум
целевой функции вдоль направления,
производная функции по этому направлению
обращается в нуль. Но производная функции
равна нулю по направлению касательной
к линии уровня. Отсюда следует, что
градиент целевой функции в новой точке
перпендикулярен направлению одномерной
оптимизации на предыдущем шаге, т. е.
спуск на двух последовательных шагах
производится во взаимно перпендикулярных
направлениях. Введение
Большой класс прикладных задач оптимизации сводится к задачам целочисленного программирования. Для решения этих задач широко применяются комбинаторные методы, основанные на упорядоченном переборе наиболее перспективных вариантов. Комбинаторные методы решения можно разделить на две группы: методы динамического программирования и методы ветвей и границ. При решении многомерных задач оптимизации предлагается совместное применение методов ветвей и границ и динамического программирования. На первом этапе задача решается методом динамического программирования отдельно по каждому из ограничений. Последовательности, полученные в результате решения функционального уравнения динамического программирования, в дальнейшем используется для оценки верхней (нижней) границы целевой функции. На втором этапе задача решается методом ветвей и границ. При использовании этого метода определяется способ разбиения всего множества допустимых вариантов на подмножества, то есть способ построения дерева возможных вариантов, и способ оценки верхней границы целевой функции. Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность решения дискретных задач оптимизации. При решении задач большой размерности с целью уменьшения членов оптимальной последовательности используются дополнительные условия отсечения. 1.
Историческая справка
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. Этот метод является наиболее общим среди всех методов дискретного программирования и не имеет принципиальных ограничений по применению. Алгоритм метода ветвей и границ представляет собой эффективную процедуру перебора всех целочисленных допустимых решений. Метод ветвей и границ - один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. 2. Описание метода
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не меньше рекорда
- наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. Если удается отбросить все элементы разбиения, то рекорд - оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д. При применении метода ветвей и границ к каждой конкретной задаче в первую очередь должны быть определены две важнейшие его процедуры: 1) ветвления множества возможных решений; 2) вычисления нижних и верхних оценок целевой функции. 2.1 Правила ветвления
В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов: 1. ветвление множества допустимых решений исходной задачи D; 2. ветвление множества D" получаемого из D путем снятия условия целочисленности на переменные. Первый способ ветвления обычно применяется для задач целочисленного программирования и заключается в выделении подобластей возможных решений путем фиксации значений отдельных компонент целочисленных оптимизационных переменных (рис. 1). На рис. 1-а дана геометрическая интерпретация области допустимых решений задачи целочисленного программирования, определяемой двумя линейными ограничениями и условиями неотрицательности переменных, и образующихся при ветвлении подобластей, а на рис. 1-б показана соответствующая схема ветвления. Второй способ ветвления - более универсальный, чем первый. Для осуществления ветвления некоторой области D i " этим способом на D i " решается оптимизационная задача с целевой функцией исходной задачи и действительными переменными. Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j - я. Обозначим ее значение в найденном оптимальном решении x 0 [j]. Говорят, что ветвление осуществляется по переменной x[j]. Область D i " разделяется на две подобласти D i1 " и D i2 " следующим образом: где ] - целая часть значения x 0 [j] На рис. 2 условно дана геометрическая интерпретация такого ветвления. Рис. 2. Геометрическая интерпретация ветвления Видно, что при этом из области D i " удаляется часть между плоскостями вновь введенных ограничений. Так как переменная x[j] по условиям области допустимых решений исходной задачи - целочисленная, то из подобласти допустимых решений исходной задачи. D i (D i D i ") при таком изъятии не исключается ни одного решения. 2.2 Формирование нижних и верхних оценок целевой функции
Прежде чем начать обсуждение данного вопроса, необходимо сказать, что общепринятым является применение метода ветвей и границ для задачи, в которой направление оптимизации приведено к виду минимизации. Для компактности дальнейших обозначений и выкладок запишем задачу дискретного программирования, для которой будем применять метод ветвей и границ, в следующей обобщенной форме: где х - вектор оптимизационных переменных, среди которых часть действительных, а часть целочисленных; f(x) - в общем случае нелинейная целевая функция; D - область допустимых решений задачи дискретного программирования общего вида. Нижние оценки целевой дикции в зависимости от выбранного способа ветвления могут определяться либо для подобластей D i D либо для подобластей D i " D" (D i " и D" получены из соответствующих множеств D i и D путем снятия условий целочисленности на дискретные переменные). Вычисление нижних оценок в каждом конкретном случае может осуществляться с учетом особенностей решаемой задачи. При этом чтобы оценки наиболее эффективно, выполняли свою функцию, они должны быть как можно большими, т.е. быть как можно ближе к действительным значениям min f(x). Это необходимо в первую очередь для того, чтобы нижние оценки как можно точнее отражали действительное соотношение min f(x) на образовавшихся при ветвлении подмножествах и позволяли более точно определять направление дальнейшего поиска оптимального решения исходной задачи. На рис. 3 показан такой идеальный случай, когда нижние оценки (соединены ломаной штрихпунктирной линией) правильно отражают соотношения между действительными минимальными значениями f(x) (соединены штриховой линией) для четырех подмножеств допустимых решений D 1 , D 2 , D 3 , D 4 . Один из универсальных способов вычисления нижних оценок заключается в решении следующей задачи: Определенная таким образом о i является нижней оценкой f(x) на D i (или D i "), так как D i D i ". Если при решении задачи (4) установлено, что, то для общности будем полагать, что. Необходимо отметить одно важное свойство нижних оценок, заключающееся в том, что их значения для образовавшихся при ветвлении подмножеств не могут быть меньше нижней оценки целевой функции на множестве, подвергавшемся ветвлению. Совместно с нижней оценкой в методе ветвей и границ используются верхние оценки f(x). Как правило, вычисляют лишь одно значение верхней оценки, которую определяют как значение целевой функции для лучшего найденного допустимого решения исходной задачи. Такую верхнюю оценку иногда называют рекордом. Если же можно для решаемой задачи достаточно просто и точно получить верхние оценки f(x) для отдельных множеств, образующихся при ветвлении, то их необходимо использовать в методе для уменьшения вычислительной сложности процесса решения. При использовании единой верхней оценки ее первоначальное значение обычно полагают равным бесконечности (), если, конечно, из априорных соображений не известно ни одного допустимого решения исходной задачи. При нахождении первого допустимого решения: Затем при определении более лучшего допустимого решения верхнюю оценку корректируют: Таким образом, значение верхней оценки может лишь уменьшаться в процессе решения задачи. 2.3 Алгоритм метода ветвей и границ
Основные правила алгоритма могут быть сформулированы следующим образом: 1. Ветвлению в первую очередь подвергается подмножество с номером, которому соответствует наименьшее значение нижней оценки целевой функции (I - это множество номеров всех подмножеств, (или), находящихся на концах ветвей и ветвление которых еще не прекращено). Если реализуется изложенный выше способ ветвления множеств, то может возникнуть неоднозначность относительно выбора компоненты, по которой необходимо осуществлять очередной шаг ветвления. К сожалению, вопрос о «наилучшем» способе такого выбора с общих позиций пока не решен, и поэтому в конкретных задачах используются некоторые эвристические правила. 2. Если для некоторого i-го подмножества выполняется условие, то ветвление его необходимо прекратить, так как потенциальные возможности нахождения хорошего решения в этом подмножестве (их характеризует) оказываются хуже, чем значение целевой функции для реального, найденного к данному моменту времени, допустимого решения исходной задачи (оно характеризует). 3. Ветвление подмножества прекращается, если найденное в задаче (4) оптимальное решение. Обосновывается это тем, что, и, следовательно, лучшего допустимого решения, чем в этом подмножестве не существует. В этом случае рассматривается возможность корректировки. 4. Если, где, то выполняются условия оптимальности для найденного к этому моменту лучшего допустимого решения. Обоснование такое же, как и пункта 2 настоящих правил. 5. После нахождения хотя бы одного допустимого решения исходной задачи может быть рассмотрена возможность остановки работы алгоритма с оценкой близости лучшего из полученных допустимых решений к оптимальному (по значению целевой функции): 2.4 Решение задачи методом ветвей и границ
Целые .
Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи. Если среди компонент плана имеются дробные числа, то необходимо осуществить переход к новым планам, пока не будет найдено решение задачи. Метод ветвей и границ основан на предположении, что наш оптимальный нецелочисленный план дает значение функции, большее, чем всякий последующий план перехода. Пусть переменная в плане - дробное число. Тогда в оптимальном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования -
целые .
Целые .
Возможны четыре случая при решении этой пары задач: 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции дают решение исходной задачи. 2. Одна из задач неразрешима, а другая имеет нецелочисленный оптимальный план. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу и строим две задачи, аналогичные предыдущим. 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение. 4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. И строим две задачи. Таким образом, при решении задачи получаем схему: 1. Находим решение задачи линейного программирования без учета целочисленности. 2. Составляет дополнительные ограничения на дробную компоненту плана. 3. Находим решение двух задач с ограничениями на компоненту. 4. Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи. Пример
Найдем решение задачи Целые .
Решение. Находим решение без учет целочисленности задачи симплексным методом.
Рассмотрим следующую пару задач: Задача №1 изадача №2 Первая задача имеет оптимальный план вторая - неразрешима. Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи: Задача №1.1 и задача №1.2 Задача №1.2 неразрешима, а задача №1.1 имеет оптимальный план, на котором значение целевой функции. В результате получили, что исходная задача целочисленного программирования имеет оптимальный план и. 3.
Решение задачи коммивояжера методом ветвей и границ
Рассмотрим теперь класс прикладных задач оптимизации. Метод ветвей и границ используется в очень многих из них. Предлагается рассмотреть одну из самых популярных задач - задача коммивояжера. Вот ее формулировка. Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей. 3.1 Постановка задачи
Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами - ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра - это длина соответствующей дороги. Путь, который требуется найти, это - ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми. Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес Ґ, считая, что Ґ - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом Ґ можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе. Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса. Пусть конкретный состав множества вершин и - весовая матрица данного орграфа, т.е. , причем для любого. Рассмотрение метода ветвей и границ для решения задачи о коммивояжере удобнее всего проводить на фоне конкретного примера. Пользуясь введенными здесь обозначениями, мы проводим это описание в следующей лекции. Введем некоторые термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется ноль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеют слова привести столбец матрицы. Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам. Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам. Весом элемента матрицы называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на Ґ. Следовательно, слова самый тяжелый нуль в матрице означают, что в матрице подсчитан вес каждого нуля, а затем фиксирован нуль с максимальным весом. Приступим теперь к описанию метода ветвей и границ для решения задачи о коммивояжере. Первый шаг
. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M 1 ; таким образом, итог первого шага: множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M 1 . Второй шаг.
Выберем в матрице M 1 самый тяжелый нуль; пусть он стоит в клетке; фиксируем ребро графа и разделим множество G на две части: на часть, состоящую из обходов, которые проходят через ребро, и на часть, состоящую из обходов, которые не проходят через ребро. Сопоставим множеству следующую матрицу M 1,1: в матрице M 1 заменим на Ґ число в клетке. Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M 1,1 ; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j(), сопоставим множеству. Теперь множеству тоже сопоставим некую матрицу M 1,2 . Для этого в матрице M 1 заменим на Ґ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M 1,2 . Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(), сопоставим множеству. Теперь выберем между множествами и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j() и j()). Заметим теперь, что в проведенных рассуждениях использовался в качестве исходного только один фактический объект - приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить. При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на Ґ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра. К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно. Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказываются выполненными все условия, обсуждавшиеся при описании метода ветвей и границ. После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа. 3.2 Условие задачи
Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице 3.3 Математическая модель задачи
Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус - 1, Белый дом - 2, КРК «Премьер» - 3, Администрация - 4 и 5-ый корпус - 5. Соответственно общее количество пунктов. Далее введем альтернативных переменных, принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9). Для обеспечения непрерывности маршрута вводятся дополнительно n
переменных и дополнительных ограничений (10). Суммарная протяженность маршрута F
, которую необходимо минимизировать, запишется в следующем виде: В нашем случае эти условия запишутся в следующем виде: 3.4 Решение задачи методом ветвей и границ
задача коммивояжер ветвь граница 1) Анализ множества D.
Найдем оценку снизу Н
. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке). Аналогично определяем матрицу минимальных расстояний по столбцам. Выберем начальный план: . Тогда верхняя оценка: Очевидно, что, где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку. 2) Анализ подмножества D
12 .
3) Анализ подмножества D
13 .
4) Анализ подмножества D
14 .
5) Анализ подмножества D
15 .
6) Отсев неперспективных подмножеств.
Подмножества D 13 и D 15 неперспективные. Т.к. , но, то далее будем рассматривать подмножество D 14 . 7) Анализ подмножества D
142 .
8) Анализ подмножества D
143 .
9) Анализ подмножества D
145 .
10) Отсев неперспективных подмножеств
Подмножество D 143 неперспективное. Т.к. , но, то далее будем рассматривать подмножество D 145 . 11) Анализ подмножества D
1452 .
12) Анализ подмножества D
1453 .
Оптимальное решение: . Таким образом, маршрут студента: 12-ый корпус - Администрация - 5-ый корпус - Белый дом - КРК Премьер - 12-ый корпус. Список литературы
1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. - Л.: Изд-во ЛГУ, 1981. -328 с. 2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987. -294 с. 3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с 4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. - 2-е изд., перераб и доп. - М.: Высшая школа, 1980. -300 с. 5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. -213 с. Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление. задача , добавлен 24.07.2009 Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера. контрольная работа , добавлен 07.06.2011 Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма. курсовая работа , добавлен 30.04.2011 Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи. курсовая работа , добавлен 18.06.2011 Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству. контрольная работа , добавлен 12.06.2011 Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик. реферат , добавлен 09.10.2012 Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента. контрольная работа , добавлен 27.11.2011 Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи. курсовая работа , добавлен 08.10.2015 Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ. курсовая работа , добавлен 25.11.2011 Последовательность решения линейной краевой задачи. Особенности метода прогонки. Алгоритм метода конечных разностей: построение сетки в заданной области, замена дифференциального оператора. Решение СЛАУ методом Гаусса, конечно-разностные уравнения. Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи. Алгоритм решения: Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X 0 . Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Если же среди компонент плана X 0 имеются дробные числа, то X 0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X 0) F(X) для всякого последующего плана X. Предполагая, что найденный оптимальный план X 0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X 0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования: Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев: Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II). 4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II). Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным. Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы: Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод. целочисленный программирование задача коммивояжер ранец Общая идея метода может быть описана на примере поиска минимума функции на множестве допустимых значений переменной . Функция и переменная могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ). Процедура ветвления
состоит в разбиении множества допустимых значений переменной на подобласти (подмножества) меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево , называемое деревом поиска
или деревом ветвей и границ
. Узлами
этого дерева являются построенные подобласти (подмножества множества значений переменной ). Процедура нахождения оценок
заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной . В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти , то может быть исключена из дальнейшего рассмотрения (правило отсева
). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную ; любой узел дерева поиска, нижняя граница которого больше значения , может быть исключен из дальнейшего рассмотрения. Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. Метод используется для решения некоторых NP-полных задач, таких как: Wikimedia Foundation
.
2010
.
метод ветвей и границ
- — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва] Тематики электротехника, основные понятия EN branch and bound method … Справочник технического переводчика
метод
- метод: Метод косвенного измерения влажности веществ, основанный на зависимости диэлектрической проницаемости этих веществ от их влажности. Источник: РМГ 75 2004: Государственная система обеспечения еди … Словарь-справочник терминов нормативно-технической документации
Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия
У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия
Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной. Задача о ранце (рюкзаке) (англ. … Википедия
Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
max,
7, x 1
0,
10, x 2
0.
(min – «-»;max– «+»).
(k) (z (k) –x (k)),
где
(k) – шаг, коэффициент, 0 
1.
(k) выбирается так, чтобы значение функции
F(x) было max (min) в точке х (k +1) .
Для этого решают уравнение
и
выбирают наименьший (наибольший) из
корней, но 0 
1.
или grad F(x (k +1))
= 0, то решение найдено;
max,
4, x 1
0,
2, x 2
0.
max(min),
b i , i
=
, x j
0, j =
.
,
-
некоторые положительные Const.
,
тем быстрее находится решение, однако,
точность снижается;
и увеличивают их на последующих шагах.
и
.
.
Допустимой
области, проверяют:
-
решение найдено, если нет – переход к
п. 2.
Допустимой области, задают новое значение
и
переходят к п. 4.
max,
8, x 1
0, x 2
0.
можно использовать один из методов
одномерной оптимизации. Можно и просто
двигаться в направлении, противоположном
градиенту, делая при этом не один шаг,
а несколько шагов до тех пор, пока целевая
функция не перестанет убывать. В найденной
новой точке снова определяют направление
спуска (с помощью градиента) и ищут новую
точку минимума целевой функции и т. д.
В этом методе спуск происходит гораздо
более крупными шагами, и градиент функции
вычисляется в меньшем числе точек.
Разница состоит в том, что здесь
направление одномерной оптимизации
определяется градиентом целевой функции,
тогда как покоординатный спуск проводится
на каждом шаге вдоль одного из координатных
направлений.
Нижней оценкой целевой функции f(x) на множестве D i (или D i ") будем называть величину:Подобные документы
Общее описание
Применение
См. также
Примечания
Смотреть что такое "Метод ветвей и границ" в других словарях:
Книги