Файл: Алексеев, А. М. Сетевые модели в перспективном планировании развития производства.pdf

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

В литературе описана аналогичная сетевая задача, усложнен­ ная введением непрерывной выпуклой вниз зависимости стои­ мости от продолжительности работы <рц(тц) (Berman, 1964). Метод оптимизации заключается в приближенном решении систе­ мы уравнений

22

Выполнение равенств обеспечивает станцнонарность расписа­ ния: сдвиг вправо по времени /-го события вызывает удешевле­ ние входящих и удорожание выходящих работ, причем в силу выпуклости функции cp(tij) удорожание превзойдет удешевление.

Сложность предложенной системы уравнений автор предлагает обойти путем решения отдельных уравнений последовательно для каждого события /, фиксируя при этом время наступления осталь­ ных событий (сходимость процесса не исследуется). При этом нет разделения работ на критические и некритические (сильно услож­ нившего алгоритм Форда-Фалкерсона), а также ограничений на продолжительность работАвтор статьи указывает на возмож­ ность учета этих ограничений путем «исправления» исходной за­ висимости срц(Тц) . На интервале [0, ф3] фу(А) дооп­ ределяется сильно убывающей функцией (от оо до ф;3(<А)) для

Хц'>В^ не приводят к увеличению стоимости и соответствуют за­

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

и соответствующие стоимости заданы графиками на рис. 2. Пусть выделен период времени, равный трем годам, на выполнение обе­ их работ, тогда допустимые расписания представлены на рис. 3. По суммарной стоимости наиболее предпочтительным является первое расписание (Si —60).

Найдем расписание с минимальной приведенной стоимостью выполнения работ. Затраты будем приводить к моменту времени

23

расписанию (ti2 = l; тгз= 1) предполагается интенсивное выполне­ ние работ после годового бездействия (лага). В данном случае такая стратегия неоправдана: возрастание стоимости выполнения не компенсируется обесцениванием затрат во времени. Минимум затрат достигается на втором расписании (ti2= 2 , т2з= 1). В этом условном примере наглядно проявилась тенденция к смещению капиталоемких вариантов на последние годы планового периода.

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

Один из методов сопоставления затрат во времени предложил Л. Брискин (Briskiin, 1966). Как и в предыдущих постановках, здесь задаются варианты выполнения отдельных этапов работ, характеризуемых продолжительностью выполнения и затратами. В терминах теории графов целью оптимизации является отыска­ ние цепи направленных дуг из источника в сток, на которой до­ стигаются оптимальные затраты. Отбор оптимальной комбинации вариантов ведется по двум критериям: минимизации стоимости и сокращения времени выполнения последовательности работ. От­ меченные цели оптимизации противоречивы: с одной стороны, расходы на выполнение работы падают с увеличением продолжи­ тельности, а с другой — за сокращение времени выполнения на единицу заказчик готов платить дополнительно и тем больше, чем продолжительнее общее время выполнения заказа. Функция доплат за сокращение срока выполнения предлагается в виде экспоненты 6'=с(1—ekl) + h (с, h подбираются аппроксимацией), весьма близкой к форме дисконтной зависимости

(7+Я )‘ = gl = е~ Ы’ где к = 1п С1 + Е )-

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

24

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

первому варианту, если доплата за сокращение срока выполнения с Т\ до Т2 меньше, чем разница S2—S 1 и наоборот. '

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

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

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

Чтобы описать процесс создания производственного объекта сетевым графиком, введем унифицированную форму задания ва­ риантов выполнения его отдельных работ7. Будем использовать общую единицу времени как шаг в дискретном задании функции стоимости приведенной к началу работы от срока выполнения. Эта функция задана в интервале с целочисленными (согласно выбранной единице) границами и определена в каждой целочис­ ленной точке. Для этого: 1) в качестве единицы времени выбира­ ется наибольший общий делитель продолжительностей создания

6 Возможность использования сетевых моделей в области перспек­ тивного планирования отмечалась А. Г. Аганбегяном в период первых раз­ работок и распространение системы PERT (Аганбегяи, 1964).

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

25

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

(Ь ^ '' -j) •

В пределах выделенного времени т« единственным образом определяется продолжительность выполнения itj с минимальной стоимостью приведенной к началу отрезка времени т;3 и устанав­ ливается начало U выполнения работы. Для срока окончания ра­ боты во всех случаях верно тождество:

В противном случае приведенную стоимость можно уменьшить сдвигом работы на конец интервала тгз. Выбором оптимальной продолжительности ti} и минимальной приведенной стоимости Ztj для допустимого срока т,-3- выполнения работы устанавливается зависимЬсть Zy(Ty), и вместе с этим соотношение между продол­ жительностью выполнения £,-3 и допустимой продолжитель­ ностью т,3:

Так, работа (г,/) с единственным вариантом выполнения ( а = £ у— продолжительность, 5° — стоимость) приводится к виду

ных вложений, принятая для рассматриваемой отрасли. Графйк этой функции приведен на рис. 5.

Для произвольного допустимого срока т « = Ь > а конец работы совпадает с моментом Ь, начало смещается на (Ъ—а), приведен-

ные затраты падают в g (b~a) раз. Область определения функции z ( T i3) , теоретически не ограниченная справа, будет устанавливать­ ся по другим соображениям. В этой области каждому значению Ту соответствует отличное от других значение приведенной стои­ мости, хотя технологический вариант и вместе с ним время вы­ полнения остаются постоянными: tij= a='i¥ (т,-,) (рис. 6).

Для нескольких вариантов выполнения работы (£, /) (зависи­

26

Если минимум достигается на нескольких значениях tih то одно из них фиксируется, остальные отбрасываются. Таким образом, строится однозначная функция

(1- 21)

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

Требуется установить моменты времени (расписание) {th} так, чтобы общая сумма приведенных к моменту 1\ затрат на весь комплекс работ сетевого графика была минимальной:

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

намического программирования8. Направленным перебором опре­ деляются минимальные затраты на выполнение двух (трех и т. д.) последовательных работ: работы «сшиваются», значения затрат и соответствующие t{ заносятся в таблицу. После нахождения ми­ нимума затрат для всех работ графика по таблицам восстанавли­ вается оптимальное время наступления событий9. Задача решает­ ся несколько раз для некоторого набора различных значений па­ раметра Т (срок создания объекта). Область допустимых значе­ ний Т определяется исследованием сети. В результате решения параметрической задачи находится функция изменения затрат от продолжительности создания объекта.

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

8 Алгоритм решения этой задачи разработан А. М. Алексеевым Б. А. Вертгеймом и изложен в докладе авторов на семинаре отдела опти­ мального планирования отраслей промышленности ИЭ и ОПП СО АН СССР

и ЛЭМИ НГУ в январе 1969 г.

9 Таблицы, составляемые в процессе оптимизации, удобны при ру ном счете, при использовании ЭВМ они сильно загромождают память ма­ шины и вынуждают ограничить размеры решаемых задач. Программа, реализующая данный алгоритм на БЭСМ-6 (автор Э. Н. Долинина), рассчи­ тывает сетевые графики объемом не более 500 работ.

■27