Нестандартный симплекс

[Delphist]

Симплекс метод позволяет находит max или min целевой функции и значения неизвестных для заданных ограничений.
Мою задачу можно записать в следующим виде.

F = 104*C1 + 85*C2 +49 C3 -> min;

50 <= 58.05*C1 + 83.16*C2 +34.56*C3 <= 59;
18*C1 + 20.9*C3 >= 12;
16*C1 + 0.023*С2 + 40.1*C3 <= 38;
C1 >= 0.06;
C1 + C2 + C3 = 1;

Это модель ограничений для фарша состаящая из 3-х компонентов. В качестве ограничений выступают значение по воде, белку и влаги. В одной книжке я прочитал, чтобы повысить правил-ть данной модели на 20% необходимо сделать так:
50 <= 58.05*C1 + 83.16*C2 +34.56*C3 + С1*С2*С3 <= 59;
18*C1 + 20.9*C3 + C1*C3 >= 12;
16*C1 + 0.023*С2 + 40.1*C3 + C1*C2*C3 <= 38;
Как пишут в книжке добавление слагаемоего в виде произведения неизвестных вызвано прежде всего структурно механическими изменений при смешивании компонентов фарша. Скажите, пожалуйста, правильны ли эти рассуждения.

P.S. С1, С2, С3 - массовые доли компонентов фарша.

[незваный гость]

Delphist писал(а):

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

К сожалению, сказать что-либо трудно. Поскольку эти неравенства относятся к постановке задачи, а не к математическим методам ее решения. Т.е., к к химии, биологии, физике — чему угодно, кроме математики.

А вот что можно сказать точно — что задача в такой постановке не будет решаться симплекс методом. Поскольку симплекс метод (в традиционной формулировке) решает задачу линейного программирования, а введение произведений делает ее нелинейной. Если повезет, то задача окажется выпуклой…

[Delphist]

незваный гость писал(а):

:evil:
А вот что можно сказать точно — что задача в такой постановке не будет решаться симплекс методом.

А каким методом она будет решаться?

[Руст]

У вас всего три переменных. Решайте простым перебором, минутная задача для компьютера. Можно конечно гораздо эффективнее, но это потребует гораздо большего времени на объяснение сути и составление алгоритма.

[Delphist]

Руст писал(а):

У вас всего три переменных. Решайте простым перебором, минутная задача для компьютера. Можно конечно гораздо эффективнее, но это потребует гораздо большего времени на объяснение сути и составление алгоритма.

Три переменных я написал для простоты, а на самом деле их может быть до 10-ка, и условий до 20.

[незваный гость]

Ох, Delphist, и не проста у Вас жизнь. Я сначала думал, что можно как-то попытаться модифицировать симплекс-метод, но быстро понял, что мои идеи будут работать только для выпуклой фигуры. Между тем, выпуклость Вашей области мне весьма сомнительна.

Самое неприятное в этой истории — то, что может быть несколько локальных максимумов целевой функции. Так что, тоска

Я хотел было поиронизировать над предложением Руста, но потом понял, что в нем есть любопытное зерно истины. Почва моей иронии — решение непрерывной задачи (все параметры из $\mathbb R$) перебором. Но вот что интересно и важно: Вас, видимо, не интересует точное решение. Вам должно быть нужно устойчивое решение близкое к оптимальному. Потому что и дозировки Вы можете задать лишь приближено (ну скажу я Вам, что $C_1=\frac12 \sqrt{2}$, и как Вы его закладывать в рецепт будете? округлите, ведь правда), и задание выполняется приближено (хорошо, если точность 0.1%, но я в это плохо верю). Поэтому точное решение, которое при малом отклонении становится «плохим» для Вас хуже, чем саб-оптимальное, но устойчивое. А тогда на параметрах (теоретически) можно было бы задать сетку, и перебирать в ней (как советовал Руст). Не то, чтобы это было практично.

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

[Руст]

В нелинейном случае конечно нет универсального алгоритма и 10 переменных слишком многою Могут появиться много локальных экстремумов. Поэтому боюсь дать универсальный совет. Однако, по виду ограничений (полиномы не большой степени) в принципе можно создать алгоритм, работающий хорошо в вашем случае, но это требует существенных затрат времени и не может быть решён здесь прямо на форуме.

[Yuri Gendelman]

незваный гость писал(а):

... симплекс метод (в традиционной формулировке) решает задачу линейного программирования, а введение произведений делает ее нелинейной.…

Существует т.н. метод симплексного поиска относящийся к методам безусловной оптимизации без использования производных. См., например, Химмельблау Д. Прикладное нелинейное программирование, 1975, глава 4. Симплексный поиск упоминается в разделе 4.2, хотя основное содержание этого раздела - метод Нелдера-Мида (метод деформируемого многогранника - модификация симплексного поиска). В литературе еще упоминался метод конфигураций - из того же семейства.

Но для данной задачи матрица Якоби легко считается. Так что лучше ориентироваться на методы с производными.

[Delphist]

незваный гость писал(а):

:evil:
А вот что можно сказать точно — что задача в такой постановке не будет решаться симплекс методом. Поскольку симплекс метод (в традиционной формулировке) решает задачу линейного программирования, а введение произведений делает ее нелинейной. Если повезет, то задача окажется выпуклой…

А если добавиться такое условие
lg(13)C1 + lg(12)С2 + lg(18)C3 <= 4;
То такую модель тоде нельзя считать simplex-методом?

[незваный гость]

Добавить к чему? К исходной система — она останется линейной (т.е., применять симплекс метод можно), к модифицированной — она останется нелинейной.