Метод ветвей и границ

Метод ветвей и границ

Сообщение Гость » Ср авг 28, 2019 12:57 pm

Не знаю в какой теме опубликовать вопрос, так что решил в эту. Ищу оптимальное решение для одной задачи методом ветвей и границ и возникает вопрос в целесообразности его использования. Суть в том, чтобы найти несколько решений (в идеале одно). В первой итерации (всего 24 итерации) происходит расчет некоторого значения по формуле:

значение = нач.значение + P + m * 1000 - L,

где P и L некоторые числа, которые уже заданы для каждой итерации,
m - целочисленная переменная, через которую нужно найти оптимальное решение.

Во второй итерации и далее, вместо начального значения подставляется предыдущее. При этом существуют следующие ограничения:

нач.значение = 6000,
-5 < m < 5,
4800 < значение < 16000

В итоге получается следующая картина:
пример.jpg
пример.jpg (55.63 КБ) Просмотров: 1563



Получается, что чем больше итераций тем больше возможных решений (на четвертый уже за миллион), и для оптимизации это не есть хорошо. Выходит для данной задачи данный метод нецелесообразен?
Гость
 

Re: Метод ветвей и границ

Сообщение Rados » Ср авг 28, 2019 1:31 pm

Эта задачка больше подходит к разделу ТОПОЛОГИЯ, но на этом Форуме такого раздела (пока) нету!
Целочисленная переменная m должна иметь какой-то ПРЕДЕЛ в числовом значении, либо повторяющиеся ЦИКЛЫ - как при делении ЛЮБОГО числа на 7.
На схеме Вы уже определили положительные значения, следовательно отрицательные значения "не имеют значения".
То есть, ЦИКЛИЧНОСТЬ и ИТЕРАЦИЯ должны каким-то образом "зацепляться":
https://studopedia.org/1-14720.html
Бесконечное продолжение ветвей не даёт "однозначного" решения.
Аватара пользователя
Rados
 
Сообщения: 1839
Зарегистрирован: Вт ноя 20, 2018 8:36 am
Откуда: РОССИЯ

Re: Метод ветвей и границ

Сообщение Rados » Ср авг 28, 2019 1:37 pm

Возможно, что ОПТИМАЛЬНЫМ решением как раз и будет "зацепление" чисел 11520 и 5520.
11520 : 5520 = 2 (с остатком)
Аватара пользователя
Rados
 
Сообщения: 1839
Зарегистрирован: Вт ноя 20, 2018 8:36 am
Откуда: РОССИЯ

Re: Метод ветвей и границ

Сообщение Гость » Чт авг 29, 2019 9:10 am

для оптимизации это не есть хорошо

Попробуйте ДРУГОЙ метод, например вот:
https://ru.wikipedia.org/wiki/%D0%93%D1 ... 0%B8%D1%8F
А в качестве доказательства можно предложить "константу Хайтинга", ибо "для любого натурального числа n, множество последовательностей f в Канторовом пространстве, таких что f(n) = 1 имеет меру 1/2, и множество последовательностей чей n-й член есть 0 также имеют меру 1/2".
То есть, 5520 : 11520 = 1/2 при m "чуть больше нуля", а дальнейшее вычисление (при m больше 5) - "не имеет значения".
Гость
 

Re: Метод ветвей и границ

Сообщение Гость » Чт авг 29, 2019 11:02 pm

Rados, спасибо за совет, подкинули идею! Можно ведь выбрать не сразу все варианты из допустимых, а только один, создав еще одно условие (в моем случае, это допустимо), например, параметр m выбирается максимальным, когда, скажем, текущее значение Р меньше среднего за все итерации.
Гость
 

Re: Метод ветвей и границ

Сообщение Гость » Пт авг 30, 2019 9:52 am

параметр m выбирается максимальным

Если по условиям задачи требуется ОПТИМИЗАЦИЯ, то выбирать надо тот вариант решения, который ВПИСЫВАЕТСЯ в условие "необходимой достаточности" (minimaх по-научному).
Гость
 

Re: Метод ветвей и границ

Сообщение Гость » Пт авг 30, 2019 10:34 am

Гость писал(а):выбирать надо тот вариант решения, который ВПИСЫВАЕТСЯ в условие "необходимой достаточности"

Необходимые условия (нач.значение = 6000, -5 < m < 5, 4800 < значение < 16000) и достаточные (зависимость m от Р) при выборе только одного m как раз будут выполняться.
Гость
 

Re: Метод ветвей и границ

Сообщение Гость » Пт авг 30, 2019 3:28 pm

достаточные (зависимость m от Р) при выборе только одного m

m = 4 - 0
Гость
 

Re: Метод ветвей и границ

Сообщение Rados » Пт авг 30, 2019 3:51 pm

Итерации 1 - 2 - 3 - находятся внутри кольца 4 - 0.
Если приложить топологию (см. на схеме), то решение очевидно.
Вложения
блокчейн.jpg
блокчейн.jpg (58.55 КБ) Просмотров: 1531
Аватара пользователя
Rados
 
Сообщения: 1839
Зарегистрирован: Вт ноя 20, 2018 8:36 am
Откуда: РОССИЯ


Вернуться в Вероятность и статистика