Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.06.2007, 03:51
Новичок

Отправить личное сообщение для Fedorenko Посмотреть профиль Найти все сообщения от Fedorenko
 
Регистрация: 18.06.2007
Сообщений: 3

Задача на динамическое программирование
Условие задачи.
Процесс производства продукции занимает 5 периодов. Максимальное число единиц продукции производимой за один период ограничено значением 4. Стоимости производства {0,1,2,3,4} единиц продукции для каждого периода {I,II,III, IV, V} заданы в виде таблицы. Определены также цены на хранение уже произведенной продукции (Х руб. за хранение одной единицы произведенной продукции на протяжении одного периода). Необходимо так распределить производство 15 единиц продукции по периодам, чтобы затраты на производство были минимальными.

Не удается решить задачу используя идеологию динамического программирования.

Из условия задачи следует, что не все возможные управления (назначенные к производству количества единиц продукции) на каждом отдельно взятом периоде приводят к тому, что при завершении производства (период 5) будет произведено ровно 15 единиц продукции.

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

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

Не удалось найти подходящий алгоритм и в разделе динамического программирования "Детерминированные модели управления запасами" (не удалось классифицировать приведенную задачу, как одну из возможных задач управления запасами).

Спасибо.

Последний раз редактировалось Fedorenko, 18.06.2007 в 07:02.
  #2  
Старый 18.06.2007, 10:28
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Правильно ли я понял, что Cost[np,0], где ns - номер периода, второй индекс - количество единиц, может быть ненулевой, а Cost[np, k] <> k * Cost[np, 1]? Иначе задача упрощается и решается жадным методом

P.S. В данном случае имеется всего 121 вариант распределений, дающих в сумме 15 единиц.

Последний раз редактировалось MBo, 18.06.2007 в 10:44.
  #3  
Старый 18.06.2007, 17:53
Новичок

Отправить личное сообщение для Fedorenko Посмотреть профиль Найти все сообщения от Fedorenko
 
Регистрация: 18.06.2007
Сообщений: 3

Да, Cost[np,0] для всех np в данном случае не равен нулю. Эти значения могут быть интерпретированы на практике как стоимость простоя оборудования, например.
Выполняется и неравенство: Cost[np, k] <> k * Cost[np, 1].

Да, имеется всего 121 вариант. Для этих вариантов уже сделана попытка построить взвешенный граф, дабы потом оптимальный путь дал решение задачи. Но этот процесс слишком трудоемок, хоть и осуществим. Должно быть, по-видимому, другое решение.
  #4  
Старый 18.06.2007, 18:07
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Ну про 121 вариант я упомянул, потому что в данном случае их легко и быстро перебрать, выбрав оптимальный по общей стоимости (как я понимаю, Full_Cost[np, k] = Cost[np,k] + k * (5-np) * UnitStorageCost), но тебя интересует решение для общего случая, так?

Мне не удалось пока что придумать метод для решения дин. прогр. или свести проблему к задаче о назначениях - ограничения мешают, не соображу, как их учесть.
  #5  
Старый 30.06.2007, 10:11
Новичок

Отправить личное сообщение для Fedorenko Посмотреть профиль Найти все сообщения от Fedorenko
 
Регистрация: 18.06.2007
Сообщений: 3

Решение задачи приложено к данному сообщению(-).
Решение задачи приложено к данному сообщению.
Вложения:
Тип файла: zip solution.zip (5.7 Кб, 343 просмотров)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
динамическое программирование. Артур Поиск и обсуждение книг/сайтов 9 19.01.2009 00:18
динамическое программирование по профилю artie Задачи 6 11.01.2007 18:01