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

[TamaGOch]

Есть такая задача, приведу её слово в слово.
Предприятие выпускает телевизоры и кинескопы. Фиксированные затраты на выпуск партии кинескопов равны 2500 денежных единиц. Затраты на выпуск одного кинескопа равны 8,5 денежных единиц. График выпуска телевизоров требует следующего выпуска количества кинескопов в текущем году по месяцам:
1) 150
2) 250
3) 200
4) 150
5) 110
6) 60
7) 50
8) 110
9) 130
10) 240
11) 300
12) 80
Временем, необходимым для выпуска кинескопов можно пренебречь. Решение о выпуске кинескопов принимается один раз в месяц. Найти наилучшее время для выпуска кинескопов и размер этих партий, если в настоящий момент их имеется 10, а в конце года желательно иметь 50.

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

пусть за $x_k$ обозначим количество кинескопов, имеющихся в наличии в конце $k$-го месяца, которые остались после производства телевизоров в этом месяце.
При этом $k$ меняется от 1 до 12 и есть некоторая фиктивная величина $x_0 = 10$.
По условию задачи, $x_{12} \geqslant 50$
Так же учитывается, что $x_k \geqslant 0$
За $U_k$ обозначу количество кинескопов, произведённых в начале $k$-го месяца, до производства телевизоров.
Ограничение сверху для величины $U_k$: $U_k \leqslant 294$, то есть максимальное число кинескопов, которые можно произвести по цене 8,5 за штуку при лимите 2500 денег на месяц.
Рекуррентная формула: $x_k = x_{k-1} + U_k - f_k$, где $f_k$ - требуемое количество кинескопов в $k$-ом месяце.
из соотношения $x_k \geqslant 0$ выводим нижнюю оценку для $U_k$: $f_k - x_{k-1} \leqslant U_k$
итого $f_k - x_{k-1} \leqslant U_k \leqslant 294$
Теперь ввожу функцию затрат
$d_k(U_k) = U_k \cdot 8,5$ - это количество денег, потраченных в $k$-ом месяце на производство кинескопов.

Решать буду как наc учили, с использованием функции Беллмана, это когда выбирается оптимальное управление за 1 шаг до конца, за 2 шага, и т.д. И буду минимизировать общие затраты. Ведь надо же что-то минимизировать.
Но сначала учту, что просят наличие 50 кинескопов в конце года, то есть $x_{12} \geqslant 50$ или $x_{11} + U_{12} - f_{12} \geqslant 50$ или $U_{12} \geqslant 50 + f_{12} - x_{11}$
Тогда
$S_1(x_{11}) = \min_{ 50 + f_{12} - x_{11}\leqslant U_{12} \leqslant 294}(d_{12}(U_{12})) = \min_{ 130 - x_{11}\leqslant U_{12} \leqslant 294}(U_{12} \cdot 8,5)=1105 - 8,5 \cdot x_{11}$
Пока вроде всё нормально, а вот в следующей записи, за 2 шага, возникает что-то нехорошее.
$S_2(x_{10}) = \min_{f_{11} - x_{10}\leqslant U_{11} \leqslant 294}(d_{11}(U_{11}) + S_1(x_{10} + U_{11} - f_{11})) = \min_{ 300 - x_{10}\leqslant U_{11} \leqslant 294}(U_{11} \cdot 8,5 + 1105 - 8,5 \cdot (x_{10} + U_{11} - 300)) = \min_{ 300 - x_{10}\leqslant U_{12} \leqslant 294}(3655 - 8,5 \cdot x_{10}) $
то есть, начиная с этого момента, и далее, ничего не зависит от управления.
Прошу подсказать, правильно ли я решаю для той формулировки, которую я понял. Или стоит вообще иначе понимать эту задачу?

[grizzly]

TamaGOch в сообщении #958523 писал(а):

Как по мне, эта задача достаточно криво сформулирована.

Даже не знаю, что ещё можно сказать сверх этого.

Вопрос. Как Вы понимаете:

TamaGOch в сообщении #958523 писал(а):

Фиксированные затраты на выпуск партии кинескопов равны 2500 денежных единиц.

