Задача на узкие места

[Map]

Появились некоторые вопросы по задача динамического программирования, а точнее "задача на узкие места" Беллмана. Общая схема выглядит так:
$\frac {\partial u}{\partial T}=max_z_(_0_)[(A_1c+A_2z(0),\frac {\partial u}{\partial c})]$
,где $A_i$- матрицы, $c$ , $z$ - вектора.
При этом у Беллмана написано что это нелинейное УЧП.
Как пример возьмём такое уравнение:
$\frac {\partial u}{\partial T}=a_1z_1\frac {\partial u}{\partial c_1}+(a_2z_2-z_1)\frac {\partial u}{\partial c_2}$
где $a_i=1$, $c_1=c_2=50$ , $T=5$
При ограничениях
$z_i \geq 0$
$z_1+z_2 \leq c_2$
$z_2 \leq c_1$
$(a_2z_2-z_1) \geq 0$
Нужно максимизировать $c_2$ на интервале $[0;T]$ подобрав $z_i$.
Т.к. сама задача решается численно, то она может решаться часами, в зависимости от колличества переменных, принимаемых ими значений и шагов. Условия целочисленности нет.
Мог бы кто-нибудь подсказать по поводу численного решения, а то никак не могу написать код.

[Map]

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

[samson1]

я решал аналогичную задачу, долго искал подходящий численный метод, консультировался с математиками. в итоге пришел к выводу, что при наличии более одной подбираемой константы все предложенные методы работают ужасно, и написал решение тупым перебором (метод Монте-Карло). вышло очень даже хорошо, вскрылись подробности о возможных ситуациях, упущенные при анализе.

1. определяем, с каким шагом могут меняться ваши c1, c2, z1, z2, а также диапазоны их изменения.
2. фиксируем все четыре константы, решаем обыкновенный дифур каким-либо численным методом (хоть в том же матлабе). сохраняем результат.
3. делаем приращение одной константы, повторяем п. 2
4. когда пройден весь диапазон по первой константе, делаем приращение второй, и снова проходим весь диапазон по первой. и т д.

код в итоге примет вид четырех вложенных циклов for, внутри которых решается ОДУ.

количество точек в переборе определяется как n1*n2*n3*n4, где ni - количество точек в диапазоне изменения каждой константы.

можно оптимизировать процесс, исключая заведомо неудовлетворительные комбинации. они выявляются при решении ОДУ - т. е., в какой-то момент (после первых 2-3 шагов, например) становится понятно, что при данных c1, c2, z1, z2 решение не годится, и процесс прерывается.

при не слишком мелкой сетке все не так страшно и по времени, и по памяти. у меня был перебор по 4 константам - время около 2-3 минут, количество годных комбинаций - около 10000.

5. когда перебор закончен, выбираем из набора решений то, которое подходит лучше всего.

кстати, именно так - и никак иначе - делается прогноз надежности электронных схем, где много компонентов - каждый имеет свою характеристику ухода номинала от температуры, влажности, вибрации и тп, что в итоге порождает задачу вашего типа с 20-30 параметрами. и ничего - все решается. :)

[VPopov]

samson1 в сообщении #566598 писал(а):

я решал аналогичную задачу, долго искал подходящий численный метод, консультировался с математиками. в итоге пришел к выводу, что при наличии более одной подбираемой константы все предложенные методы работают ужасно, и написал решение тупым перебором (метод Монте-Карло). вышло очень даже хорошо, вскрылись подробности о возможных ситуациях, упущенные при анализе.

Но у Вас было много времени, а если подобную задачу нужно решить достаточно быстро. Обратите внимание при таком анализе также на нечеткую логику, которая поддерживает торию нечетких множеств Заде. Для иллюстрации ее эффективности при решении такого рода напомню ее историю. Когда появились системы ПРО, то для управления противоракетами необходимо было ставить на них чуть ли не суперком, чтобы он успел все просчитать для верного нанесения удара. По стоимости он превышал сам ЗУРс. Все это породило стратегические проблемы у государств, у которых таких суперкомпов не было, а ракеты были. Сложность задачи была сравнимой с задачей обеспечения попадания «пулей в пулю». И вообще решать систему дифференциальных уравнений в железе, создаваемых с помощью акселерометров и других специальных средств - это кошмарно сложная задача. Большинство стран, в том числе и супердержавы (в то время мы еще ею были) оказались беззащитными. Возникла насущная проблема, как бы сделать так, чтобы зенитные ракеты «поумнели», не становясь при этом такими же большими и дорогими, как их объекты преследования и уничтожения.
Американские военные пригласили группу ученых, во главе которой стоял математик нового мышления Бартоломей Коско. Он в отличие от своих коллег-догматиков, предложил совершенно неожиданное решение. А почему бы не использовать кристалл, в котором зашить функции управления, описанные не в виде четких параметров (на языке непротиворечивой и непогрешимой математики), а в виде нечетких терминов? (В 80-е годы, когда предлагалось это решение, в Японии уже появились нечеткие контроллеры – экспертные системы на одном кристалле) И функцию вычисления точного решения, которое, если говорить правду, невозможно в принципе (это только в черепных коробках некоторых математиков возможны точные решения) заменил чип, величиной со спичечный коробок. Этот чип заменил нахождение решения системы дифференциальных уравнений в частных производных сведением к гораздо более простой задаче подруливания (по траектории волчьей кривой). Ведь не всегда нужно сбивать ракету в точное время, в заданном месте, ее нужно догнать или встретить и просто сбить. Таким образом, достаточно, чтобы зенитная ракета была не такой «умной», чтобы вычислить, где и как она поймает свою цель, но достаточно «хитрой», чтобы рано или поздно ее догнать. А знания о том, как догнать ракету, могут быть записаны на одном чипе на языке нечеткой и немонотонной логики, поддерживающей теорию нечетких множеств Л.Заде.

[AKM]

VPopov,

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

[VPopov]

Я [url]все[/url] понял! И все же я настоятельно советую обратить внимание математиков и особенно программистов на нечеткую логику Заде.

[AKM]

Приказ по форуму:

Настоящим приказываю:

1. Всем математикам и программистам форума бросить ту ерунду, которой вы занимаетесь, и обратить внимание на нечеткую логику Заде!

2. Забанить пользователя VPopov на 3 дня за оффтопик, и для изучения Правил форума.