решение уравнения, где некоторые неизвестные должны быть целыми числами

Question

Решить для s и t ₁ & hellip; t _n что минимизирует следующее суммирование:

& Sigma; ⁿ _{k = 1} (1 - мин ( s & middot; ) т * +1027 * к , * 1 031 * С * +1032 *_{* * к тысяча тридцать четыре * +1035 ** 1 036 *) / макс (* 1 037 * S & Мидот ; T * ** 1042 тысяча сорок-одна * к * * тысяча сорок четыре, * +1045 * С к * 1 049 *)) * * 1 051 где}

C ₁ & hellip; C _n > 1, с > 0, т ₁ & hellip; т _n & isin; ℤ ⁺

---

изменить, чтобы уточнить описание проблемы:

"как быстро вам нужен алгоритм". Не супер быстро (но не несколько секунд). n будет около 5-10 или около того.

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

То есть C ₁ ... C _n - размеры элементов на исходной странице. t ₁ ... t _n - новые целочисленные размеры в новом формате страницы. (И t ₁ ... t _n должно быть меньше X.) Коэффициент масштабирования для нового формата страницы равен s.

---

Подробнее:

Что касается того, что я сделал ранее, я нахожу самый большой элемент на исходной странице, и если он меньше X, я просто использую существующие размеры элементов на новой странице, но округляя каждый из них до целого числа. Однако, если самый большой элемент на исходной странице больше X, я делю его размер на X, чтобы получить коэффициент масштабирования s для новой страницы, и делю C ₁ ... C _n по s, чтобы получить t ₁ ... t _n . Но это приводит к расхождению в размере примерно 1-3% в среднем для каждого элемента на новой странице, но самого большого. Не совсем так заметно, но я перфекционист.

Answer 1

Вам также следует прочитать о линейном программировании с целочисленными неизвестными . Даже если это не линейное программирование, оно может дать вам представление о том, что искать.

Также вы можете обратиться к https://mathoverflow.net/, чтобы получить некоторую помощь в устранении проблемы (у вас есть проблема оптимизации в целочисленной области с разрывами в целевой функции, и моя математика немного устарела, чтобы правильно ее разместить; проверьте комбинаторная оптимизация * также 1008 *)

(для правильного решения перейдите к EDIT4 ниже)
РЕДАКТИРОВАТЬ: По поводу линейности

Ищем максимум

& Sigma; ⁿ _{k = 1} (1 - мин ( s & middot; т * ** +1028 +1029 * к * * тысяча тридцать один, * * С тысячей тридцать-дв _к ) / макс (* тысяча тридцать-восемь * S & Мидот ; T * ** 1042 тысяча сорок одна * к * +1045 *, C _{к * 1 050 *})) * * тысячу пятьдесят две может быть таким же, как смотреть на максимум для

& Sigma; ⁿ _{k = 1} (max ( s & middot; t *) 1068 * _k , C _k ) - мин ( s & middot; * * т тысячу восемьдесят-одна * ** 1083 тысячу восемьдесят два ** * 1 084 к * 1 086 *, * +1087 * С * 1 088 ** +1089 * к * +1092 *))

при условии, что

& Sigma; ⁿ _{k = 1} max ( s & middot; t _k , C _k )> 0

(что всегда «верно» с учетом ваших условий)

И срок

& Sigma; ⁿ _{k = 1} (max ( s & middot; t *) 1137 * _k , C _k ) - мин ( с & middot; T * ** 1152 тысячу сто пятьдесят-одна * к * * один тысяча сто пятьдесят пять, C * ** 1 158 +1159 * к ))

можно записать как

& Sigma; ⁿ _{k = 1} Abs ( s & middot; t _k - C _k )

который, если удерживать знак вопроса выше, дает следующее

• максимизировать s и все т _k
• свернуть все C _k

Таким образом, все C = 1 и все t и s → ∞, для которых ваше исходное выражение приближается к n.

Хорошо, поэтому изначально я ошибся в своем предложении, потому что я предполагал, что вопрос не выродится в тривиальный случай, что на самом деле вполне очевидно.

EDIT2: Моя математика ржавая, описанная выше процедура неверна (первый шаг), но вывод / решение, кажется, подтверждают, поэтому я не буду исправлять (это немного усложняется)

EDIT3 ( C _k являются константами и другими исправлениями):

Может быть, мне следует исправить ответ, я считаю, что для решения проблемы достаточно следующих аргументов:

Тот факт, что C _k постоянны и не равны 1, не имеет значения. Чтобы максимально увеличить оригинальное выражение

& Sigma; ⁿ _{k = 1} (1 - мин ( с & middot; ) т _{* * K одна тысяча двести пятьдесят-одно * ** 1 253 тысяча двести пятьдесят два *, С * ** 1256 тысяча двести пятьдесят пять * к * ** 1 259 тысячи двести пятьдесят-восемь *) / максу (* 1 260 * S & Мидот ; * * т тысячу двести шестьдесят-две к * ** 1 266 * 1267, C к * +1272 *))}

