Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Подгонка суммы или диофантовы уравнения
СообщениеДобавлено: 02 фев 2019, 06:01 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2019, 02:47
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Продублирую в этом разделе, ибо писал в существующей теме в школьном разделе, а задача явно не школьная.
Задача возникла из практики: есть большая (порядка 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. Так что это даже и не совсем диофантовы уравнения.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подгонка суммы или диофантовы уравнения
СообщениеДобавлено: 02 фев 2019, 06:57 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2019, 02:47
Сообщений: 4
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Если бы пространство не было дискретным, то решение находится несложно:

[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. А в дискретном пространстве надо будет найти несколько ненулевых, причем, вероятно, разных знаков.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Подгонка суммы или диофантовы уравнения
СообщениеДобавлено: 02 фев 2019, 07:22 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Смотрите задачу о рюкзаке

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 3 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Диофантовы уравнения

в форуме Теория чисел

lenka44_44

7

636

12 сен 2018, 22:10

Диофантовы уравнения

в форуме Геометрия

mdauletiyarov

5

171

05 ноя 2022, 07:17

Диофантовы уравнения

в форуме Теория чисел

Anashkin V

2

272

21 дек 2020, 01:11

Диофантовы уравнения

в форуме Алгебра

Petja234

19

697

27 май 2021, 11:57

Преобразовать диофантовы уравнения

в форуме Алгебра

gtdd1962

6

420

18 янв 2016, 10:43

Диофантовы уравнения с 2 неизвестными

в форуме Теория чисел

kda

29

880

22 апр 2019, 18:35

Диофантовы пятерки

в форуме Теория чисел

s_e_r_g

17

537

16 апр 2022, 12:29

Конгруэнтность суммы

в форуме Теория чисел

Cocoa_lapin

1

418

10 дек 2015, 18:57

Огрубление суммы

в форуме Ряды

Misterio

9

1261

06 апр 2018, 12:10

Предел суммы

в форуме Пределы числовых последовательностей и функций, Исследования функций

Gosrabios

8

423

20 ноя 2018, 18:34


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 22


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved