4. ОПТИМИЗАЦИЯ ПЛАНА КОМПЛЕКСА РАБОТ

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

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

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

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

Наконец, возможна еще одна постановка задачи оптимизации плана. После построения сетевого графика нам стало известно, что минимальное время выполнения всего комплекса работ укладывается в заданный срок с избытком:

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

Дадим постановку каждой из этих задач оптимизации в формульной записи. Для простоты будем предполагать, что критический путь — один (если это не так, очевидно, всегда можно, внося во времена выполнения работ -изменения, сделать критический путь единственным, подобно тому, как мы поступали в вырожденных задачах линейного программирования).

Задача 1. Комплекс состоит из работ с временами выполнения известен критический путь, причем время выполнения комплекса равно

где суммирование распространяется только на критические работы. Заданный срок выполнения комплекса работ равен

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

Спрашивается, какие дополнительные средства следует вложить в каждую из работ, чтобы:

— срок выполнения комплекса был не выше заданного

— сумма вложенных средств достигала минимума.

Таким образом, нам требуется определить неотрицательные значения переменных (дополнительные вложения) так, чтобы выполнялось условие

где суммирование распространяется по всем критическим работам нового критического пути (полученного после перераспределения средств и изменения времен), и чтобы при этом общая сумма дополнительных вложений была минимальна:

Поставленная задача напоминает задачу линейного программирования, потому что в ней при некоторых ограничениях-неравенствах требуется минимизировать линейную функцию (4.3) от элементов решения. Однако в общем случае входящие в ограничения (4.2) функции нелинейны, так как вложение каких-то средств в работу не обязательно вызывает линейное уменьшение времени, затрачиваемого на эту работу. Поэтому в общем виде поставленная задача относится к классу задач нелинейного программирования, которые гораздо сложнее линейных задач и общие способы решения которых не разработаны. Такими нелинейными задачами мы здесь заниматься не будем, отсылая интересующихся к специальным руководствам ([2, 28]). Однако, если ограничиться сравнительно небольшими изменениями плана (такими, при которых время выполнения работ приблизительно линейно зависит от вложенных дополнительных средств, а критический путь не меняется), поставленная задача становится задачей линейного программирования и может быть решена уже известными нам способами (см. гл. 2).

Пример 1. Имеется комплекс работ параметры которого даны в структурно-временной табл. 4.1.

Таблица 4.1

Сетевой график комплекса работ дан на рис. 10.5. Завершение работы — узел критический путь состоит из работ . Время окончания комплекса:

Это время должно быть уменьшено до для этого нам понадобится форсировать некоторые критические работы. Известно, что в работу а; можно вложить средства в размере не более, чем при этом время выполнения работы уменьшается согласно линейной зависимости!

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

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

Решение. Условия (4 4) и (4.5) дают

Рис. 10.5

Новый срок выполнения работ (при условии, что критический путь не изменится)

Эта величина не должна превосходить

откуда

Поставим задачу линейного программирования: найти неотрицательные значения переменных удовлетворяющие условиям-неравенствам (4.6), (4.7) а обращающие в минимум линейную функцию

(4.8)

Решаем задачу согласно общим правилам симплекс-метода (см. гл. 2).

Таблица 4.2

Таблица 4.3

Таблица 4.4

Введением дополнительных переменных условия-неравенства (4.6), (4.7) преобразуются в равенства:

Составляем симплекс-таблицу (табл 4.2). Полагая свободные переменные равными нулю: получим недопустимое решение, в котором поэтому опорное решение ОЗЛП требуется еще найти. Поступаем согласно общему правилу нахождения опорного решения ОЗЛП (см. § 7 гл 2) Отбрасывая временно строку L (при нахождении опорного решения она не нужна) и выбирая в качестве разрешающего элемента элемент —6 в последней строке, получим симплекс-таблицу (табл. 4.3).

Продолжая действия, приходим к опорному решению, записанному в табл. 4.4.

В табл. 4.4 все свободные члены уже положительны, значит, опорное решение найдено. В строке L табл. 4.4 помещена (в стандартном виде) линейная функция L, выраженная через новые свободные переменные

Все коэффициенты в верхней строке табл. 4.4 отрицательны; следовательно, увеличение каждой из свободных переменных может только увеличить функцию L. Значит, оптимальное решение найдено:

При этих значениях переменных сумма вложений достигает минимума

Таким образом, оптимальным решением по вложению средств является следующее: вложить сумму в работу в работы а, и не вкладывать средств. При этом срок Т выполнения работ будет:

Проверим, сохранится ли при таком решении критический путь?

Из рис. 10.5 видно, что сокращение с 20 до 10 еще не меняет критического пути, но находится уже на самой границе того сокращения, при котором критический путь меняется.

Возникает естественный вопрос: а как быть, если при вложении средств в какие-то работы критический путь изменится? Оказывается, в этом случае задачу оптимизации также можно свести к задаче линейного программирования, но к другой — уже более сложной, с большим числом переменных. Покажем, как это делается, на том же примере, но в буквенном виде, не доводя до численных результатов.

