Книги по разным темам Pages:     | 1 |   ...   | 10 | 11 | 12 | 13 | 14 |   ...   | 26 |

Для =1 и = 2 лемма доказывается элементарными преобразованиями при произвольном > 0. Численные эксперименты подтверждают выполнение леммы при 1 независимо от значения > 0. То есть можно предположить справедливость леммы при 0 < 1, но строго эта гипотеза не доказана.

неравенство f (u) 0 при 1 < u < v. В этом случае f (u) лежит не ниже оси абсцисс, то есть f (u) 0 и неравенство доказано.

Вычислим первую производную:

f (u) = - (u -1) -1u -1 + ((1+ (u -1) / v) -1) -1(1 + (u -1) / v) -1 / v + + ((1 + (v -1) / u) -1) -1(1 + (v -1) / u) -1(v -1) / uМножитель не влияет на знак второй производной. Игнорируя его, вычислим вторую производную и проведем некоторые преобразования. Получим:

f (u) = ( -1)[((1+ (u -1)/ v) -1) -2 (1+ (u -1) / v)2 /(u + v -1)2 - - (u -1) -2 u2 /u2 - ((1+ (v -1) / u) -1) -2 (1+ (v -1) / u)2( -1) (v -1)2 / u4 ] + + ( -1)[ ((1+ (u -1) / v) -1) -1(1+ (u -1)/ v) /(u + v -1)2 - (u -1) -1u /u2 - ((1+ (v -1)/ u) -1) -1(1+ (v -1) / u) -2 (v -1)2 / u4 ] - 2[((1+ (v -1) / u) -1) -1(1+ (v -1) / u) -1(v -1) / u3] Рассмотрим вторую квадратную скобку и первые два ее слагаемых. Выполнено u > 1+ (u -1) / v в силу 1 < u < v. Таким образом, при 1 второе слагаемое по модулю не меньше первого. Третье слагаемое неположительно. То есть неположительна вся вторая квадратная скобка. В силу положительной в выражении для f (u) может быть только первая квадратная скобка. Покажем, что ее первое слагаемое по модулю меньше второго, чем докажем лемму. Соответствующее неравенство имеет вид:

((1+ (u -1) / v) -1) -2 (1+ (u -1) / v)2 /(u + v -1)2 (u -1) -2u2 /uМожно переписать:

((1+ (u -1) / v) -1) -1((1+ (u -1) / v) -1)-1(1+ (u -1)/ v)2 /(u + v -1) (u -1) -1(u -1)-1u2 /uВ силу 1 и u > 1+ (u -1) / v первая скобка слева не превосходит первой справа. Сократим неравенство и проведем некоторые преобразования. Получим:

u -1 (1+ (u -1) / v) -1 u + v - u u2 (1+ (u -1) / v)Проведем замену x = u, y = 1+ (u -1) / v. Тогда 1 < y < x и (u + v -1) / u = (x -1)y /[(y -1)x], получим:

2( -1) (x -1) /[x2( -1) (x -1)2 ] ( y -1) /[y ( y -1)2 ].

Рассмотрим левую часть как функцию g() от x. Справа стоит такая же функция от y. С учетом 1 < y < x осталось показать невозрастание g(x) при x 1. Вычислим производную:

g (x) = [ x3( -1)(x -1)2 - 2( -1)x2( -1)-1(x -1)(x -1)2 - - 2(x -1)x2( -1)(x -1)]/[x2( -1)(x -1)2]2 Сократив в полученном неравенстве знаменатель и множитель (x-1)x2( -1)-1, будем иметь: x (x-1) -2( -1)(x -1)(x-1)-2x(x -1) или x [ (1-x)-2]+2 (x-1)+20. Преобразуем: (x-1)(2-x ) 2(x -1).

Выполнено 2 - x 1, тогда, сократив неравенство, получим (x -1) 2(x -1). Рассмотрим разность правой и левой частей как функцию h() от x. Тогда h(1) = 0 и h (x) = (2x -1 -1) 0 в силу 1 и x 1. Таким образом, h(x) 0, что и доказывает неравенство g (x) 0. Лемма доказана.

