3. Оптимизация сетевых планов комплекса работ

3.1. Постановка задачи оптимизации

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

(3.1)

где n - число работ сетевого графика, номер последней работы, завершающей комплекс работ.

Обычно не составляет большого труда рассчитать стоимость выполнения работ в нормальном и форсированном режимах С_{Di и} C_di соответственно. Сложней бывает рассчитать промежуточные значения стоимости С _i.

, (3.2)

поэтому зависимость С_i=f(t_i) в первом приближении принимают линейной, которая задается двумя точками (рис. 4).

, (3.3)

где (3.4)

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

1. Задано допустимое время выполнения комплекса работ сетевого графика т0.

(3.5)

Необходимо определить длительность и стоимость всех работ так, чтобы суммарная стоимость С_СГ была минимальна

(3.6)

2. Задана допустимая суммарная стоимость выполнения работ сетевого графика С₀

(3.7)

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

(3.8)

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

3. Обычно задача ставиться в более общем виде: желательно минимизировать не один из показателей при ограничении на другой, а по возможности уменьшить и время, и стоимость, находя между ними некоторый разумный компромисс. При этом, вообще говоря, может иметь место либо одно, либо даже оба ограничения, (3.5), (3.7), ясно что они не должны противоречить друг другу. Наличие ограничений не влияет на метод решения задачи, они могут быть учтены на последнем этапе принятия решения, поэтому при описании алгоритма решения эти ограничения не рассматриваются.

Для решения задач оптимизации по двум показателям (времени и стоимости), целесообразно использовать метод отбрасывания явно неэффективных решений. Общее число решений в ОДР (область допустимых решений) и на ее границах, задаваемых неравенствами (3.1), (3.2), измеряется многими тысячами даже для сравнительно простых сетевых графиков. Цель алгоритма оптимизации состоит в нахождении множества вариантов, лежащих на левой нижней границе области решений, т.е. одновременно минимизирующих и время и стоимость.

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

В пределах линейной модели найденные точки зависимости оптимальной стоимости С_опт от оптимального времени выполнения работ сетевого графика Т_опт С_опт=f (Т_опт) позволяет восстановить всю зависимость, соединив их отрезками прямых (см. пример рис. 7). Следовательно, алгоритм решения задачи в общей постановке позволяет решать задачу и в двух первых постановках (3.5), (3.6), и (3.7), (3.8).

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

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

Вторая задача: увеличить время выполнения сетевого графика до допустимого значения, но, таким образом, чтобы при этом получить максимальную экономию средств.

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

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