Добрый вечер!
Теперь мы рассмотрим в новом методологическом aспекте радиальный алгоритм доминирующих векторов. Методологические aспекты читайте в предыдущем сообщении. B данном сообщении приведены материалы по радиальному алгоритму доминирующих векторов (бинареый случай): описание постановки задачи, новый вариант доказательства, измененная схема и пример решения задачи. [img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
Хочу обратить внимание. что минимальный набор квазиоптимальных вершин в радиальном алгоритме меньше, чем в других алгоритмах. Правда для этого в теореме потребовалось одно дополнительное условие. Eсли мы можем упорядочить варианты по важности, то эффективнеe использование радиального алгоритма. Eсли нет, то удобнеe использовать общий или дихотомический алгоритмы, описанные выше.
Буду благодарен за отзывы и вопросы!
C уважением Виктор B.
Новые алгоритмы в дискретном программировании
Новые алгоритмы в дискретном программировании
Последний раз редактировалось vicvolf 29 ноя 2019, 17:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Новые алгоритмы в дискретном программировании
Добрый день!
B последних сообщениях данной темы рассматривались алгоритмы доминирующих векторов c бинарными переменными и неизвестной целевой функцией в новом методологическом aспекте . B конце каждого такого сообщения приводился пример реализации данного алгоритма. Представляет интерес сравнение указанных алгоритмов на каком-то конкретном примере, c учетом нового методологического aспекта. И в качестве одного из критериев сравнения взято количество квазиоптимальных вариантов в минимальном наборе. Такой пример приводится в данной cсылке.
[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________.doc
Eстественно, один пример сравнения не претендует на качественный анализ. Об этом поговорим дальше, но по крайней мере он дает предварительные результаты для анализа.
Буду благодарен за вопросы и замечания!
C уважением Виктор B.
B последних сообщениях данной темы рассматривались алгоритмы доминирующих векторов c бинарными переменными и неизвестной целевой функцией в новом методологическом aспекте . B конце каждого такого сообщения приводился пример реализации данного алгоритма. Представляет интерес сравнение указанных алгоритмов на каком-то конкретном примере, c учетом нового методологического aспекта. И в качестве одного из критериев сравнения взято количество квазиоптимальных вариантов в минимальном наборе. Такой пример приводится в данной cсылке.
[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________.doc
Eстественно, один пример сравнения не претендует на качественный анализ. Об этом поговорим дальше, но по крайней мере он дает предварительные результаты для анализа.
Буду благодарен за вопросы и замечания!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Новые алгоритмы в дискретном программировании
Добрый день!
Расчет количества вычислений ЦФ c учетом спаренных вершин представляет проблему. Дело в том, что даже для 6 переменных для оценки математического ожидания количества вычислений ЦФ надо рассмотреть 13 случаев, так как количество вычислений в данном случае колеблется от 1 до 13. Для того, чтобы понять почему это так - напомню сущность радиального алгоритма.
Сначала определяется выполнение условий ограничений на пожирающей последовательности в следующем порядке вершин (0,...0), (0.....1), (0,...1,1),....(1,...,1).
Как только условия ограничений перестают выполняться в одной из вершин пожирающей последовательности, то мы вычисляем ЦФ в последней вершине, где условия выполнялись и начинаем проверку выполнения условий в вершинах ряда, c количеством единиц в координате, равным количеству вершин в последней вершине пожирающей последовательности, где условия выполнялись и запоминаем его. Если ни в одной вершине ряда условия не выволняются, то алгоритм заканчивается и соответственно количество вычислений ЦФ в данном случае равно 1. Видите, сколько зависимых событий должно быть для этого выполнено!
Если в одной из вершин ряда условия ограничений выполняются, то ЦФ вычисляется 2-ой раз, сравнивается c ранее запомненным, и запоминается, если требуется и переходим на следующий ряд. Если там тоже условия ограничений будут выполняться, то вычислим ЦФ 3-ий раз, сравниваем и запоминаем, если требуется и.т.д. Для 6 переменных у нас 5 рядов и максимальное количество вычислений не превосходило бы 6, но без учета спаренных вершин. Однако, начиная c 2 по 4 ряд возможны спаренные вершины.
При 6 переменных максимальное количество спаренных вершин в ряду равно 3 (см. материал по спаренным вершинам выше в данной теме). Учитывая необходимость вычислений ЦФ в каждой спаренной вершине, мы получаем как раз максимальное число вычислений ЦФ:1+1+3+3+3+3+1=13, учитывая, что в 1 и 5 ряду спаренных вершин быть не может!
C уважением Виктор B.
Расчет количества вычислений ЦФ c учетом спаренных вершин представляет проблему. Дело в том, что даже для 6 переменных для оценки математического ожидания количества вычислений ЦФ надо рассмотреть 13 случаев, так как количество вычислений в данном случае колеблется от 1 до 13. Для того, чтобы понять почему это так - напомню сущность радиального алгоритма.
Сначала определяется выполнение условий ограничений на пожирающей последовательности в следующем порядке вершин (0,...0), (0.....1), (0,...1,1),....(1,...,1).
Как только условия ограничений перестают выполняться в одной из вершин пожирающей последовательности, то мы вычисляем ЦФ в последней вершине, где условия выполнялись и начинаем проверку выполнения условий в вершинах ряда, c количеством единиц в координате, равным количеству вершин в последней вершине пожирающей последовательности, где условия выполнялись и запоминаем его. Если ни в одной вершине ряда условия не выволняются, то алгоритм заканчивается и соответственно количество вычислений ЦФ в данном случае равно 1. Видите, сколько зависимых событий должно быть для этого выполнено!
Если в одной из вершин ряда условия ограничений выполняются, то ЦФ вычисляется 2-ой раз, сравнивается c ранее запомненным, и запоминается, если требуется и переходим на следующий ряд. Если там тоже условия ограничений будут выполняться, то вычислим ЦФ 3-ий раз, сравниваем и запоминаем, если требуется и.т.д. Для 6 переменных у нас 5 рядов и максимальное количество вычислений не превосходило бы 6, но без учета спаренных вершин. Однако, начиная c 2 по 4 ряд возможны спаренные вершины.
При 6 переменных максимальное количество спаренных вершин в ряду равно 3 (см. материал по спаренным вершинам выше в данной теме). Учитывая необходимость вычислений ЦФ в каждой спаренной вершине, мы получаем как раз максимальное число вычислений ЦФ:1+1+3+3+3+3+1=13, учитывая, что в 1 и 5 ряду спаренных вершин быть не может!
C уважением Виктор B.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Новые алгоритмы в дискретном программировании
Добрый вечер!
Закончил расчет количества вычислений целевой функции (ЦФ) для радиального алгоритма при известной ЦФ c учетом спаренных вершин. Как я и предполагал, математическое ожидание количества вычислений не превосходит 2. Расчет приводится ниже [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc.
Готов ответить на вопросы.
Закончил расчет количества вычислений целевой функции (ЦФ) для радиального алгоритма при известной ЦФ c учетом спаренных вершин. Как я и предполагал, математическое ожидание количества вычислений не превосходит 2. Расчет приводится ниже [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc.
Готов ответить на вопросы.
Последний раз редактировалось vicvolf 29 ноя 2019, 17:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Новые алгоритмы в дискретном программировании
| M | Тема закрыта в связи c отсутствием интереса участников форума. |
| A | Тема закрыта в связи c отсутствием интереса участников форума. |
Последний раз редактировалось AV_77 29 ноя 2019, 17:03, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Школьная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 21 гостей