УЧЕБНИКИ 3 Экономика / Управленческие решения / Степанов А.Г. Разработка управленческого решения средствами пакета Excel. 2001

Метод сетевого планирования

Теория управления проектами рассматривает понятие проекта как некоторое мероприятие с ограниченными ресурсами и сроками [16, 17]. Характерным признаком проекта можно считать возможность его разбиения на ряд отдельных элементарных работ, которые выполняются независимо друг от друга. Как правило, в этом случае можно выделить работы, выполнение которых не может быть начато ранее, чем завершены некоторые другие. Математическим методом, используемым для разработки решений в управлении проектами, является метод сетевого планирования.

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

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

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

61

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

Решение задач сетевого планирования в управлении проектами (в том числе, в условиях риска и неопределенности) в настоящее время обеспечивается специализированными программными комплексами, такими как Time-line, Microsoft Project, Primavera. Встроенные программные средства содержат, в частности, и возможности оптимизации решения задач синтеза. Таким образом, следует признать, что решение указанного класса динамических задач уже доведено до практической деятельности менеджера.

Методы теории массового обслуживания

Предметом исследования теории массового обслуживания являются так называемые системы массового обслуживания, предназначенные для выполнения какого-то потока заявок, поступающих в систему в общем случае в случайные моменты времени [18]. Показателями эффективности работы системы массового обслуживания являются: среднее (математическое ожидание) числа заявок, обслуживаемых в единицу времени; среднее число заявок в очереди, среднее время ожидания обслуживания; вероятность отказа в обслуживании без ожидания; вероятность того, что число заявок в очереди превысит определенное значение. Системы массового обслуживания подразделяются на два основных класса – с отказами и с ожиданием. Последние в свою очередь подразделяются на виды в зависимости от того, как организована очередь: с ограниченной или с неограниченной длиной, с ограниченным или с неограниченным временем ожидания и т.п. При классификации систем массового обслуживания большое значение имеет дисциплина выбора заявок из числа поступивших и распределение их по каналам обслуживания (“первым пришел – первым обслужен” или “последним пришел – первым обслужен”). Наконец, во внимание может приниматься приоритет обслуживания, регулирующий место заявки в очереди. Таким образом, средствами теории массового обслуживания могут решаться прикладные задачи менеджмента. Как было указано ранее, следует различать прямую задачу (задачу анализа) и обратную задачу (задачу синтеза), являющуюся основной задачей при разработке управленческого решения. Методы теории массового обслуживания доведены до практической деятельности менеджера специализированными пакетами программного обеспечения, такими как GPSS, Math-Cad и т.п.

62

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

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

Водной из возможных постановок [14] предметом вариационного

исчисления является отыскание неизвестных функций y(x) или yi(x), реализующих максимум или минимум определенных интегралов вида

x2

I = ∫ F[ y( x), y′( x), x]dx

x1

или

x2

I = ∫ F[ y1( x), y2 ( x),..., yn ( x); y1′( x), y2′ ( x),..., yn′ ( x); x]dx,

x1

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

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

Развитие идей вариационного исчисления привело к определенной модернизации постановки исходной задачи в виде учета ограничений функции y(x) и созданию теории оптимального управления. Методы решения подобных задач опираются на реализацию так называемого принципа максимума Понтрягина [20]. Практическая реализация методов

63

вариационного исчисления позволяет решать динамические задачи разработки управленческого решения [21].

Методы решения дискретных задач

Рассмотренные ранее динамические задачи формулировались в предположении непрерывности времени как аргумента. Во многих приложениях менеджмента это допущение является неверным. Очень часто приходится сталкиваться с задачами, для которых интересующие зависимости определяются только в некоторые фиксированные моменты времени, число которых может быть ограниченным. Математически в этом случае обычное непрерывное время t заменяется неким набором дискретных отсчетов t = n∆ tn, где n – номер отсчета, а ∆ tn – шаг дискретизации, n = 0,1,2,…, N–1,… – номер отсчета. Обычно рассматривают эквидистантные задачи, для которых ∆ tn= ∆ t = const.

Дискретное представление исходных зависимостей заставляет вводить в рассмотрение не интегральные зависимости, а суммы. Формально такая замена проводится достаточно легко, однако в этой операции имеется ряд тонких моментов, которые необходимо принимать во внимание. К их числу следует в первую очередь отнести размер выборки N.

