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

Сетевой график работ составлен таким образом, что израсходованы все ресурсы В. Однако на этом графике не все работы критические, поэтому можно уменьшить время 7'_крза счет резервов, образующихся на некритических работах. Перенеся эти резервы на критические работы, можно уменьшить время их выполнения и тем самым получить новые сроки выполнения работ и соответственно меньший Г_кр. Оптимальным сетевым планом будет такой план, когда Г_к°_р получится наименьшим из всех возможных в данных условиях. Очевидно, новые длительности всех путей в таком случае будут равны, т. е.

Механизм перераспределения средств включает уменьшение средств части работ (i, j) на некоторую величину Ху < b что приводит, естественно, к увеличению времени ее выполнения.

Средства Ху, вложенные в другую работу (A, k)_y Ху = х^ь приводят к уменьшению времени ее выполнения.

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

что показывает на экспонентную форму связи.

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

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

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

На этом основании общий срок выполнения всего комплекса работ определяется целевой функцией следующего вида:

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

В процессе перераспределения средств необходимо соблюдать условие ограничения на величину снимаемых средств Xjj с работы (i, j), которое определяется наличием свободного резерва времени г|‘^в этой работы по формуле

и, следовательно, удовлетворять этому условию.

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

Перед началом оптимизации расположим длительности всех путей последовательно в порядке увеличения их резервов.

11а первом этапе оптимизации выбираем резерв работ, ближайший к критическому пути Z. J = 50 дн., путь L->, = 43 дня. На этом пути 1₃ некритическая работа (5, 8') имеет свободный резерв времени =7 дн. Условие допустимости решения по величине переносимых средств определяется выражением.

Перенесем часть средств работы (5, 8') на работу критического пути (1, 2).

Замечание. Переносить средства с работы одного пути, например (5, 8') пути 1₂, на любую работу, даже и критическую, но входящую в этот же путь Ь₂, например (0, 1), нельзя.

Величину переносимых средств и длительности новых равных критических путей Т[ = Г₃ = Т'_щ> можно найти, составив и решив следующую систему уравнений:

Найдя величину переносимых средств, проверяем допустимость такого решения по ограничению. Если оно недопустимо, то переносим средства на любую другую работу; опять составляем новую систему уравнений и таким образом продолжаем оптимизацию. Новые длительности работ (5, 8') и (1, 2) находим по формулам.

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

На втором этапе рассматриваем следующий ближайший некритический путь Lна котором у работы (7, 7') имеется свободный резерв времени:

Проверяем условие допустимости решения относительно величины переносимых средств.

Затем переносим часть средств яуу работы (7, 7') на две работы (1, 2) и (5, 8') для сокращения времени выполнения работ первого и второго путей. Для нахождения величин переносимых средств составим систему уравнений.

Затем находим величины переносимых средств ду-ч ₂. Х5 ₈, а также новые длительности работ.

Длительности новых критических путей вычисляем по формуле.

На третьем этапе путь L-> имеет резерв времени у работы (5,5').

Проверяем условие допустимости решения по формуле.

Затем переносим резервы с некритической работы (5,5') на работы (1, 2), (5, 8'), (7, 7') остальных критических путей, для чего запишем систему уравнений.

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

Теперь длительности всех четырех путей от исходного события (0) к завершающему (9) стали равными.

Оптимизация закончена. Таким образом, применение методов сетевого моделирования позволило выявить экономию 50 — 43,3 = 6,7 дня, но переводу коммерческого предприятия на самообслуживание.

С учетом полученных в результате решения новых значений длительностей работ построим оптимальный сетевой план (рис. 4.34) комплекса работ по переводу коммерческого предприятия на самообслуживание.

Рис. 434.

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