semopt8 (Практические занятия)

Занятие 8. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГОЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯМЕТОД ВЕТВЕЙ И ГРАНИЦПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x jj =1≤ bi , i = 1, … , m ;x j ≥ 0 , целые, j = 1, … , n .АлгоритмШаг 1. Положить k = 0 , решить задачу ЗЛП-0 без учета требований на целочис-ленность переменных и определить x 0∗ , f ( x 0∗ ) . Проверить целочисленность решения:а) если решение целочисленное, то расчет закончен: x ∗ = x 0∗ , f ( x ∗ ) = f (x 0∗ );б) если решение x 0∗ нецелочисленное, включить k = 0 в множество J = {k }номеров задач, подлежащих дальнейшему ветвлению, и перейти к шагу 2.Шаг 2. Выбрать задачу для приоритетного ветвления:а) если k = 0 , выбрать для ветвления задачу ЗЛП-0 , исключить номер k = 0 измножества J = {k } и перейти к шагу 3;б) если k ≠ 0 и J ≠ ∅ , выбрать номер задачи k ∈ J , которому соответствует максимальное значение целевой функции на оптимальном решении x k∗ , исключитьномер k из множества J = {k } и перейти к шагу 3;в) если k ≠ 0 и J = ∅ , перейти к шагу 7.Шаг 3.

Осуществить ветвление задачи ЗЛП- k . Для этого выбрать нецелочисленную координату x k∗j по установленному правилу и сформировать:[ ][ ]а) два дополнительных ограничения: x j ≤ x kj ∗ , x j ≥ x kj ∗ + 1 ;б) две задачи ЗЛП- 2k + i , i = 1,2 :ЗЛП- 2k + 1 , получаемую в результате добавления к задаче ЗЛП-k дополни-[ ]тельного ограничения x j ≤ x kj ∗ ;ЗЛП- 2k + 2 , получаемую в результате добавления к задаче ЗЛП-k дополни-[ ]тельного ограничения x j ≥ x kj ∗ + 1 .Положить i = 1 и перейти к шагу 4.Шаг 4. Решить задачу ЗЛП- 2k + i :210а) если множество допустимых решений задачи пустое, то исключить задачу израссмотрения и перейти к шагу 6;б) если множество допустимых решений задачи не пустое, определить()x 2k + i ∗ , f x 2k + i ∗ и перейти к шагу 5.Шаг 5.

Проверить решение x 2k +i ∗ на целочисленность:а) если решение x 2k +i ∗ целочисленное и получено первым при ветвлении задач,имеющих нецелочисленное решение, положить f = f ( x 2k + i ∗ ) и включить решение x 2k +i ∗ во множество X ∗ возможных оптимальных решений исходнойзадачи.Сравнить значения f (x k ∗ ), k ∈ J , с f для нецелочисленных решений, полученных раньше, чем первое целочисленное решение:• если f ( x k ∗ ) ≤ f , исключить номер k из множества J ;• если f ( x k ∗ ) > f , оставить задачу с номером k во множестве J для дальнейшего ветвления;Перейти к шагу 6;б) еслирешениеx 2k +i ∗целочисленное,значениеужеfнайденоиf ( x 2k + i ∗ ) ≥ f , то включить решение x 2k +i ∗ во множество X ∗ возможных оп-тимальных решений исходной задачи. Если f ( x 2k + i ∗ ) < f , не включать решение x 2k +i ∗ во множество X ∗ и перейти к шагу 6;в) если решение x 2k +i ∗ нецелочисленное и значение f еще не найдено, включитьномер 2k + i во множество J и перейти к шагу 6;г) если решениеx 2k +i ∗нецелочисленное, значениеfуже найдено иf ( x 2k + i ∗ ) > f , то включить номер 2k + i в множество J.

