рощения выводов примем, что все параметры системы ограничений положительные числа. Заметим, что если не требовать целочисленности решений, то задача (1.5.7), (1.5.8) легко решается. Ее оптимальное решение: Ь ,/а ч . если Бм/а „ = шах Б^/а* , О, если 1 &к. Оптимальное значение величины 0 . ^ ) = Ь; тах э^/а^ . 52 xij = Обозначим у. = т а х з ч/ а ф, ] = 1 ,т . Заметим, что для всех q. Увеличим величину так, чтобы б^ = эда^. Тогда оценочная задача (1.5.6), (1.5.9) запишется в следующем виде: определить значения yj > О, j = l,m , минимизирующие функцию B( y ) = Z bjyj i при ограничениях 2 а , ^ > с (, i = l,п. j Таким образом, в непрерывном случае оценочная задача становится двойственной задачей линейного программирования. Рассмотрим на примере применение метода ветвей и границ для решения задачи целочисленного линейного программирования. Пример. Определить значения x¡ = {0; 1}, i = l,n , максимизирующие функцию Ф (х)= 1 0 x1+8 x2 +6 x3+7 x4 при ограничениях 6Xi+3Х2+2Хз+5Х4 < 1 1 , 3xi+5х2 +6 х3 +Зх4 <11. Для построения оценочных задач возьмем Sn = ал, s¡2 —c¡-a¡i, i = 1,4. Получаем две задачи о ранце. Задача 1. |
является оценкой сверху оптимального решения исходной задачи. Окончательно получаем следующую формулировку оценочной задачи: определить значения {sjj}, i = l,n , j = l,m , максимизирующие величину Ф(э) при ограничениях (2.6). Оценочную задачу назовем двойственной к исходной задаче целочисленного линейного программирования. Обоснованием этого названия служит следующая интересная связь. Рассмотрим обычную задачу линейного программирования (2.4), (2.5) (без требования целочисленности). Для упрощения выводов примем, что все параметры системы ограничений положительные числа. Заметим, что если не требовать целочисленности решений, то задача (2.7), (2.8) легко решается. Ее оптимальное решение: Ъ ,/а ц , если Sy/atj -m a x s ^ /a ^ , О, если i * к. Оптимальное значение величины O j(sj)= b. m axs^/a^ . х« = Обозначим y i = maxSqj/a^, j = l,m . Заметим, что y ^ s ^ / a ^ для всех q. Увеличим величину Sqj так, чтобы Sqj = yjaqj. Тогда оценочная задача (2.6), (2.9) запишется в следующем виде: определить значения yj >0, j = l,m , минимизирующие функцию В(у) = 1 Ь ,у , j при ограничениях 2 а уУ. С,*) 1= 1,п. j Таким образом, в непрерывном случае оценочная задача становится двойственной задачей линейного программирования. Рассмотрим на примере применение метода ветвей и границ для решения задачи целочисленного линейного программирования. Пример. Определить значения X j= {0;l}, i = l,n , максимизирующие функцию Ф (х)= 10х(+8х2+6х3+7х4 при ограничениях 6х1+3хг+2хз+5х4 <11, 3х1+5х2+6хз+3х4 ^11. Для построения оценочных задач возьмем S;i = ац, 8й = С1а п, i = 1,4. Получаем две задачи о ранце. |