Решение задачи ЦЛП методом «ветвей и границ»

Одним из основных и наиболее универсальных комбинаторных методов решения задачи ЦЛП является метод «ветвей и границ». Этот метод заключается в пошаговом разбиении всего множества вариантов на ряд подмножеств с их оценкой. Метод ветвей и границ был впервые предложен X.Лэндом и А.Дойгом для решения линейных целочисленных задач и получил название «алгоритм Лэнда и Дойга». Данный алгоритм включает следующие основные этапы.

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

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

1)выбирается переменная, имеющая значение собственной дробной части, наиболее близкое к 0,5;

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

3)переменная выбирается произвольным образом.

После этого формируются два ограничения:

x_j£a_j и x_j³a_j+1 (5.2),

где a_j – целая часть нецелочисленного значения переменной x_j, полученного на предыдущем шаге решения задачи.

Исходная задача с добавленным ограничением x_j£a_j составляет вариант задачи №2, а исходная с добавленным ограничением x_j³a_j+1 - вариант №3.

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

1)выбирается вершина, которой соответствует задача ЛП с наибольшим значением целевой функции в оптимальном решении;

2)вершина выбирается произвольным образом.

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

4.Процесс ветвления и решения задач ЛП продолжается до получения целочисленного оптимального решения одной из задач ЛП. Значение Z в этом решении представляет собой нижнюю границу целевой функции в оптимальном решении исходной задачи ЦЛП. На этом этапе фиксируются все вершины (задачи ЛП), для которых значение Z в оптимальном решении не превосходит полученной нижней границы. Эти вершины называются прозондированными, поскольку области допустимых решений соответствующих им задач ЛП не содержат решений лучших, чем полученное. Естественно, что в дальнейшем ветвлении они не участвуют.

Признаком отсутствия целочисленного решения является наличие признаков несовместности системы ограничений для всех из рассматриваемых на каком-либо шаге вариантов решения задачи ЛП.

5.Выбор вершин для дальнейшего ветвления осуществляется до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим значением Z дает оптимальное решение исходной задачи ЦЛП. Следовательно, эффективность алгоритма существенно зависит от скорости последовательного зондирования вершин.

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

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