Построение календарного плана с минимальными дополнительными затратами (метод дихотомического программирования)

Решение:

Применим метод дихотомического программирования к решению данной задачи.

Рассмотрим сетевой график без контуров, в котором некоторое множество Q зависимостей является мягкими (—-). При построении дихотомического представления учитываются только моменты окончания тех работ j, которые связаны мягкими зависимостями хотя бы с одной работой, то есть существует работа i, такая что ij? Q (3, 6 и 7 работа).

Построим дихотомическое представление сетевого графика.

Построим соответствующие матрицы для t3, t6 и t7.

Опишем метод построения этой матрицы для мягких зависимостей.

Возможны 4 варианта:

— Зависимости (1−3) и (2−3) учитываются:

Тогда момент завершения работы 3 равен:. Дополнительных затрат нет.

— Зависимость (1−3) учитывается, а зависимость (2−3) не учитывается:

Тогда момент завершения работы 3 равен:. Дополнительные затраты равны 9.

— Зависимость (1−3) не учитывается, а зависимость (2−3) учитывается:

Тогда момент завершения работы 3 равен:. Дополнительные затраты равны 7.

— Обе зависимости не учитываются:

Тогда момент завершения работы 3 равен:. Дополнительные затраты равны 7+9=16.

Теперь можно решить задачи оптимизации дополнительных затрат для любого T.

1. Возьмём T 16.

Из матрицы t7 получаем, что t5=9, t3=7, следовательно, зависимость (5;7) учитывается;

Из матрицы t3 получаем, что при t3=7, t1=3, t2=5. Т. е. зависимости (1;3) и (2;3) учитываются;

Из матрицы t6 получаем: t3=7, t4=9, т. е. зависимость (3;6) учитываются Таким образом, учитываются все зависимости и дополнительные затраты равны S (16)=0.

2. Возьмём T 14.

Из матрицы t7 получаем, что t5=0, t3=7 — это удовлетворяет ограничению T? 14. Зависимость (5;7) не учитывается;

Из матрицы t6 получаем, что при t3=7, t4=9.

Из матрицы t4 получаем, что при t3=7, t1=3, t2=5.

Таким образом, учитываются все зависимости, кроме (5;7) и дополнительные затраты равны S (14)=9.

3. Возьмём T 12.

Из матрицы t7 получаем, что t5=0, t3=5, следовательно, зависимость (5;7) не учитывается;

Из матрицы t6 получаем, что при t3=5, t4=9,т.е. зависимость (3;6) учитывается;

Из матрицы t4 получаем: t2=0, t1=3, т. е. зависимость (2;3) не учитывается, а зависимость (1;3) учитывается.

Дополнительные затраты равны S (12)=9+9=18.

4. Возьмём T 9.

Из матрицы t7 получаем, что t5=0, t3=2, следовательно, зависимость (5;7) не учитывается;

Из матрицы t6 получаем, что при t3=2, t4=9,т.е. зависимость (3;6) учитывается;

Из матрицы t4 получаем, что при t3=2, t2=0, t1=0, т. е. обе зависимости не учитываются.

Дополнительные затраты равны S (9)=7+9+9=25.