Некоторые экономические задачи, решаемые методами динамического программирования

Оптимальная стратегия замены оборудования

Одной из важных экономических проблем является опреде­ление оптимальной стратегии в замене старых станков, агре­гатов, машин на новые.

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

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

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

Введем обозначения: r(t) — стоимость продукции, произ­водимой за один год на единице оборудования возраста t лет;

u(t) — ежегодные затраты на обслуживание оборудования возраста t лет;

s(t) — остаточная стоимость оборудования возраста t лет;

Р — покупная цена оборудования.

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

Обозначим через f_N(t) максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стра­тегии.

Возраст оборудования отсчитывается в направлении тече­ния процесса. Так, t = 0 соответствует случаю использования нового оборудования. Временные же стадии процесса нумеру­ются в обратном направлении по отношению к ходу процесса. Так, N = 1 относится к одной временной стадии, остающей­ся до завершения процесса, а N = N — к началу процесса (рис. 29.1).

На каждом этапе N-стадийного процесса должно быть при­нято решение о сохранении или замене оборудования. Выбран­ный вариант должен обеспечивать получение максимальной прибыли.

Функциональные уравнения, основанные на принципе оп­тимальности, имеют вид:

Уравнение (29.1) описывает N-стадийный процесс, а (29.2) — одностадийный. Оба уравнения состоят из двух час­тей: верхняя строка определяет доход, получаемый при сохра­нении оборудования; нижняя — доход, получаемый при замене оборудования и продолжении процесса работы на новом обору­довании.

В уравнении (29.1) функция r(t) — u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N-й стадии процесса.

Функция f_N-1 (t + 1) характеризует суммарную прибыль от (N — 1) оставшихся стадий для оборудования, возраст которо­го в начале осуществления этих стадий составляет (t + 1) лет.

Нижняя строка (29.1) характеризуется следующим обра­зом: функция s(t) — Р представляет чистые издержки по замене оборудования, возраст которого t лет.

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

Последняя функция f_N-1 в (29.1) представляет собой доход от оставшихся N — 1 стадий, до начала осуществления которых возраст оборудования составляет один год.

Аналогичная интерпретация может быть дана уравне­нию для одностадийного процесса. Здесь нет слагаемого вида f₀(t + 1), так как N принимает значение 1, 2,..., N. Равенство f₀(t) = 0 следует из определения функции f_N(t).

Уравнения (29.1) и (29.2) являются рекуррентными соот­ношениями, которые позволяют определить величину f_N(t) в зависимости от f_N-1(t + 1). Структура этих уравнений показы­вает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N — 1).

Расчет начинают с использования уравнения (29.1). Урав­нения (29.1) и (29.2) позволяют оценить варианты замены и сохранения оборудования, с тем чтобы принять тот из них, ко­торый предполагает больший доход. Эти соотношения дают возможность не только выбрать линию поведения при реше­нии вопроса о сохранении или замене оборудования, но и опре­делить прибыль, получаемую при принятии каждого из этих решений.

Пример 1. Определить оптимальный цикл замены оборудо­вания при следующих исходных данных: Р = 10, S(t) = 0, f(t) = r(t) — u(t), представленных в табл. 29.1.

Решение. Уравнения (29.1) и (29.2) запишем в следующем виде:

Для N = 1

Для N = 2

