Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Реферат

по дисциплине: Математическое моделирование

ДИНАМИЧЕСКАЯ ЗАДАЧА ВЫБОРА ОБЪЕМА ПАРТИЙ

Иркутск, 2009 год

1. Постановка задачи

Предприятие должно разработать календарную программу выпуска некоторого вида изделий на плановый период, состоящий из N отрезков. Предполагается, что для каждого из отрезков известен точный прогноз спроса на выпускаемую продукцию; для разных отрезков времени спрос:

- не одинаков. Временем изготовления партий изделий пренебрегаем. Стоимость выпуска партии с(х_і) зависит от ее объема. Сюда же входят затраты на наладку оборудования, которые не зависят от объёма выпускаемых изделий, но эти затраты присутствуют в каждом изготовлении партии изделий.

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

Обозначим через S(y_i) затраты по хранению избыточного запаса y_i на i-ом отрезке.

Требуется определить такую программу выпуска x_i в каждом из отрезков, при которой минимизируется общая сумма затрат на производство и содержание запасов, при условии полного и своевременного удовлетворения спроса на продукцию в каждом из отрезков.

Число отрезков N = 8, сумма затрат на производство и содержание запасов продукции на i-ом отрезке планового периода определяется выражением:

Где:

Здесь:

а = 16 - затраты на наладку оборудования в начале производства каждой партии изделий;

b(x_i) = 4x_i - затраты на изготовление одного изделия.

Спрос по периодам равен соответственно:

Выяснить, при каком соотношении между фиксированной стоимостью заказа партии А и удельными затратами на хранение S оптимальная программа изготовления деталей будет совпадать со спросом. Разработанный программный продукт должен обрабатывать числовые значения из заданного диапазона:

а) число отрезков N может быть 7, или 8, или 9;

б) спрос на каждом отрезке планового периода может быть задан;

в) затраты на наладку оборудования в начале производства каждой партии изделий могут быть;

г) затраты на изготовление одного изделия могут быть;

д) затраты по хранению запаса y_i на i-ом отрезке могут вычисляться по формуле:

2. Обоснование математической модели

Cумма затрат на производство и содержание запасов продукции на i-ом отрезке планового периода определяется выражением:

Где:

Здесь:

a - затраты на наладку оборудования в начале производства каждой партии изделий;

b(x_i) = 4x_i - затраты на изготовление одного изделия.

Общий вид:

Где:

A > 0 - стоимость одного запуска станка;

N > 0 - количество запусков станка;

B > 0 - стоимость изготовления одной детали;

S > 0 - стоимость хранения одной детали;

x_i - количество деталей, произведенных в i-ый день;

y_i - количество деталей, взятых со склада в i-ый день.

- система ограничений:

Где:

x_i - количество деталей производимых в i-ый день;

y_i - количество деталей получаемых со склада в i-ый день;

y_i-1 - количество деталей сданных на склад в (i-1)-ый день, причем y для первого и последнего дня равен нулю, так как нет смысла сдавать детали на склад в последний день и невозможно получить со склада детали в первый день, так как склад пока пуст. (y₁ = 0 и у_n = 0);

d_i - спрос на продукцию в i-ый день.

Математическая модель:

Один запуск станка стоит 16 условных единиц, а производство одной детали 4. Хранение одной детали за одни сутки составляет условных единиц.

3. Краткие сведения о методе решения задачи

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

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

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

Так, если система в начале k - шага находится в состоянии и мы выбираем произвольное управление , то она придет в новое состояние в:

(1)

И последующие управления должны выбираться оптимальными относительно состояния .

Последнее, означает, что этих управлениях минимизируется величина:

То есть показатель эффективности на последующих до конца процесса шагах, обозначим через:

Выбрав оптимальное управление на оставшихся:

Получим величину, которая зависит только от , то есть:

Назовем величину условным минимумом. Если мы теперь выберем на k-м шаге некоторое произвольное управление , то система придет в состояние .

Согласно принципу оптимальности, необходимо выбирать управление так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на шагах, начиная с k-го и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

(2)

Получившего название основного функционального уравнения динамического программирования, или основного рекуррентного уравнения Беллмана.

Из уравнения (2) может быть получена функции:

Пока не будет определена величина, представляющая по определению значение показателя эффективности процесса в целом:

Решая уравнение (2) для определения условного максимума показателя эффективности шагов, начиная с k-го, мы определяем соответствующее оптимальное управление , при котором этот максимум достигается. Это управление также зависит от .

Основное значение уравнения (2), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции:

Что сводится к решению последовательности n задач, задаваемых соотношениями (1), каждое из которых является задачей максимизации функции одной переменной .

В результате последовательного решения п частных задач на условный максимум определяют две последовательности функций.

Условные минимумы и соответствующие им условные оптимальные управления.

Указанные последовательности функций в дискретных задачах получают в табличной форме, а в непрерывных моделях - аналитически. После выполнения первого этапа (условной оптимизации) приступают ко второму этапу - безусловной оптимизации.

Если начальное состояние задано , то непосредственно определяют искомое безусловное оптимальное управление по цепочке:

(3)

Если задано множество начальных состояний , то дополнительно решают еще одну задачу на минимум:

Откуда находят , а затем по цепочке (3) - безусловное оптимальное управление.

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

Приведем рекуррентные соотношения для этого случая. Уравнения состояний для прямого хода удобно записывать в виде:

Введем в рассмотрение условные минимумы показателя эффективности за k шагов, от 1-го до k-го. Повторив приведенные рассуждения, придем к следующей системе уравнений Беллмана:

В результате решения этих уравнений получим последовательности:

Далее определим безусловное оптимальное управление по цепочке:

.

4. Проверка достоверности полученных результатов

Рассчитав 3 шага, можно проверить программу, убрав ее ограничения на количество отрезков N.

Подставим значения в программу:

Получаем, что расхождений с программой нет, следовательно, результаты достоверны.

Теперь проверим правильность вычисления соотношения между фиксированной стоимостью заказа партии А и удельными затратами на хранение S, при которой, оптимальная программа изготовления деталей будет совпадать со спросом, т. е.:

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

Проверим правильность графика, подставив в целевую функцию.

Рассчитав 3 шага, можно проверить программу, убрав ее ограничения на количество отрезков N и поля «Затраты на хранения». Подставим значения в программу:

Получаем, что по оптимальной программе хранить продукцию на складе не выгодно и целевая функция не зависит от затрат на хранение S, следовательно, график построен верно.

5. Алгоритм решения задачи

1. Проверка правильности ввода данных.

2. Начиная с последнего дня, подсчет на основе системы ограничений:

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

3. Подсчет значений целевой функции:

Для каждой полученной комбинации удовлетворения спроса.

4. Поиск минимального значения целевой функции:

И соответствующей ей комбинации удовлетворения спроса.

5. Вывод в окно программы минимального значения целевой функции и соответствующей ей комбинации удовлетворения спроса в виде удобном для просмотра.

Размещено на Allbest.ru