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

Задача целочисленного линейного программирования в общей постановке

Математическая модель включает в себя систему линейных алгебраических ограничений, которые в матричной форме имеют вид (1) -(3):

Ax b, (1)

0 x, (2)

x(i) Z, i=1,2,...,m, (3)

где A nm матрица ограничений задачи, x - m мерный вектор столбец неизвестных, b - n мерный вектор строка правых частей или свободных членов, Z - множество целых чисел.

В качестве критерия оптимальности выберем

F(x)= (c, x) extr. (4)

Здесь c - m мерный вектор коэффициентов целевой функции, (c, x) -скалярное произведение векторов с и x.

Задача (1) - (4) называется задачей целочисленного линейного программирования в общей постановке в матричной форме.

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

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

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

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

Основные понятия метода ветвей и границ.

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

Свойства, связывающие исходную задачу с ее релаксацией:

- если релаксация задачи не имеет решения, то и исходная задача решения не имеет,

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

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

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

Кандидат - задача, для которой необходимо провести процедуру ветвления.

Потомок - подзадача, полученная в результате ветвления кандидата.

Стратегия -порядок выбора задач кандидатов.

Рекорд -значение критерия, соответствующее наилучшему решению, полученному к данному этапу вычислений.

Дата добавления: 2017-02-01; Просмотров: 81; Нарушение авторских прав?; Мы поможем в написании вашей работы!