Вычисления продолжаем до тех пор, пока не будет выпол­нено условие f₁(1) > f₂(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае ис­пользования старого. Результаты расчетов помещаем в табли­цу, момент замены отмечаем звездочкой, после чего дальней­шие вычисления по строчке прекращаем (табл. 29.2).

Можно не решать каждый раз уравнение (29.3), а вычис­ления проводить в таблице. Например, вычислим f₄(t):

Дальнейшие расчеты для f₄(t) прекращаем, так как f₄(4) = 23 < f₃(1) = 24.

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

Ответ. Для получения максимальной прибыли от ис­пользования оборудования в двенадцатиэтапном процессе оп­тимальный цикл состоит в замене оборудования через каждые 4 года.

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

Пусть имеется некоторое количество ресурсов х, которое необходимо распределить между п различными предприяти­ями, объектами, работами и т.д. так, чтобы получить мак­симальную суммарную эффективность от выбранного способа распределения.

Введем обозначения: x_i — количество ресурсов, выделен­ных i-му предприятию (i = );

g_i(x_i) — функция полезности, в данном случае это величи­на дохода от использования ресурса x_i, полученного i-м пред­приятием;

f_k(x) — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприя­тий.

Сформулированную задачу можно записать в математи­ческой форме:

при ограничениях:

Для решения задачи необходимо получить рекуррентное соотношение, связывающее f_k(x) и f_k-1(x).

Обозначим через х_k количество ресурса, используемого k-мспособом (0 ≤ x_k ≤ х), тогда для (k — 1) способов остается ве­личина ресурсов, равная (x — x_k). Наибольший доход, который получается при использовании ресурса (x — x_k) от первых (k — 1) способов, составит f_k-1(x — x_k).

Для максимизации суммарного дохода от k-гo и первых (k — 1) способов необходимо выбрать x_k таким образом, чтобы выполнялись соотношения

Рассмотрим конкретную задачу по распределению капита­ловложений между предприятиями.

Распределение инвестиций для эффективного использования потенциала предприятия

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

Для расширения производства совет директоров выделя­ет средства в объеме 120 млн р. с дискретностью 20 млн р. Прирост выпуска продукции на предприятиях зависит от вы­деленной суммы, его значения представлены предприятиями и содержатся в табл. 29.3.

Найти распределение средств между предприятиями, обес­печивающее максимальный прирост выпуска продукции, при­чем на одно предприятие можно осуществить не более одной инвестиции.

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

Рекуррентные соотношения будут иметь вид:

для предприятия № 1

для всех остальных предприятий

Решение будем проводить согласно рекуррентным соотно­шениям в четыре этапа.

1-й этап. Инвестиции производим только первому пред­приятию. Тогда

2-й этап. Инвестиции выделяем первому и второму пред­приятиям. Рекуррентное соотношение для 2-го этапа имеет вид

Тогда

при х = 20 f₂(20) = max (8 + 0,0 + 10) = max (8, 10) = 10,

при x = 40 f₂(40) = max (16,8 + 10,20) = max (16, 18, 20) =20,

при х = 60 f₂(60) = max (25,16 + 10, 8 + 20,28) = max (25,26, 28,28) =28,

при х = 80 f₂(80) = max (36,25 + 10,16 + 20,8 + 28,40) = max (36, 35, 36, 36, 40) = 40,

при х = 100 f₂(100) = max (44,36 + 10,25 + 20,16 + 28,8 + 40,48) = max (44, 46, 45, 44, 48, 48) = 48,

при х = 120 f₂(120) = max (62,44 + 10,36 +20,25 + 28,16 + 40,8 + 48,62) = max (62, 54, 56, 53, 56, 56, 62) = 62.

3-й этап. Финансируем 2-й этап и третье предприятие. Расчеты проводим по формуле

Тогда

при х = 20 f₃(20) = mах (10, 12) = 12,

при x = 40 f₃(40) = max (20,10 + 12,21) = max (20, 22, 21) = 22,

при х = 60 f₃(60) = max (28,20 + 12,10 + 21,27) = max (28, 32, 31, 27) = 32,

при х = 80 f₃(80) = max (40,28 + 12,20 + 21,10 + 27,38) = max (40, 40, 41, 37, 38) = 41,

при x = 100 f₃(100) = max (48,40 + 12,28 + 21,20 + 27,10 + 38,50) = max (48, 52, 49, 47, 48, 50) = 52,

при х = 120 f₃(120) = max (62,48 + 12,40 + 21,28 + 27,20 + 38,10 + 50,63) = max (62, 60, 61, 55, 58, 60, 63) = 63.

4-й этап. Инвестиции в объеме 120 млн р. распределяем между 3-м этапом и четвертым предприятием.

При х = 120 f₄(120) = max (63,52 + 11,41 + 23,32 + 30,22 + 37,12 + 51,63) = max (63, 63, 64, 62, 59, 63, 63) = 64.

Получены условия управления от 1-го до 4-го этапа. Вер­немся от 4-го к 1-му этапу. Максимальный прирост выпус­ка продукции в 64 млн р. получен на 4-м этапе как 41 + 23, т.е. 23 млн р. соответствуют выделению 40 млн р. четвертому предприятию (см. табл. 29.3). Согласно 3-му этапу 41 млн р. получен как 20 + 21, т.е. 21 млн р. соответствует выделеник 40 млн р. третьему предприятию. Согласно 2-этапу 20 млн р. получено при выделении 40 млн р. второму предприятию.

Таким образом, инвестиции в объеме 120 млн р. целесообразно выделить второму, третьему и четвертому предприятиям по 40 млн р. каждому, при этом прирост продукции будет максимальным и составит 64 млн р.

Минимизация затрат на строительство и эксплуатацию предприятий

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

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

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

Введем обозначения:

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

x_i — количество ресурса, используемого по i-му способу (i = );

g_i(x_i) — функция расходов, равная, например, величине за­трат на производство при использовании ресурса x_i по i-му способу;

φ_k(x) — наименьшие затраты, которые нужно произвести при использовании ресурса х первыми k способами.

Необходимо минимизировать общую величину затрат при освоении ресурса x всеми способами:

при ограничениях

Экономический смысл переменных x_i состоит в нахождении количества предприятий, рекомендуемого для строительства в i-м пункте. Для удобства расчетов будем считать, что пла­нируется строительство предприятий одинаковой мощности.

Рассмотрим конкретную задачу по размещению предприя­тий.

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

Необходимо разместить предприятия таким образом, что­бы обеспечить минимальные суммарные затраты на их строи­тельство и эксплуатацию. Значения функции затрат g_i(x) при­ведены в табл. 29.4.

В данном примере g_i(х) — функция расходов в млн р., ха­рактеризующая величину затрат на строительство и эксплуа­тацию в зависимости от количества размещаемых предприя­тий в i-м районе;

φ_k(x) — наименьшая величина затрат в млн. р., которые нужно произвести при строительстве и эксплуатации предпри­ятий в первых k районах.

Решение. Решение задачи проводим с использованием ре­куррентных соотношений: для первого района

для остальных районов

Задачу будем решать в три этапа.

1-й этап. Если все предприятия построить только в пер­вом районе, то

минимально возможные затраты при х = 5 составляют 76 млн р.

2-й этап. Определим оптимальную стратегию при разме­щении предприятий только в первых двух районах по формуле

Найдем φ₂(l):

g₂(1) + φ₁(0) = 10 + 0 = 10,

g₂(0) + φ₁(l)= 0 +11 = 11,

φ₂(l) = min (10, 11) = 10.

Вычислим φ₂(2):

g₂(2) + φ₁(0) = 19 + 0 = 19,

g₂(l) + φ₁(l) = 10 + 11 = 21,

g₂(0) + φ₁ (2) = 0 + 18 = 18,

φ₂(2) = min (19, 21, 18) = 18.

Найдем φ₂(3):

g₂(3) + φ₁ (0) = 34 + 0 = 34,

g₂(2) + φ₁(l) = 19 + 11 = 30,

g₂(1) + φ₁(2) = 10 + 18 = 28,

g₂(0) + φ₁(3) = 0 + 35 = 35,

φ₂(3) = min (34, 30, 28, 35) = 28.

Определим φ₂(4):

g₂(4) + φ₁(0) = 53 + 0 = 53,

g₂(3) + φ₁(l) = 34 + 11 = 45,

g₂(2) + φ₁(2) = 19 + 18 = 37,

g₂(l) + φ₁(3) = 10 + 35 = 45,

g₂(0) +φ₁(4) = 0 + 51 = 51,

φ₂(4) = min (53, 45, 37, 45, 51) = 37.

Вычислим φ₂(5):

g₂(5) + φ₁(0) = 75 + 0 = 75,

g₂(4) + φ₁(l) = 53 + 11 = 64,

g₂(3) + φ₁(2) = 34 + 18 = 52,

g₂(2) + φ₁(3) = 19 + 35 = 54,

g₂(1) + φ₁(4) = 10 + 51 = 61,

g₂(0) + φ₁(5) = 0 + 76 = 76,

φ₂(5) = min (75, 64, 52, 54, 61, 76) = 52.

3-й этап. Определим оптимальную стратегию при раз­мещении пяти предприятий в трех районах по формуле

φ₃(x) = min{g₃(x₃) + φ₂(x – х₃)}.

Найдем φ₃(5):

g₃(5) + φ₂(0) = 74 + 0 = 74,

g₃(4) + φ₂(1) = 54 + 10 = 64,

g₃(3) + φ₂(2) = 36 + 18 = 54,

g₃(2) +φ₂(3) = 20 + 28 = 48,

g₃(1) + φ₂(4) = 9 + 37 = 46,

g₃(0) + φ₂(5) = 0 + 52 = 52,

φ₃(5) = min (74, 64, 54, 48, 46, 52) = 46.

Минимально возможные затраты при х = 5 составляют 46 млн р.

Определены затраты на строительство предприятий от 1-го до 3-го этапа. Вернемся 3-го к 1-му этапу. Минимальные затраты в 46 млн р. на 3-м этапе получены как 9 + 37, т.е. 9 млн р. соответствуют строительству одного предприятия в третьем районе (см. табл. 29.4). Согласно 2-му этапу 37 млн р. получены как 19 + 18, т.е. 19 млн р. соответствуют строитель­ству двух предприятий во втором районе. Согласно 1-му этапу 18 млн р. соответствуют строительству двух предприятий в первом районе.

Ответ. Оптимальная стратегия состоит в строительстве одного предприятия в третьем районе, по два предприятия во втором и первом районах, при этом минимальная стоимость строительства и эксплуатации составит 46 ден. ед.

Нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий

Требуется проложить путь (трубопровод, шоссе) между двумя пунктами А и В таким образом, чтобы суммарные за­траты на его сооружение были минимальные.

Решение. Разделим расстояние между пунктами А и В на шаги (отрезки). На каждом шаге можем двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А в В представляет ступенчатую ломаную линию, от­резки которой параллельны одной из координатных осей. За­траты на сооружение каждого из отрезков известны (рис. 29.2) в млн р.

Разделим расстояние от А до В в восточном направлении на 4 части, в северном – на 3 части. Путь можно рассматри­вать как управляемую систему, перемещающуюся под влияни­ем управления из начального состояния А в конечное В. Со­стояние этой системы перед началом каждого шага будет характеризоваться двумя целочисленными координатами х и у. Для каждого из состояний системы (узловой точки) найдем условное оптимальное управление. Оно выбирается так, что­бы стоимость всех оставшихся шагов до конца процесса была минимальна. Процедуру условной оптимизации проводим в об­ратном направлении, т.е. от точки В к точке А.

Найдем условную оптимизацию последнего шага (рис. 29.3).

В точку В можно попасть из B₁ или В₂. В узлах запишем стоимость пути. Стрелкой покажем минимальный путь.

Рассмотрим предпоследний шаг (рис. 29.4).

Для точки В₃ условное управление — по оси X, а для точки B₅ — по оси Y. Управление для точки В₄ выбираем как

т.е. по оси Y.

Условную оптимизацию проводим для всех остальных уз­ловых точек (рис. 29.5).

Получим

где с — север, в —восток.

Минимальные затраты составляют

Если решать задачу исходя из оптимальности на каждом этапе, то решение будет следующим:

Затраты составят 10 +12 + 11 + 10 + 9 + 13 +10 = 75 > 71.

Ответ. Прокладывать путь целесообразно по схеме: с, с, в, с, в, в, в, при этом затраты будут минимальные и составят 71 млн р.

УПРАЖНЕНИЯ

29.1. К началу рассматриваемого периода на предприятии установлено новое оборудование. Зависимость производитель­ности этого оборудования от времени его работы, а также за­траты на содержание и ремонт при различном времени его ис­пользования приведены в табл. 29.5.

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

29.2. К началу анализируемого периода на предприятии уста­новлено новое оборудование.

Определить оптимальный цикл замены оборудования при сле­дующих исходных данных:

покупная цена оборудования (Р) составляет 12 ден.ед.;

остаточная стоимость оборудования S(t) = 0;

f_N(t) = r(t) — u(t) — максимальный доход, получаемый от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стра­тегии, где r(t) — стоимость продукции, выпускаемой за год на единице оборудования возраста t лет, u(t) — ежегодные затра­ты на обслуживание оборудования возраста t лет;

N = 8 лет.

Зависимость f_N(t) от N задана в табл. 29.6.

29.3. Торговая фирма располагает 5 автолавками, которые мо­гут быть направлены в воскресный день в 3 населенных пунк­та. Считается, что товарооборот фирмы зависит лишь от коли­чества и ассортимента направляемых товаров и определяется числом посланных в тот или иной населенный пункт машин.

Среднее значение товарооборота в тыс. р. в каждом из на­селенных пунктов задано в табл. 29.7.

Найти оптимальную стратегию фирмы в распределении авто­лавок по населенным пунктам, максимизирующую общий то­варооборот.

29.4. В табл. 29.8 указан возможный прирост выпуска продук­ции четырьмя плодово-консервными заводами области в млн р. при осуществлении инвестиций на их модернизацию с дискрет­ностью 50 млн р., причем на один завод можно осуществить только одну инвестицию.

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

29.5. В трех областях необходимо построить 5 предприятий по переработке сельскохозяйственной продукции одинаковой мощности.

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

Функция расходов g_i(x), характеризующая величину затрат на строительство и эксплуатацию в зависимости от коли­чества размещаемых предприятий в i-й области, приведена в табл. 29.9.

29.6. Проложить трубопровод между двумя пунктами А и В так, чтобы суммарные затраты на его изготовление были ми­нимальные. Исходные данные по затратам в млн р. для про­ведения расчетов представлены на рис. 29.6.

Глава 30. СЕТЕВЫЕ МОДЕЛИ

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

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

Основные понятия сетевой модели

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

Теория графов оперирует понятием пути, объединяющим последовательность взаимосвязанных ребер. Контур означает такой путь, у которого начальная вершина совпадает с конеч­ной. Сетевой график — это ориентированный граф без конту­ров. В сетевом моделировании имеются два основных элемен­та — работа и событие.

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

Фиктивная работа — это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь — это любая непрерывная последовательность (цепь) работ и событий.

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

При построении сетевых моделей необходимо соблюдать следующие правила.

1. Сеть изображается слева направо, и каждое событие с большим порядковым номером изображается правее преды­дущего. Общее направление стрелок, изображающих работы, также в основном должно быть расположено слева направо, при этом каждая работа должна выходить из события с мень­шим номером и входить в событие с большим номером.

2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся про­межуточное событие и фиктивная работа (рис. 30.1).

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

4. В сети не должно быть промежуточных событий, кото­рым не предшествует хотя бы одна работа (рис. 30.3).

5. В сети не должно быть замкнутых контуров, состоя­щих из взаимосвязанных работ, создающих замкнутую цепь (рис. 30.4). Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исход­ного события, которому дается номер 1. Из исходного собы­тия 1 вычеркивают все исходящие из него работы, на остав­шейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычеркивают работы, выходящие из события 2, и вновь находят на остав­шейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до заверша­ющего события. Пример нумерации сетевого графика показан на рис. 30.5.

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

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

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

Расчет временных параметров сетевого графика

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

Расчет критического пути включает два этапа. Первый на­зывается прямым проходом. Вычисления начинают с исходного события и продолжают до тех пор, пока не будет достигнуто завершающее событие. Для каждого события определяется од­но число, представляющее ранний срок его наступления. На втором этапе, называемом обратным проходом, вычисления на­чинают с завершающего события и продолжают, пока не будет достигнуто исходное событие. Для каждого события вычисля­ется поздний срок его наступления.

Рассмотрим прямой проход:

t_i^р.н. — ранний срок начала всех операций, выходящих из события i.

Если i = 0, то t₀^р.н. = 0;

t_j^р.н. — ранний срок начала всех операций, входящих в j.

Тогда

где t_ij — продолжительность операции (i,j);

Прямой проход закончился, начинаем обратный:

t_i^п.o — поздний срок окончания всех операций, входящих в событие i.

Если i = п, где п — завершающее событие сети, то t_n^п.o = t_n^р.н. и является отправной точкой обратного прохода;

t_i^п.о = (t_j^п.о - t_i,j) для всех операций (i,j);

Используя результаты вычислений при прямом и обрат­ном проходах, можно определить операции критического пу­ти. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям:

Для рассматриваемого примера критический путь включа­ет операции (0,2), (2,3), (3,4), (4,5), (5,6).

Операции связаны еще с двумя сроками:

t_ij^п.н. — поздний срок начала работы. Он является наибо­лее поздним (максимальным) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок:

t_ij^р.o — ранний срок окончания работы. Он является наибо­лее ранним (минимальным) из возможных моментов окончания работы при заданной продолжительности работ:

Различают два вида резервов времени: полный резерв (r_п) и свободный резерв (r_св).

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

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

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

Построение сетевого графика и распределение ресурсов

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

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

На рис. 30.8 показана потребность в рабочей силе при усло­вии выбора в качестве календарных сроков некритических опе­раций начала их ранних сроков, на рис. 30.9 — потребность в рабочей силе при выборе наиболее поздних сроков.

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

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

Учет стоимостных факторов при реализации сетевого графика

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

На рис. 30.12 показана линейная зависимость стоимости операции от ее продолжительности. Точка (D_B, С_B), где D_B — продолжительность операции, а С_B — ее стоимость, соответ­ствует нормальному режиму выполнения операции. Продолжи­тельность операции можно уменьшить (сжать), увеличив ин­тенсивность использования ресурсов, а следовательно, увели­чив стоимость операции. Однако существует предел, называе­мый минимальной продолжительностью операции. За точкой, соответствующей этому пределу (точка максимально интен­сивного режима), дальнейшее увеличение интенсивности ис­пользования рес