Я это понимаю примерно так:
Если мы решили выпустить партию из 10 кинескопов, то это нам обойдётся в сумме в $2500+10\cdot 8,5$ д.е.
Но это я так понимаю по опыту общения с бухгалтерами и экономистами. А как это бывает в идиотских задачниках, не уверен.

[Евгений Машеров]

Если не заданы расходы, связанные с избыточным запасом кинескопов (складское хранение, проценты за кредит и т.п.), а также ограничения на размер склада, то оптимальное решение - заказать в начале года 1870 кинескопов. Тогда расходы на запуск партии, равные 2500 денежных единиц, распределятся на эти 1870 штук. При любом другом распределении запускать придётся две и более партий, соответственно расходуя 5000, 7500 и т.д. единиц вместо 2500. В реалистичной постановке есть расход на хранение, и его снижение может потребовать разбивки на две и более партии, несмотря на появление расходов на запуск новых партий. Могут быть также соображения не допустить "омертвления капитала" и пр. Но данных для этого не приведено.

[grizzly]

Евгений Машеров
Идеальное объяснение. Но я не рискнул выйти с таким к ТС: меня насторожила фраза

TamaGOch в сообщении #958523 писал(а):

Решение о выпуске кинескопов принимается один раз в месяц.

Вполне возможно, что партия выпускается каждый месяц, а фиксированные расходы на нулевую партию составляют те же 2500 д.е. (Кто сталкивался с производством, поймёт :) Но даже при таких допущениях задача умнее не становится.

[TamaGOch]

А если всё таки забыть про формулировку, и попробовать её решать, как я понял. То есть каждый месяц от нас требуется наличие какого-то количества кинескопов. Раз в месяц мы их производим. Производим некоторое количество от нуля до 294. И стараемся, чтобы вот то требуемое количество всегда было, не забывая и о следующих месяцах.
Просто независимо от деталей этой задачи, оптимальное решение должно быть. Так пусть я её понял так, но ход решения всё равно не даёт мне ответа, как быть?

[Евгений Машеров]

А волшебное число 294 откуда? Оно в условии есть? Может, там ещё что-то найдётся?

[grizzly]

Евгений Машеров в сообщении #958653 писал(а):

А волшебное число 294 откуда? Оно в условии есть?

Да нет, это от неправильного понимания фиксированных затрат. Я почему и спрашивал. ($294=\lfloor 2500/8.5 \rfloor$.)

-- 08.01.2015, 19:10 --

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

[TamaGOch]

TamaGOch в сообщении #958523 писал(а):

Ограничение сверху для величины $U_k$: $U_k \leqslant 294$, то есть максимальное число кинескопов, которые можно произвести по цене 8,5 за штуку при лимите 2500 денег на месяц.

[Евгений Машеров]

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

[grizzly]

TamaGOch
В любом случае я тоже предлагаю считать "фиксированные затраты" дополнительно отдельно на партию, независимо от количества единиц. (По правилам "фиксированные затраты" учитываются также и во время простоя, но здесь лучше не усложнять.)

Если у Вас больше нет данных и Вы не можете уточнить задачу, то я предлагаю Вам пойти по такому пути.
1) Рассчитайте план выпуска на год при следующих условиях / ограничениях:
а) раз в месяц выпускается точно одна партия телевизоров.
б) план минимизирует количество денег, в которых возникнет необходимость для выпуска максимальной партии. Для этого производство должно быть максимально равномерным, но гарантировать выполнение потребностей для телевизоров.

2) Рассчитайте план выпуска на год при следующих условиях / ограничениях:
а) Количество выпущенных партий в году равно 11.
б) план минимизирует количество денег, в которых возникнет необходимость для выпуска максимальной партии. Для этого производство должно быть максимально равномерным, но гарантировать выполнение потребностей для телевизоров.

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

-- 08.01.2015, 23:37 --

И кстати, в процессе решения п.1 вполне может оказаться (скорее всего так и будет), что 12 циклов -- излишняя роскошь и хватит меньшего количества. Тогда п.2 решать не нужно. Оптимальное количество в п.1 и будет решением.