Применение метода ветвей и границ к решению задач линейного целочисленного программирования
Рассмотрим задачу ЦЛП в матричной форме записи. Обозначим ОДП этой задачи D, а ОДП ЗЛП без ограничений целочисленности - G. Точно так же обозначим соответствующие системы ограничений, а сами задачи будем называть D-задача и G-задача. max CX D представляет собой часть G. G будем рассматривать в качестве исходного множества (рис.19).
Решим вначале G-задачу. Пусть при решении этой задачи получен оптимальный план ХG. Значение целевой функции на нем zG - оптимум G-задачи - будем использовать в качестве границы . В самом деле, zG СХ Х G; zG СХ Х D. Если план ХG целочисленный, то решение задачи окончено. Таким образом, мы ответили на первый и третий вопросы, конкретизирующие метод ветвей и границ. Предположим, что хотя бы одна компонента ХG не целочисленна: хGi Z. Целой частью числа называют наибольшее целое число, меньшее или равное данному. Обозначим целую часть числа хGi [хGi]. Конкретизируем второй вопрос. Разобьем D на D1 и D2 следующим образом: D1={X D: хi [хGi]}; D2={X D: хi [хGi] + 1} (т.е. к одному множеству отнесли все допустимые планы, у которых i-я компонента не больше целой части хGi, а к другому - у которых не меньше следующего целого числа). Разбивая D, мы одновременно разбиваем и G (рис.20). Это разбиение обладает следующими свойствами: G1 G2 G (объединение этих множеств содержится в G, но не равно ему); D1 D2 = D (в устраненном «коридоре» нет ни одной точки с целочисленными координатами).
При этом устраняется и план ХG. Далее решение задачи продолжается для каждого из подмножеств G1 и G2. Сходимость алгоритма основана на том, что в ограниченной ОДП множество дискретных точек конечно. Следует отметить, что метод ветвей и границ легко обобщается и на частично целочисленные задачи (в качестве переменной, по которой разбивается множество, выбирают одну из тех, на которые наложены ограничения целочисленности).
3.5. Пример решения задачи целочисленного линейного программирования методом ветвей и границ
Требуется решить следующую задачу: max 2х1 + х2 5х1 + 2х2 10 3х1 + 8х2 13 х1,2 0 х1,2 Z Вначале решим эту задачу графически без ограничений целочисленности. Решение может быть найдено как симплекс-методом, так и графически. Найдем его графически (рис.21).
Координаты точки оптимума можно найти, решив систему уравнений: 5х1 + 2х2 = 10 х1=27/17 3х1 + 8х2 = 13 х2=35/34 ХG = (27/17;35/34), zG=143/34. Начнем строить дерево, первая вершина которого будет соответствовать всей ОДП нецелочисленной задачи (G), а ее оценка будет равна zG (рис.22).
Полученный план не является целочисленным, поэтому возьмем его произвольную нецелочисленную компоненту, например, первую (х1 Z; [х1] = [27/17] = 1) и разобьем ОДП на две части следующим образом: G1 = {X G: х1 1}; G2 = {X G: х1 2}. Изобразим это графически (рис.23).
Из рис.6 видно, что G2 представляет собой одну точку ХG2=(2;0), следовательно, на этом множестве оптимум задачи равен 4 ( 2=4). План ХG2 является целочисленным, следовательно, решение целочисленной задачи уже, возможно, найдено. Однако, следует еще найти оценку множества G1. Она может оказаться не менее 4 (но обязательно не более 143/34). Если это так, то нужно проверить, не является ли целочисленным решение задачи на G1. Если оно целое, то является решением задачи, а если нет, то процесс решения необходимо продолжить, разбивая G1. На G1 точку оптимума можно найти, решив систему уравнений: х1 = 1 х1=1 3х1 + 8х2 = 13 х2=5/4 ХG1 = (1; 5/4), zG1=13/4. Оценка меньше 4, следовательно, решением задачи является Х*=ХG2=(2;0),z*=4.
Для задачи с булевыми переменными алгоритм метода ветвей и границ будет тот же, но разбиение проводится по первой по счету переменной, значение которой не равно 0 или 1. На одном подмножестве эта переменная приравнивается 1 (эта ветвь рассматривается вначале), а на другом - нулю. Следует отметить, что для таких задач разработан более эффективный алгоритм решения (так называемый аддитивный), также основанный на методе ветвей и границ. В нем обычно требуется меньшее число итераций, а кроме того, и расчеты на каждой итерации являются менее трудоемкими, не требуют применения симплекс-метода.
Вопросы и упражнения
1. Как ставится задача целочисленного линейного программирования? 2. Какие существуют подходы к решению такой задачи? 3. В чем заключается идея метода ветвей и границ? 4. Как применяется этот метод к задаче целочисленного линейного программирования? 5. Как применяется этот метод (в ППП QSB) к задачам с булевыми переменными? 6. Решить методом ветвей и границ (и проиллюстрировать решение построением дерева) задачу max 3х1 + 2х2 7х1 + 5х2 35 9х1 + 4х2 36 х1,2 0 х1,2 Z
|