Если число N сравнительно велико,

	x(t)	а шаг дискретизации Dt оказывает-
		ся относительно небольшим, проце-
		дура дискретизации не оказывает су-
		щественного влияния на результат
		решения (рис. 3.5).
	t	Ситуация существенно меняется
		в том случае, когда за время интер-
	Рис. 3.5. Дискретизация	вала дискретизации функция успева-
	с малым шагом при большом N	ет существенно измениться, а само
		число ее отсчетов невелико (рис.3.6).
	x(t)	Если в первом случае можно го-
		ворить о приближенном дискретном
		представлении, то во втором речь
		идет о существенном искажении
		вида функции, что приводит к серь-
	t	езным изменениям в структуре ре-
	Рис. 3.6. Дискретизация	шения и может дать существенно от-
	с большим шагом при малом N	личные результаты. Основным ме-

64

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

∞

X ( jω )= ∫ x(t) exp(− ωj t)dt= F ( x(t)).

−∞

Существует обратное преобразование

		1	∞
	x(t) =		∫ X ( jω ) exp( ωj t) ωd= F −1( Xω ( j )).
		2π
			−∞

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

H ( jω )= Y ( jω ) .

X ( jω )

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

Исследование дискретных выборок может производиться за счет дискретизации исходного выражения шагом T

X ( jω )= ∑∞	x[n]exp(− ωj n).
n=−∞

Обратное преобразование в этом случае имеет вид

π

x[n] = 21π −∫π X ( jω ) exp( ωj n)ωd .

Если дискретная выборка ограничена N отсчетами, то возможны два представления спектра – непрерывное

N −1
X ( jω )= ∑	x[n]exp(− ωj n),	(3.12)

n=0

65

		1			π
	x[n] =				∫	X ( jω ) exp(ωj		n)ωd			(3.13)
		2π
					−π
	и дискретное
			1		N −1			2π np
	X [ p] =				∑	x[n]exp(− j				),	(3.14)
			N n=0						N
	N −1						2π np
	x[n] = ∑				X [ p]exp( j				),		(3.15)
	n=0						N

где p – номер спектральной составляющей. Первая пара выражений (3.12) и (3.13) представляет собой преобразование Фурье дискретной конечной выборки, а вторая пара (3.14) и (3.15) получила название дискретного преобразования Фурье.

Важной особенностью дискретного преобразования Фурье является наличие конечного числа N спектральных отсчетов, что позволяет вычислять его точно. Для дискретного преобразования найдены методы, позволяющие вычислять его с меньшим числом математических операций, чем требуется по основной формуле, получившие название быстрого преобразования Фурье (БПФ). Обычно именно это преобразование реализовано в виде функций или надстроек в типовых программных системах. Следует отметить, что, в отличие от преобразования Фурье дискретной конечной выборки, дискретное преобразование Фурье периодизирует исходный процесс во временной области, повторяя исходную выборку N отсчетов бесконечное количество раз. Это обстоятельство приходится принимать во внимание при сравнении спектров X(jw) и X(p) особенно при малых N.

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

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

Динамическим программированием называется метод оптимизации, в котором процесс принятия решения может быть разбит на шаги [15]. Каждый шаг переводит объект управления из состояния Sk в состояние

66

Sk+1 посредством управления Xk. Если общее количество шагов равно n, то можно говорить о последовательности состояний S0 , S1,..., Sk −1, Sk ,..., Sn−1, Sn системы, которую она принимает в результате воздействия n различных управлений X(X1, X2,…, Xk,…, Xn). Целевая функция системы зависит от начального состояния и управления

E=E(S0,X).

Предполагается, что состояние системы Sk в конце k-го шага зависит только от предшествующего состояния Sk-1 и управления на k-м шаге Xk. Тогда уравнение состояния системы имеет вид

Sk = ϕ k (Sk −1, X k ), k = 1,2,..., n.

Если считать целевую функцию аддитивной от показателя эффективности каждого шага, то на шаге k ek = ek (Sk −1, X k ), и целевая функция имеет вид

E = ∑n ek (Sk −1, X k ).

k =1

