Динамическое программирование

[Alexey1]

Здравствуйте!
Скажите каким образом можно решить транспортную задачу с использованием динамического программирования? Как в этом случае определить состояния, управления, и т.п.. Ну например, если есть 2 источника сырья ($S_1 , S_2$) и три пункта назначения этого сырья ($D_1 , D_2 , D_3$). А также стоимости доставки сырья в каждый из пунктов назначения ($c_{ij}, i=1,2, j=1,2,3$). Кроме того, количество сырья в пунктах назначения не может быть меньше чем спрос на это сырье (равенство не имеется ввиду).
Сложность заключается именно в определении состояний, так как имеется два источника сырья и решения должны приниматься в отдельности для каждого из них. Если определить состояния как количество сырья в источниках, то начальное состояние известно для двух источников сырья, а вот конечное состояние только для их суммы.
Заранее спасибо.

[gris]

Очень запутанно у Вас написано в самом конце.
По ходу самая обычная транспортная задача.
Есть два источника сырья и известно, сколько сырья в каждом источнике.
Есть три пункта назначения и известна потребность в сырье для каждого из них.
Есть матрица стоимости перевозки единицы сырья.
Требуется удовлетворить потребителей за наименьшие деньги.
Если сумма сырья в источниках равна сумме потребности в нём, то задача задача будет замкнутой (закрытой). В случае неравенства вводим фиктивного потребителя или поставщика и сводим задачу к замкнутой.
Решается обычно методом потенциалов. Всё хорошо описано в учебниках.
В вашем случае прекрасно решится в Excel с помощью Solver("поиск решения", по моему).
Начёт осложнений задачи. Может оказаться, что условие состоит в том, чтобы на складах осталось не более или не менее некоторого количества сырья( порознь или в сумме), то есть некоторым потребителям придётся завести больше, чем им нужно или же наоборот, некоторых удовлетворить не полностью. А иначе зачем вести потребителю лишнее сырьё?
Постарайтесь более чётко написать условия задачи.

[Alexey1]

Большое спасибо за ответ. Описал не очень подробно, просто из литературы понял, что почему-то задачка (как Вы и сказали) стандартная.
Условие :
Источники сырья $S_1 , S_2$. Количество сырья в каждом источнике соответственно : $a_1=5, a_2=7$
Пункты назначения $D_1 , D_2 , D_3$. Спрос на сырьё в каждом пункте назначения соответственно : $b_1=3,b_2=2, b_3=6$.
Стоимость доставки $x$ единиц сырья $c_{ij}, i=1,2, j=1,2,3$ :
$c_{1,1} (x)=3+x^2$,
$c_{1,2} (x)=1+x^2$,
$c_{1,3} (x)=4+x^2$,
$c_{2,1} (x)=7+x^{3/2}$,
$c_{2,2} (x)=5+x^{3/2}$,
$c_{2,3} (x)=9+x^{3/2}$.
Смысл состоит в построении модели динамического программирования для решения задачи. Но для этого необходимо определить состояния системы, управления, и т.п. С этим вот и возникла сложность. Можно ли решить задачу без метода потенциалов?
Ещё раз спасибо.

[gris]

Ха! так это нелинейная задача. Сразу бы и написали.

[Alexey1]

И тем не менее возможно ли её решить в том смысле в котором я описал.

Добавлено спустя 27 минут 2 секунды:

Тут вот ещё такая подсказка появилась. При наличии $n$ источников и $m$ назначений, состояние будет вектором описывающим наличие сырья в $n-1$ источнике сырья. Но всё равно, каким же тогда образом выбрать эти состояния.