Оценочная модель

Шкала оценок: отлично =10, плохо = 1.

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

Модели распределения капиталовложений. Далее анализируется возможность использования математического программирования для оценочной модели. Сог­ласно такому подходу, необходимо найти такой набор x_i ( x_i=0 или 1) для каждого из nпроектов, при котором достигается

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

,

где R_i — ресурсы, выделенные i-му проекту, R — общее коли­чество ресурсов; значение х_i(переменная выбора) зависит от того, выбран ( x_i =1) или нет (х_i =0) i-й проект. Для решения этой задачи используются методы целочисленного программирования. Используемая в задаче модель линейного программирования, может быть модифицирована с учетом сроков (вариантов) выполнения проектов, например большой, средний, малый. Тогда j-й ва­риант i-го проекта определяется булевой переменной x_ij. Чтобы каждый вариант проекта выбирался не более чем один раз, вводят дополни­тельное ограничение

для возможных проектов i = 1,..., n, составляющих портфель проектов, из которых производится отбор и для которых распределяются средства; m_i — число вариантов i-го проекта. В этом случае задача сводится к нахождению

(где b_ij — ожидаемая прибыль от j-говарианта i-го проекта),

при рассмотренных ранее ограничениях.

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

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

а) размещение, размеры и специализацию производственных o6ъектов;

б)технологию производства (выбор из возможных вариантов);

в)экономическую целесообразность реконструкции, технического nepeвооружения или дальнейшей эксплуатации производственного объекта;

г) экономически эффективные варианты строительства новых производственных объектов;

д) распределение капитальных вложений между объектами по времени и др.

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

Здесь используются следующие обозначения:

i — номер подразделения предприятия; I – множество подразделений предприятия; n - число всех подразделений предприятия; j - номерварианта развития каждого подразделения предприятия; m_i - число всех вариантов развития – i-го подразделения предприятия;

q - номенклатура выпускаемой продукции;

N - множество номенклатуры выпускаемой продукции;

t - номер года планового периода;

Т - множество лет планового периода;

c_ij – расчетное значение результата (прибыль, затраты и т.д) i-го подразделения при j-ом варианте развития;

p_ijqt – объем выпуска q -ой продукции в i-ом подразделении согласно j-му варианту развития в году t;

Qqt – спрос на производство q -ой продукции в году t;

Kijt- объём капитальных вложений, необходимых в i-ом подразделении в году t согласно j -му варианту развития;

К_t - лимит, капитальных вложений, выделенных на развитие предприятия в году t;

x_ij- искомая переменная, равная 1, если в i-ом пподразделении принимается j-ый вариант развития, и равная 0 в противном случае Требуется определить оптимальный вариант развития предприятия по критерию эффективности, при ограничениях на объём выпускаемой продукции, объём капиталы вложений, выбор вариантов и целочисленности решения.

Сетевое планирование и управление. После принятия решения о начале работ над проектом обычно необходимо решить задачу реализации проекта (составить график выполнения) за заданное время с использованием выделенных ре­сурсов. Для решения этой задачи в период 1956—1958 гг. были раз­работаны два метода. Один из них — метод критического пути, или МКП (Critical Path Method — СРМ), — впервые был исполь­зован компанией DuPont Co. и получил дальнейшее развитие в работах фирмы Mauchly Associates. Другой метод — ме­тод оценки и пересмотра проектов, или ПЕРТ (Project Evaluation, and Review Technique — PERT), — был разработан для министер­ства военно-морских сил США в соответствии с программой соз­дания подводных лодок, оснащенных ракетами «Поларис».

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

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

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

Рис. 4.17. Сетевой график на языке работ и событий

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

Последовательность взаимосвязанных работ образует в сетевом графике так называемый путь m. Продолжительностью Тm пути m называют сумму продолжительностей тех работ, которые этот путь составляют. Путь, ведущий от начала сетевого графика к его концу и имеющий наибольшую продолжительность, называется критическим и обозначается m_кр, а его продолжительность называется критическим временем Tкр. Критическое время Ткр показывает наиболее ранний возможный срок выполнения того комплекса работ, который представлен данным сетевым графиком. Всякая задержка выполнения работы, лежащей на критическом пути, приводит к задержке выполнения работ всего комплекса. Это значит, что критический путь представляет собой «узкое место» в данном комплексе, поэтому он должен привлекать особое внимание руководства.

Существует несколько самых общих правил, относящихся к составлению и построению сетевого графика.

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

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

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

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

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

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

Для того чтобы какое-нибудь событие Аj свершилось, требуется, чтобы были закончены все работы (Ai1, Аj), (Аi2, Аj),..., (Аin, Аj), которые входят в это событие (рис. 4.18).

Рис.4.18. Множество работ, входящих в событие Aj

Обозначим множество работ, входящих в событие Aj, через U_j⁺. Очевидно возможным сроком свершения j-го события Аj можно считать любой момент времени, который наступает после того, как выполнены все работы множества Uj+. Наиболее ранний из возможных срок свершения j-ro события является первым из основных временных параметров сетевого графика и обозначается через t_р(i).

