61. Оптимизац проекта по времени за счет вложен выделен сумм.Ср.

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

Рассмотрим две постановки задачи оптимизации проекта по времени с использованием дополнительных средств.

Задача 1. Пусть задан сетевой график проекта G=(E,), время выполнения каждой работы обозначим через. Вложение дополнительных средствв работу (i,j) сокращает ее выполнение до значения , где– технологический коэффициент использования дополнительных средств.

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

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

minF=

Задача 2. Задача заключается в максимально возможном сроке выполнения проекта за счет суммы дополнительных средств, не превышающих B

Если проект будет завершать несколько работ, то необходимо добавить фиктивную работу (n,n-1), время выполнения которой равно 0, т. е. , тогда Ц. Ф. будет иметь вид:

62. Оптимизация проекта по стоимости при нефиксированной величине критического пути.

Пусть для каждой работы известны следующие данные:

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

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

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

Коэффициент дополнительных затрат(КДЗ) – коэффициент, который находится по формуле:

И показывает насколько увеличится стоимость работы (i,j), при уменьшении времени ее выполнения на 1 еденицу.

Задача 1. Пусть задан сетевой график проекта G=(E,).

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

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

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

Алгоритм:

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

Общий шаг:

1. Среди критических работ находим работу, для которой КДЗ наименьший, если эта работа является общей для всех критических путей или критический путь один, то она и подлежит сокращению. Если же найденная работа не является для критических путей общей, однако критические пути имеют один или несколько общих работ, то на каждом из параллельных участков критических путей находим работу с наименьшим КДЗ. Суммирует КДЗ этих работ и сравниваем с КДЗ той из общих работ, для которой он наименьший. Если сумма КДЗ работ не больше КДЗ общей работы, то эти 2 работы и подлежат сокращению. Если сумма КДЗ=КДЗ общей работы, то сокращению подлежат все три работы. Если КДЗ общей работы больше суммы КДЗ работ, то сокращению подлежит общая работа. Если критические пути не имеют общих работ, то на каждом из них находится работа с наименьшим КДЗ, которая подлежит сокращению.

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

3. Для нового сетевого графика определим .

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

Вопрос №63 Оптимизация проекта по стоимости при фиксированной величине критического пути

Пусть для каждой работы известны след. данные:

- мин. прод-ть выполн. раб., кот. соотв. наименьшие затраты .

-норм. прод-ть, кот. будут соответств. наименьшие затраты .

Будем считать, что затраты на выполнение отд. работ нах-ся в обратной зав-ти от прод-ти их выплн-я.

К-м доп. затрат (КДЗ) будем считать к-т, кот. нах-ся по форм. и показывает, насколько увел-ся ст-ть работы (ij)при уменьшении времени её выполнения на одну ед.

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

Понятно, что в этом сл. cт-ть проекта будет наиб-й, а время вып-я наименьшим. Ставится задача миним-и ст-ти проекта за счёт увеличения времени отд. работ при фиксир. сроке t0 . В этом сл. tкр. может быть < заданного срока или равно ему. Если =t0 , то в этом сл. оптим-я возможна только за счёт резервов некрит. работ, а если <0, то за счёт резервов всех работ проекта. После оптим-и все работы будут крит-ми, т.к. их прод-ти будутдостигать наиб-х возм. значений. Ни одно событие, ни одна работа не будут иметь резерва. Такой план наз-ся безерезервным. Здесь ранние и поздние сроки свершения событий будут совпадать, а времена начала и окончания работ будут совпадать со сроками свершения событий, поэтому неизв. задачи будем считать сроки свершения событий. Прод-ть выпол-я кажд. работы в оптим. плане опр-ся как разность , а ст-ть вып-я работ будет опр-ся по формуле.

След-но, модель задачи запишется в виде:

->=, (i;j)∊

=0, <=

Вопрос №64 Оптимизация проекта по ресурсам

Данная задача явл-ся осн. задачей при планир-и.

Пусть задан сет. график проекта: G=(E;). Кол-во ресурсов =R. Для каждой работы будут приписаны 2 числа: 1. Прод-ть вып-я работы (); 2.– интенсивность потр. рес-в, т.е. кол-во ресурса, кот. необходимо для вып-я работ (i;j). Требуется так разместить работы во времени, чтобы в любой момент времени было дост. кол-во ресурса и при этом время вып-я всего комплекса работ было мин-м.

Алгоритм

Предв. шаг: по сет. гр. составляем лин., по кот. опр-м крит. время и крит. путь.

1. 1 проецир-м на ось времени начало и конец кажд. работы. На каждом врем. отрезке опр-м суммарное кол-во потр-го ресурса.

1.2 рассматриваем отрезок [] . Над этим отрезком рассм-м все работы. Нумеруем эти работы в порядке возрастания их полных резервов времени. Работы с одинаковыми полными резервами нумеруем в порядке убывания интенсивности.

1.3 в порядке присвоенных номеров послед-но суммируем инт-ти работ и сравниваем полученные суммы с заданной величиной ресурса. Если после прибавления инт-ти оосн. работ сумма превосходит R, то эта работа сдвигается вправо на вел-ну рассматр. отрезка. Переходим к добавлению инт-ти очередной работы.

Общий шаг:

1. Рассматриваем отрезок [;]. Рассм. все работы, лежащие над этим отрезком. Нумеруем эти работы, но в первую очередь нумеруются работы, кот. нач-ся левее начала отрезка. Эти работы нумеруются в порядке возрастания разности между остальными резервами этих работ и концом отрезка. Ост. работы нум-ся согл. 1-го шага.

2. пунк 3 1-го шага.