Утверждение 2.11. При функционале (III) с функцией сложности вида (2.2) и 1, 11 среди последовательных организаций, в которых второй и последующие элементы расположены в порядке неубывания сложности2, найдется организация, оптимальная на Op ( f ).

Доказательство. Пусть G Op ( f ) - оптимальная на Op ( f ) организация с порядком элементов ai1,,ain, удовлетворяющим условиям леммы 2.2. Обозначим y = C({ai1,, ai j }), j = 1, n.

j Тогда P(G) = (y2 / y1 -1) + + (yn / yn-1 -1). Пусть в G для некоторого j = 2, n -1 имеет место C({ai j }) > C({ai j+1}).

Обозначим x = C({ai j })1/, y = C({ai j+1})1/. Поменяем местами {ai j } и {ai j+1}, чем изменим лишь два слагаемых в P(G). Получим последовательную организацию G. При этом в силу Условия 1 и 1 необходимы лишь для выполнения леммы 2.3. Как отмечено в сноске к формулировке леммы 2.3, она выполнена при =1 и = для любых > 0, что позволяет предположить справедливость леммы при 1 и 0 < 1. Таким образом, выполнение утверждения в этой области является гипотезой.

См. опр. 1.33.

y C({ai j }) > C({ai j+1}) условие леммы 2.2 будет справедливо и j-после перестановки. Тогда можно записать:

= P(G) - P(G ) = (y / y -1) + (y / y -1) - j j-1 j+1 j - ((y1/ 1 + y) / y -1) - ( y /(y1/ 1 + y) -1) j- j -1 j +1 jОбозначим z = y1/ 1, тогда y = (z + x), y = (z + x + y).

j- j j+Условие 0 примет вид:

((z + x) / z -1) + ((z + x + y) /(z + x) -1) ((z + y) / z -1) + ((z + x + y) /(z + y) -1) Обозначим u = 1+ y / z, v = 1+ x / z.1 Тогда 1 u < v и неравенство примет вид:

(v -1) + ((1+ (u -1) / v) -1) ((u -1) + ((1+ (v -1) / u) -1), что выполнено при 1 и 1 в силу леммы 2.3. То есть 0, следовательно P(G ) P(G). Получили оптимальную последовательную организацию, для которой выполнены условия леммы 2.2 и неравенство C({ai j }) C({ai j+1}). Продолжая такие действия, в итоге придем к оптимальной на Op ( f ) организации, в которой второй и последующие элементы расположены в порядке неубывания сложности. Утверждение доказано.

В результате по поводу решения задачи об оптимальной организации одной группы f для функционала (III) можно сделать следующие выводы:

a. Для функции сложности вида (2.2) и 1, 1 найти организацию, оптимальную на Op ( f ), можно следующим образом: поставим на первое место поочередно каждый элемент, остальные расположим в порядке неубывания сложности, выберем из полученных n организаций организацию минимальной стоимости, она и будет искомой (см. утв. 2.11). То есть на Op ( f ) оптимальна одна из n организаций.

b. Функционал - существенно выпуклый при 1 (см. утв. 2.10).

Тогда (см. теор. 1.8) решение на Op ( f ) будет решением и на z > 0 в силу z x > y 0.

~ ~ O( f ), O( f ), Or ( f ), Or ( f ). В силу пункта a) при функции сложности вида (2.2) и 1 задача на этих множествах решается путем сравнения стоимостей n организаций.

По поводу решения задачи об оптимальной организации произвольного набора групп f = { f1,, fm} для функционала (III) можно сделать следующий вывод. Функционал - существенно выпуклый при 1 (см. утв. 2.10), следовательно (см. теор. 1.8) ~ решение задачи на Op (f ) будет решением и на O(f ), O(f ), Or (f ), ~ Or (f ), то есть задача на этих множествах решается с помощью алгоритмов поиска оптимальной последовательной организации (см. гл. IV).