Алгоритм вычисления t_p(j). Предположим, что для событий Аi1, Аi2,..., Аin (рис.4.18), которыми начинаются работы, входящие в j-e событие (работы множества Uj+), ранние сроки свершения уже вычислены, т. е. уже известны t_p(i1), t_p(i2),..., t_p(in). Тогда любой из возможных сроков свершения j-rо события t_вз(j)должен удовлетворять условию

Следовательно, наиболее ранний из возможных сроков свершения j-ro события t_р(j) определяется следующим образом:

Таким образом, отправляясь от начального события, срок которого известен (t(0) =0), можно последовательно, по формуле расчета t_p(j), определить все ранние сроки свершения событий j сетевого графика. Ранний срок последнего события t_p(m) определяет критическое время свершения всего комплекса работ.

Теперь рассмотрим, какие же сроки свершения событий можно считать допустимыми. Дело в том, что при выполнении работ, которые лежат на путях, ведущих к j-му событию, могут произойти те или иные задержки. В связи с этим j-е событие не наступит в минимально возможный срок t_p(j), и запаздает в сравнении с ним. Но слишком большое опоздание в сроке свершения j-го события может отразиться на сроке окончания всего комплекса работ. Очевидно, что допустимым сроком свершения события Аj можно считать такой срок, при котором «не сорвется» срок окончания всего комплекса работ, равный критическому времени Ткр. Наиболее поздний из допустимых срок свершения j-ro события является вторым из основных временных параметров сетевого графика и обозначается через t_п(j).

Алгоритм для вычислеиия t_п(j). Рассмотрим работы, исходящие из j-ro события, т. е. работы (Аj, Аk1), (Aj, Ak2,),..., (Аj, Аkq), (рис. 4.19).

Рис.4.19. Множество работ, исходящих из события Aj.

Обозначим множество этих работ через Uj-. Допустим, что для всех событий Ak1, Аk2,,..., Аkq, которыми заканчиваются работы множества Uj-, уже вычислены наиболее поздние сроки их свершения, т. е. уже известны t_п(k1), t_п(k2),..., t_п(kq). Тогда допустимым сроком свершения j-ro события t_дп(j) может быть только такой срок, который, будучи сложен с продолжительностью любой работы множества Uj- (исходящей из j-ro события), даст момент времени, не превосходящий ни одного из сроков t_п(k1), t_п(k2),..., t_п(kq), т. е.

Следовательно, наиболее поздним из допустимых будет срок, определенный равенством

Таким образом отправляясь от конечного события, для которого t_п(m) =Tкр, можно по формуле расчета t_п(j) определить все поздние сроки свершения событий j сетевого графика.

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

Rm = Tkp - Tm.

Очевидно, что для критического пути Rkp=0. Некритические пути имеют положительные резервы времени.

Резервом времени события Aj называется разность между наиболее поздним и наиболее ранним сроками свершения этого события. Обозначим резерв времени события Аj через Rj, тогда

Rj = t_п(j) - t_р(j)

Так как на критическом пути t_п(j) =t_р(j), то, следовательно, резервы времени для свершения событий на критическом пути равны нулю, т. е. Rj = 0.

Полным резервом времени работы (Ai, Aj), обозначаемым R_п(ij), называется величина, определяемая следующим образом:

R_п(ij) = t_п(j) -t_р(i) - tij

Полный резерв времени R_п(ij) для любой работы не отрицателен, R_п(ij) ³ 0, причем он равен нулю только тогда, когда работа (Аi, Аj) лежит на критическом пути. В дальнейшем такие работы будем называть критическими. Рассматривая какую-нибудь некритическую работу (Аi, Аj), можно по ее полному резерву R_п(ij) судить о том, каким запасом времени мы располагаем для увеличения продолжительности ее выполнения. Если резерв времени R_п=(ij) использован полностью, то такая работа и путь, который содержит эту работу, становятся критическими.

Примером расчета по рассмотренному алгоритму может служить сетевой график проекта (рис.4.20) и его временные характеристики (табл. 4.7)

Рис. 4.20. Сетевой график проекта А (во времени).

Таблица 4.7

Временные характеристики сетевого графика для проекта А

1) Фиктивные работы не приведены.

2) Эти работы, по определению, принадлежат критическому пути.

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

Предположим, что для выполнения каждой из работ 1-3, 1-5, 1-2 и 2-4 (рис.4.20) требуется один исполнитель, который будет занят полный рабочий день. Вместе с тем имеются только два исполни­теля.

Ограничение, накладываемое на трудовые ресурсы (два исполнителя), может быть удовлетворено без продления времени завершения проекта, если задержать на 8 ед. времени начало ра­боты 1-3 (оно может быть задержано до 14 ед. времени без задержки; завершения проекта). Другой возможный вариант состоит в вы­полнении каждой из работ 1-3 и 1-2 с меньшей скоростью (напри­мер, соответствующей половине возможностей человека) при условий, что время их завершения увеличится вдвое.

