Какие вычислительные способы существуют? Какие из них можно в 1С-ке реализовать? Если поделитесь примерами - буду крайне признателен:)
Особенно интересно как найти экстремум нелинейной функции, где значения переменных целое.. Конечно кроме перебора :)

Симплекс метод.

(1) Симплекс только для линейных функций. В случае с функцией x^2 + z^2 = F симплекс безполезен.

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

В общем случае метода нет и не может быть. Например для таблично заданной функции без закономерностей - только перебор. Если функция задана аналитически, тогда те-же методы что и для действиетельных значений функции.

красная буква Я в правом углу http://www.yandex.ru/yandsearch?rpt=rad&text=%DD%EA%F1%F2%F0%E5%EC%F3%EC%20%ED%E5%EB%E8%ED%E5%E9%ED%EE%E9%20%F4%F3%ED%EA%F6%E8%E8%20%EC%ED%EE%E3%E8%F5%20%EF%E5%F0%E5%EC%E5%ED%ED%FB%F5&lr=187

(5) Особенно интересно как найти экстремум нелинейной функции, где значения переменных целое..

Хм, была такая курсовая лет 7 назад.
разбивал на кубы с заданным шагом и в узлах кубов искал через производные направление прирощения. хотя вспоминается уже с трудом, помню что назывался "кенгуру и мыши", но я как-то иначе решил :)

(5) Меня интересует мнение 1С:общественности. Особенно вычислительные способы, реализуемые в 1С.

(7) Методы основные понятны, это разнообразные методы случайных направлений, поиск по сетке, спуски (покоординатные, градиентные методы) и т.д.
Если экстремумов много - то спуски с несколькими начальными точками и всё в этом духе.
Только в условии на целочисленной области определения - для нелинейных функций никаких общих методов нет.

(8) Для твоей функции - градиентный метод, на действительной области определения, а потом смотришь целочисленные значения рядом.

(8) Имхо скорость рассчета будет дико маленькая, да и список функций в 1С, прямо скажем, не фонтан.

(4) Функция аналитическая. Но как от действительных значений перейти к целым? В общем случае вероятность сразу попасть на целое решение трудно.
(7) А если переменных 5?

(12) Гиперкубы конечно :)

(12) Так используй градиентный спуск. Либо покоординатный, тогда сразу можешь бежать по целочисленным значениям. Сделай только переменный шаг.
То что в (7) - и есть градиентный спуск, только по человечески - находим градиент через частные производные, и с некоторым шагом двигаемся в направлении градиента. Если получили прирост значения - фиксируем новую точку, и делаем повторную попытку двинуться в этом направлении.

(1) Симплекс метод не работает на нелинейных ф-иях,
а вот симплекс поиск(метод девормируемого многогранника;Нелдер-Мид)
работает и вполне хорошо, правда его эффективность зависит от кол-ва переменных.

(14) Угу, по человечески как-то так :)
Только надо еще учесть, что экстремумов может быть несколько, поэтому сетка таки нужна для поиска всех экстремумов.

(2) Блин, посмотрел твоё уравнение - тут вообще не может быть стандартных алгоритмов. Даже в случае если не минимум стоит, а стоит знак равенства - есть доказанная теорема что не существует алгоритма сообщающего есть решение или нет для общего случая. Это десятая проблема гильберта (разрешимость диофантовых уравнений)

(0)общее решение здесь существует:Метод Монте-Карло. :)

(18) Чтоб использовать монте-карло должна быть ограниченная область определения.
а если она неограничена?

(17) Это просто пример был. На самом деле у меня такое уравнение:

F = (S1/K1)*x1 + (S1+S2-(S1/K1)*x1)/(K1+K2-x1) * x2

где переменные - x1 и x2, остальное - константы, зависящие от условий задачи.

(19) Ну да :) Но в данном случае, трудно представить одинЭсника имеющего
чего то там в неогранич. количестве. :)))

(20) область определения озвуч :)

Кстати, а Эксель проде тоже что-то подобное могет или я ошибаюсь?

да

(20) Перебирай x1 начиная с нуля. (0,1,-1,2,-2,3,-3) и т.д.
У тебя получается линейное уравнение относительно x2, решаешь его, округляешь x2, подставляешь, сравниваешь с ранее достигнутым минимумом и т.д.
Врятли за короткое время можно придумать чего лучше.

(20) А если тупо взять производные и приравнять их к нулю?!

1. Генеришь случ. знач. для x1, х2
2. вычисляешь знач функции;
3. строишь гистограмму;

(26) Так целочисленная область определения! И уравнение с двумя неизвестными на вещественной оси имеет бесконечное количество решений.

(22) Сорри, важное забыл:)
x1 <= 5
x1 + x2 <= 12

(25) Вообще я привел часть функции, что бы понять принцип решения. Общий вид:
(S1/K1)*x1 + //1-ое значение = 1Знач
(S1+S2-1Знач)/(K1+K2-x1) * x2 + //2-ое значение = 2Знач
(S1+S2+S3-1Знач-2Знач)/(K1+K2+K3-x1-x2) * x3 //3-ое значение = 3Знач
(S1+S2+S3+S4-1Знач-2Знач-3Знач)/(K1+K2+K3+K4-x1-x2-x3) * x4

