|
Все aj такж е делим на 2 части Uy и vy для каж дой верш ины ниж него уровня так, что 4ij + Vjj = ai, для всех i, j . (3.8) Рассмотрим следующие две задачи. З а д а ч а 1. Определить xij так, чтобы максимизировать Е ч л 126 (3.9) > .1 при ограничениях (3.5). З а д а ч а 2. М аксим изировать (3.10) при ограничениях (3.7). Обозначим Sm(u) и Lm (v) оптимальные реш ения первой и второй задач при заданных и и v. О ценочная задача заключается в определении (Пц) и {Vij}, м иним изирую щ их F(u,v)=Sn,(u) + L J y ) (3.11) при ограничении (3.8)1 Заметим, во-первых, что в оптимальных реш ениях первой и второй задач можно принять U ij = У ь V ij = 3 i У ь j = l,m Во-вторы х, решение первой задачи очевидно: S „ ( u ) = 2 ;y , (3.12) j в третьих, решение m вторых задач при заданных {y i} сводится к решению одной задачи о ранце: определить х, = 0 ,1 , м аксим изирую щ ие S x , ( a , y , ) (3.13) При ограничении Z X j a i < T . (3.14) |
92 Обозначим S„,(u) и L„,(v) оптимальные решения первой и второй задач при заданных и и v. Оценочная задача заключается в определении {uy} и [vy , минимизирующих F(u,v)= S Ju) + L „(v) (3.3.11) при ограничении (3.3.8). Заметим, во-первых, что в оптимальных решениях первой и второй задач можно принять «11=У* . Vy = а , у „ j = l,m Во-вторых, решение первой задачи очевидно; s „(x )= 2 ;y , Р-3.12) I В третьих, решение m вторых задач при заданных {yj} сводится к решению одной задачи о ранце: определить х, = 0,1, максимизирующие Е х ,( а ,у ,) (3.3.13) J при ограничении Х х л ^ Т . (3.3.14) Решим задачу (3.3.13) и (3.3.14) при у, =0, 1= 1,п. |