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

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

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

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

Составим математическую модель задачи. Обозначим размер пополнения запасов в k-м промежутке времени через x_k, а уровень запасов в начале этого промежутка (после произведенного расхода) — через -Согласно условию, суммарные затраты в k-м промежутке зависят от x_k и — среднего уровня запасов в k-м промежутке, равного

(5.1)

Следовательно, затраты в k-м промежутке можно рассматривать как функцию

Целевая функция задачи — суммарные затраты — запишется в виде

(5.2)

Требуется определить переменные x_k, которые связаны с переменными балансовыми уравнениями

(5.3)

выражающими уровень запаса в начале (k+1)-гo промежутка через сумму уровня запасов в начале k-гo промежутка и пополнения запасов в этом промежутке x_k минус расход d_k.

Ставится задача — найти совокупность п переменных x_k, удовлетворяющих ограничениям (5.3) — (5.5) и минимизирующих функцию (5.2).

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

Дадим описание динамической модели задачи. Будем рассматривать n-шаговый процесс оптимизации с параметрами состояния и переменными управлениями x_k. Тогда равенство (5.3) представляет собой уравнение состояния. Здесь удобнее использовать прямую схему расчета, так как задано конечное состояние.

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

Обозначим через ) условные оптимальные затраты за промежутки, начиная с 1-го до k-гo включительно, если в конце k-гo промежутка уровень запасов равен .

Начинаем с условной оптимизации 1-го шага в предположении, что к концу этого шага система окажется в состоянии

(5.6)

На k-м шаге получим соответственно

(5.7)

В соответствии с формой рекуррентных соотношений удобно и уравнение состояния (5.3) записать в виде

(5.8)

При решении локальных задач в соответствии с уравнениями (5.6) и (5.7) будем считать, что состояние в конце шага известно. Поэтому и неравенство (5.4) удобно записать для т. е. в виде , откуда следуют ограничения на x_h:

(5.9)

Функцию затрат также удобно привести к зависимости от состояния в конце шага, используя уравнение (5.8):

Выполнив условную оптимизацию, получим последовательно

Далее (безусловная оптимизация), находим Z_max = при заданном конечном состоянии, или Z_max = и , если конечное состояние не задано. Затем последовательно определяем

Данная задача является примером общего случая, когда функции ) — затраты на производство и — затраты на хранение — являются вогнутыми (Функция f(x), определенная в промежутке X, называется вогнутой, если для любых точек x₁

X, x₂ X (x₁ x₂) выполняется неравенство f(t₁x₁+t₂x₂)≥t₁f(x₁)+t₂f(x₂) при любых t₁≥0, t₂≥0 таких, что t₁+t₂=1). Тогда суммарные затраты и целевая функция также вогнутые функции от переменных

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

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

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

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

Например, функция

является вогнутой, так как коэффициент при x_h убывает с ростом x_h

Известно, что глобальный минимум вогнутой функции достигается по крайней мере в одной из угловых точек области. В рассмотренном выше случае область задана системой п линейных уравнений (5.3). и условиями неотрицательности (5.4) и (5.5). Угловым точкам области соответствуют опорные решения системы (5.3); в каждом из которых не более чем п переменных x_k и положительны, а остальные равны нулю. Предположим, что все . Тогда, при любом k, если , то , а если , то , иначе нечем будет обеспечить расход d_k к концу k-гo периода. Одновременно невозможно, чтобы , так как при этом в опорном решении системы (5.3) оказалось бы более чем п положительных составляющих.

Из уравнения состояния (5.8) получим

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

Для 1-го шага (k=1) имеем и, следовательно,

Оптимальное управление пополнением запасов x_k на любом k-м шаге имеет следующий вид:

Задача 2. Определить оптимальное пополнение запасов в течение четырех периодов при следующих условиях: пополнение запасов может производиться партиями, кратными 50; функции затрат на хранение и на пополнение , одинаковые для всех периодов времени, заданы в табл. 2:

Задача носит дискретный характер. Для упрощения, поскольку расход и пополнение кратны 50, расчеты будем вести в целых партиях. Таким образом, d₁ = 3, d₂=l, d₃ = 2, d₄ = 2, переменные x_h и параметры меняются с шагом в единицу. Вычисления выполняем в соответствии с моделью, приведенной в задаче 1. Как обычно, при выполнении первого этапа расчеты производим в таблицах: основной (табл. 3) и вспомогательных (табл. 4—7).

Для 1-го шага имеем единственное значение . Поэтому

Прежде чем перейти к табулированию, определим предельные значения для параметров состояния. Так как , то даже при должно быть , следовательно, . Соответственно

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

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

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

Уточним постановку задачи. Возможны три варианта в очередности пополнения и расходования запасов в каждом из промежутков времени: I вариант — пополнение предшествует расходу; II вариант — расход предшествует пополнению и III вариант — очередность любая.

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

Указанные варианты условия отразятся на форме ограничений модели задачи.

Составим динамическую модель задачи. Рассмотрим n-шаговый процесс, понимая под k-м шагом промежуток времени, в котором принимается решение о пополнении или расходовании запасов (k = 1, 2,..., п).

В качестве параметров состояния примем запас товаров в начале k-гo шага. Переменными управления служат размеры пополнения (х_к) и расхода (у_к) запасов на k-м шаге. Тогда уравнение состояния, выражающее материальный баланс запасов, запишется в виде

(5.11)

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

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