На рис. 2.7 результат утверждения 2.10 изображен схематично. По вертикальной оси отложено значение. Значение, отложенное по горизонтальной оси, никакой роли не играет (результат верен для любой функции сложности) и сохранено для аналогии с рис. 2.5, 2.6. При 1 - область с горизонтальной штриховкой - на O(f ) оптимальна последовательная организация произвольного набора групп f = { f1,, fm} (функционал - существенно выпуклый). Если набор f = { f } состоит из одной группы, то при функции сложности вида (2.2) и 1, 1 на O( f ) оптимальна последовательная организация, в которой элементы, начиная со второго, расположены в порядке неубывания сложности (правая часть графа в области с горизонтальной штриховкой).

Рис. 2.7. Оптимальная организация для функционала (III).

При < 1 - белая область - функционал не является ни выпуклым, ни вогнутым1. Аналитическое решение задачи в этой области на данный момент отсутствует. В пункте 1 з1 главы III (см. рис. 3.2) приведен пример использования алгоритмических методов решения, из которого можно сделать вывод, что в вышеуказанной области оптимальная организация ведет себя сложным образом.

5. Вид оптимальной организации для функционала (IV).

Утверждение 2.12. Функционал (IV) - выпуклый при 1. Доказательство. Рассмотрим произвольный набор групп {g1,, gk } и его разбиение на поднаборы {h1,h2} = {g1, g2} и {h3,, hk } = {g3,, gk }. Обозначим h = h1 h2; y = C(h);

xi = C(gi ), i = 1,k ; x = C(g1 gk ) ; P1 и P2 - соответственно левая и правая части в неравенствах определения 1.30. Тогда P2 = (2y - x1 - x2) + ((k -1)x - y i=3,k xi ), P1 = (kx - i=1,k xi ).

Из (2.3) и 1 следует P2 (2y - x1 - x2 + (k -1)x - y i=3,k xi ).

Для доказательства неравенства P2 P1 достаточно показать, что y + (k -1)x i=1,k xi kx - i=1,k xi. Последнее неравенство имеет вид y x, что выполнено в силу монотонности функции сложности. Утверждение доказано.

Покажем, что функционал (IV), вообще говоря, на является существенно выпуклым при 1. Например, пусть m =1 и необходимо организовать группу f = {a1,, a4}, функция сложности имеет вид (2.2), C(a1) = = C(a4 ) = 1, = 1, = 1.

Тогда стоимость последовательной организации равна 9.

Стоимость дерева, в котором f организуется из промежуточных Можно подобрать сложности, при которых нарушаются оба неравенства в опр.1.30.

При <1 можно подобрать сложности, при которых нарушается неравенство а) в опр. 1.30. То есть утверждение неулучшаемо.

групп {a1, a2} и {a3,a4}, равна 8. Таким образом, функционал (IV) - выпуклый, но не существенно выпуклый (см. теор. 1.8).

Утверждение 2.13. Последовательная организация, в которой элементы расположены в порядке неубывания сложности, оптимальна на Op ( f ) при функционале (IV) с функцией сложности вида (2.2) и = 1.Доказательство. Рассмотрим некоторую организацию G Op ( f ). В G элементы расположены в некотором порядке ai1,,ain. Обозначим g = {ai1,, ai j }, C = C({ai j }), j = 1, n.

j j Тогда P(G) = (2C(g ) - C(g ) - C ) = C(g ) - j j-1 j j j =2,n j =2,n-- C + 2C(gn). От порядка элементов зависит лишь первое j j =1,n слагаемое. При изменении порядка элементов ak и ak +1 слагаемое 1/ 1/ C(gk ) изменится на (C(gk )1/ - Ck + Ck +1 ). Если Ck > Ck+1, то стоимость P(G) уменьшится. Следовательно, оптимальной на Op ( f ) может быть лишь организация, в которой элементы расположены в порядке неубывания сложности. Утверждение доказано.

В результате по поводу решения задачи об оптимальной организации одной группы f для функционала (IV) можно сделать следующие выводы:

a. На Op ( f ) при функции сложности вида (2.2) и = 1 решением будет последовательная организация, в которой элементы расположены в порядке неубывания сложности (см. утв. 2.13), то есть в этом случае задача на Op ( f ) решена аналитически.

