интересно
Предыдущая | Содержание | Следующая

Оптимизационные модели программы

Оптимизация сетевой схемы программы

Сетевая схема программы отображает взаимо связь проектов.

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

перед работой (обозначается кружком).

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность выполнения каждой работы (табл. 16.1).

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

Работа обозначается двумя индексами / —j, где / — номер события, после которого начинается работа,; — номер события, которым заканчивается работа (см. также табл. 16.2).

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

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

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

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

  (рис. 16.2).

Из рис, 16.2 видно, что резерв работы 1-3, который будем обозначать Diy равен 5 — 2 = 3. Значит, работа 1-3 может быть начата не в начальный момент времени, а спустя 3 ед. времени или продолжаться на 3 ед. больше, чем первоначально предполагалось, т. е. может длиться

 


2 + 3 = 5 ед. без увеличения момента наступления конечного события 4.

третьего события можно записать

записано в скобках, чтобы было наглядно вид-

но, что это интервал времени между двумя последовательными событиями. И этот интервал за вычетом резерва Dl3 равен продолжительности работы 1-3. В этой зависимости нам задана продолжительность работы £ - 2 (правая часть уравнения), остальные величины — искомые переменные. Если их обозначить:

и получить линейное уравнение с тремя неизвестными.

Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему:

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

Если вместо t. подставить их известные (заданные) значения, получим;

Эта система структуры сети содержит пять линейных уравнений с девятью неизвестными. Значит, она имеет бесчисленное множество решений. Чтобы ее решить, надо добавить граничные условия и ЦФ.

При этом возможны две постановки задач оптимизации.

Первая постановка: задаемся временем начала работ, т. е. значением 7|Тнапример Т =0, и стремимся закончить комплекс работ как можно раньше:

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

на +4 больше, чем в 1-й постановке

Обе постановки — это задачи линейного программирования, которые можно решить (табл.  16.4).


Из таблицы видно, что резерв Д. не зависит от постановки задачи. Времена окончания работ в первой постановке и начала работ во второй постановке определяются заданными граничными условиями.

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

В общем виде топология сети запишется:

А число ограничений т — R, т. е. каждой работе соответствует ограничение.

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

Тогда общие постановки запишутся:

— заданные плановые сроки начала и окончания работ

сети.

Например, для графика (рис.  16.3) из 11 событий и 20 работ (всего лишь) первая постановка при 7",= 0 будет иметь вид:

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