Алгоритм расчета общей суммы

[kashperuk]

Обязательно.
Не могу же я оставить общественность (господ, если Вам так угодно ) без ответа.

Если кто чего умное придумает, обязательно пишите.

[EVGL]

Да, напишите продолжение, пожалуйста, очень интересно. Мне кажется, надо начинать "what if" со значения с наибольшим количеством (1000). Отсортировать по количеству. Пропробовать изменить цену для наибольшего количества на +-0,01, а потом попытаться "подровнять" по моей методике постепенно спускаясь вниз. Зафиксировать, что было лучше: +0,01 или -0,01. Повторить со следующим количеством (15), но с большим шагом изменения цены и т.д.

[kashperuk]

Да. У нас текущий алгоритм, придуманный сходу, пока где-то так и работает:

1. Сортируем по кол-ву в убывающем порядке.
2. Рассчитываем (общее отклонение - кол-во). если оно по модулю меньше чем общее отклонение, то уменьшаем/увеличиваем в зависимости от знака результата цену на 0.01.
2.1. Повторяем пока разница цены не будет больше 10% или (общее отклонение - кол-во) по модулю не будет больше чем общее отклонение.
3. Переходим к след. кол-ву.

Ну, если отклонение стало равно 0.00, то понятное дело, выходим из любого цикла.

Тут уже и оптимизацию придумали, чтобы раскидать пропорционально по всем ценам отклонения, а не тупо с одной строки все срубать:

делать приведенный выше алгоритм итетационно, то есть за раз уменьшать/увеличивать цену не больше чем "Заданный параметр в %".
При этом нужен еще один параметр - "Максимальное кол-во циклов"

Прям параметры, как у пересчета себестоимотси получаются

[KiselevSA]

Интересно, из какого места у данной задачи растут ноги. В свое время я сумел на проекте убедить, что вывод данных обратным счетом является оптимальным вариантом. Т.к. ни в однм регламентирующем документе не сказано, что в выходных документах (отчетах) сумма по строке должна быть равна цене умноженной на количество.
Если описанный алгоритм размазывания дельты рассматривается с теоретической точки зрения, я могу согласиться с постановкой (не забывайте про количество по строке, размазывать надо только по тем строкам, у которых количество менее 10, иначе придется играться с отрицательными коррекциями по некоторым строкам).
А если это в практической плоскости, то задайте вопрос бухгалтерам, а что будет, если в документе (отчете) несколько строк для одного и того же товара, отличающегося, например, партией или ГТД с разными ценами, выровненными при размазывании? Их этот вариант не волнует?

[kashperuk]

Итак.
Решение оказалось банально у нас под носом.
Правда пока непонятно, как же им воспользоваться

В Microsoft Excel есть встроенный инструмент "Поиск Решения" (SOLVER), который решает задачи, в том числе и целочисленные задачи квадратичного программирования, примером которой является приведенная задача.

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

Есть два варианта дальнейшего развития решения:
1. Попробовать повторить этот алгоритм в Аксапте (для этого нужно иметь доступ к исходным кодам надстройки solver.xla(m))
2. Выгружать данные в Эксель, запускать надстройку (которая должна быть установлена у пользователя), получать из Экселя данные и использовать их.
Для этого нужно перенести макрос, запускающий решение, в Аксапту. Что тоже усложняется за счет различных версий Эксель у пользователей (а с этим постоянно проблемы).

Код, который делает это в VBA, такой приблизительно:

    SolverAdd CellRef:="$D$2:$D$5", Relation:=4, FormulaText:="целое"
    SolverAdd CellRef:="$D$10:$D$13", Relation:=3, FormulaText:="$F$10:$F$13"
    SolverAdd CellRef:="$D$10:$D$13", Relation:=1, FormulaText:="$G$10:$G$13"
    SolverOk SetCell:="$D$16", MaxMinVal:=2, ValueOf:="0", ByChange:="$D$2:$D$5"
    SolverSolve

Исходный код надстройки недоступен, но "нечестным" путем его удалось получить
Я бы выложил сюда, но не знаю, нарушает ли это какие-то правила.
Кода много, как выдрать из него только требуемую функциональность пока тоже непонятно.

