Студопедия

КАТЕГОРИИ:



Мы поможем в написании ваших работ!

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Мы поможем в написании ваших работ!

Виды и сущность оптимизации сетевых моделей


 

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

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

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

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

Задан сетевой график G = (Е,) выполнения проекта, где Е — множество событий, а — множество работ. Продолжительность каждой работы равна tij. Известно, что вложение дополнительных средств хij в работу (i, j) сокра­щает время ее выполнения от tij до t'ij, причем , где kij – технологические коэффициенты использования дополнительных средств. Но сокращение продолжительности работы не беспредельно, для каждой работы существует минимально возможное время ее выполнения dij.

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



Математически условия задачи можно записать следую­щим образом:

 

; (6.3)

; (6.4)

; (6.5)

; (6.6)

; (6.7)

. (6.8)

 

Ограничение (6.4) определяет время завершения проекта, оно должно быть не больше заданного tо. Ограничения (6.5) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (6.6) показывают зависимость продол­жительности каждой работы от вложенных в нее дополнитель­ных средств. Ограничения (6.7) обеспечивают выполнение ус­ловий предшествования работ: время начала выполнения каж­дой работы должно быть не меньше времени окончания непос­редственно предшествующих ей работ. Ограничение (6.8) — условие неотрицательности.

Задача 2заключается в сокращении срока выполнения проекта, насколько это возможно за счет вложения суммы дополнительных средств, не превышающей В. Время выполне­ния каждой работы должно быть не меньше минимально воз­можного времени dij. Необходимо определить время начала и окончания каждой работы и величину дополнительных средств хij, которые нужно выделить на ускорение выполне­ния работы (i,j).

Математическая модель задачи 2 имеет вид:

 

; (6.9)

; (6.10)

; (6.11)

; (6.12)

. (6.13)

 

Смысл ограничений (6.10) – (6.13) аналогичен соответствующим огра­ничениям постановки задачи 1 (6.4) - (6.8). Если в последнее событие сети n входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю . Тогда целевая функция запи­шется так .

6.2 Оптимизация проекта по стоимости. В общем случае стоимость выполнения работы зависит от ее продолжительности. Продолжительность каждой работы может изменяться между двумя границами dij и Dij, определя­емыми техническими или экономическими соображениями. Если Dij — нормальная продолжительность, ей соответствует минимальная стоимость сij выполнения работы (i, j); если dij — минимально возможная (экстренная) продолжитель­ность работы, при этом стоимость работы будет максимальной Cij. Если при планировании проекта для каждой работы будет взята ее нормальная (наибольшая) длительность Dij, то стои­мость проекта будет минимальной. Если для каждой работы взять ее ускоренную, минимально возможную продолжитель­ность dij, то получим срочный план. Стоимость выполнения проекта в этом случае будет максимальной.

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

 

. (6.14)

 

Рассмотрим оптимизацию комплекса работ по стоимости при фиксированном сроке выполнения.

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

Увеличение продолжительности работы (i, j) по сравне­нию с минимальным сроком выполнения на () вызовет экономию средств на величину hij () , a стоимость выполнения работы станет равна

 

C = Cij - hij (). (6.15)

 

Если t0 = tкp, то оптимизация осуществляется за счет увели­чения продолжительности некритических работ; если tкр < t0, — то за счет всех работ комплекса.

Математическая запись задачи:

 

; (6.16)

; (6.17)

; (6.18)

; (6.19)

; (6.20)

. (6.21)

 

Здесь 1 — номер исходного события, n — номер заверша­ющего события.

Рассмотрим оптимизацию комплекса работ по стоимости при нефиксированном сроке выполнения.

Пусть задан сетевой график проекта и известны продол­жительность каждой работы и стоимость ее выполнения в нормальном (Dij, cij) и срочном (dij, Cij) режиме работы. Если все работы выполняются в нормальном режиме, то критичес­кий срок будет наибольшим, а стоимость выполнения — наи­меньшей. Время выполнения проекта может быть уменьше­но путем увеличения стоимости. Необходимо сократить кри­тический срок до некоторого минимально возможного значе­ния при наименьшем возрастании стоимости выполнения проекта.



6.3 Оптимизация проекта по ресурсам. Пусть проект задан сетевым графиком. Для выполнения проекта выделено R единиц ресурса. Каждая работа характе­ризуется продолжительностью выполнения tij и интенсив­ностью потребления ресурса rij. Под интенсивностью потреб­ления будем понимать требуемое количество ресурса для вы­полнения работы (i, j) в единицу времени. Для простоты до­пустим, что интенсивности постоянные.

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

<== предыдущая лекция | следующая лекция ==>
Постановка задач для решения методами СПУ | Предмет и задачи теории игр

Дата добавления: 2014-01-03; Просмотров: 1268; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.006 сек.