Динамические модели управления ограниченными ресурсами в промышленной логистике (стр. 4 )

Сформулированная задача распределения ресурсов является линейного программирования (ЛП). Решение этой задачи может быть осуществлено методами линейного программирования.

Легко видеть, что если в качестве критерия оптимального деления ресурсов принять максимум прибыли от обработанного объема заявок, то показателем эффективности будет значение следующей линейной относительно функции

;

Где ci – прибыль, получаемая при обработке единицы объема заявок вида i (i=1,...,m).

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

Докажем следующее утверждение.

Утверждение 1. Пусть есть оптимальное распределение ресурсов на один день и объем обработанных заявок на каждой операции Oij за первый день. Если известно, что интенсивность поступления заявок в последующие P-1 день таковы, что выполняется система неравенств:

P=2,…,T; i=1,…,m; j=1,…,Ni,

тогда решение задачи распределения ресурсов на один день может быть перенесено на все последующие дни, если объемы обработки зая­вок по каждому виду wi (i=1,...,m) для решения на период в один день таковы, что выполняется следующее неравенство:

T wi ≥ bi, i=1,…,m.

Доказательство утверждения 1 следует из того факта, что предлагаемое решение задачи (13) - (16) является оптимальным для ситуации, когда вектор b=(0,…,0).

Учитывая неравенство (17), получим,  что условия (5) также выполнены для заданного вектора ресурсов b=(b1,…,bm), что и доказывает сформулированное утверждение.

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

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

Введем следующие определения.

Определение 1. Назовем задачу (13) - (16) устойчивой по специализации приборов, если существует такое > 0, что при увеличении всех нулевых элементов матрицы () на величину не более чем > 0 значение функционала (13) в решении задачи (13) - (16) остается неизменным.

Определение 2. Задача (13) - (16) устойчива по интенсивности поступающего потока заявок, если существует такое > 0 , что при увеличении потока заявок   на величину не более чем , значение функционала (13)  задачи (13) - (16) остается неизменным.

Определение 3. Задача (13) - (16) устойчива по производительности приборов, если существует такое > 0, что при увеличении всех ненулевых элементов матрицы () величину не более чем , значение функционала (13) при решении задачи (13) - (16) сохраняется.

Определение 4. Задача (13) - (16) устойчива по числу приборов, участвующих в обработке поступающего потока заявок, если существует такое >0, что при увеличении числа приборов на один с производительностями прибора по всем видам операций не более  , значение функционала (13) в решении задачи (13) -(16) не меняется.

Определение 5.

Задача (13) - (16) устойчива по плановым ограничениям, заданным вектором b=(b1,…,bm), если существует такое >0, что при увеличении координат вектора b  на величину не более чем , значение функционала (13) не изменяется.

Докажем следующие утверждения.

Утверждение 2. Задача (13) - (16) устойчива по специализации приборов и по интенсивности потоков заявок, если выполняются следующие соотношения:

а) > 0, j=1,…,m; l=1,…,N;

б) (i=1,…,m),

где Т* - число дней в директивном периоде планирования;

в)  (i=1,…,m),

Доказательство.

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

Устойчивость по специализации приборов вытекает из того, что по условию а) увеличение производительности приборов произойдет только на операциях, отличных от операций Oij(i=1,…,m). Из условий б) и в) следует, что загрузка приборов в оптимальном решении будет только на операциях O. 

Утверадение 3.

Задача (10) - (13) устойчива по производительности приборов и по их числу, если для каждой операции обработки выполняются следующие условия:

Vij(T)=0,  (i=1,…,m; j=1,…,Ni)

где Т - день окончания планового периода.

Доказательство.

Доказательство утверждения 3 следует из того факта, что весь объем поступивших заявок на обработку в систему полностью обработан,  поэтому наращивание производительности, участвующих в обработке приборов, не может увеличить значения функционала (13) задачи (13) - (16).

Утверждение 4.

Задача (13) - (16) устойчива по плановым ограничениям, гогда и только тогда, когда выполняется следующая система неравенств:

(i=1,…,m).                                                (18)

Доказательство.

Достаточность условия (15) вытекает из того, что при увеличении координат вектора b значение функционала (13) в оптимальном решении может только уменьшиться, поэтому, взяв в качестве величину, равную

,

получим по определению устойчивость задачи (13) - (16) при изменении плановых ограничений.

Необходимость условия (18) для устойчивости задачи (13) - (16) непосредственно вытекает из определения устойчивости по плановым ограничениям.

При анализе решений задачи (13) - (16) нередко необходи­мо не только выяснить, устойчива ли задача (13) - (16) по исходным параметрам, перечисленным в определениях 1 - 5, но и в случае, если задача устойчива, вычислить максимальное увеличение (уменьшение) входного параметра, при котором значение функционала (13) сохраняется.

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

max

p=1,…,T; для любого Oijи;, q=1,…T, l=1,…,N;

i=1,…,m; i=1,…,m; j=1,…,Ni; q=1,..,T; l=1,...,N,

Где - доля времени работы прибора l на операции Oij в день в решении (13)-(16) при интенсивностях поступления заявок ; - доля времени работы прибора l на операции Oij в день q при прежних интенсивностях поступления заявок

(i=1,…,m; j=1,…,Ni ;q=1,…,T).

Задача вычисления максимального приращения производительности приборов, при котором сохраняется значение функционала задачи оптимального распределения ресурсов (13)-(16), формулируется так:

max

;