|
Согласно втором у способу решается задача линейного программирования без требования целочислепности. Рассмотрим простой П р и м е р . Определить значения Xj = {0; 1}, i = 1, 2 м аксим изирую щ ие ф ункцию ф(х) = 4 2 x i+ 14x2 при ограничениях ЗХ] + 4x2 ^ 6 5 xi + 2x2 < 6 Получим оценку методом сетевого программирования. Для этого достаточно положить Зц = 42, 32= 14, Si2 = S22 = 0. Решение первой оценочной задачи Xj = 1, Х2 = О, ф1 = 42 является допустимы м для второй задачи и, следовательно, оптимально. П олучим оценку, решая нецелочисленную задачу линейного програм м ирования. Ее решение x i= 6/7;х2 = б/7;ф „ =48 > 42. К а к видим, оценка сущ ественно хуже. 2.3. М о д ел ь опред ел ения о п т и м а л ь н ы х объем ов о п е р а ц и й П од операцией будем понимать процесс, описываемый уравнением h ( t) = d x ( x ) / d t = f [ u ( t ) ] , (1) где h (t) — ско ро сть (и н те н с и в н о с ть ) о пер а ц и и в м о м е н т t (ска л я р ); u (t) — количество ресурсов на операции в мом ент t (вектор); x ( t) — состояние операции в момент t (скаляр). Ф ун кц и я f (и) предполагается, ка к правило, неубы ваю щ ей, непреры вной справа, причем f (0 )= 0 . Будем предполагать, ч то ресурсы у ч а ств ую т в операции в определенном соотнош ении (наборе), т. е. u ( t) = a v ( t) , где с> 0 — заданный вектор. В этом случае зависимость f (и ) м ож но представить в виде /(у ), где V — количество ресурсов (единиц наборов). Начальное состояние операции принимается равным О, конечное — некотором у числу w , которое называется объемом операции. М ом ент окончания операции t количество ресур74 |
Si2= Ci, Sii = 0), TOможно утверждать, что применение метода дихотомического программирования дает лучшие (или такие же) оценки. Во втором способе решается задача линейного программирования без требования целочисленности. Рассмотрим простой пример. Пример 5.2. Определить Х; = {0; 1}, i = 1,2 максимизирующее ф(х) = 42х1 + 14x2 При ограничениях 3x1 + 4x2 ^ 6 5x1 + 2x2 ^ 6 Получим оценку методом дихотомического программирования. Для этого достаточно положить 8ц=42, S2=14, si2= S22= 0. Решение первой оценочной задачи Х = 1, Х2= 0, ф =42 является допустимым для второй задачи и, следовательно, является оптимальным. Получим оценку, решая нецелочисленную задачу линейного программирования. Ее решение Х = -у ; Х2 = ^ ; Ф о = 4 8 > 4 2 Как видим, оценка существенно хуже. Ниже рассмотрим ряд прикладных задач, решаемых методом дихотомического программирования. 2.6. Некоторые обобщения Рассмотрим общую постановку задачи дискретной оптимизации: определить вектор X с дискретными компонентами, обеспечивающий шах ф(х) при ограничении f(x) < Ь Обе функции ф(х) и Дх) допускают дихотомические представления. Однако, эти представления в общем случае разные, что не позволяет применить метод дихотомического программирования. Рассмотрим частный случай, когда обе функции допускают дихотомическое представление типа дерева [30]. Пусть задано дихотомическое представление Gi, имеющее структуру Si. Требуется ответить на вопрос, можно ли реализовать его дихотомическим представлением Ог , имеющим другую структуру S2. Реализация од67 |