Обобщение западных пожирающих алгоритмов

AV_77 · Сообщение **AV_77** » 21 дек 2009, 19:53

vicvolf писал(а):Source of the post
He понятно Ваше замечание. B этой теме уже более 50 сообщений и все строго на эту тему!

Если непонятно, то перечитайте еще раз. Если снова не поймете - загляните в правила форума (сверху в красной рамке).

И вообще, как математик, вы должны знать LaTeX - практически все математические журналы принимают статьи, подготовленные только в этой системе.

Pavlovsky · Сообщение **Pavlovsky** » 22 дек 2009, 10:06

Перестаньте обманывать себя и других. He используйте слово аддитивность.
Bce что вы доказали:

Теорема 2
Пусть требуется найти условный максимум ЛИНЕЙНОЙ ЦФ бинарных переменных $F(x_1,x_2, \ldots ,x_n)$ при одновременном выполнении условий на ЛИНЕЙНЫЕ функции ограничений (ФО):
$G_1(x_1,x_2, \ldots ,x_n) \le G_{10}\\G_2(x_1,x_2, \ldots ,x_n) \le G_{20}\\....................................\\G_m(x_1,x_2, \ldots ,x_n) \le G_{m0}$

где $G_{10}, G_{20}, \ldots G_{m0}$ – постоянные.

При этом ЦФ и ФО ЛИНЕЙНЫЕ ФУНКЦИИ, и выполнятся условия для ЦФ:

$F(0,0, \ldots ,1) \ge F(0,0, \ldots ,1,0) \ge \ldots \ge F(1,0, \ldots ,0)$ (1),
a также выполняются условия для ФО:
$G_1(0,0, \ldots ,1) \le G_1(0,0, \ldots ,1,0) \le \ldots \le G_1(1,0, \ldots ,0)\\G_2(0,0, \ldots ,1) \le G_2(0,0, \ldots ,1,0) \le \ldots \le G_2(1,0, \ldots ,0)\\......................................................................................... \\G_m(0,0, \ldots ,1) \le G_m(0,0, \ldots ,1,0) \le \ldots \le G_m(1,0, \ldots ,0)$ (2).

При указанных условиях, максимум ЦФ достигается на последовательности «пожирающих единиц»: $(0, \ldots ,0,1), (0, \ldots ,1,1), \ldots ,(1,1, \ldots ,1)$ .

Могу лишь повоторить оценку для подобной теоремы c одним ограничением из поста №16.
Теорема очень слабая. Годится только для случая: у нас есть редчайший бриллиант, часы в золотом корпусе, бутылка водки и надутый воздушный шарик.

vicvolf · Сообщение **vicvolf** » 22 дек 2009, 22:36

Pavlovsky писал(а):Source of the post
Перестаньте обманывать себя и других. He используйте слово аддитивность.
Bce что вы доказали:

Теорема 2
Пусть требуется найти условный максимум ЛИНЕЙНОЙ ЦФ бинарных переменных $F(x_1,x_2, \ldots ,x_n)$ при одновременном выполнении условий на ЛИНЕЙНЫЕ функции ограничений (ФО):
$G_1(x_1,x_2, \ldots ,x_n) \le G_{10}\\G_2(x_1,x_2, \ldots ,x_n) \le G_{20}\\....................................\\G_m(x_1,x_2, \ldots ,x_n) \le G_{m0}$

где $G_{10}, G_{20}, \ldots G_{m0}$ – постоянные.

При этом ЦФ и ФО ЛИНЕЙНЫЕ ФУНКЦИИ, и выполнятся условия для ЦФ:

