Математика \ Методы оптимизации

Дискретное программирование. Задачи дискретного программирования в САПР. Методы решения задач дискретного программирования, страница 7

Этот метод предусматривает замену задачи I последовательностью подзадач I₁, I_2,…, I_n,решаемых на непересекающихся подмножествах, содержащих допустимые целочисленные решения. Такие подзадачи решаются как обычные задачи ЛП при отбрасывании требования целочисленности. При наличии в решении задачи нецелочисленных значений переменных, полученных на определенном шаге, производится так называемое “ветвление” задачи, состоящее в формировании двух новых подзадач, имеющих дополнительное ограничения.

Такие ограничения обычно строятся следующим образом. Пусть одна из нецелочисленных переменных имеет вид: x _k= [b_k] + f_k. Тогда в первую подзадачу вводится ограничение

x _k£ [b_k] , а в другую –

x _k³ [b_k] +1.

(Можно сказать, что в этом случае произведено ветвление задачи по переменной x_k) .

Алгоритм метода предусматривает процедуру последовательного построения ветвлений и решения соответствующих задач ЛП. В результате такой процедуры находится оптимальное решение задачи ЦЛП.

Рассмотрим упрощенный пример решения задачи ЦЛП методом ветвей и границ. Пусть исходная задача имеет вид

max z = 7x₁+3x₂

5x₁+2x₂20;

8x₁+4x₂38; (3.25)

x_1,x₂0 ;

x₁,x₂– целые. (3.26)

Данную задачу без наложения требований целочисленности (задачу (3.25)) назовем задачей 1. В результате решения этой задачи как непрерывной найдем оптимальное решение:

x=1, x=7,5, z₁=29,5 , где верхний индекс у переменных и нижний у целевой функции соответствует номеру задачи. В полученном решении x=7,5, не удовлетворяет требованиям целочисленности.

Произведем ветвление по переменной x₂. Сформируем две новые задачи с ограничениями, исключающими возможность получения нецелочисленного значения х₂=7,5. Такие ограничения имеют вид: х₂7 и х₂8.

Задача 2 :

max z =7x₁+3x₂;