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

Процедура оценок.

Рассмотрим задачу целочисленного линейного программирования в общей постановке в матричной форме.

Ax b, (1)

0 x, (2)

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

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

Не уменьшая общности, будем считать, что все коэффициенты задачи целочисленные.

Пусть x - оптимальное решение исходной задачи, y - m мерный вектор, оптимальное решение задачи линейного программирования (1), (2), (4), которая естественно является релаксацией для исходной целочисленной задачи линейного программирования.

Пусть рассматриваемая задача является задачей на максимум (extr = max).

Тогда в качестве верхней оценки выбирается величина

V=F(с, y), а точнее целая часть этой величины.

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

Процедура ветвления.

Если среди компонент вектора y нет дробных, то в этом направлении ветвление прекращается, т.к. лучшее решение в этом направлении исходной задачи определяется целочисленным вектором y. Пусть y(i) - некоторая дробная компонента. Ветвление происходит в направлении этой компоненты следующим образом. Пусть y(i) = [y(i)] + {y(i)}, где [s] - целая часть числа s, а {s} - дробная часть числа s. Тогда подзадачами, порожденными этим направлением, будут две задачи линейного программирования, к исходным ограничениям первой из которых добавляется ограничение

x(i) [y(i)],

а к исходным ограничениям второй задачи добавляется ограничение

[y(i)] + 1 x(i).

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