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

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

xj £ [xj*] и xj ³ [xj*] + 1,

где [xj*] – целая часть нецелочисленного значения переменной xj* в оптимальном решении, и затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.

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

Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное Lгр. При этом рассмотрение других задач продолжается до тех пор, пока не будет получено:

— На одной из ветвей недопустимое решение.

— На одной из ветвей целочисленное решение. Тогда значение целевой функции сравнивается с Lгр (верхним – при max, нижним – при min); если полученное значение хуже, оно отбрасывается; если – лучше, то принимается за граничное.

— На одной из ветвей нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается.

На первом цикле расчета

.

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