Модели целочисленного булевого программирования. Алгоритм последовательного анализа вариантов решения

Если прекратить вычисления непосредственно перед тем, как алгоритм сходится (т.е. еще тогда, когда основной список еще не пуст), то можно установить, какая часть из возможных решений подверглась перебору (явному или неявному). Для определения этого показателя после шагов 2 и 3 всякий раз возвращаются к шагу 1, подсчитывая значение дроби , где величина s равна числу переменных, содержащихся в частичном решении на шаге 1. Алгоритм частичного перебора можно модифицировать для решения частично целочисленных задач, в которых только переменные =1, j =1, 2, . . . , р (< n), должны быть равны нулю или единицы, а на остальные переменные наложено ограничение , j = р+1, . . ., n. Частичное решение должно включать только целочисленные переменные, однако к свободным переменным относятся любые переменные, не вошедшие в частичное решение. Проверка (1.9) и (1.10) сохраняются, если не считать того, что проверка (1.10) применяется только к свободным целочисленным переменным. Кроме того, вместо . Наконец, описание шага 5 изменяется следующим образом. Шаг 3. Если (расширенное) решение содержит все р целочисленные переменные, то нужно решить полученную задачу линейного программирования, отыскав тем самым соответствующие оптимальные значения остальных свободных переменных (при этом ограничения задачи линейного программирования формируются с учетом выбранных значений целочисленных переменных, вошедших в частичное решение). Если допустимого решения не существует, то принять = и вернуться к шагу 1. В противном случае необходимо зафиксировать полученное оптимальное решение, принять равным соответствующему оптимальному значению целевой функции и вернуться к шагу 1. Если (расширенное) частичное решение содержит менее р целочисленных переменных, перейти к шагу 4.