В противном случаеисключить номер 2k + i из рассмотрения и перейти к шагу 6;Шаг 6. Проверить условие i ≤ 2 :а) если i < 2 , положить i = 2 и перейти к шагу 4;б) если i = 2 , перейти к шагу 2.Шаг 7. В множестве X ∗ выбрать решение (решения), которому соответствует наибольшее значение целевой функции. Оно является решением x ∗ исходной задачи. Еслимножество X ∗ пустое, то исходная задача не имеет решения.Пример 1. Найти оптимальное решение задачиf (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x 2 ≤ 2,8 , x1 , x 2 ≥ 0, целые.† 1. Положим k = 0 .

Решим ЗЛП-0, т.е. исходную задачу без учета требованияцелочисленности, графически. Как следует из рис. 1, а, максимум достигается в точкеA = x 0∗ = (1,2; 2,8)T , f ( x 0∗ ) = 6,8. Решение не является целочисленным. Включим номерk = 0 во множество J и перейдем к шагу 2.2112 0 . Так как k = 0 , выберем для ветвления задачу ЗЛП-0 , исключим k = 0 измножества J и перейдем к шагу 3.3 0 .

Осуществим ветвление задачи ЗЛП-0. Выберем нецелочисленную координатус наименьшим индексом: x10∗ = 1,2 . Сформируем:а) дополнительные ограничения: x1 ≤ [1,2] = 1 , x1 ≥ [1,2] + 1 = 2 ;б) две задачи ЗЛП- 2k + i , k = 0 ; i = 1,2 :ЗЛП-1ЗЛП-2f (x ) = x1 + 2 x 2 → max,f (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x1 + x 2 ≤ 4,x 2 ≤ 2,8 ,x 2 ≤ 2,8 ,x1 , x 2 ≥ 0, x1 ≤ 1 ;x1 , x 2 ≥ 0, x1 ≥ 2 .x2x2ЗЛП-04x 2 = 2,8A321x 2 = 2,82x1 + x 2 = 41∇f0x1∇f243x1012аx204x 2 = 2,83x 2 = 2,82Dx2 = 2x1 + x 2 = 41∇f1x1 = 13C2x1 + x 2 = 4∇f24ЗЛП-3x2x1 = 243бЗЛП-21ЗЛП-1B3x1 + x 2 = 41x1 = 1434x1в0123г2124x1ЗЛП-4x2x1 = 14x2 = 33x 2 = 2,82X =∅10∇f123x14дРис.

1x1 + x 2 = 4Положим i = 1 и перейдем к шагу 4.4 0 . Решим задачу ЗЛП-1 графически (рис. 1, б). Максимум достигается в точкеx1∗ = B = (1; 2,8) T , f (x 1∗ ) = 6,6 . Перейдем к шагу 5.5 0 . Решение x 1∗ – нецелочисленное, и значение f еще не найдено.

Поэтомувключим номер k = 1 во множество J и перейдем к шагу 6.6 0 . Проверим выполнение условия i ≤ 2 : i = 1 < 2 . Положим i = 2 и перейдемк шагу 4.41 . Решим задачу ЗЛП-2 графически (рис. 1,в). Получим решение в точкеx 2∗ = C = (2; 2) T , f (x 2∗ ) = 6 . Перейдем к шагу 5.51 . Решение x 2∗ – первое целочисленное. Положим f = f ( x 2 ∗ ) = 6. Включимрешениеx 2∗во множествоX ∗ . Сравним значениеf (x 1∗ )сf . Так какf (x1∗ ) = 6,6 > f = 6 , оставим задачу ЗЛП-1 для дальнейшего ветвления и перейдем к шагу 6.61 .

Проверим выполнение условия i ≤ 2 : i = 2 . Перейдем к шагу 2.21 . Имеем k = 1 и J = {1} ≠ ∅ . Выберем задачу ЗЛП-1 для ветвления. Исключимk = 1 из множества J и перейдем к шагу 3.31 . Осуществим ветвление задачи ЗЛП-1. Выберем нецелочисленную координатус наименьшим индексом: x 12∗ = 2,8 . Сформируем:а) дополнительные ограничения: x 2 ≤ [ 2,8] = 2 , x 2 ≥ [2,8] + 1 = 3 ;б) две задачи ЗЛП- 2k + i , k = 1 ; i = 1,2 :ЗЛП-3ЗЛП-4f (x ) = x1 + 2 x 2 → max,f (x ) = x1 + 2 x 2 → max,x1 + x 2 ≤ 4,x1 + x 2 ≤ 4,x 2 ≤ 2,8x 2 ≤ 2,8x1 , x 2 ≥ 0, x1 ≤ 1 ,x1 , x 2 ≥ 0, x1 ≤ 1 ,x2 ≤ 2 ;x2 ≥ 3 .213Положим i = 1 и перейдем к шагу 4.4 2 .

Решим задачу ЗЛП-3 графически. Условный максимум достигается в точкеx 3∗ = D = (1; 2) T , f (x 3∗ ) = 5 (рис. 1,г). Перейдем к шагу 5.5 2 . Решение x 3∗ – целочисленное. Так как значение f уже найдено, то сравнимf (x 3∗ ) = 5 с f . Имеем f ( x 3 ∗ ) = 5 < f = 6 , поэтому не включаем решение x 3∗ в множе-ство X ∗ возможных оптимальных решений исходной задачи. Задачу ЗЛП-3 исключим издальнейшего рассмотрения. Перейдем к шагу 6.61 .

Проверим выполнение условия i ≤ 2 : i = 1 < 2 . Положим i = 2 и перейдем кшагу 4.4 3 . Решим задачу ЗЛП-4 графически. В этой задаче ограничения не совместны(рис. 1,д), множество допустимых решений пустое. Исключим задачу ЗЛП-4 из дальнейшего рассмотрения. Перейдем к шагу 6.6 2 . Проверим выполнение условия i ≤ 2 : i = 2 . Перейдем к шагу 2.2 2 . Так как множество k ≠ 0 и J = ∅ , перейдем к шагу 7.x0∗ЗЛП-0= (1,2; 2,8)Tf (x 0∗ ) = 6,8x1 ≥ 2x1 ≤ 1ЗЛП-2ЗЛП-1x 2∗ = (2; 2) Tx1∗ = (1; 2,8) Tf (x 1∗ ) = 6,6x2 ≤ 2x3∗f (x 3∗ ) = 5f ( x 2∗ ) = 6НЦx2 ≥ 3ЗЛП-4ЗЛП-3= (1; 2)НTЦX =∅Рис.

27 0 . Так как множество X ∗ содержит единственное целочисленное решение, тоx ∗ = x 2∗ = (2, 2) T , f ( x ∗ ) = f = 6 – решение исходной задачи. Процесс решения отраженна рис. 2. ■214.