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

Ответить


Смайлики
:D :) ;) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :!: :?: :idea: :arrow: :| :mrgreen: :geek: :ugeek:
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЁН
Смайлики ВКЛЮЧЕНЫ
Обзор темы
LaTeX помочь
Каждая формула должна начинаться с [tex]\textrm{[tex]}[/tex] и заканчиваться с [tex]\textrm{[/tex]}[/tex].

   
   

Если вы не хотите добавлять вложения, оставьте поля пустыми.

Развернуть Обзор темы: Метод ветвей и границ

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

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

Итерации 1 - 2 - 3 - находятся внутри кольца 4 - 0.
Если приложить топологию (см. на схеме), то решение очевидно.
Вложения
блокчейн.jpg
блокчейн.jpg (58.55 КБ) Просмотров: 3205

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

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

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

m = 4 - 0

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

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

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

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

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

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

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

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

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

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

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

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: Метод ветвей и границ

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

Возможно, что ОПТИМАЛЬНЫМ решением как раз и будет "зацепление" чисел 11520 и 5520.
11520 : 5520 = 2 (с остатком)

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

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

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

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

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

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

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

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

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

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

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



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

Вернуться к началу