|
при ограничениях (2.8) Обозначим через O j(sj) оптимальное реш ение j -й задачи (s j= {Sy}). Согласно теореме, величина 70 I (2.9) является оценкой сверху оптимального реш ения исходной задачи. О кончательно получаем следую щ ую ф ормулировку оценочной задачи: определить значения {Sjj}, i = l, n , j = l, m , максимизирую щ ие величину Ф (з) при огранш гениях (2.6). О ценочную задачу назовем двойственной к исходной задаче целочисленного линейного программирования. О боснованием этого названия служ ит следующая интересная связь. Рассмотрим обы чную задачу линейного программ ирования (2.4), (2.5) (без требования целочисленности). Д ля упрощ ения выводов примем, что все параметры системы ограничений — положительные числа. Заметим, что если не требовать целочисленности реш ений, то задача (2.7), (2.8) легко решается. Ее оптимальное решение: Ч / % . если5,уа,^=тах8^/а^, О, если i к. Оптимальное значение величины Ф ,(з J = Ь^ m ax s ^ /a ^ . Обозначим y^ = m a x s ^ /a ^ , j = I,m . Заметим, что для всех q. Увеличим величину Sqj так, чтобы Sqj =у)а(у. Тогда оценочная задача (2.6), (2.9) запишется в следующем виде: определить значения у ] > 0 , j = l,m , м иним изирую щ ие ф ункцию в (у ) = Е Ч у , при ограничениях 2 а , у ^ > с . , 1= 1,п . |
и рассмотрим m задач целочисленного линейного программирования следующего вида: определить целочисленный вектор х, максимизирующий S j(x)= X s(i^i (5.4) при ограничениях (5.5) Обозначим через (sj) оптимальное решение ]»ой задачи (Sj = {Sij}). Согласно теореме 4.1, величина / \ (s)=£® j(sj) j=l (5.6) является оценкой сверху оптимального решения исходной задачи. Окончательно получаем следующую формулировку оценочной задачи: определить {Sjj}, i = l,n , j = l,m , максимизирующие Ф(з) при ограничениях (5.3). Оценочную задачу назовем двойственной к исходной задаче целочисленного линейного программирования. Обоснованием этого названия служит следующая интересная связь. Рассмотрим обычную задачу линейного программирования (5.1)*(5,2) (без требования целочисленности). Для упрощения выводов примем, что все параметры системы ограничений положительные числа. Заметим, что если не требовать целочисленности решений, то задача (5.4)-(5.5) легко решается. Ее оптимальное решение: Ху = Ь, Sg Sqj если — = max— (5.7) 0, если i 7bк. Оптимальная величина (5.4) составит ® j(sj)= bj max— . (5.8) Обозначим Заметим, что s..; У: = m a x -^ , j = l,m . 62 |