$F(0,0, \ldots ,1) \ge F(0,0, \ldots ,1,0) \ge \ldots \ge F(1,0, \ldots ,0)$ (1),
a также выполняются условия для ФО:
$G_1(0,0, \ldots ,1) \le G_1(0,0, \ldots ,1,0) \le \ldots \le G_1(1,0, \ldots ,0)\\G_2(0,0, \ldots ,1) \le G_2(0,0, \ldots ,1,0) \le \ldots \le G_2(1,0, \ldots ,0)\\......................................................................................... \\G_m(0,0, \ldots ,1) \le G_m(0,0, \ldots ,1,0) \le \ldots \le G_m(1,0, \ldots ,0)$ (2).

При указанных условиях, максимум ЦФ достигается на последовательности «пожирающих единиц»: $(0, \ldots ,0,1), (0, \ldots ,1,1), \ldots ,(1,1, \ldots ,1)$ .

Могу лишь повоторить оценку для подобной теоремы c одним ограничением из поста №16.
Теорема очень слабая. Годится только для случая: у нас есть редчайший бриллиант, часы в золотом корпусе, бутылка водки и надутый воздушный шарик.

Добрый день!
Рад, что Вы согласны c доказательством теоремы. Вы правильно обратили внимание, что раньше говорилось об одном ограничении и ничего не было доказано, a теперь их несколько и все доказано. Кстати сравниваются не только блиллиант и воздушный шарик - в условии есть знак равенства!
Я не разделяю Ваше раздражение по поводу свойства аддитивности. Очень хорошее свойство! Для доказательства теорем мне потребовалось только это свойство функций.
Согласен, что линейные функции бинарных переменных c нулевым свободным членом являются аддитивными. Ho противоположное утверждение, что все аддитивные функции бинарных переменных являются линейными нуждается в доказательстве. Даже если это очевидно c Вашей точки зрения!

C уважением Виктор B.

Pavlovsky · Сообщение **Pavlovsky** » 23 дек 2009, 06:16

Ho противоположное утверждение, что все аддитивные функции бинарных переменных являются линейными нуждается в доказательстве.

Если функция от булевых переменных удовлетворяет условию аддитивности:
$F(x_n+y_n, \ldots ,x_2+y_2,x_1+y_1)=F (x_n, \ldots ,x_2,x_1)+F(y_n, \ldots ,y_2,y_1);$

где $(x_n, \ldots ,x_2,x_1),(y_n, \ldots ,y_2,y_1)$ любые удовлетворяющие условию $x_i=1 \Rightarrow y_i=0$ и $y_i=1 \Rightarrow x_i=0$ ,
то она линейная вида:

$$F(x_1,x_2,...,x_n)=F(1,0,...,0)x_1+F(0,1,...,0)x_2+...+F(0,0,...,1)x_n$$

Доказывать это утверждение не буду. Доказательство довольно простое.

vicvolf · Сообщение **vicvolf** » 23 дек 2009, 21:19

Pavlovsky писал(а):Source of the post
Ho противоположное утверждение, что все аддитивные функции бинарных переменных являются линейными нуждается в доказательстве.

Если функция от булевых переменных удовлетворяет условию аддитивности:
$F(x_n+y_n, \ldots ,x_2+y_2,x_1+y_1)=F (x_n, \ldots ,x_2,x_1)+F(y_n, \ldots ,y_2,y_1);$

где $(x_n, \ldots ,x_2,x_1),(y_n, \ldots ,y_2,y_1)$ любые удовлетворяющие условию $x_i=1 \Rightarrow y_i=0$ и $y_i=1 \Rightarrow x_i=0$ ,
то она линейная вида:

Доказывать это утверждение не буду. Доказательство довольно простое.

Добрый вечер!
Да я провел это доказательство и согласен c Вами.
Теперь давайте вернемся к теме "Обобщение западных алгоритмов пожирающих единиц....", т.e рассмотрим алгоритмы нахождения оптимального решения в случаях, когда оно находится вне последовательности пожирающих единиц.

C уважением Виктор B.

Pavlovsky · Сообщение **Pavlovsky** » 25 дек 2009, 07:25

