Управление запасами при заданном расходе

Процесс управления рассматривается как многошаговый разделенный на n – промежутков времени (дни, декады, месяцы и т.д.). В каждом из промежутков задан расход d _k k = 1, n. Известно начальный уровень запасов, а также зависимость суммарных затрат на хранение и пополнение запасов в данном промежутке k (на данном шаге) от среднего уровня хранимых запасов и от величины их пополнения. Требуется определить размеры пополнения запасов на каждом промежутке времени. Для обеспечения заданного расхода d _k при минимальных суммарных затратах за весь планируемый период. Обозначим размер пополнения запасов на каждом шаге x _k , а уровень запасов вначале k-го шага x _k-1 тогда средний уровень запаса определяется .

Основное баланссовое уравнение:

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

Затраты на весь период, целевая функция на весь период:

Условия обеспечения расхода и ограничения на управление .

Такого рода задачи при большом числе переменных (при больших n) и при нелинейности функции , это задача не может быть решена классическими методами, в особенности при целочисленных или дискретных x _k . Поэтому для решения такого типа задач используется метод динамического программирования.

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

Система должна быть переведена из некоторого начального состояния под действием управления U, в конечное состояние наиболее эффективным способом.

- вектор состояния

Компоненты его числа называют фазовыми координатами системы.

- вектор управления (или просто управление)

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

Z - целевой функционал (целевая функция), которая количественно выражает через начальное состояние и управление, принятый критерий оптимальности Z.

В динамическом программировании процесс принятия решений рассматривается как многошаговый.

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

Если обозначим эффективность процесса при оптимальном управлении на шагах от k+1 до n – ного т.е. это

То будут иметь место следующие рекуррентные соотношения

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

При решении задач методом динамического программирования выполняются следующие требования: для конкретно поставленной задачи выясняется, что есть состояние и что есть управление, определяется на какое число n шагов разбивается процесс; записываются уравнения состояния, почти всегда весьма целесообразно «запроектировать» процесс решения представив его в виде графа, в виде схемы или каким либо другим образом это помогает сформулировать основные рекуррентные соотношения динамического программирования (уравнения Беллмана), далее осуществляют условную оптимизацию обычно в форме специальных таблиц, «традиционным» при этом является развертывание процесса от конца к началу, далее осуществляется безусловная оптимизация и определяется оптимальный процесс, оптимальная фазовая траектория, выдается анализ полученного решения (обычно на предмет единственности или не единственности решения) дается интерпретация полученных результатов в терминах поставленной задачи.

Лекция №10. Динамическая модель задачи складирования

Постановка задачи: емкость склада ограничена некоторой величиной с. В каждом из n промежутков времени запасы могут пополняться с затратами a_n на единицу продукции и расходоваться с получением дохода b_n за единицу продукции, причем решение о пополнении или расходовании запасов принимается однократно в каждом промежутке времени. Определить оптимальную стратегию в управлении запасами из условия максимизации суммарной прибыли при заданном начальном уровне запасов.

Уточним постановку задачи. Возможны три варианта в очередности пополнения и расходования запасов в каждом из промежутков времени: 1 вариант – пополнение предшествует расходу; 2 вариант – расход предшествует пополнению и 3 вариант – очередность любая.

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

x _k = x _k-1 + x _k – y _k - уравнение состояния

Так как заданным является начальный уровень запасов на складе x ₀, процесс разворачивают от конца к началу, рекуррентные соотношения имеют вид:

Переменные x_k и y_k должны удовлетворять условиям неотрицательности:

x_k ³ 0 y_k ³ 0

Ограничения зависящие от варианта очередности:

1 вариант - x _k-1 + x_k £ с , y_k £ x _k-1 + x_k

2 вариант - x _k-1 – y_k + x_k £ с , y_k £ x _k-1

3 вариант - по обстановке 1 или 2.

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

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

1 вариант. x _k-1 + x_k £ с , y_k £ x _k-1 + x_k

2 вариант. x _k-1 – y_k + x_k £ с , y_k £ x _k-1

Начальное состояние x ₀ задано, условную оптимизацию разворачиваем от конца к началу

Если использовать случай (3), то к рассматриваемым добавляется точка С^*.

Дата добавления: 2014-03-15; просмотров: 473; Нарушение авторских прав

Мы поможем в написании ваших работ!