Решением задачи динамического программирования является определение такого управления X(X1, X2,…, Xn), которое переводит систему из состояния S0 в состояние Sk при наибольшем (наименьшем) значении Е.

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

Рассмотрим последний шаг n. Состояние системы к началу шага

Sn–1, Xn – управление, а en (Sn−1, X n ) – целевая функция. Согласно принципу оптимальности управление Xn нужно выбирать так, чтобы для любого состояния Sn–1 получался условный максимум целевой функции

e (Sn−1) en (Sn−1) = max{en (Sn−1, X n )}.

Решение X (Sn−1) , при котором достигается e (Sn−1) называется условным оптимальным управлением на шаге n. Условный максимум целевой функции отыскивается для всех возможных состояний системы на

67

последнем шаге. Далее рассматривается совместно последний и предпоследний шаг. Целевая функция в этом случае имеет вид

en−1(Sn−2 , X n−1) + en (Sn−1).

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

en−1(Sn−2 ) = max {en−1(Sn−2 , X n−1) + en (Sn−1)}.

{X n−1}

При известном управлении Xn–1 состояние системы

Sn−1 = ϕ n−1(Sn−2 , X n−1) . Поэтому целевая функция e (Sn−2 ) зависит только от состояния на предыдущем шаге и текущего управления. Далее

рассматривается три, четыре и т.д. последних шага. В общем случае для шага k получается уравнение Белмана, впервые разработавшего метод динамического программирования:

ek (Sk −1) = max{ek (Sk −1, X k ) + ek +1(Sk )}.

{X k }

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

en (Sn−1), en−1(Sn−2 ),..., e2 (S1), e1(S0 ),

X n (Sn−1), X n−1(Sn−2 ),..., X 2 (S1), X1(S0 ).

Решение задачи динамического программирования получается в результате подстановки конкретного значения S0 в выражение для решения на первом шаге X1(S0 ) и e1(S0 ) . Далее определяется состояние первого шага

S1 = ϕ 1(S0 , X1)

итак далее для всех n шагов. Оптимальное решение задачи получается при последовательном расчете оптимальных решений X i (Si ) и ei (Si−1)

иновых состояний Si+1 = ϕ i+1(Si X i ) .

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

68

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

Метод сведения динамической задачи к статической

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

E(k ) = E(C(k ), X	(k )) →	max,
gi (k ) = gi ( A(k ), X (k ))	{<=, =, >=}bj (k ),
где k – текущий момент времени, 0 ≤ k≤		L− 1 .

Рассмотрим совместную однокритериальную статическую задачу в условиях определенности, решение которой X представляет собой набор из L самостоятельных решений X[k] для текущего момента времени k. Будем считать, что критериальная функция новой совместной задачи определяется как сумма критериальных функций для каждого момента времени, а ограничения для каждого момента времени добавляются к общему списку ограничений задачи. Тогда условие новой задачи можно записать как

Е(k) = ∑L	E(C(k), X (k)) → max,
k =0

gi (k ) = gi ( A(k ), X (k )) {≤= ,= ,≥ }bi (k ),

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

Реализация метода в общем случае приводит к существенному росту трудоемкости вычислений. Отметим, что если количество перемен-

69

ных при использовании метода всегда возрастает в L раз, то число уравнений ограничений может быть значительно сокращено за счет конкретного рассмотрения динамических параметров. Так, если к категории динамических относятся один или несколько параметров bi, то рассмотрение каждого из них во времени увеличивает количество ограничений в L раз. Для статических bi нет необходимости увеличивать количество уравнений, поскольку в этом случае они имеют смысл величины имеющегося ресурса на весь интервал планирования. Наконец, зависимость от времени неконтролируемых факторов C и A вообще может быть легко учтена при записи выражения целевой функции или ограничений особенно в численной форме.

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

Задача управления запасами

Задача управления запасами впервые была описана и решена в 1915 году Фордом Хариссом [24]. В ее основе лежит проблема, связанная с рассогласованием режимов работы поставщика и потребителя. Наличие склада позволяет обеспечить независимость работы потребителя от условий поставки материальных ресурсов. Затраты на содержание складского хозяйства включают в себя собственно затраты на хранение, затраты на взаимодействие с поставщиками (затраты на оформление заказа), на компенсацию дефицита и на информационное обеспечение складского хозяйства.

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

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

70