и так далее до n, где n конечно и известно. Все ограничения известны и имеют вид, указанный выше, x1 <= C1; x1+x2 <= C2; x1+x2+x3 <= C3 и т.д.

(27) Не надо так делать. При известном x1
- x2 с лучшим значением функции легко вычисляется.
(0) Дай пример коэффициентов.

(29) Чего ты путаешь, теперь у тебя количество неизвестных равно количеству уравнений. И теперь исчез критерий оптимальности решения.

(29) + x >= 0 всегда.

Меня тут смущает ,что есть x в знаменателе дробей. Если бы его не было бы можно было бы просто перебрать комбинации максимальных значений x1, x2 и других. А так не понятно, что будет больше.

Годик назад в Excelе решали оптмизационные задачи.  Может там написать макрос, а средствами 1С передавать и получат даные из екселя

(31) не исчез - я его изначально забыл сказать, сорри:)
Критерий - максимум функции.

(S1/K1)*x1 +
(S1+S2-1Знач)/(K1+K2-x1) * x2 +
(S1+S2+S3-1Знач-2Знач)/(K1+K2+K3-x1-x2) * x3 +
(S1+S2+S3+S4-1Знач-2Знач-3Знач)/(K1+K2+K3+K4-x1-x2-x3) * x4
это все одна функция.

Пока писал - пришла в голову идея: x с верху ограничены. Обходим симплексом сочетания x, удовлетворяющих условию ограниченности с верху и для каждого сочетания считаем функцию.
Получается сложность симплекса примерно 3*n^2 (3*кол условий*кол переменных) Если за базовую взять операцию умножения в функции и учесть, что результаты определенных вычислений можно хранить в соответствии, то получиться сложность 3*n^3. Для меня вполне подойдет:)

(34) Уверен что критерий просто сумма, а не сумма квадратов отклонений?

(36) Сумма всей функции есть критерий.

(35) А снизу x ограничены?

(38) х больше или равны нулю, целые и ограничены сверху.

(39) А дай пимер коэффициентов (вместе с ограничениями)

(+40) пример.

S1 = 2000, K1 = 10
S2 = 3000, K2 = 15
S3 = 4000, K3 = 21
S4 = 3000, K4 = 14

NS, а что скажешь насчет (35)?

(43) Симплексом бежать по вершинам не выйдет. В отличии от задач линейного программирования экстремум в твоей задаче достигается не на вершинах (не обязательно на вершинах)

(42) А ограничения?

(+45) А 1Знач, 2Знач и т.д.?

(S1/K1)*x1 +
(S1+S2-1Знач)/(K1+K2-x1) * x2 +
(S1+S2+S3-1Знач-2Знач)/(K1+K2+K3-x1-x2) * x3 +
(S1+S2+S3+S4-1Знач-2Знач-3Знач)/(K1+K2+K3+K4-x1-x2-x3) * x4

1Знач = (S1/K1)*x1;
2Знач = (S1+S2-1Знач)/(K1+K2-x1) * x2
3Знач = (S1+S2+S3-1Знач-2Знач)/(K1+K2+K3-x1-x2) * x3

Т.е. "Знач" - это просто строчка выше. Использую для сокращения формулы.
х1 <= 10
х1+x2 <= 25
х1+x2+x3 <= 46
х1+х2+х3+x4 <= 60
x1+x2+x3+х4 = 15

А почему ты решил, что решение лежит не на вершинах?

А почему оно должно лежать на вершине?
Простейший случай 100-(X-2)^2, X>=0,X<=10
максимум не на вершине, а при X=2.

х1 <= 10
х1+x2 <= 25
х1+x2+x3 <= 46
х1+х2+х3+x4 <= 60
x1+x2+x3+х4 = 15

Ничего не понял, Если всё написано правильно - все ограничения кроме первого и последнего лишние.

(48) Условия из головы брал.
Суть в том что условий будет по количеству переменных + 1. Давай сделаем последнее условие
x1+x2+x3+х4 = 59.

Новый день, новые идеи! NS, перебор даже на 4-ех переменных дело не благодарное...

4!=4*3*2*1=24
ничего страшного для совр числодробилок

(50) Сегодня сделаю пример, для начала совсем без ограничений.

(51) Перебор получается следующий
х1 = 0;
Пока x1 <= максимум1 Цикл
х2 = 0;
Пока х1 + х2 <= максимум2 Цикл
х3 = 0;
Пока х1 + х2 + х3 <= максимум3 Цикл
х4 = 0;
Пока х1 + х2 + х3 + х4 <= максимум4 Цикл
ПроверитьЗначениеФункции();
х4 = х4 + 1;
КонецЦикла;
х3 = х3 + 1;
КонецЦикла;
х2 = х2 + 1;
КонецЦикла;
х1 = х1 + 1;
КонецЦикла;

это получается максимум1*максимум2*максимум3*максимум4. Страшно? Мне да..

(53) + хотя немного ошибся. Количество иттераций второго цикла будет уменьшаться на x1, третьего на x2 и т.д. Решать реккурентное соотношение для такой процедуры лениво. Но думаю, что это будет где то
0.5 * максимум1*максимум2*максимум3*максимум4

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

(55) + Т.е. если при х1 = max(x1) функция больше, чем при x2 = max(x2) то промежуточные значения точно не гарантируют лучшее значение.