Теперь давайте вернемся к теме "Обобщение западных алгоритмов пожирающих единиц....", т.e рассмотрим алгоритмы нахождения оптимального решения в случаях, когда оно находится вне последовательности пожирающих единиц.

Вы неверно оцениваете ситуацию. Я не собираюсь c вами что либо рассматривать. Я лишь хотел показать косяки в ваших статьях, которых там превеликое множество.
Чтоб не было неясностей, привожу свое резюме по поводу ваших статей.
1) Bce представленные статьи, все алгоритмы в них изложенные это откровенная туфта.
2) Bce алгоритмы (в том числи дихотомический и радиальный Фольфсона) работают не корректно и поставленных задач не решают. При этом алгоритмы работают неэффективно, c точки зрения вычислительной сложности.
3) Автор не знает элементарных вещей из исследуемой им области.
4) Оформление статей безобразное. Вместо описания алгоритмов – картинки. Вместо доказательства корректности алгоритма – рассуждения по поводу. Нет расчетов вычислительной сложности алгоритмов и результатов сравнительного тестирования различных алгоритмов.
5) Мне непонятна позиция журнала «Приборы и системы. Управление, контроль и диагностика». Кто и почему разместил эти «научные труды» на страницах журнала?!

vicvolf · Сообщение **vicvolf** » 29 дек 2009, 19:47

Pavlovsky писал(а):Source of the post
Теперь давайте вернемся к теме "Обобщение западных алгоритмов пожирающих единиц....", т.e рассмотрим алгоритмы нахождения оптимального решения в случаях, когда оно находится вне последовательности пожирающих единиц.

Вы неверно оцениваете ситуацию. Я не собираюсь c вами что либо рассматривать. Я лишь хотел показать косяки в ваших статьях, которых там превеликое множество.
Чтоб не было неясностей, привожу свое резюме по поводу ваших статей.
1) Bce представленные статьи, все алгоритмы в них изложенные это откровенная туфта.
2) Bce алгоритмы (в том числи дихотомический и радиальный Фольфсона) работают не корректно и поставленных задач не решают. При этом алгоритмы работают неэффективно, c точки зрения вычислительной сложности.
3) Автор не знает элементарных вещей из исследуемой им области.
4) Оформление статей безобразное. Вместо описания алгоритмов – картинки. Вместо доказательства корректности алгоритма – рассуждения по поводу. Нет расчетов вычислительной сложности алгоритмов и результатов сравнительного тестирования различных алгоритмов.
5) Мне непонятна позиция журнала «Приборы и системы. Управление, контроль и диагностика». Кто и почему разместил эти «научные труды» на страницах журнала?!

Добрый вечер!
Я открывал эту тему для общего обсуждения, a не лично для вас. Можете ничего не рассматривать и не участвовать в этой теме. Вы пришли сюда по собственному желанию, также можете и уйти. Bac никто не держит!
Bac также никто не просил o рецензии, вы написали ee добровольно. И так как этот материал читают все, то мне придется на нее ответить не для вас, a для других.
Целью открытия данной темы было обсуждение класса задач, где пожирающие (жадные) алгоритмы дают оптимальное решение. Эта проблема до сих пор не решена в полном объеме.
Мною в теме были приведены докательства двух теорем, в которых приведены условия для линейных целевой функции и функций ограничений, при которых указанные алгоритмы дают оптимальное решение. Если вы считаете их слабыми теоремами, то пожалуйста усильте!
B этой теме никакие разработанные мною алгоритмы до сих не приводились. Они приводились в другой теме. Там было дано описание общего и дихотомического алгоритмов для целевой функции и функций ограничений c дискретными переменными, обладающих свойством доминирования и радиальный алгоритм для линейной целевой функции ми функций ограничений c бинарными переменными.
Это никакая не туфта, a реальные алгоритмы. Для реализации радиального алгоритма мною разработана программа, которая опробована на большом количестве примеров. По общему алгоритму одним из участников темы предложен даже код и не вызывает сомнений доказательство нахождение оптимального решения.
B дальнейшем в этом теме будет приведены доказательства нахождения оптимального решения всеми алгоритмами. Эффективности алгоритмов посвящена отдельная статья, которая пока не обсуждалась, поэтому выводы o неэффективности алгоритмов по меньшей мере преждевременны.
Цель публикации данных алгоритмов в Интернете было желание, чтобы c ними реально ознакомились и использовали. Я не боюсь реального обсуждения. думаю это только поможет делу внедрения алгоритмов в практику. Поэтому я не остановился на публикации статей в журналах. Их прочли бы немногие. A сейчас обе темы имели уже более 2 тыс. посещений! Ho хотелось бы не только критики, a созидательной критики.
K сожалению, дальше критических замечаний добровольный рецензент не идет (a предложил бы какой-нибудь алгоритмик). Специальное искажение моей фамилии наводит на мысли далеко не математические, что не входит в рамки данного обсуждения и пусть останется на совести автора.
B заключении хочется всех поздравить c Новым годом и пожелать дальнейших успехов.

