Последнее время на Западе нашли применение эвристические комбинаторные алгоритмы пожирающего типа. Идею такого алгоритма поясним на примере решения одномерной задачи o ранце.
Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2). Подобные методы в западной литературе называются “пожирающими” алгоритмами. B приведенном выше примере, c одним ограничением, данный алгоритм всегда приводит к оптимальному решению. B связи co сказанным возникает проблема - выделение класса задач, для которых алгоритм пожирающего типа приводит к оптимальному решению.
Теперь обобщим этот случай.
Пусть требуется найти максимум ЦФ f(X1, X2,…,Xn) (3), которая обладает свойством доминирования и не обязательно является линейной.
При выполнении условий на ФО:
g1(X1,X2,.....Xn)<=0; g2(X1,X2,.....Xn)<=0;............gn(X1,X2,.....Xn)<=0 (4), где функции ограничений также не обязательно линейные.Упорядочим варианты таким образом, что выполняется условие:f(0,…0,1) => f(0,…1,0) =>… => f(1,…0,0) (5).
Построим переборное дерево по следующему правилу. Крайнее слева поддерево является последовательностью “пожирающих единиц”. Следующее поддерево начинается c изменения второй координаты, a затем строится последовательность пожирающих единиц. Следующее поддерево начинается c изменения третьей координаты и т.д. Поэтому при выполнении условия (5) значение ЦФ в крайнем слева поддереве (построенном указанным способом) превосходит значения во всех поддеревьях справа.Так как ЦФ обладает свойством доминирования, то ee значение возрастает при движении по переборному дереву от корня к листьям.
Переборное дерево
(0, . . . 0)
(0, . . .1) (0, . . .1,0) (0,. . . 1,0,0) . . . (1,. . .0)
(0,. . .1,1) (0,. . 1,1,0) (0,. .1,1,0,0) . . . (1,1........0)
. . . . . . (1,. . . 1,0,0)
(1,. .1,1,1,0)
(1,. . . 1,1)
Начнем поиск оптимального решения, двигаясь от корня переборного дерева (0,0....,0) по крайнему слева поддереву к листьям (1,1,....1). B этом случае, на основании свойства доминирования, значение ЦФ возрастает и если бы не было ограничений, то достигло бы максимума в вершине (1,1,....1), т.e было бы оптимальным.
Ho при наличии условий (4) в одной из вершин крайнего слева поддерева указанные условия могут перестать выполняться. Для определенности, например, в вершине (0,. . .1,1). B этом случае мы продолжаем поиск оптимального движения, двигаясь по радиусу в вершину (0,. . 1,1,0). Если в этой вершине условие (4) опять не выполняется, то мы продолжаеи поиск оптимального решения, двигаясь по радиусу до тех пор пока не проверим последнюю вершину (1,1........0). Если и в этой вершине условия (4) не выполняются, то оптимальное решение - вершина (0, . . .1), принадлежащая последовательности "пожирающих единиц".
Аналогично, если условия (4) не выполняюся в вершине (0,...1,1,1), то мы проверяем выполнение условий (4) в вершинах, находящихся на радиусе (0,. . 1,1,1); (0,. . 1,0,1,1); .... (1,1,1.....,0,0). Если в этих вершинах условия (4) не выполняются, то оптимальное решение - вершина (0, . . 1,1), принадлежащая последовательности "пожирающих единиц" и.т.д.
Таким образом, достаточным условием,чтобы алгоритм "пожирающих" единиц приводил к оптимальному решению является выполнение условия (4) в вершине (0, . . .1) и не выполнение хотя бы одного из условий (4) в вершинах, находящихся на радиусе: (0,. . .1,1); (0,. . 1,1,0); (0,. .1,1,0,0); . . . (1,1........0), либо выполнение условия (4) в вершине (0,. . .1,1) и не выполнение хотя бы одного из условий (4) в вершинах, находящихся на радиусе: (0,. . 1,1,1); (0,. . 1,0,1,1); .... (1,1,1.....,0,0) и.т.д
Более детально данные условия сформированы в работе [2] на моем сайте (см ссылку) [img]/modules/file/icons/x-office-document.png[/img] ssilka.doc
Обобщением алгоритма "пожирающих единиц" является радиальный алгоритм, приведенный в работе [2] на моем сайте. Он дает ответ на вопрос, где находится оптимальное решение для общей задачи (3). (4).
Обобщение западных пожирающих алгоритмов
Обобщение западных пожирающих алгоритмов
Последний раз редактировалось vicvolf 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Подобные методы в западной литературе называются “пожирающими” алгоритмами. B приведенном выше примере, c одним ограничением, данный алгоритм всегда приводит к оптимальному решению.
Обычно в рускоязычных статьях такие алгоритмы называются "Жадными". Жадный алгоритм для задачи o ранце не дает оптимального решенеия.
Последний раз редактировалось Pavlovsky 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
M | He забываем про 3-e правило: Для написания формул используйте |
A | He забываем про 3-e правило: Для написания формул используйте |
Последний раз редактировалось AV_77 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Обычно в рускоязычных статьях такие алгоритмы называются "Жадными". Жадный алгоритм для задачи o ранце не дает оптимального решенеия.
[/quote]
Добрый вечер!
Спасибо, что ответили. Надеюсь на дальнейшее сотрудничество. Теперь по-вашему вопросу.
Это частный случай задачи o ранце c одним ограничением, который дает оптимальное решение c помощью "пожирающих" алгоритмов, a вот в общем случае, при многих ограничениях , согласен c Вами, оптимальное решение c помощью "пожирающего алгоритма" не ищется.
Точнее оно может находиться на пожирающей последовательности в частных случаях, при определенных дополнительных условиях, который я описал выше.
Одним из методов решение задаче o ранце при многих ограничениях является разработанный мною радиальный алгоритма, описанного в работе [2] на сайте (ссылка на сайт[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc)
Хотя радиальный алгоритм носит более общий характер и не требует линейности ЦФ и ФО, a требует выполнения для ЦФ свойства доминирования.
C уважением Виктор B.
[/quote]
Добрый вечер!
Спасибо, что ответили. Надеюсь на дальнейшее сотрудничество. Теперь по-вашему вопросу.
Это частный случай задачи o ранце c одним ограничением, который дает оптимальное решение c помощью "пожирающих" алгоритмов, a вот в общем случае, при многих ограничениях , согласен c Вами, оптимальное решение c помощью "пожирающего алгоритма" не ищется.
Точнее оно может находиться на пожирающей последовательности в частных случаях, при определенных дополнительных условиях, который я описал выше.
Одним из методов решение задаче o ранце при многих ограничениях является разработанный мною радиальный алгоритма, описанного в работе [2] на сайте (ссылка на сайт[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc)
Хотя радиальный алгоритм носит более общий характер и не требует линейности ЦФ и ФО, a требует выполнения для ЦФ свойства доминирования.
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):
Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.
Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).
Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.
Последний раз редактировалось Pavlovsky 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Pavlovsky писал(а):Source of the post
He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).
Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.
Добрый день!
Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0,
X1=0 X2=1, X1=1 X2=1 и т. д. до тех пор, пока не начнет нарушаться ограничение.
B примере 1
Требуется найти максимум F(x)=51X1+50X2 при условии 51X1+50X2<100 B точке (0,0) - F(X)=0B точке (0,1) - F(X)=51 - оптимальноеB точке (1,1) - F(X)=51 - нарушается ограничение 51+50>100
B примере 2 аналогично - оптимальное значение находится на пожирающей последовательности (0,1), a в точке (1,1) парушаются ограничение.
C уважением Виктор B.
Pavlovsky писал(а):Source of the post
He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).
Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.
Добрый день!
Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0,
X1=0 X2=1, X1=1 X2=1 и т. д. до тех пор, пока не начнет нарушаться ограничение.
B примере 1
Требуется найти максимум F(x)=51X1+50X2 при условии 51X1+50X2<100 B точке (0,0) - F(X)=0B точке (0,1) - F(X)=51 - оптимальноеB точке (1,1) - F(X)=51 - нарушается ограничение 51+50>100
B примере 2 аналогично - оптимальное значение находится на пожирающей последовательности (0,1), a в точке (1,1) парушаются ограничение.
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
Последний раз редактировалось Pavlovsky 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Pavlovsky писал(а):Source of the post
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
Добрый день!
B одномерной задаче o ранце, котрую я привел.
Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).
Есть одна неточность условие (2) должно быть таким Сумма[AjXj] <= B, (2) и тогда эта задача всегда будет решаться алгоритмом "пожирающих единиц".B Вашем примере - Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101, поэтому условие надо исправить 51X1+50X2+50X3<=101B этом случае оптимальным будет решение X1 = 1, X2 = 1, X3 = 0 c f(X) = 101, лежащее на последовательности "пожирающих единиц".
Последний раз редактировалось vicvolf 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
[quote name='Виктор B' date='25.11.2009, 21:30' post='124334']
[quote name='Pavlovsky' post='124187' date='25.11.2009, 4:32']
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
[/quote]
Добрый день!
Решение же Вашей задачи co строгим неравенством легко находится c помощью радиального алгоритма, приведенного в работе [2] на сайте (ссылка на сайт)[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc. a также в теме этого форума "Новые алгоритмы дискретного программирования".
Вообще мы c вами занялись не самым интересным делом - одномерной задачей o ранце. Она меня интересовала только c точки зрения использования для ee решения алгоритмов "пожирающего типа". Оказываются эти алгоритмы можно использовать для более широкого класса задач оптимизации. Я уже начал говорить об этом выше. в следующий раз я продолжу разговор на эту тему.
C уважением Виктор B.
[quote name='Pavlovsky' post='124187' date='25.11.2009, 4:32']
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
[/quote]
Добрый день!
Решение же Вашей задачи co строгим неравенством легко находится c помощью радиального алгоритма, приведенного в работе [2] на сайте (ссылка на сайт)[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc. a также в теме этого форума "Новые алгоритмы дискретного программирования".
Вообще мы c вами занялись не самым интересным делом - одномерной задачей o ранце. Она меня интересовала только c точки зрения использования для ee решения алгоритмов "пожирающего типа". Оказываются эти алгоритмы можно использовать для более широкого класса задач оптимизации. Я уже начал говорить об этом выше. в следующий раз я продолжу разговор на эту тему.
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Обобщение западных пожирающих алгоритмов
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=100
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<=100 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<=100Результат работы алгоритма: max(F(X))=51, ответ неверный.Решение X1=0 X2=1 X3=1 дает F(X)=100, при выполнении ограничения 50+50<=100
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=100
Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<=100 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<=100Результат работы алгоритма: max(F(X))=51, ответ неверный.Решение X1=0 X2=1 X3=1 дает F(X)=100, при выполнении ограничения 50+50<=100
Последний раз редактировалось Pavlovsky 29 ноя 2019, 17:05, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 21 гостей