182169 (629343), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

(4.5)

Уравнение состояния выражает остаток средств после k-гo шага и имеет вид

(4.6)

Пусть —условный оптимальный доход, полученный от распределения средств между двумя предприятиями за n—k+1 лет, начиная с k-гo года до конца рассматриваемого периода. Запишем рекуррентные соотношения для этих функций:

(4.7)

где - определяется из уравнения состояния (4.6).

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

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

Задача 3. Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течение трехлетнего планового периода при следующихусловиях:

1) начальная сумма составляет 400;

2) вложенные средства в размере х приносят на предприятии I доход f₁(x) и возвращаются в размере 60% от х, а на предприятии II — соответственно f2(x) и 20%;

3) ежегодно распределяются все наличные средства, получаемые из возвращенных средств:

4) функции f₁(x) и f2(x)заданы в табл. 1:

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

Процесс управления является трехшаговым. Параметр — средства, подлежащие распределению в k-м году (k=l, 2, 3). Переменная управления — средства, вложенные в предприятие I в k-м году. Средства, вложенные в предприятие II в k-м году, составляют Следовательно, процесс управления на k-м шаге зависит от одного параметра (модель одномерная). Уравнение состояния запишется в виде

(4.8)

А функциональные уравнения в виде

(4.9)

(4.10)

Попытаемся определить максимально возможные значения, для которых необходимо проводить табулирование на k-м шаге (k=l, 2, 3). При =400 из уравнения (4.8) определяем максимально возможное значение имеем = 0,6*400=2400 (все средства вкладываются в предприятие I). Аналогично, для получаем предельное значение 0,6*240 = 144. Пусть интервал изменения совпадает с табличным, т. е. Δх =50. Составим таблицу суммарной прибыли на данном шаге:

Это облегчит дальнейшие расчеты. Так как то клетки, расположенные по диагонали таблицы, отвечают одному и тому же значению , указанному в 1-й строке (в 1-м столбце) табл. 2. Во 2-й строке таблицы записаны значения f₁(x), а во 2-м столбце — значения f₂(у)взятые из табл. 1.Значения в остальных клетках таблицы получены сложением чисел f₁(x) и f₂(у),стоящих во 2-й строке и во 2-м столбце и соответствующих столбцу и строке, на пересечении которых находится данная клетка. Например, для =150 получаем ряд чисел: 20 —для х = 0, у=150; 18 —для х=50, у=100; 18— для х—100, у=50; 15 — для х= 150, у=0.

Проведем условную оптимизацию по обычной схеме. 3-й шаг. Основное уравнение (4.9)

Как указывалось выше, . Просмотрим числа на диагоналях, соответствующих =0; 50; 100; 150 и на каждой диагонали выберем наибольшее. Это и есть В 1-й строке находим соответствующее условное оптимальное управление. Данные оптимизации на 3-м шаге поместим в основную таблицу (табл. 4). В ней введен столбец Δх, который в дальнейшем используется при интерполяции.

Оптимизация 2-го шага проведена в табл. 5 согласно уравнению вида (4.10):

При этом может быть получен максимальный доход, равный Zmax=99,l. Прямой подсчет дохода по табл. 2 для найденного оптимального управления дает 97,2. Расхождение в результатах на 1,9 (около 2%) объясняется ошибкой линейной интерполяции.

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

2.2.5 Оптимальное управление запасами

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

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

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

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

Управление запасами в общем случае состоит в воздействии на соотношение между двумя основными факторами— пополнением и расходом. Цель управления — оптимизация некоторого критерия, зависящего от расходов на хранение запасов, стоимости поставок, затрат, связанных с пополнением, штрафов и т. д.

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

Запасами могут быть товары, поставляемые в магазин определенными партиями и предназначенные для удовлетворения непрерывного, но подверженного случайным колебаниям покупательского спроса. Критерий оптимальности — суммарные затраты на поставки, хранение запасов и изменение производственного ритма в связи с вариациями спроса.

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

Число таких примеров можно было бы умножить. Однако в настоящем параграфе мы рассмотрим лишь некоторые простейшие динамические модели задач управления запасами.

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

Рассмотрим модель задачи управления запасами при заданном расходе. Управление в этих задачах будет сводиться к пополнению.

Задача 1. Планируемый период разделен на n промежутков времени (дни, месяцы, кварталы и т. д.), в которых задан расход d_k (k=l, 2, ..., п), производимый в конце каждого из промежутков. Известны начальный уровень запасов и зависимость суммарных затрат на хранение и пополнение запасов в данном периоде от среднего уровня хранимых запасов и их пополнения.

Характеристики

Список файлов курсовой работы