Лекция №1 (стр. 1 )

Лекция №1

2. Оптимизация плана комплекса работ

Сетевой график может быть использован для оптимизации плана работ. Это улучшение может производиться с различными целями. Например, может оказаться, что общее время выполнения комплекса работ Т не устраивает исследователя. Возникает вопрос - как нужно форсировать работы, чтобы общее время не превосходило заданного срока Т0. Для этого имеет смысл форсировать именно критические работы, снижение длительности которых непосредственно скажется на времени Т.

Форсирование работ требует вложение каких-то средств. Возникает задача : какие дополнительные средства и в какие работы следует вложить, чтобы общий срок выполнения комплекса работ был не больше заданной величины Т0, а расход дополнительных средств был минимальным.

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

Возможна еще одна постановка задачи оптимизации плана.

Если после построения сетевого графика стало известно, что min время выполнения всего комплекса работ укладывается в заданный срок с убытком :

Т < Т0

т. е. имеется резерв времени. Растянув работы, можно сэкономить некоторые средства. Возникает задача: до каких пределов можно увеличивать времена выполнения работ и каких работ, чтобы полученная экономия была max. В такой постановке может ставиться задача оптимизации необязательно всего плана, а отдельных некритических дуг, на которых выявлены временные резервы.

Задача №1

Комплекс работ состоит из работ а1, а2, ... ,аn с временами выполнения t1, t2, ..., tn. Известен критический путь, причем время выполнения комплекса работ равно

Т = ti > T0

T0 - заданный срок выполнения комплекса работ.

Известно, что вложение х дополнительных средств в работу а сокращает время ее выполнения с ti до t= f i(хi)<ti. Возникает вопрос какие дополнительные средства х1, х2, ..., хn следует вложить в каждую из работ чтобы : - срок выполнения комплекса был не выше Т0 T £ T0 - сумма вложенных средств достигала min . T = f i(хi) £ T0 x = xi® min Если предположить, что входящие в ограничения функции f i(хi) - линейны, т. е. ограничиться сравнительно небольшим уменьшением плана, то поставленная задача есть задача линейного программирования. Однако в общем случае, входящие в ограничения функции f i(хi) не линейны (т. к. вложение каких-то средств в работу ai необязательно вызывает линейное уменьшение времени) и в общем виде поставленная задача нелинейного программирования. Этот случай рассматривать не будем. Пример Имеется комплекс работ a1 , a2 , ... , an

N n/n	Работа аi	Опирается на работы	Время ti
1.	a1	¾	20
2.	a2	¾	10
3.	a3	¾	8
4.	a4	a1, a2	20
5.	a5	a1, a2, a3	10
6.	a6	a1, a2, a3	5
7.	a7	a6	5
8.	a8	a4, a5, a7	10

Построим сетевой график

а4 A1 А4 A5 а1 А6 А8 A2 а2 10 20 25 30 40 50

t

а3 A3 A7 Время выполнения комплекса : Т = t1+ t4 t8= 50 Это время должно быть уменьшено до Т0= 40. Для этого нужно форсировать некоторые критические работы. Известно, что в работу аi можно вложить средства xi в размере не более, чем сi, при этом время выполнения работы уменьшится линейно : xi < ci t = t i (1 - bi xi) Для критических работ а1, а4, а8 параметры bi, ci b1 = 0,2 ; c1 = 2 b4 = 0,3 ; c4 = 2 b8 = 0,1 ; c8 = 5 Требуется определить вложения x1, x4 , x8 так. чтобы срок выполнения комплекса был не больше Т0 = 40, а сумма вложений ® min x1 + x4 + x8 ® min ограничения : 2 - х1 ³ 0

2 - х4 ³ 0

5 - х8 ³ 0

Новый срок выполнения работ (при условии, что критический путь не изменится). Т = t + t + t = t1 (1 - 0,2x1) + t4(1 - 0,3x4) + t8(1 - 0,1x8) = 20(1-0,2 x1) + 20(1 - 0,3x4) + 10(1 - 0,1x8) = 50 - 4x1 - 6x4 - x8 £ 40 Т £ 40 или 4x1 + 6x4 + x8 ³ 10

Имеем задачу линейного программирования : найти неотрицательные значения x1, x4 , x8 удовлетворяющие ограничениям :

4x1 + 6x4 + x8 ³ 10

2 - х1 ³ 0

2 - х4 ³ 0

5 - х8 ³ 0 и образующие в min линейную форму L = x1 + x4 + x8 ® min Решаем симплекс методом. Вводим дополнительные переменные y1, y2, y3, y4. Оптимальное решение x1 = y1 = x8 = 0 y1 = 2; y2 = 1/3; y3 = 5; x4 = 5/3; Lmin = 5/3. Т. о. оптимальным решением будет : вложить сумму x4 = 5/3 в работу a4; в работы a1, a8 ничего не вкладывать. При этом срок выполнения работ Т= t1 + t + t8 = 20 + 20(1 - 0,3 5/3) + 10 = 20 + 10 + 10 = 40 T0 . Сокращение t4 с 20 до 10 не имеет критический путь, но находится на самой границе. Возникает вопрос : как быть, если при вложении средств в какие-то работы критический путь изменится. В этом случае задачу оптимизации можно свести к задаче линейного программирования, но с большим количеством переменных.

Пусть x1, ... , x8 - средства, вкладываемые в работы a1, ... , a8. Моменты начала работ t1, ... , t8, при этом t1 = t2 = t3 = 0 окончания работ T1 , T2 , ... , T8 Структурная таблица дает следующие ограничения t4 ³ T1 , t4 ³ T2 t5 ³ T1 , t5 ³ T2 , t5 ³ T3 t6 ³ T1 , t6 ³ T2 , t6 ³ T3 t7 ³ T6 t8 ³ T4 , t8 ³ T5 , t8 ³ T7 Условия зависимости времени выполнения работы от вложенных средств дают ограничения - равенствo Ti = ti - ti bi xi + ti (i = ) Сохраняются условия неравенства xi £ ci (i = ) Условие выполнения всего комплекса работ T1 £ T0 ... T8 £ T0 или Т8 £ Т0

При этих условиях нужно минимизировать линейную форму L = x1 + ... + x8 Т. о. имеем 21 переменную, 8-ограничений - равенств; 21 ограничение неравенства. Вероятностные факторы, учитываемые при сетевом планировании программ

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