Вы должны свернуть

& Sigma; ⁿ _{k = 1} min ( s & middot; t * ** 1293 одна тысяча двести девяносто два * к , С * +1297 ** ** 1 298 1299 * к * * тысяча триста один) / макс ( S & Мидот; T _к , C _к )

поскольку область всего положительна, чтобы сделать это соотношение минимальным, вы должны сделать числитель как можно меньшим, а знаменатель - как можно большим.

Отношение равно нулю, если

• t _k равно 0 для всех k ⇒ мин (0, C _k ) / макс (0, C _k ) = 0 / C _k = 0

Также приближается к нулю, если

• s приближается к нулю (как и выше, только это предел, равный 0)
• с приближается к бесконечности ⇒ мин (∞, C _k ) / макс (∞, C _k ) = C _k / ∞ = 0
  (вышеуказанные равенства должны были использовать предельную запись ...)
• t _k приближается к бесконечности для всех k

(каждое условие достаточно само по себе и представляет решение, при объединении их не позволяйте приблизиться к 0, в то время как t _k приближается к бесконечности или наоборот, в таком случае имеет значение, какой из них подходит к нему быстрее)

РЕДАКТИРОВАТЬ4: (фактическое решение)
Ну, в основном все вышеперечисленное дает ответ на неправильный вопрос , потому что я искал максимум исходной целевой функции, а не минимум.

Как минимум, это немного интереснее, минимум достигается, если каждый член

мин ( S & Мидот; T _к , C _к ) / макс (* +1416 * S & Мидот; * +1418 * T _{* * к тысяче четыреста двадцать один * 1 422 *}, * * С тысяча четыреста двадцать четыре _k ) = 1

Это максимум этого термина с учетом области параметров. Если предположить (на данный момент), что C _k является целым числом, то решение может быть найдено для

с = 1
T * ** 1 442 1443 * к * * = тысяча четыреста сорок шесть * +1447 * С * +1449 * к * 1 451 ** +1453 * Однако C _k не является целым числом в общем случае, поэтому нам нужно найти s, для которых C _k / s является целым числом.

Если мы можем написать C _k как

N _k / D _k где N, D ∈ ℤ ⁺ (другими словами, если C _k равно рационально )

тогда решение может быть

s = 1 / & prod; ⁿ _{k = 1} D _к
t _k = N _k / D _k & middot; & prod; ⁿ _{k = 1} D _k (то есть ∈ ℤ ⁺ )

Примечание: Вместо того, чтобы выбирать s как произведение всех знаменателей, он может быть установлен на наибольший общий знаменатель, и тогда t _k можно рассчитать соответствующим образом.

Примечание 2: Построение диаграмм рассматриваемых функций помогло мне уловить мою ошибку неверного прочтения вопроса (понимание того, что минимум гораздо интереснее). Также я понял, что функции являются непрерывными (но не гладкими, поэтому деривации являются прерывистыми).

Note3: Вышеупомянутое решение работает для рациональных чисел, но я представляю, что иррациональные числа не сделают решение бесполезным, поскольку десятичные или другие рациональные представления иррациональных чисел дадут приблизительное решение, пропорционально близкое к реальному решению, поскольку представление близко к фактическому значению иррационального числа .

Answer 2

Пожалуйста, используйте для этого Maple, Mathcad или Sage.Вот список программного обеспечения, которое может вам в этом помочь: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Answer 3

Я думаю, что неразумность дала правильный ответ.Вам необходимо прочитать книгу о «Нелинейном целочисленном программировании».У меня нет хорошей книги, чтобы рекомендовать вас, но вы, вероятно, можете найти что-то, зайдя в библиотеку.

Я не думаю, что lp_solve недостаточно хорош для вас, потому что вы не можете переписать свою проблемув смешанную целочисленную задачу целочисленного линейного программирования (MILP).Maple и Mathcad не очень хорошая идея, потому что вы не ищете пакет символической алгебры.

Я думаю, что книга скажет вам сделать ветвление и связывание.Вот схематическое описание:

1) Начните с решения обобщенной задачи, где t_k - все действительные натуральные числа

минимизируют Σnk = 1 (1 - min (s · tk, Ck) / max(s · tk, Ck)) при условии, что s> 0, t1… tn ∈ R +

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

2) Как только вы нашли это решение, вы можете выполнить шаг ветвления.Выберите переменную t_k и целое число a_k и самостоятельно решите две следующие задачи

Задача 1 минимизируйте Σnk = 1 (1 - min (s · tk, Ck) / max (s · tk, Ck))при условии, что s> 0, t1… tn ∈ R + и t_k <= a_k </p>

Задача 2 минимизировать Σnk = 1 (1 - min (s · tk, Ck) / max (s · tk,Ck)), при условии, что s> 0, t1… tn ∈ R + и t_k> = a_k

3) Продолжайте выполнять шаги ветвления, пока не разбьете свою задачу на набор подзадач, которые каждыйесть целочисленное решение.Затем вы можете сравнить эти целочисленные решения и выбрать лучшее.

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