Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 98
Скачиваний: 0
тельность каждой операции, т. е. определен оптимальный по стоимости календарный план развития работ.
Задача оптимизации сетевого графа по фактору стоимо
сти ставится следующим образом. |
|
контуров, |
состоящий |
||||
Задан сетевой граф G(X, U) |
без |
||||||
из множества вершин х-г и множества дуг |
На каждой |
||||||
дуге Uij |
указаны два неотрицательных числа: Dtj и di}— |
||||||
соответственно максимальная |
и |
минимальная продолжи |
|||||
тельность |
tu выполнения работы. |
Зависимость стоимости |
|||||
от времени выражается функцией |
. |
Общая стои |
|||||
мость всего проекта |
R(t), где £ = {£ г;} , |
рассчитывается по |
|||||
формуле |
|
|
|
|
|
|
|
|
|
R ( f ) |
|
|
|
|
(1.1) |
|
|
Щ}Ф |
|
|
|
|
|
Задан набор ограничений: |
|
|
|
|
|
||
|
|
Т ~ т , - г и > |
0 |
|
|
|
|
|
|
|
|
|
|
|
(1.2) |
|
|
Т о = 0 , Т„< Т дир |
|
|
|||
Здесь То, Тп— соответственно |
время |
начала и окончания |
|||||
проекта, |
переменные |
Tt,T j — время наступления события, |
|||||
Тдир — директивный срок. |
|
|
|
|
|
||
Ставится задача |
отыскания |
плана |
[t= {t ij] , т = { Т Д ], |
||||
минимизирующего функционал (1.1) при ограничениях (1.2). Для решения сформулированной задачи в настоящее время применяются различные методы. Перечислим основные раз работки и остановимся на изложении общего недостатка, присущего, на наш взгляд, проводимым исследованиям.
Наиболее известными методами решения задачи явля ются метод Дж. Келли [27, 65] и аналогичный ему метод
Д. Фулкерсона [33, |
62]. Зависимость стоимости каждой ра |
|
боты от времени ttj |
предполагается линейной и выражается |
|
формулой |
|
|
|
1"ij Ьij dijtij. |
(1.3) |
С учетом указанных ограничений на каждом шаге миними зируется стоимость
R(t) = |
-------------------------nyti'iviMHWI |
UijQG |
|
|
(^ - V*j;■ ИичМШЩ |
В качестве первого приближения берется Т1ппри максималь
ном |
значении ttj = Z )iy-, когда потребление ресурсов R = |
= 2 |
j (Pij— aijDij) минимально. |
(U) |
|
Сокращение продолжительности критического пути Тхп возможно только за счет уменьшения времени выполнения работ, составляющих критические пути. В сетевом графике может быть несколько критических путей. Обозначим эти пути через pi, рг, •. •, рр. Чтобы сократить величину най денную на первом шаге при 4j = D tj, нужно одновремен но уменьшить на одно и то же значение продолжительность каждого из критических путей. С уменьшением времени осуществления работ увеличиваются, согласно (1.3), исполь зуемые ресурсы. Поэтому возникает необходимость выбора в каждом критическом пути р% таких работ, которые в сум ме давали бы наименьшее приращение ресурсов AR.
Пусть продолжительность некоторой работы (ij) критиче ского пути р£ уменьшили на единицу (t — 1). Тогда прира щение ресурсов Ar tj выразится, согласно (1.3), так:
Q’ijifij 1)] \tyij
Уменьшение продолжительности сразу нескольких работ, принадлежащих к различным критическим путям ц, приве
дет к увеличению общего уровня ресурсов на haи = Л R. ij
Для определения множества работ F, которому соответ ствует минимальная величина AR, Дж. Келли использует минимальный разрез транспортной сети. Как известно, ми нимальный разрез обладает таким свойством, что из каж дого критического пути обязательно выбирается по одной дуге и сумма пропускных способностей этих дуг минималь
на.
Минимальный разрез транспортной сети строится сле дующим образом. Из сетевого графа вычеркиваются все дуги, означающие некритические работы, поскольку умень шение времени t предполагается только на дугах крити ческого пути. Если дуга (г, j) соответствует критической ра боте и Чу> d-Ф то ее продолжительность можно уменьшить до значения di}. Пропускная способность такой дуги берет
ся равной коэффициенту a i}. Если же работа (г, ;) критиче ская и время ее выполнения минимально ttj = dtj, то про пускная способность дуги (i, j) в транспортной сети полага ется равной оо. Это делается для того, чтобы рассматривае мая дуга, имея большую пропускную способность, не вошла в минимальный разрез, т. е. уменьшать продолжитель ность работы не следует, так как 4; минимально.
•18=,
Таким образом находится набор критических работ F, доставляющих минимум приращения ресурсов AR. Число AR в этом случае выступает в роли максимального потока через транспортную сеть. До сих пор мы предполагали, что можно уменьшить значение Т п1 на единицу. Однако времен ные оценки работ допускают сокращение критического пути на величину .6>»1.
Величина б определяется по формуле
S=min(min(fy—dj ); (Т„1—Т1под)), |
(1.5) |
( i № F |
|
где Тгп0д — длина максимального подкритического пути. Стоимость проекта равна
R2 ==Ri~\~AR •6.
Произведение AR- 6 показывает, насколько увеличиваются используемые ресурсы за счет сокращения Ткр на величи ну б.
Описанные действия составляют одну итерацию. Най денные временные оценки на данной итерации принимаются в качестве исходных для следующей итерации. Процесс за кончится тогда, когда на k-й итерации выполнится условие
ТяА:< 7 7дир, т. е. продолжительность Ткр не превысит дирек тивного срока.
В работе С. Е. Кларка [59] рассматривается другой под ход. Функции rij(tij) предполагаются строго выпуклыми книзу. Задача заключается в минимизации общего уровня ресурсов R при заданном времени Т осуществления ком плекса. Доказывается, что для оптимальности решения не обходимо и достаточно, чтобы все операции были критиче скими и в любой момент времени £ е [0 , Т] количество по требляемых ресурсов на работах фронта было постоянным. Под фронтом понимаются работы, производимые одновре менно в момент t. Действительно, если работы, не принад лежащие к критическому пути, целиком используют свой резерв времени, то они становятся критическими. Увели чение продолжительности выполнения работ за счет резерва времени приводит к уменьшению общего уровня использу емых ресурсов. На основании этого предлагается алгоритм решения.
Аналогичный подход изложен в работе Е. В. Бирмана [56]. В работе А. Кофмана, Г. Дебазея [33] рассматривает ся случай, когда длительность tij операций является вели чиной детерминированной. Другими словами, при данной стоимости операции rtJ ее длительность ttj — определен
ная величина. Авторы описывают два аспекта, представля ющие интерес с точки зрения оптимизации плана выполне ния проекта:
а) уменьшение полной стоимости проекта при неизмен ной общей продолжительности его выполнения;
б) ускорение реализации проекта (комплекса операций) при наименьших затратах.
В первом варианте задача сводится к уменьшению общей стоимости проекта путем сокращения свободных резервов некритических операций в пределах, установленных огра ничениями
где dtj и D%j — соответственно нижняя и верхняя границы изменения длительности tiyкаждой операции. Эти ограни чения могут определяться техническими или экономически ми соображениями.
Полная стоимость проекта R получается как сумма сто имостей всех операций:
(ij)eu
где rtj = 0 , если (i, j) q U (U — множество дуг, составляю щих сеть проекта).
Задача решается в предположении, что возрастание сто имости операций пропорционально уменьшению их длитель ности.
Второй вариант задачи заключается в минимизации об щей продолжительности осуществления проекта. Это дости гается уменьшением длительности тех критических опера ций, которые при одинаковом сокращении времени приво дят к наименьшему увеличению стоимости. Для случая, когда функции г ^ = fifij) имеют вид параболы, выпуклой ломаной или прямой, эти методы дают достаточно хорошее приближение к оптимуму.
В настоящее время для оптимизации сетевых моделей по фактору стоимости наиболее простым для расчетов яв ляется градиентный метод, описанный А. С. Бурчаковым, Б. М. Воробьевым и др. [12, 27].
Если зависимость прямых затрат Cij от продолжитель ности tij выполнения операции (г, j) можно выразить в ви
де линейной или кусочно-линейной функции
(1.6)
(1.7)
201
то угловой коэффициент
представляет собой увеличение стоимости, приходящейся на единицу времени сокращения продолжительности операции.
Значения C(<f..) |
и С(п..) определяются по формуле (1.6) |
при |
tij = dij и tij |
= D tj. Таким образом, коэффициент |
atj |
можно интерпретировать как градиент изменения прямых затрат на время выполнения операции (г, у).
Пусть составлен |
сетевой |
график. |
Если Ткр> Т дир , то |
необходимо сократить Ткр до |
ТдИр за счет привлечения ми |
||
нимального объема |
дополнительных |
ресурсов. Для реше |
|
ния задачи находятся критический путь, подкритические пути, резервы времени. Далее уменьшается продолжитель
ность той критической работы, у которой градиент |
агу |
ра |
|||
вен минимуму. |
задач |
посвящено много |
работ. |
||
Решению аналогичных |
|||||
Например, в работе С. И. Зуховицкого и И. А. Радчик J27] |
|||||
рассматривается зависимость |
rtj |
прямых затрат на осуще |
|||
ствление каждой работы |
utj |
от ее продолжительности |
ti} |
||
в виде функции |
|
|
|
|
|
|
|
(1.8) |
где Сц — заданный параметр, a |
принимает значения в |
|
пределах (d < ttj < |
Задача |
в этом случае ставится |
так: найти минимум функции потребления ресурсов
(1.9)
при ограничениях
Tj—Ti^dij для всех ии,
(1.10)
То=0, Тп^.Тдир.
Здесь T j — Ti=tij — время выполнения работы иц (вклю чая резерв времени), определяемое разностью между позд ним окончанием и ранним началом работы, Т дир — дирек тивный срок завершения проекта. Функция R выпуклая, и задача может быть решена одним из методов выпуклого программирования [26, 40].
21