|
Таким образом, в непрерывном случае оценочная задача становится двойственной задачей линейного программирования. Рассмотрим на примере применение метода ветвей и грагш ц для реш ения задачи целочисленного линейного программирования. 71 П р и м е р . Определить значения Х = { 0 ;1 } , i = l,n , максим изирую щ ие ф ункцию Ф ( х ) = 10X 1 + 8X2+ 6X3+ 7X4 при ограничениях 6х 1+Зх 2+2хз+ 5 х4 < 1 1 , ЗХ1+5Х2+6хз+ЗХ4 < 11. Для построения оценочны х задач возьмем 5 ц = а ;ь Si2 = C i-a ii, i = l,4 . П о лучаем две задачи о ранце. З а д а ч а 1. ф1 = т а х (6 х + 3 х 2+2 хз+5 х 4), 6 х 1 + З х 2 + 2 х з + 5 х 4 < 1 1 . Она имеет два реш ения; Xi = X4 = 1, хг = хз = О и x i = хг = хз = 1, X4 = 0. В обоих случаях ф1 = 1 1 . З а д а ч а 2. фг = m ax(4 x i+ 5 x 2+4 x 3+ 2 x 4), ЗХ1+5Х2+6Хз+ЗХ4 < 1 1 . Ее решение: Х==Х2 = Х4 = 1 , хз = 0, ф2 = 1 1 . О ценка сверху исходной задачи фо = ф1 +ф2 = 22. Для улучш ения оценки увеличим S21 и S41 на единицу, уменьш ив на единицу S22 и $42. Получаем две новые оценочные задачи. З а д а ч а !. ф] = m a x (6 x i+ 4 x 2+ 2 x 3+ 6 x 4), 6х]+Зх2+2хз+5х4< и . ( 1 0 ) Ее решения; Xi = Х4 = 1, Х2 = Хз = 0; Xi = Х2 = хз = I , Х4 = 0; Хг = Хз = Х4 = 1, Xi = 0; ф, = 1 2 . З а д а ч а 2. фг = т а х ( 4 х 1+4 х 2+ 4 х з+ 1х 4), ЗХ]+5х 2+6хз+Зх4 < П . (11) Ее решение: Х[ = Хг = X4 = I, Хз = 0; ф2 = 9. |
s.,: Vj > — для всех q. Увеличим Sqj так, чтобы ~ yjSqjТогда оценочная задача (5.3), (5.6) запишется в следующем виде: определить У; > О, j = 1 ,т , минимизирующие B (y )= S b jy j (5-9) при ограничениях 2 ]a ijy j> C j, i = l,n . (5.10) j Таким образом, в непрерывном случае оценочная задача становится двойственной задачей линейного программирования. Рассмотрим на примере применение метода ветвей и границ для решения задачи целочисленного линейного программирования. Пример 5.1. Определить xj = {0;1}, i = 1,п , максимизирующие Ф(х) = 10x1+8x2+6x3+7x4 при ограничениях 6х1+Зх2+2хз+5х4<11, ЗХ1+5Х2+6Хз+ЗХ4 <11. Для построения оценочных задач возьмем 5ц = ац, Sj2 = Cj-aii, i = 1,4. Получаем две задачи о ранце. Задача 1. Ф1 = т а х ( 6 х 1 + 3 х 2 + 2 х з + 5 х 4 ) , 6Х+ЗХ2+2Хз+5Х4 < 11. Она имеет два решения: 1)Xi = X4 = l, Х2-Х з = 0, 2)Х1=Х2 = Хз = 1, Х4= 0. В обоих случаях ф = 11. Задача 2. Ф2 = тах(4х+5х2+4хз+2х4), ЗХ+5Х2+6Хз+ЗХ4 < 11. Ее решение: 63 |