Метод ветвей и границ, Ветку считают тупиковой, если: - Целочисленное программирование

Впервые метод ветвей и границ был предложен Ландом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования (Land A. H., Doig A. G. An automatic method of solving discrete programming problems // Econometrica. V28, 1960).

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

Решается исходная задача ЛП при условии непрерывности переменных.

Если все корни решения нецелочисленны (в обратном случае - оптимальное целочисленное решение найдено), производим ветвление задачи на две, для каждой из задач вводим дополнительные ограничения по одной из переменных xiai, xibi, где ai - наибольшее целое, не превосходящее xi, а bi - наименьшее целое, большее xi, например, при корне исходной задачи x2=2.3 доп. ограничение в одной ветви будет x22, а по другой - x23.

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

Ветку считают тупиковой, если:
    А) допустимое решение очередной задачи ЛП отсутствует; Б) текущее решение (значение целевой функции) хуже уже найденного целочисленного решения; математический программирование алгоритм В) текущая задача ЛП является подзадачей ранее рассчитанной задачи.

Похожие статьи




Метод ветвей и границ, Ветку считают тупиковой, если: - Целочисленное программирование

Предыдущая | Следующая