b. Функционал выпуклый при 1 (см. утв. 2.12), следовательно ~ ~ решение на D2 ( f ) будет решением и на O( f ), Or ( f ) (см.

следствие 1 к теор. 1.5), то есть задача на этих множествах Возможно, утверждение выполнено и при 1. Однако в общем случае оптимальная на Op ( f ) организация не будет оптимальна на O( f ) и даже на D( f ), что делает неактуальным громоздкое уточнение вида оптимальной последовательной организации.

решается с помощью алгоритмов поиска оптимального 2-дерева (см. гл. III).

c. Если функция сложности имеет вид (2.2) и = 1, = 1, то стоимость организации двух подгрупп для функционалов (II) и (IV) совпадают. Для структурных функционалов искать оптимальное 2-дерево на D2 ( f ) можно среди деревьев без повторяющихся групп (см. теор. 1.7). В таких деревьях каждая неэлементарная группа организуется ровно из двух подгрупп (см. лемму 1.4), то есть на D2 ( f ) функционалы (II) и (IV) равны. Таким образом, функционал (IV), также как и (II), описывает бинарное алфавитное кодирование (см. п.2 з1 и п.з2). Задача на D2 ( f ) решается с помощью алгоритма Хаффмана с порядком сложности n log n (см. п.2 з1). В силу ~ ~ пункта b алгоритм Хаффмана дает решение и на O( f ), Or ( f ).

Априори представляется разумным использовать этот алгоритм и в качестве эвристического при 1 или 1.

Рис. 2.8. Оптимальная организация для функционала (IV).

На рис. 2.8 результат утверждения 2.12 изображен схематично. По вертикальной оси отложено значение. Значение, отложенное по горизонтальной оси, никакой роли не играет (результат верен для любой функции сложности) и сохранено для аналогии с рис. 2.5, 2.6. При 1 - область с перекрестной штриховкой - на O(f ) оптимальна 2-организация произвольного набора групп f = { f1,, fm} (функционал - выпуклый). При < - белая область - функционал не является ни выпуклым, ни вогнутым1. Аналитическое решение задачи в этой области на данный момент отсутствует. В пункте 2 з1 главы III (см. рис. 3.4) приведен пример использования алгоритмических методов решения.

Кратко подведем итоги главы II. В з1 различные частные задачи: оптимальная организация технологического взаимодействия элементов, построение оптимального алфавитного кода, построение оптимальной структуры системы управления сетью доставки материальных потоков и др. сформулированы в терминах задачи оптимизации иерархической структуры. При этом многие задачи (см. п.п.1-4 з1) описываются структурным функционалом стоимости. К таким задачам применимы рассмотренные в данной работе общие методы решения. Вполне естественно, что для конкретных задач могут существовать более эффективные частные методы. Однако универсальность общих методов позволяет проанализировать каждую новую частную задачу Ув первом приближенииФ, а затем при необходимости учитывать ее специфику. В пунктах 4 и 5 з1 приводятся примеры задач с неструктурным функционалом стоимости, что иллюстрирует необходимость дальнейшего изучения общей задачи и в этом случае.

Соответствие выпуклости и вогнутости функционала УклассическимУ определениям выпуклой и вогнутой функции затрат описано в пункте 1 з1.

В пункте 2 з1 приведен пример сведения УклассическойФ задачи дискретной оптимизации, встречающейся в теории кодирования, к общей задаче об оптимальном r -дереве организации. Сложность задачи построения оптимального дерева в общем случае не ограничена полиномом (см. гл. III). Однако пункт 2 з1 показывает, что для конкретного вида функционала (см.

формулу (2.1)) существуют вполне эффективные алгоритмы решения.

В з2 определены так называемые анонимные функционалы стоимости, то есть структурные функционалы, которые зависят не от самих организуемых групп, а от некоторой их характеристики - сложности. Введены понятия однородности (независимости от Можно подобрать сложности, при которых нарушаются оба неравенства в опр.1.30.

масштаба сложности) и корректности в нуле (стоимость добавления подгруппы нулевой сложности нулевая) анонимного функционала. Исходя из возможных содержательных интерпретаций, предложены примеры однородных функционалов (I)-(IV). Функционалы (I), (II) монотонны, (III), (IV) - нет.

Pages:     | 1 |   ...   | 10 | 11 | 12 | 13 | 14 |   ...   | 26 |    Книги по разным темам