2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нестандартный симплекс
Сообщение21.08.2007, 18:45 
Симплекс метод позволяет находит 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 - массовые доли компонентов фарша.

 
 
 
 
Сообщение21.08.2007, 23:23 
Аватара пользователя
:evil:
Delphist писал(а):
Как пишут в книжке добавление слагаемоего в виде произведения неизвестных вызвано прежде всего структурно механическими изменений при смешивании компонентов фарша. Скажите, пожалуйста, правильны ли эти рассуждения.

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

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

 
 
 
 
Сообщение22.08.2007, 08:48 
незваный гость писал(а):
:evil:
А вот что можно сказать точно — что задача в такой постановке не будет решаться симплекс методом.

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

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

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

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

 
 
 
 
Сообщение22.08.2007, 19:53 
Аватара пользователя
:evil:

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

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

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

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

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

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

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

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

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

 
 
 
 
Сообщение05.09.2007, 04:59 
Аватара пользователя
:evil:
Добавить к чему? К исходной система — она останется линейной (т.е., применять симплекс метод можно), к модифицированной — она останется нелинейной.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group