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

Алгоритм метода ветвей и границ представляет собой эффективную процедуру перебора всех целочисленных допустимых решений.

Шаг 1. Решаем сформулированную задачу как задачу ЛП (обозначим ЛП-1), рассматривая все ее переменные как непрерывные. Пусть W₁ - оптимальное значение ее целевой функции. Допустим, в оптимальном решении ЛП-1 некоторые целочисленные переменные принимают дробные значения. Тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае W₁ - верхняя граница оптимального значения W исходной задачи.

В решенном нами примере 9.1 линейного программирования “Оптимизация размещения побочного производства лесничества” верхняя граница соответствует 34 тыс. руб. при x₁=3.6 и x₂=6.4. Очевидно, что переменные x₁ (число откармливаемых бычков) и x₂ (количество выращиваемых партий продукта растениеводства) должны быть целочисленны.

Шаг 2. Производим ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении ЛП-1. Выбор переменной, по которой производим ветвление, осуществляется по ряду правил:

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

· расстановка приоритетов и ветвление по переменным с наибольшим приоритетом (данная переменная представляет важное решение, ее коэффициент стоимости или прибыли в целевой функции существенно превосходит остальные и т.д.);

· Произвольные правила выбора (например, переменную с наименьшим порядковым номером).

В рассматриваемой целочисленной версии примера 9.1 в качестве переменной, по которой будет вестись ветвление, следует рассматривать x₁, т.к. коэффициент стоимости при этой переменной максимален.

Шаг 3. Пусть ветвление происходит по x_i, дробное значение которой в ЛП-1 равно b_i. Далее рассматриваются уже две новые задачи ЛП-2 и ЛП-3, которые образуются путем введения двух дополнительных ограничений x_i£a_i , x_{i ³}g_i, где a_i - наибольшее целое, не превосходящее b_i, g_i - наименьшее целое, большее b_i. Допустим, оптимальные значения ЛП-2 и ЛП-3 содержат дробные значения целочисленных переменных и поэтому не являются допустимыми.

Для рассматриваемого примера b₁=3,6, a₁=3, g₁=4.

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

· использование наибольшего оптимального значения целевой функции;

· “последним пришел - первым вышел”.

Шаг 5. Процесс ветвления и решения задач ЛП продолжаем до получения целочисленного решения одной из задач ЛП. Значение W в полученной точке представляет собой нижнюю границу оптимального значения ЦФ исходной задачи ЦП. На этом этапе все вершины (задачи ЛП), для которых оптимальное значение W не превосходит полученной нижней границы (“прозондированные” вершины). Вершина является прозондированной в следующих случаях:

· оптимальное решение, соответствующее данной вершине, целочисленно;

· задача ЛП не имеет допускаемого решения;

· оптимальное значение W не превосходит текущей нижней границе.

Ветвление происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим W дает оптимальное решение исходной задачи ЦП.

Процесс ветвления и решения рассматриваемой задачи представлен на рис. 10.1. Оптимальное решение - W=32,5 млн. руб.; x₁=4; x₂=5.

Рис. 10.1. Процесс ветвления для примера 9.1 в целочисленной постановке методом ветвей и границ

Date: 2016-07-25; view: 484; Нарушение авторских прав