Основные этапы решения задачи целочисленного программирования (ЗЦП) методом ветвей и границ

 

Шаг 1. Исходная ЗЦП решается как задача линейного программирования (ЗЛП) (снимаем ограничения вида (г)). При этом за «рекорд» в ЗЦП принимают значение целевой функции, полученное при решении ЗЛП .

Шаг 2. Если все переменные приняли целочисленные значения, то получено оптимальное решение в ЗЦП, уход на шаг 8. Если нет, то в решенной на шаге 1 ЗЛП выбирают одну из переменных, которая приняла нецелочисленное значение. Пусть это будет переменная . Для нее вводят следующие два дополнительных ограничения.

(1),

(2),

где — целая часть нецелочисленного значения переменной , полученной при решении ЗЛП.

Шаг 3. Решаются уже две новые ЗЛП вида (а)–(в) п. 3.5 , в каждой из которых введены по одному дополнительному ограничению (1) и (2). Другими словами, исходная задача ЛП разбивается на две новые ЗЛП (происходит ветвление). Обозначим их соответственно ЗЛП–II и ЗЛП–III. Результаты решения получает , .

Шаг 4. Если в ЗЛП–II получаем целочисленное значение всех переменных, то .

Шаг 5. Если в ЗЛП–III получаем целочисленное значение всех переменных, то .

В том случае, когда в ЗЛП–II и ЗЛП–III получены целочисленные решения, то происходит их сравнение.

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

Шаг 6. Если в сформированных на шаге 3 решения не являются целочисленными, то происходит проверка следующих двух условий

, .

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

Если , , то уход на шаг 7, а ЗЛП вида (II) дальше не решается.

Если , , то уход на шаг 7, а ЗЛП вида (III) дальше не решается.

Шаг 7. Осуществляется проверка все ли нецелочисленные переменные, полученные на шаге 2, просмотрены. Если нет, то формирование новых условий вида (6) в ЗЛП–II и III и переход на шаг 3, если да, то переход на шаг 8.

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

 

Пример.

Решение. В результате решения задачи симплекс-методом найдём оптимальное решение: ; L₁ = 29,5; где верхний индекс переменных – номер задачи.

В полученном решении х₂ = 7,5 – нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Задача 2:

Задача 3:

Результаты решения симплекс-методом задачи 2: ; L₂ = 29,4; задачи 3: ; L₃ = 29,25.

В задаче 1 переменная х₁¹=1 – целочисленная, а в последующих задачах при целочисленности х₂, х₁ перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на х₁ и т.д. (рис.3.6.1).

Рис.3.6.1

Результаты решения непрерывной и целочисленной задачи вводятся в табл.3.6.1. В качестве оптимального принимается решение задачи 5, которое даёт наибольшее из целочисленных решений значение целевой функции.

Таблица 3.6.1

№ задачи	х1	х2	L
		7,5	29,5

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

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

Обязательное условие метода – наличие верхних границ на значения переменных D_j. Если D_j не назначена, то её определяют по зависимости:

,

где - минимальные значения всех х_j, для которых определяется верхняя граница D_j.