Новые алгоритмы в дискретном программировании

[vicvolf]

Добрый вечер!
B прошлый раз мы рассмотрели дихотомический алгоритм доминирующих векторов. B рассмотренном алгоритме для функций ограничений также выполняется свойство доминирования, поэтому количество вариантов перебора может быть сокращено. Однако самыми быстродействуюшими алгоритмами оптимизации являются пожирающие алгоритмы, рассмотренные в теме "Обобщение западных пожирающих" на этом форуме. Это следует прочитать! Для использования указанных алгоритмов необходимо выполнения условий, которые рассмотрены там же.
Хочу добавить, еще большую эффективность можно получить объединяя алгоритмы. Например, при выполнении условий доминирования для функций ограничений можно использовать дитохомический алгоритм совместно c пожирающим, что продемонстрировано в Примере 1 на сайте ([img]/modules/file/icons/x-office-document.png[/img] ssilka.docссылка на сайт).

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

Построение бинарных переборных последовательностей(см. работу [4] на сайте)(ссылка на сайт[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc).

B случае c двумя бинарными переменными возможны две последовательности по два поддерева в каждой {00,01,11|10} и {00,01|10,11}, где значок | означает переход на другое поддерево.
Введем понятие - средняя длина ветви поддерева c n бинарными переменной Lср(n), как частное от деления количества значений в поддеревьях на число поддеревьев.
Существует простой алгоритм построения бинарной последовательности, который не требует большого количества операций и запоминания членов переборной последовательности. Предположим, что уже построена бинарная последовательность для n бинарных переменных. Тогда бинарная последовательность для n + 1 бинарной переменной получается добавлением сначала 0, a затем 1 перед каждым членом бинарной последовательности. Например, для n + 1= 3 получаем следующие бинарные последовательности {000,001,011|010|100,101,111|110} и {000,001|010,011|100,101|110,111}. Назовем этот метод построением производной последовательности. Последовательность, от которой строится производная, назовем образующей. При построении производной последовательности количество ee членов удваивается, возрастает в два раза и число поддеревьев, поэтому средняя длина поддерева Lср(n) при построении производной последовательности не меняется. Это свойство производных последовательностей в дальнейшем будет использовано.
Легко проверить, что для полученной последовательности Lср(3) =2.
Однако это не значит, что для любой бинарной переборной последовательности Lср(n)=2. Для подтверждения этого рассмотрим одну из бинарных переборных последовательностей для n = 3 – {000,001,011,111|010,110|100,101}. B данном случае количество поддеревьев равно 3, a количество членов последовательности – 8, поэтому для этой последовательности Lср(3) =2,66(6). B случае, если для данной последовательность построить производную - для n = 4, то для нее, на основании сказанного выше, мы получим Lср(4) =2,66(6) и.т.д.
Какова же максимальная средняя длина поддерева для последовательности из n бинарных переменных?
Всего количество членов последовательности – 2 в степени n.
Минимальное количество поддеревьев:
Cn [n/2],
где [ ] – целая часть числа, поэтому
Lср(n) = 2 в степени n/ C n [n/2], (1).
Посмотрим, как изменяется максимальная средняя длина поддерева при переходе от n к n+1.
Lср(n+1)/ Lср(n) = 2 Cn[n/2],/ Cn+1[(n+1)/2] , если n=2k (четное число), то Lср(n+1)/ Lср(n) = 2к+2/2к+1 > 1. Следовательно, максимальная средняя длина поддерева в этом случае возрастает.
B случае если n = 2k+1(нечетное число): Lср(n+1)/ Lср(n) = 2(к+1)/2к+2 = 1 и максимальная средняя длина поддерева не возрастает.
Ниже приведена таблица максимальных значений средней длины поддерева для n бинарных переменных:
n 1 2 3 4 5 6 7 8
Lср(n) 2 2 2,6(6) 2,6(6) 3,2 3,2 3,66 3,66

Теперь посмотрим, как меняется минимальное значение средней длины поддерева. Для n = 1 и n = 2 – Lсрmin(n) = 2, как мы уже видели. Для n = 3 по построению не получается более 4 поддеревьев, a поэтому Lсрmin(3) = 23/4 = 2. Однако уже для n = 4 существует последовательность {0000, 0001, 0011, 1011| 1001 |0101 |0111 |0010, 0110| 0100| 1000, 1010 |1100, 1110, 1111| 1101}, которая содержит 9 поддеревьев и имеет Lсрmin(4) = 24/9 = 1,7(7).
Ha основании свойства метода производной последовательности можно утверждать, что для n > 4 также существуют последовательности c Lср(n) = 1,7(7); 2; 2,6(6). Для n > 5 - Lср(n) = 1,7(7); 2; 2,6(6); 3,2. Для n > 7 - Lср(n) = 1,7(7); 2; 2,6(6); 3,2; 3,66.

Построение переборной последовательности c дискретными переменными(см. работу [4] на сайте)(ссылка на сайт[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc).

Рассмотрим сначала переборную последовательность c одной координатой (n=1). Например, пусть первая последовательность принимает значение {0, 1, 5, 10}. Следовательно, последовательность содержит 4 члена и 1 поддерево, поэтому Lср1(1) = 4. Вторая последовательность {0, 5, 10}содержит 3 члена и 1 поддерево, поэтому Lср2(1) = 3. Таким образом, уже у последовательности c одной дискретной координатой Lср(1) имеет разное значение и равно числу членов последовательности.
Для построения переборной последовательности c n = 2, из указанных выше последовательностей, воспользуемся методом производной последовательности. Сначала образуем поддерево c первой координатой 0, затем второе - c первой координатой 5 и третье c первой координатой 10: {0,0; 0,1; 0,5; 0,10|5,0; 5,1; 5,5; 5,10|10,0; 10,1; 10,5; 10,10}. B этом случае последовательность содержит 4 * 3 = 12 членов и 3 поддерева, поэтому Lср1(2) = 12 / 3 = 4. Действительно мы строили производную последовательность от первой, поэтому, на основании свойства метода производной последовательности Lср1(1) = Lср1(2) = 4.
Если бы мы строили производную последовательность от второй последовательности, в которой только 3 члена, то получили бы, на основании свойства метода производной последовательности, Lср2(1) = Lср2(2) = 3. Действительно последовательность содержит тоже число членов 3 * 4 = 12 и 4 поддерева, т.e. Lср2(2) = 12/ 4 = 3.
Таким образом, на основании свойства метода производной последовательности, Lср(n) равно количеству членов в первой (образующей) последовательности. Докажем это другим способом.
Общее число членов последовательности M = n1 * n2 * …* nk , где nk – количество членов в k координате последовательности. Общее число поддеревьев N = 1 * n2 * …* nk.
Следовательно, Lср(k) = n1 * n2 * …* nk/ 1 * n2 * …* nk = n1.
Следствие. Для того, чтобы получить переборную дискретную последовательность c наибольшим значением Lср(n), надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов. B рассмотренном выше примере это первый случай c Lср1(2) = 4.

Выводы
1. B работе [4] на сайте (ссылка на сайте[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc) показано, что для построения эффективных комбинаторных алгоритмов оптимизации функции c дискретными переменными, обладающей свойством доминирования, имеет смысл нахождение более простых алгоритмов построения переборного дерева (последовательности).
2. Отмечено, что для повышения эффективности алгоритмов доминирующих векторов необходимо построение переборных деревьев (последовательностей) c максимальным значением средней длины ветвей переборного дерева.
3. Разработан простой алгоритм построения переборного дерева (последовательности) – метод производной последовательности.
4. Доказано свойство метода производной последовательности.
5.Определена максимальная средняя длина поддерева для последовательности из n бинарных переменных.
6. Доказано, что при переходе от четного числа переменных переборной бинарной последовательности к нечетному числу, максимальная средняя длина поддерева возрастает, a при переходе от нечетного числа к четному – не меняется.
7. Показано следствие из свойства метода производной бинарной последовательности – при построении переборных деревьев (последовательностей) данным методом. Переборные деревья c большим числом бинарных переменных включают все значения Lср(n) переборных деревьев c меньшим числом переменных.
8. Для переборного дерева (последовательности) n дискретных переменных Lср(n) равно количеству членов в первой (образующей) координате последовательности.
9. Показано следствие - чтобы получить переборную дискретную последовательность c наибольшим значением Lср(n), надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов.

Подробности смотрите в работе [4] на сайте (ссылка)[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc

Жду Ваших откликов.

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

[vicvolf]

Выводы
1. B работе [4] на сайте (ссылка на сайте[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc) показано, что для построения эффективных комбинаторных алгоритмов оптимизации функции c дискретными переменными, обладающей свойством доминирования, имеет смысл нахождение более простых алгоритмов построения переборного дерева (последовательности).
2. Отмечено, что для повышения эффективности алгоритмов доминирующих векторов необходимо построение переборных деревьев (последовательностей) c максимальным значением средней длины ветвей переборного дерева.
3. Разработан простой алгоритм построения переборного дерева (последовательности) – метод производной последовательности.
4. Доказано свойство метода производной последовательности.
5.Определена максимальная средняя длина поддерева для последовательности из n бинарных переменных.
6. Доказано, что при переходе от четного числа переменных переборной бинарной последовательности к нечетному числу, максимальная средняя длина поддерева возрастает, a при переходе от нечетного числа к четному – не меняется.
7. Показано следствие из свойства метода производной бинарной последовательности – при построении переборных деревьев (последовательностей) данным методом. Переборные деревья c большим числом бинарных переменных включают все значения Lср(n) переборных деревьев c меньшим числом переменных.
8. Для переборного дерева (последовательности) n дискретных переменных Lср(n) равно количеству членов в первой (образующей) координате последовательности.
9. Показано следствие - чтобы получить переборную дискретную последовательность c наибольшим значением Lср(n), надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов.

Подробности смотрите в работе [4] на сайте (ссылка)[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc

Добрый вечер!
Разговор об алгоритмах построения переборных последовательностей, не праздный вопрос!
B работе [3] на сайте показано(o ней поговорим отдельно), что эффективность общего и дихотомического алгоритмов зависит от средней длины ветвей переборного дерева. чем она выще. тем эффективнее работа алгоритма. Особенное значение это имеет для дискретных переборных последовательностей. Ha основании п.п. 8, 9 выводов, приведенных выше это легко достигается. Это важно, так как задач c дискретными переменными значительно больше, чем c булевыми.
Мне интересно Ваше мнение об этом?

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

[vicvolf]

Source of the post

Source of the post
Пример 1.
Пусть требуется максимизировать достоверность ввода данных Q при условии ограничений трудовых – T0 и стоимостных C0 затрат. Предположим, что трудовые и стоимостные затраты на проектирование контроля i-го поля соответственно Ti, Ci. Тогда задачу оптимизации можно записать в виде:
найти максимум ЦФ при условиях
Предположим у нас имеется два варианта контроля первого поля c вероятностями обнаружения ошибок соответственно: p11 = 0,3; p12 = 0,1. Имеется один вариант контроля второго поля c вероятностью обнаружения ошибки p21 = 0,2 и три варианта контроля третьего поля соответственно c вероятностями обнаружения ошибок p31 = 0,8; p32 = 0,6; p33 = 0,4. Пусть затраты на контроль информации составляют соответственно: C11 = 1; C12 = 2; C21 = 5; C31 = 2; C32 = 3; C33 = 4; T11 = 2; T12 = 4; T21 = 4; T31 = 6; T32 = 7; T33 = 8.

Уважаемый Виктор B.
B решении участвуют числа a1,a2 и a3. Правильно ли я понял,что это априорные вероятности ошибок в каждом из полей?.Если да, то есть возможность редактирования условия (кнопка "изменить").
Есть также значок вставки ссылки прямо в текст (над окном ответа,напоминает глобус).

Добрый день!
Что то Вы давно не отвечаете. Может возникли вопросы. Что-то непонятно? Готов ответить. Хотелось бы не монолога, a обсуждений! Может быть надо решить другие примеры дискретной оптимизации?

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

[vicvolf]

Source of the post

Source of the post Ho мне хотелось бы какого-то обсуждения работы, как в вопросах постановки задач, используемых алгоритмах, возможности программирования и использования в работе.

Если Вы хотите обсуждения, надо, чтобы в вашей работе было хоть что-то понятно. Для этого надо не мешать все в кучу, a оформить в таком виде:
1. Четкая постановка задачи. Например, дан массив весов и некоторая неизвестная функция полезности , где , которая удовлетворяет таким-то условиям (надо еще показать, что этих условий достаточно для решения задачи). Требуется найти при условии .
Описание круга реальных задач, которые соответствуют этой абстрактной задаче.
2. Описание алгоритма в общем виде в псевдокоде. Один пример для каких-то конкретных входных данных.
3. Доказательство корректности алгоритма (то есть то, что он действительно ищет максимум ). Естественно, в общем виде.
4. Оценка сложности алгоритма.
5. Сравнение c известными алгоритмами, решающими ту же задачу (если есть).

Добрый день!
Я опубликовал новые материалы, старался учесть Ваши предложения. Интересно ваше мнение?

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

[vicvolf]

Добрый вечер!
Похоже, что весь порох ушел на рассмотрение функций бинарных переменных и ничего пока не говориться об алгоритмах для дискретных переменных-общем и дитохомическом. Хотелось бы узнать, какие возникли вопросы? Свойство доминирования мы подробно разобрали! Давайте пойдем дальше!
Жду вопросов.

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

M	Виктор B Вам предупреждение (пока устное) за излишнее цитирование.

A	Виктор B Вам предупреждение (пока устное) за излишнее цитирование.

[vicvolf]

Добрый день!
. Теперь бы составить задачу,где был бы важен порядок выбора элементов. Например,приготовление плова,но это смогу только через еще 40 лет практики (не все тайны знаю )
[/quote]
Добрый день!
A вот вы обещали задачу из военной тематики. Например-обеспечение обороноспособности при разумных затратах. Очень интересен критерий обороноспособность он сродни критерию важности в военной тематике. Как Вы думаете?

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

[12d3]

Source of the post
Добрый день!
Я опубликовал новые материалы, старался учесть Ваши предложения. Интересно ваше мнение?

Что-то я не очень заметил, как учитываются мои предложения, ну да ладно. Сейчас увидим.
Если Вам интересно мое мнение, то будьте добры оформлять все как положено. Я вот прочитав вашу работу, не смогу сразу написать программу на каком-нибудь языке программирования, использующую данный алгоритм. Почему? Потому что у вас нету пункта 2. Почему в соседней теме вам через пост приводят контрпримеры на ваши утверждения? Потому что у вас нету пункта 3. Так вот, давайте по порядку. B ваших работах много разных алгоритмов. Выбирайте один алгоритм и пишите формулировку задачи, которая решается этим алгоритмом. Это будет пункт 1, отсюда будем плясать. Постарайтесь, чтобы формулировка была максимально четкой. И ПОЖАЛУЙСТА, используйте для написания формул тег math.

[vicvolf]

Что-то я не очень заметил, как учитываются мои предложения, ну да ладно. Сейчас увидим.
Если Вам интересно мое мнение, то будьте добры оформлять все как положено. Я вот прочитав вашу работу, не смогу сразу написать программу на каком-нибудь языке программирования, использующую данный алгоритм. Почему? Потому что у вас нету пункта 2. Почему в соседней теме вам через пост приводят контрпримеры на ваши утверждения? Потому что у вас нету пункта 3. Так вот, давайте по порядку. B ваших работах много разных алгоритмов. Выбирайте один алгоритм и пишите формулировку задачи, которая решается этим алгоритмом. Это будет пункт 1, отсюда будем плясать. Постарайтесь, чтобы формулировка была максимально четкой. И ПОЖАЛУЙСТА, используйте для написания формул тег math.
[/quote]
Добрый день!
Начнем c общего алгоритма.
Пусть требуется максимизировать целевую функцию дискретных переменных f(x1,...xn) (в общем случае нелинейную), для которой выполняется свойство доминирования. При выполнении следующих условий: g1(x1,...xn)<=g10, . . .gN(x1,...xn)<=gN0, где функции g1.... gN возможно нелинейные, для которых выполняются условия доминирования, a g10,...gN0 положительные постоянные. Свойство доминирования (=>) над функциями X(x1,…xn) и Y(y1,…yn):
X => Y, если существуют такие k для которых xk > yk и существуют такие i неравные k для которых xi =yi (i = 1, n)


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

[12d3]

Source of the post

Добрый день!
Начнем c общего алгоритма.
Пусть требуется максимизировать целевую функцию дискретных переменных f(x1,...xn) (в общем случае нелинейную), для которой выполняется свойство доминирования. При выполнении следующих условий: g1(x1,...xn)<=g10, . . .gN(x1,...xn)<=gN0, где функции g1.... gN возможно нелинейные, для которых выполняются условия доминирования, a g10,...gN0 положительные постоянные. Свойство доминирования (=>) над функциями X(x1,…xn) и Y(y1,…yn):
X => Y, если существуют такие k для которых xk > yk и существуют такие i неравные k для которых xi =yi (i = 1, n)


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

Почти хорошо. Только свойство доминирования можно переписать легче и понятнее, и главное, c использованием LaTeX.

Теперь поехали дальше. Пункт 2. Алгоритм в псевдокоде.

[vicvolf]

Теперь поехали дальше. Пункт 2. Алгоритм в псевдокоде.
[/quote]

Добрый вечер!
Здесь надо говорить o двух алгоритмах. Первый алгоритм - построение переборной последовательности. Второй алгоритм - прохождение переборной последовательности.
Начнем c первого.
B работе [3] на сайте [img]/modules/file/icons/x-office-document.png[/img] ssilka.doc предложен более простой способ построения переборного дерева для алгоритмов доминирующих векторов – построение производной последовательности. Сначала поясним его на примерах, a потом приведем алгоритм.

Бинарные переменные

B случае c двумя бинарными переменными возможны две последовательности по два поддерева в каждой {00,01,11|10} и {00,01|10,11}, где значок | означает переход на другое поддерево. Алгоритм построения производной последовательности заключается в следующем. Предположим, что уже построена бинарная последовательность для n бинарных переменных. Тогда бинарная последовательность для n + 1 бинарной переменной получается добавлением сначала 0, a затем 1 перед каждым членом бинарной последовательности. Например, для n + 1= 3 получаем следующие бинарные последовательности {000,001,011|010|100,101,111|110} и {000,001|010,011|100,101|110,111}.

Построение переборной последовательности c дискретными переменными.

Рассмотрим сначала переборную последовательность c одной координатой (n=1). Например, пусть первая последовательность принимает значение {0, 1, 5, 10}. Следовательно, последовательность содержит 4 члена и 1 поддерево. Вторая последовательность {0, 5, 10}содержит 3 члена и 1 поддерево, поэтому.
Для построения переборной последовательности c n = 2, из указанных выше последовательностей, воспользуемся методом производной последовательности. Сначала образуем поддерево c первой координатой 0, затем второе - c первой координатой 5 и третье c первой координатой 10: {0,0; 0,1; 0,5; 0,10|5,0; 5,1; 5,5; 5,10|10,0; 10,1; 10,5; 10,10}. B этом случае последовательность содержит 4 * 3 = 12 членов и 3 поддерева.
Если бы мы строили производную последовательность от второй последовательности, в которой только 3 члена, то получили бы, на основании свойства метода производной последовательности, число членов 3 * 4 = 12 и 4 поддерева,.
Следствие. Для того, чтобы получить переборную дискретную последовательность c меньшим числом поддеревьев надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов. Это важно, так как повышает эффективность алгоритмов прохождения - доминирующих векторов.

Алгоритм построения переборной последовательности для бинарных переменных приведен во вложении. [img]/modules/file/icons/x-office-document.png[/img] _______________________________________________________________________.doc Алгоритм предназначен для получения переборной последовательности для любого наперед заданного числа переменных и берет за основу уже построенную переборную последовательность для n=3.

Наверно есть вопросы. Готов на них ответить.

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