Не менее важная роль отводится резервному времени при сокращении длительности критического пути (путей). Предполо­жим, что допускается перемещение исполнителей работ 1-3 и 1-2 на работу 1-5. В результате этого произошла бы задер­жка работ 1-3 и 1-2, тогда как продолжительность работы 1-5 сократилась. Оптимальное решение достигается либо, когда ни один исполнитель не может быть перемещен на другую работу, так как все резервное время ликвидировано, либо когда нельзя больше уменьшить критический путь за счет перераспределения ресурсов с работы, имеющей резерв времени, на критическую. Подоб­ные перемещения возможны только в рамках заданных ограни­чений на ресурсы, в противном случае возникает необходимость выравнивания ресурсов.

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

В табл. 4.8 приводятся данные для случая выравнивания потреб­ности в трудовых ресурсах, который исследовался автором дан­ной главы. Был построен сетевой график с невыравненным пот­реблением ресурсов, удовлетворявший все заинтересованные стороны (рис. 4.21).

Таблица 4.8

Показатели работ над проектом

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

²) Людей с этой работы перемещать нельзя.

³) Эти люди не подчиняются руководителю проекта.

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

Приемлемым вариантом плана работ оказался график, представленный на

рис. 4.22. Ограничение по трудовым ресурсам было удовлетворено за счет задержки начала работ 1, 5, 9 и 10 и разделения работы 1 на два этапа, которые выполнялись с разрывом в четыре недели. Таким образом, чтобы сократить длительность некоторых работ критического пути, не потребовалось никакого перераспределения людей между работами и не пришлось использовать данные о за­висимости длительности выполнения работы от числа исполни­телей, приведенные в табл. 4.8.

Рис. 4.21. Сетевой график проекта с невыравненной потребностью в ресурсах.

Сокращение общей длительности выполнения проекта, которая на рис. 4.22 равна 20 нед, возможно за счет дополнительных затрат, как это показано в табл. 4.9. Например, общая длительность проек­та может быть сокращена до 17 нед, если затратить дополнитель­но 2000 долл. на работу 11 и 200 долл. на работу 8. Принимая во внимание затраты, такой вариант более эффективен, чем вариант, согласно которому для достижения такого же сокращения дли-тельности проекта необходимо затратить 3000 долл. на работу 11.

Рис. 4.22. Сетевой график проекта с выравненной потребностью в ресурсах.

Таблица 4.9

Показатели «время — затраты»

1) Сокращение достигается ва счет привлечения дополнительных субподрядчиков.

2) Сокращение достигается за счет передачи некоторой части работ сторонней организации (для остальных частей работы число исполнителей остается без измене­ния).

При этом, однако, нарушается ограничение на число одновременно работающих людей (т. е. требуется использовать более четырех исполнителей). Используя данные, приведенные на рис. 4.22 и в табл.4.9, можно построить график выполнения проекта за 17 нед, который удовлетворял бы этому ограничению. Один из вариан­тов такого графика учитывает затраты указанных выше 2200 долл. на работы 11 и 8, 1000 долл. на работу 6 и 500 долл. на работу 5. Заметим, что сокращение длительности работ 11 и 8 (рис. 4.22) требует одновременного сокращения длительности работ 6 и 5, если должны по-прежнему соблюдаться ограничения на трудовые ресурсы и длительность проекта. Этот вариант более эффективен по затратам (3700 долл.), чем вариант, предусматривающий до­полнительные затраты в 2000 долл. на работу 6 и 3000 долл. на работу 11.

Таблица 4.10

Перераспределение трудовых ресурсов

График работ для одного из возможных вариантов перерас­пределения исполнителей между работами в пределах имеющихся ресурсов приведен на рис. 4.23 (исходные данные приведены в табл.4.8, а произведенные перемещения исполнителей — в табл.4.10). При таком графике ограничение на трудовые ресурсы (не более четырех исполнителей) также нарушается.

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

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

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

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

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

Рис. 4.23. Сетевой график после перераспределения трудовых ресурсов.

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

Следует отметить, что многие организации, в том числе IBM, McDonnell Automation, Control Data Corp., имеют программыдля ЭВМ, способные планировать графики для больших (до 4000 работ) проектов со многими ресурсами. Эти программы, как правило, включают средства для расчленения работ, составления расписания в пределах допустимого колебания уровня ресурсов, учета стоимости работ, различные средства составления отчетов, несколько эвристических правил упорядочения и выравнивания ресурсов.

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

Литература

1. Исследование операций. 2. Модели и применения./Под ред. Дж.Моудера, С.Элмаграни: Пер.с анг.-М.: " МИР", 1981.-677с.

2. Махуренко Г.С. Методы системного анализа в упpавлении моpским тpанспоpтом.- М., ЦРИА Моpфлот 1982