В качестве переменных введем средства вкладываемые в работы моменты начала работ (моменты равны 0) и моменты окончания всех работ. Структурная таблица дает нам следующие ограничения-неравенства:

Условия зависимости времени выполнения работы от вложенных средств дадут нам ограничения-равенства:

(напомним, что здесь — постоянные). Далее, сохраняются ус-лови я-неравенства

Наконец, условие выполнения всего комплекса работ в срок обратится в ограничения-неравенства

из которых, в силу особенностей данной конкретной структурной таблицы, можно оставить лишь последнее: Та

При всех этих условиях нужно минимизировать линейную функцию

Итак, задача свелась к задаче линейного программирования с 21 переменной, с 8 ограничениями-неравенствами и 21 ограничением-неравенством; введением дополнительных переменных ее можно свести к ОЗЛП с 42 переменными и 29 ограничениями-равенствами. Конечно задача с семью переменными и четырьмя ограничениями-равенствами во много раз проще; так что в таких случаях разумно сначала проверить, не сохранится ли критический путь прежним, как это было при числовых значениях рассмотренных в примере 1.

Задача 2. Имеется совокупность работ: с временами выполнения Время выполнения комплекса работ выражается формулой

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

Имеется некоторый неизменный запас подвижных средств В, который распределен между работами так, что каждой работе соответствует количество подвижных средств, равное соответственно

Известно, что количество средств снятое с работы увеличивает время ее выполнения с до

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

Спрашивается: как надо перераспределить имеющиеся подвижные средства В между работами для того, чтобы срок выполнения комплекса был минимальным?

Покажем, как может быть решена подобная задача.

Обозначим — количество подвижных средств, перебрасываемых на работу отрицательно, если с работы снимается какое-то количество средств).

Величины должны удовлетворять ограничениям:

Естественно, что сумма средств, снимаемых с каких-то работ, должна быть равна сумме средств, добавляемых другим работам, так что

После переброски средств для тех работ, на которые они перебрасываются, новые времена будут равны

для тех же работ, с которых средства снимаются:

Общий срок выполнения комплекса работ будет:

где первая сумма распространяется на все работы, на которые переносятся средства, если они входят в критический путь; вторая — на все работы, с которых переносятся средства, если они входят в критический путь.

Естественно, кажется, считать, что перенос средств имеет смысл только с некритических работ на критические; однако не надо забывать, что при этом некритические работы могут переходить в критические а наоборот; поэтому в формуле (4.14) в общем случае присутствуют обе суммы.

Итак, перед нами стоит задача: найти такие значения переменных чтобы выполнялись ограничения (4.10), а функция (4.14) обращалась в минимум.

Задача представляет собой задачу нелинейного программирования даже в случае, когда функции (что с некоторой натяжкой можно допустить) линейны. Существенно нелинейным в функции (4.14) является то, что значения — номеров работ, на которые распространяется сумма (т. е. критических работ), сами зависят от

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

Пример 2. Комплекс работ задан структурно-временной табл. 4.5 Здесь критическими являются работы время выполнения комплекса Некритической является работа На ней имеется запас подвижных средств Запасы подвижных средств на остальных двух работах отсутствуют.

Таблица 4.5

Известно, что переброска средств с работы увеличивает время ее выполнения до

Запас средств переброшенный на работу уменьшает время ее выполнения до

Запас средств переброшенный на работу уменьшает время ее выполнения до

Требуется определить, как оптимальным образом перебросить свободные средства с работы на работы , и чтобы срок выполнения комплекса был минимален.

Решение. Обозначим количества средств, перебрасываемые с работы соответственно на через Требуется найти такие неотрицательные значения чтобы выполнялись условия:

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

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

«Перескок» работы на критический путь происходит, когда осуществляется равенство:

или (если с работы сняты все средства)

что осуществляется при . Значит, работа при критической не станет: критическими останутся работы Предположим, что это так. и в формуле (4.16) второй член будет равным нулю, а два другие и

Учитьшая (4.15), имеем и

Исследуем эту функцию на максимум; найдем ее производную по

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

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

Итак, в нашем примере наивыгоднейшее перераспределение средств состоит в следующем: из имеющегося запаса свободных средств средства должны быть перенесены на работу а средства — на работу При этом время выполнения комплекса работ принимает минимальное значение Времена выполнения отдельных работ будут равны соответственно

Задача 3. Имеется комплекс работ с временами выполнения Для этого комплекса найден критический путь и установлено, что минимальное время выполнения комплекса где — заданный срок выполнения. Предполагается снизить темпы выполнения некоторых работ с тем, чтобы срок выполнения комплекса довести до заданного значения за счет этого предполагается получить экономию средств. Увеличение времени выполнения работы на (т. е. доведение времени выполнения работы до ) высвобождает некоторые средства которые зависят от задержки :

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

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

где сумма, как и ранее, распространяется только на критические работы.

Требуется выбрать такие неотрицательные значения переменных чтобы сумма высвободившихся средств достигала максимума:

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