Проверяемый текст
Крюков, Сергей Вениаминович; Оптимизационные модели и механизмы корпоративного управления (Диссертация, апрель 2005)
[стр. 51]

Рассмотрим на ряде задач построение оценочной задачи и метод ветвей и границ на основе полученной оценки.
Рассмотрим следующую постановку задачи целочисленного линейного программирования.
Определить целочисленный неотрицательный вектор х=
{хь Х2, ..., Х4}, максимизирующий функцию ф(х) = ЕсХ* (1.5.4) 1*1 при ограничениях Е аах1 ¿ = 1>т (1.5.5) 1 Для построения оценочной задачи разделим С1на шчастей вцтак, что Е 5о = ср ¡ = 1,п (1.5.6) ) ирассмотрим шзадач целочисленного линейного программирования следующего вида: определить целочисленный вектор х, максимизирующий функцию ^(х) = Е 5^ О-5-7)I при ограничениях Е аих( Ь)(1-5-8) I Обозначим через Ф ^) оптимальное решение уй задачи ^ {вд}).
Согласно теореме, величина Ф (з)=1>;У (1.5.9) является оценкой сверху оптимального решения исходной задачи.
Окончательно получаем следующую формулировку оценочной задачи: определить значения
{вд}, 1=1,п, ] = 1,ш, максимизирующиевеличину Ф(в)при ограничениях (1.5.6).
Оценочную задачу назовем двойственной кисходной задаче целочисленного линейного программирования.
Обоснованием этого названия служит следующая интересная связь.
Рассмотрим обычную задачу линейного программирования
(1.5.4), (1.5.5) (без требования целочисленности).
Для уп51
[стр. 94]

оценку снизу для первого подмножества.
Получаем следующее решение: Xi = 1, Х21= 2, Х22—2, Х3= 3 с затратами фо = 31.
Получим оценку снизу для второго подмножества.
Оптимальное решение модифицированной задачи имеет вид: х, = 1,х2= 3, х3= 2 с величиной затрат фо = 32.
Выбираем первое подмножество с минимальной оценкой.
Поскольку полученное решение модифицированной задачи является допустимым для исходной задачи, то оно оптимально.
Рассмотрим на ряде задач построение оценочной задачи и метод ветвей и границ на основе полученной оценки.

Задача целочисленного линейного программирования Рассмотрим следующую постановку задачи целочисленного линейного программирования.
Определить целочисленный неотрицательный вектор х
“ {xi, Х2.......Х4}, максимизирующий функцию ф(х) = £ с , х, (2.4) i-l при ограничениях X a ijx i ^ b j> J = 1»m (2-5) Для построения оценочной задачи разделим Cj на ш частей Sy так, что 5 > и= с р i = 1,п (2.6) j и рассмотрим ш задач целочисленного линейного программирования следующего вида: определить целочисленный вектор х, максимизирующий функцию sj(x ) = E s ex > (2 *7) i при ограничениях X a ijxi bj.
(2.8) i Обозначим через Oj(Sj) оптимальное решение j -й задачи (Sj = {sy}).
Согласно теореме, величина Ф О О = 2 > , У (2 .9 ) i-i 94

[стр.,95]

является оценкой сверху оптимального решения исходной задачи.
Окончательно получаем следующую формулировку оценочной задачи: определить значения
{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.
Получаем две задачи о ранце.

[Back]