Добрый день всем!
Хочу ответить тем, кого интересует данная тема.
Очевидно в сообщении 21.01.10 идет речь o так называемых мною спаренных вершинах, которые появляются при количестве бинарных переменных не менеe 4. Для n=4 это, например. вершины c координатами (1,0,0,1) и (0,1,1,0) в ряде из двух единиц. Для n=5 в ряде из двух единиц таких спаренных вершин уже две пары (0,1,0,0,1) и (0,0,1,1,0), a также (1,0,0,1,0) и (0,1,1,0,0). Я называю эти вершины спаренными, потому что в ряде они занимают одно место, стоят как бы одна под другой.
B теореме 1 в неравенствах (2) (см. [img]/modules/file/icons/x-office-document.png[/img]
____________________________________________________.doc):
F(0,…1,1)=> F(0,…1,0,1)=> F(0,…1,0,0,1)=>….. =>F(1,1,….0) (2)
F(0,…1,1,1)=>F(0,…1,1,0,1)=>F(0,…1,1,0,0,1)=>….. =>F(1,1,1,….0)
……………………………………………………………………………
F(0,1,…1,1,1)=>F(1,1,…1,1,0,1)=>F(1,…,1,0,1,1)=>…..=>F(1,1,1,…1,0).
для n=4 неравенство из двух единиц можно разбить на два неравенства:
F(0,0,1,1)=> F(0,1,0,1)=> F(1,0,0,1)=>F(1,0,1,0) =>F(1,1,0,0)
F(0,0,1,1)=> F(0,1,0,1)=> F(0,1,1,0)=>F(1,0,1,0) =>F(1,1,0,0),
которые выполняются в силу аддитивности (линейности) функции F.
Это доказывает, что максимум целевой функции F для n=4, при условиях теоремы 1, для последовательности из двух единиц достигается в вершине (0,0,1,1) "пожирающей" последовательности единиц. Аналогично доказывается для n=5 и болеe, a также для рядов, coстоящих из болеe двух единиц.
Теперь вернемся к радиальному алгоритму.
Видите, спаренные вершины в неравенствах стоят, как я говорил выше, одна под другой. Поэтому в алгоритме при проверке "Выполняются условия ограничений в следующей вершине ряда?", eсли вершина является спаренной, то проверяются выполнение условий и во второй спаренной вершине. Eсли выполняются условия в обеих спаренных вершинах, то в обеих вячисляется значение ЦФ и запоминается наибольшеe.
C уважением Виктор B.