Теория оптимизации

1) Компания рассматривает вопрос о строительстве завода. Возможны три варианта:

-построить большой завод стоимостью 605 тыс. $. При большом спросе годовой доход составит 245 тыс.$ в течение следующих 6 лет с вероятностью 65%, а при низком спросе ежегодные убытки составят 145 тыс.$;

- построить маленький завод стоимостью 345 тыс.$. При большом спросе годовой доход составит 45 тыс.$ в течение следующих 6 лет с вероятностью 65% а при низком спросе ежегодные убытки составят 20 тыс.$

- отложить строительство на 2 года для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью 75% и 25% соответственно.

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

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

Решение

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

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

Белыми узлами мы будем обозначать места, где нам предстоит принять решение.

Анализ дерева альтернатив следует начать с вычисления ожидаемой монетарной ценности ветвей, приводящих в крайние черные узлы. Это узлы 2, 3, 6, 7, 8. Первый шаг анализа – вычисление ожидаемых монетарных ценностей для каждой из ветвей дерева

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

Показатель EMV составит:

Для ветви 2: EMV2= (245*6*0,65-145*6*0,35)=651 тыс.$.

Для ветви 3: EMV3= (45*6*0,65-20*6*0,35)=133,5 тыс.$.

Для ветви 6: EMV6= (6,5*4*0,7-10*4*0,3)=6,2 тыс.$.

Для ветви 7: EMV7= (245*1,1*4*0,91-145*0,85*4*0,09)=936,61 тыс. $

Для ветви 8: EMV8= (45*1,1*4*0,91-20*0,85*4*0,09)=174,06 тыс. руб.

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

Для ветви 5: EMV5= max(936,61-605; 174,06-345)=331,61 тыс.$. (большой завод)

Для ветви 4: EMV4= (331,61*0,75+6,2*0,25)=250,26 тыс.$.

Для ветви 1: EMV1= max(651-605; 133,5-345; 250,26)=250,26 тыс.$. (отложить строительство)

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

2. По представленным оценкам продолжительности работ необходимо построить сетевой график, вычислить все характеристики работ и событий. Найти критический путь и его продолжительность. Построить график Ганта. Оптимизировать по затратам и ресурсам при условии, что наличный ресурс составляет 13 единиц. Определить вероятность завершения проекта за 38 дней

Решение

Построим соответсвующий сетевой график.

Каждая работа имеет три временные оценки: оптимистическую (), пессимистическую () и наиболее вероятную (); по формуле определяется среднее время выполнения работы. При расчете время работы округляем до ближайшего целого числа

Наносим полученные данные на сетевой график и нумеруем события. Получим:

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

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

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

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

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

Критическое событие – событие, расположенное на критическом пути.

Существует простой алгоритм нахождения критического пути и критического времени, основанный на понятии раннего времени наступления события.

Ранний срок свершения события - это ранний срок, необходимый для выполнения всех работ, предшествующих данному событию:

Где - ранний срок свершения события ;

- продолжительность работы;

- множество работ, входящих в событие .

Таким образом, раннее время наступления конечного события составляет 40 недель. Следовательно,

.

Имеем один критических пути:

Рассматривая формулы по которым было найдено критическое время, определим критический путь:

12358101214151617

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

,

Где - поздний срок свершения события ;

Тогда резерв времени события равен:

.

Для событий, лежащих на критическом пути, резервы равны нулю.

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

Срок начала работ находится по формуле TРн (I, J) = TР (I). Эти значения уже вычислены.

Графу 4 заполняем, суммируя значения граф 2 и 3.

После этого заполняем графу 6, пользуясь формулой: TПо (I, J) = TП (J).

Значения графы 5 получаем вычитанием графы 2 из графы 6.

Полные резервы работ получаем вычитанием граф (5) – (3) или (6) – (4).

Независимые резервы работ вычислим по формуле

Свободные резервы работ находим по формуле

В графе 8 таблицы напротив некоторых работ стоят прочерки, т. к. независимые резервы этих работ отрицательны.

Построим график Ганта

Диаграмма Ганта (англ. Gantt chart, также ленточная диаграмма) — это популярный тип столбчатых диаграмм, который используется для иллюстрации плана, графика работ по какому-либо проекту. Является одним из методов планирования проектов. Первый формат диаграммы был разработан Генри Л. Гантом (Henry L. Gantt, 1861-1919) в 1910 году.

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

На некоторых диаграммах Ганта также показывается зависимость между задачами. Диаграмма может использоваться для представления текущего состояния выполнения работ: часть прямоугольника, отвечающего задаче, заштриховывается, отмечая процент выполнения задачи; показывается вертикальная линия, отвечающая моменту «сегодня».

Диаграмма Ганта - это один из наиболее популярных способов графического представления плана проекта, представляет собой изображение календарного графика задач в проекте.

Диаграмма Ганта позволяет:

·  визуально оценить последовательность задач, их относительную длительность и протяженность проекта в целом;

·  сравнить планируемый и реальный ход выполнения задач;

·  детально проанализировать реальный ход выполнения задач.

Построим графики привязки и загрузки для оптимизации по ресурсам.

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

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

·  на графике привязки над каждой работой написать количество ее исполнителей;

·  подсчитать количество работающих в каждый день исполнителей и отложить на графике загрузки.

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

Исходные данные для оптимизации загрузки

Рис. Графики загрузки (а) и привязки (b) до оптимизации

Организация, выполняющая проект, имеет в распоряжении только единиц ресурса. Но в соответствии с графиком загрузки, в течении интервала времени с 24 по 28 неделю для выполнения проекта требуется загрузка в 16 единиц. Таким образом, возникает необходимость снижения максимального количества ресурса с 16 до 13 единиц

Проанализируем возможность уменьшения загрузки (16 человек) в течении 24-й недели дня. Используя , сдвинем работу на 3 недели, что снизит загрузку 24-й недели до 13 единиц. Дальше мы можем сдвинуть начало работы (13, 15) на 2 недели, но это приведет только к увеличению загрузки с 29й по 31ю недели

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

Рис. Графики загрузки (а) и привязки (b) после оптимизации

Пусть требуется оценить вероятность выполнения проекта в директивный срок, равный Т = 38 дней. Для данного сетевого графика дисперсии продолжительности работ критического пути рассчитываются по формуле

σ2 (1→2) =; σ2 (2→3) =; σ2 (3→5) = 2,778; σ2 (5→8) = 0,444; σ2 (10→12) = 0,111; σ2 (14→15) = 0,25; σ2 (15→16) = 0,111; σ2 (16→17) = 0,111

Используя формулы , , получим

Тогда искомая вероятность

0,3340

Т. е. вероятность завершения проекта в Тож – 38 дней составляет 33,4%

< Предыдущая		Следующая >