Файл: Падалко Л.П. Математические методы оптимального планирования развития и эксплуатации энергосистем учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.07.2024
Просмотров: 113
Скачиваний: 0
за а |
и Ь, а |
работа d — за b |
и не обязательно за а, то |
|
данную |
сеть |
следует заменить |
другой (рис. 4.5); |
|
3) |
в |
сети |
не д о л ж н о быть |
контуров (рис. 4.6); |
и с. 4.4.
о-^—-9-^—0
і
I
о—-—чЬ—^—о рис-4-5-
Р и с 4.6.
Р и с. 4.7.
4) при наличии в сети нескольких конечных событий (такая сеть называется многоцелевой) их следует свести к одному с помощью фиктивных работ (рис. 4.7);
181
5) если в сетевом графике одна или несколько работ могут начаться не после окончания всей предшествую щей работы, а только части ее, то в 'предшествующей ра
боте делаются ответвления |
(рис. 4.8); |
6) їв сетевом графике |
не д о л ж н о быть так называе |
мых тупиковых работ (рис. 4.9). Поскольку последние не оказывают влияния на срок свершения конечного собы тия, то они могут быть исключены.
Р н с. 4.8.
|
|
Р и с . 4.9. |
Составление сетевого графика производится в такой |
||
последовательности: |
|
|
1) |
формулировка |
цели всей работы, установление со |
д е р ж а н и я конечного |
события; |
|
2) |
составление списка всех событий и работ в опре |
|
деленном порядке; |
|
|
3) |
н у м е р а ц и я событий; |
|
4)составление сетевого графика;
5)анализ сетевого графика (проверка правильности
его с о с т а в л е н и я ) ; |
|
|
. |
|
6) |
определение |
временных оценок |
сетевого графика . |
|
Д л я |
к а ж д о й работы устанавливается |
ее |
продолжитель |
|
ность, для к а ж д о г о |
события определяется |
наиболее ран |
||
ний, наиболее поздний сроки и резерв «времени; 7) выявление критического пути.
На этом заканчивается подготовка сетевого графика к процессу его оптимизации.
.182
§ 4.3. Методы оптимизации сетевых графиков
Оптимизация по критерию времени. Составленная се тевая модель не всегда бывает приемлемой . Срок свер
шения всей р а б о т ы может не |
у к л а д ы в а т ь с я |
в |
з а д а н н ы й |
||
директивный, стоимость всех |
р а б о т может |
превосходить |
|||
установленные лимиты и т. п. В этом |
случае |
требуется |
|||
приведение модели в соответствие с условиями |
задачи, |
||||
или, иначе говоря, оптимизация |
сетевого |
графика |
по то |
||
му или иному критерию. |
|
|
|
|
|
Бели продолжительность критического пути превыша ет директивный срок, то требуется произвести анализ се тевого графика д л я и з ы с к а н и я возможностей сокраще ния продолжительности критического пути. Критический
путь |
может быть |
сокращен в |
р е з у л ь т а т е перераспреде |
ления |
средств, |
используемых |
для выполнения работ. |
Идея перераспределения заключается в том, что изыски ваются возможности снятия части сил и средств с нена пряженных путей и передачи этих сил и средств на усиле ние работ по критическому пути. В результате перерас
пределения добиваются |
того, |
чтобы |
продолжительность |
критического пути была |
не |
в ы ш е |
директивного срока. |
Оптимизация по критерию время — стоимость. Тре бование задачи в данном случае сводится к минимиза ции времени выполнения всего комплекса работ в соот ветствии с з а д а н н ы м директивным ороком таким обра зом, чтобы затраты на производство работ оказались ми нимальными .
Время |
Время |
Время |
Р и с |
4.10. |
|
В а ж н о й исходной предпосылкой для оптимизации по этому критерию является наличие стоимостных характе ристик, показывающих зависимость стоимости от време
ни выполнения |
или наоборот. Эта зависимость |
может |
|
быть нелинейной |
(рис. 4. 10, а), линейной |
(рис. |
4.10, б) |
183
и дискретной (рис. 4.10, б) . Кроме того, имеют место следующие свойства этой зависимости. Время выполне ния работы может иметь экстренную и нормальную про
должительность. Экстренное время |
— |
это минимальное |
|||
предельное |
время, н и ж е которого |
срок |
выполнения |
рабо |
|
ты быть не |
может, независимо |
от того, юколько дополни |
|||
тельных средств вкладывается |
в |
нее. |
Нормальное |
вре |
|
мя — это продолжительность р а б о т ы в нормальных ус
ловиях. |
|
|
|
Н и ж е мы изложим принципиальный |
подход к реше |
||
нию поставленной |
задачи только для |
случая |
линейной |
зависимости. |
|
|
|
Математически |
задача формулируется так. Требует |
||
ся минимизировать |
затраты на производство |
работ |
|
2 ( * / ; - с А ) |
|
|
|
|||
ч |
|
|
|
|
|
|
при наличии следующих ограничений: |
|
|
||||
продолжительность к а ж д о й работы |
д о л ж н а |
нахо |
||||
диться |
в заданных |
пределах: |
|
|
||
Tmin |
f |
S |
Tmajt- |
|
|
|
Х ІІ |
^ Чі |
1 |
ij > |
|
|
|
продолжительность к а ж д о г о возможного пути от на |
||||||
чального события |
к конечному д о л ж н а |
быть не |
выше |
|||
директивного |
срока: |
|
|
|||
У t- |
Т |
|
|
|
|
|
Ч |
|
|
|
|
|
|
К а к |
видно, мы получили задачу линейного програм |
|||||
мирования, |
которую можно решить соответствующими |
|||||
методами . Однако мы п о к а ж е м иной, более простой ме тод. Этот метод является приближенным, но тем не ме нее вполне удовлетворительным.
Схема решения сводится к тому, что вначале состав ляется сетевой график для нормальных продолжитель -
настей р а б о т и |
соответственно нормальных затрат . |
Д а - ( |
лее находится |
критический путь, определяется его |
про |
должительность и подсчитьііваются нормальные затраты по сетевому графику. Если продолжительность критиче ского пути оказывается выше директивного срока, то со
кращается время выполнения отдельных работ, |
л е ж а |
щих на критическом пути. П р и этом в первую |
очередь |
184
с о к р а щ а ю т с я те работы, |
д л я |
которых коэффициент, |
по |
||
к а з ы в а ю щ и й приращение |
з а т р а т на |
работу, отнесенную |
|||
к единице времени, наименьший . Однако, с о к р а щ а я |
кри |
||||
тический |
путь, необходимо следить |
за другими путями, |
|||
т а к к а к |
последние могут |
оказаться |
критическими. |
|
|
|
з |
J^K |
^ |
|
|
|
ч© ©/ |
|
УФ |
|
|
4 ^ ^ ^ У 7 |
Р и с . 4.11. |
Л І Г |
|
Следовательно, сокращение критического пути м о ж н о осуществлять либо до исчерпания возможности дальней шего с о к р а щ е н и я (когда все работы будут выполняться экстренно), либо до появления нового критического пути. Когда в сетевом графике появляется несколько критиче ских путей, то следует с о к р а щ а т ь продолжительность работ так, чтобы при этом снижалось время всех криті-ь ческих путей. П р и этом подход остается прежним — уве
личение з а т р а т д о л ж н о |
быть минимальным . Оптимиза |
|||||
ция п р е к р а щ а е т с я тогда, |
когда |
продолжительность |
кри |
|||
тнческого пути уравнивается с директивным |
сроком. |
|
||||
Оптимальное распределение |
ограниченных |
ресурсоз |
||||
по времени. Требование з а д а ч и |
сводится к |
следующему . |
||||
Известны |
наличные з а п а с ы ресурсов в к а ж д у ю |
единицу |
||||
времени |
(сутки, неделя, |
м е с я ц ) . Требуется составить |
та |
|||
кой сетевой график, чтобы расход ресурсов в |
к а ж д у ю |
|||||
единицу времени не п р е в ы ш а л |
наличных запасов, а |
вре |
||||
мя выполнения всего комплекса работ было бы при этом
минимальным . Н и ж е мы и з л о ж и м приближенный |
алго |
||||
ритм решения этой |
задачи . |
|
|
|
|
|
П о к а ж е м схему |
решения |
на п р и м е р е |
сетевого |
графи |
ка, |
приведенного на рис. 4.11. Здесь цифры в к р у ж к а х |
||||
над |
р а б о т а м и п о к а з ы в а ю т |
потребление |
некоторого ре |
||
сурса в единицу времени — интенсивность расхода ре
сурса. Ц и ф р ы |
п о д р а б о т а м и |
показывают их продолжи |
тельность. П о л а г а е м наличие |
ресурса в единицу време |
|
ни равным 12. |
Составляем |
линейную д и а г р а м м у этого |
185
комплекса |
работ (рис. 4.12, |
а) |
и д и а г р а м м у |
расхода |
ресурсов в соответствии с сетевым |
графиком (рис. 4.12,6). |
|||
К а к видно, |
расход ресурсов |
в |
некоторые |
интервалы |
времени оказывается больше маличного количества ре
сурсов. |
Следовательно, |
требуется корректировка сетевой |
модели |
для приведения |
ее в соответствие с требования |
ми задачи . |
|
|
•1
|
1 2 |
3 |
4 |
5 |
6 |
7 8 3 1011121314 |
t |
|
|
|
||
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|
|
Iff |
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
8.—^ |
,9 |
|
|
|
|
|
||
|
|
|
|
5 |
|
|
|
|
||||
|
|
|
|
|
|
|
~ |
|
|
|
|
|
|
123 |
|
45 |
|
6789 |
1011121314 |
t |
Рис . |
4.12. |
|||
|
|
|
|
|
|
|||||||
Выявляем |
критический путь |
О—1—3—4—5{Ткр |
= 1 4 ) . |
|||||||||
З а т е м выполняем |
нумерацию |
работ |
в |
интервале ^ = 0, |
||||||||
t = 2. |
Первый |
|
номер |
присваивается критической |
работе, |
|||||||
затем |
следующий |
номер |
присваивается |
некритической |
||||||||
работе, резерв времени которой меньше резерва |
времени |
|||||||||||
всех некритических работ. Если таких работ |
окажется |
|||||||||||
больше единицы, |
|
то |
они |
получают |
'номера |
в |
порядке |
|||||
убывания их необходимого ресурса. В данном случае мы имеем: 0—1 — № 1; 0—3 — № 2; 0—2 — № 3. Подсчи тываем количество ресурсов, необходимых для выполне-
186