Кто что скажет/посоветует?

[kashperuk]

Только что просмотрел все исходные коды, которые открылись после удаления пароля с файла solver.xlam

Нету там алгоритма. Он спрятан где-то глубже
Для получения результата вызывается

answer = Application.Run("[" & ThisWorkbook.Name & "]Excel4Functions!SolveCall")

где ThisWorkbook.Name = SOLVER.XLAM.

Кстати, пока просматривал код, наткнулся на смешной код, достойный темы The Daily Axapta WTF:

   If Left(Application.OperatingSystem, 1) = "W" Then
      helpfile = "xladdin.chm"
   Else
      helpfile = ":MS EXCEL HELP"
   End If

Application.OperatingSystem вернуло в моем случае Windows (32-bit) NT 5.1 или что-то в этом роде
Точно индусы писали

[petr]

Можно попробовать найти эту функцию в OpenOffice, там исходные тексты открытые

[KiselevSA]

Цитата:

Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University).

Алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc. Чтобы получить более подробные сведения об используемых алгоритмах оптимального поиска, обратитесь по адресу:

Frontline Systems, Inc.
P.O. Box 4288
Incline Village, NV 89450-4288
(775) 831-0300
Адрес в Интернете: http://www.frontsys.com
Электронная почта: info@frontsys.com

[kashperuk]

Цитата:

Сообщение от KiselevSA

Чтобы получить более подробные сведения об используемых алгоритмах оптимального поиска, обратитесь по адресу:

Frontline Systems, Inc.
P.O. Box 4288
Incline Village, NV 89450-4288
(775) 831-0300
Адрес в Интернете: http://www.frontsys.com
Электронная почта: info@frontsys.com

Завтра вылетаю. Кто со мной?

Одним словом, пошел вторым путем. Работает.
Есть определенные ньюансы, ессно. Надо еще тестировать.

[kashperuk]

Цитата:

Сообщение от kashperuk

Завтра вылетаю. Кто со мной?

Одним словом, пошел вторым путем. Работает.
Есть определенные ньюансы, ессно. Надо еще тестировать.

Эх. Беру свои слова назад. Нифига не работает.
Точнее, написано то все правильно.
Но при большом кол-ве строк в отчете поиск решения ничего не делает, возвращая при этом 8,00 - код ошибки, сигнализирующей о том, что задача для него слишком сложная.

Придется таки искать саму реализацию алгоритма.
Может сайт вышеприведенный прольет какой-то свет.

А может у кого-то уже есть готовый алгоритм?

[EVGL]

Google: http://www-fp.mcs.anl.gov/otc/GUIDE/.../nonlinearcon/
Немножко лагранжианов, немножко дифференциальных уравнений... Не зря же мы учились в ВУЗе, не правда ли?

[kashperuk]

Цитата:

Сообщение от EVGL

Google: http://www-fp.mcs.anl.gov/otc/GUIDE/.../nonlinearcon/
Немножко лагранжианов, немножко дифференциальных уравнений... Не зря же мы учились в ВУЗе, не правда ли?

Спасибо, конечно.
Может и не зря, но понял мало

Поиск решений работает нуу очень долго... Даже тот, что скачал с сайта по ссылке.
К примеру, на поиск решения с 95 строками уходит порядка 3 минут!!! При этом, судя по его логам, он решает около 2500 подзадач!!!

Переделал сегодня алгоритм по старому варианту (описан выше).
Наш алгоритм довольно прост и прямолинеен. Работает быстро. За 1 проход по таблице
Правда, в общем случае, конечно же, дает результаты хуже, чем поиск решений. (но не намного)
Пока так. (просто срочно нужны были результаты)

Возможно в будущем при наличии времени и желания доделаем оптимальный вариант, уже без применения Экселя. Главное с алгоритмом ветвей и границ (или симплекс методом - поди разбирись, что конкретно нужно использовать) разобраться для целочисленного квадратичного случая.

Спасибо всем за участие.