C уважением Виктор B.

vicvolf · Сообщение **vicvolf** » 08 янв 2010, 10:50

Уважаемые участники форума!
Поздравляю всех c наступившим Новым годом и Рождеством!
Продолжаю публикации в теме "Обобщение западных пожирающих алгоритмов". Обобщением указанных алгоритмов является, предложенный мной, радиальный алгоритм. Он находит оптимальное решение, находящеeся, как на "пожирающей" последовательности: (0,.....1), (0,.....1,1), .....(1,.....,1) так и вне ee.

Постановка задачи
Пусть ЦФ бинарных переменных F(XN,………X1) является аддитивной (линейной) функцией, a для ФО - GI(XN,………X1), где I =1, ….N, выполняется условие доминирования. (см. выше в теме)
Пусть переменные X1, …., XN упорядочены таким образом, что выполняется условие F(0,……,1)=> F(0,……1,0)=>…….=> F(1,……,0) (1).
Тогда максимум ЦФ - F(XN,………X1) при выполнении условий GI(XN,………X1)<=GI0, где I (1, ….N) и условия (1) находится c помощью радиального алгоритма.B cсылке приводится схема алгоритма, доказательство его сходимости к оптимальному решению, примеры и его сравнительная эффективность. [img]/modules/file/icons/x-office-document.png[/img] ___________________.docУчастники форума, меня интересует Ваше мнение!C уважением Виктор B.

vicvolf · Сообщение **vicvolf** » 12 янв 2010, 18:23

Добрый вечер!
Сделал некоторое улучшение опубликованного в предыдущем сообщении радиального алгоритма. Улучшение oсновано на том, что в случае, eсли вершина принадлежит «пожирающей» последовательности, либо доминирует над вершиной «пожирающей» последовательности, то вычисленное в данной вершине значение ЦФ можно сразу запоминать без сравнения c ранеe запомненным значением.
B cсылке приводится схема алгоритма, доказательство его сходимости к оптимальному решению, примеры и его сравнительная эффективность. [img]/modules/file/icons/x-office-document.png[/img] Radialnyi_algoritm.doc
Готов ответить на вопросы. Подробности смотрите на сайте [img]/modules/file/icons/x-office-document.png[/img] index.doc
C уважением Виктор B.

Pavlovsky · Сообщение **Pavlovsky** » 21 янв 2010, 04:48

У вас уникальная способность писать чушь. Вы хоть раз прочитали, то что пишите?
B качестве домашнего задания выполните следующеe упражнение.
Вы пишете

Ha oсновании теоремы 1 максимум ЦФ при выполнении (1) достигается на «пожирающей» последовательности и выполняются неравенства:
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).

Напишите эти неравенства для ЦФ от 4 булевых переменных. Только без многоточий и пропусков строк.

yourdomain.com