Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
stmnf |
|
|
Задача возникла из практики: есть большая (порядка 50 строк) таблица товаров с разными ценами и количествами, есть общая сумма, но ее надо чуть-чуть подкорректировать, сохранив математическую точность вычисления. Менять можно только количество (с точностью до 3 знаков). Цена и сумма имеют точность 2 знака. Промежуточные суммы в каждой строке округляются до 2 знаков. Задача усложнена тем, что нужно не любое решение, а в идеале оптимальное, с минимально возможным изменением количества (по сумме модулей или квадратов изменений в каждой строке). Как вижу пути решения? Пока кроме перебора ничего на ум не приходит. Для начала, очевидно, нужно постараться как можно ближе подойти к искомой сумме, меняя количества построчно, начиная со строк с самыми высокими ценами и заканчивая самыми низкими. Возможно, уже тут задача и решится (хотя, вероятно, не оптимально, особенно если минимальная цена сильно меньше остальных). Если нет, начинаем перебор. Берем для начала 2 строки с минимальными ценами и пытаемся в них подвигать количества в некоторых пределах. Если не решается - берем три строки с минимальными ценами и т.д. Очевидно, тут главное вовремя остановиться. Скажем, на 10 строках, ну или посмотреть по скорости работы. Ясно, что начиная с меньших цен мы повышаем шансы на нахождение решения в принципе, но понижаем шансы на нахождение оптимального решения. Впрочем, задав определенные рамки, скажем, любое количество меняется не более, чем на 2 кванта, мы, может, и не найдем самое оптимальное решение, но имеем хорошие шансы найти практически приемлемое. Хотя, уверен, тут можно было бы как-нибудь приложить и приближенные численные методы, и что-то типа метода наименьших квадратов. Может, ткнете куда-нибудь где почитать? Спасибо. P.S. Математически задача выглядит как [math]\boldsymbol{C} \boldsymbol{X} = \mathcal{R}[/math], где [math]\boldsymbol{C}[/math] и [math]\boldsymbol{X}[/math] - вектора в многомерном пространстве целых чисел, [math]\boldsymbol{C}[/math] - неизменный вектор цен, [math]\boldsymbol{X}[/math] - вектор изменений количества, [math]\mathcal{R}[/math] - разница сумм. [math]\mathcal{R}[/math] и [math]\boldsymbol{X}[/math] малы, нужно найти [math]\boldsymbol{X}[/math] с наименьшей нормой. Вроде так. После приведения к целым числам получится, что компоненты [math]\boldsymbol{C}[/math] имеют диапазон приблизительно 1000 - 50000 и могут принимать любые целые значения, компоненты [math]\boldsymbol{X}[/math] имеют порядок единиц, и чем меньше, тем лучше, а [math]\mathcal{R}[/math] кратно 1000 и обычно составляет порядка нескольких тысяч или нескольких десятков тысяч с любым знаком. И да, нюанс: сумма в каждой строке предварительно округляется. Т.е. в данном случае это не будет обычное скалярное произведение: после умножения компонент перед сложением эти произведения нужно округлить до 1000. Так что это даже и не совсем диофантовы уравнения. |
||
Вернуться к началу | ||
stmnf |
|
|
Если бы пространство не было дискретным, то решение находится несложно:
[math]\boldsymbol{X}[/math] [math]=[/math] [math]\frac{ \boldsymbol{C} \mathcal{R} }{ \left\| \boldsymbol{C} \right\|^2 }[/math] Может, это как-то можно использовать в качестве первого приближения для перебора. Хотя едва ли: тут в [math]\boldsymbol{X}[/math] все компоненты ненулевые и одного знака, но мизерные, при малом [math]\mathcal{R}[/math] округляющиеся до 0. А в дискретном пространстве надо будет найти несколько ненулевых, причем, вероятно, разных знаков. |
||
Вернуться к началу | ||
swan |
|
|
Смотрите задачу о рюкзаке
|
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Диофантовы уравнения
в форуме Теория чисел |
7 |
636 |
12 сен 2018, 22:10 |
|
Диофантовы уравнения
в форуме Геометрия |
5 |
171 |
05 ноя 2022, 07:17 |
|
Диофантовы уравнения
в форуме Теория чисел |
2 |
272 |
21 дек 2020, 01:11 |
|
Диофантовы уравнения
в форуме Алгебра |
19 |
697 |
27 май 2021, 11:57 |
|
Преобразовать диофантовы уравнения
в форуме Алгебра |
6 |
420 |
18 янв 2016, 10:43 |
|
Диофантовы уравнения с 2 неизвестными
в форуме Теория чисел |
29 |
880 |
22 апр 2019, 18:35 |
|
Диофантовы пятерки
в форуме Теория чисел |
17 |
537 |
16 апр 2022, 12:29 |
|
Конгруэнтность суммы
в форуме Теория чисел |
1 |
418 |
10 дек 2015, 18:57 |
|
Огрубление суммы
в форуме Ряды |
9 |
1261 |
06 апр 2018, 12:10 |
|
Предел суммы
в форуме Пределы числовых последовательностей и функций, Исследования функций |
8 |
423 |
20 ноя 2018, 18:34 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 22 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |