|
графа путь, состоящ ий из верхних огибаю щ их д у г будет соответствовать реш ению когда работы выполняются по самому деш евому варианту, а путь, состоящ ий из н и ж н и х огибаю щ их д у г будет соответствовать реш ению , когда работы выполняются по самому дорогом у варианту. Естественно, что эти достаточно тривиальные решения будут в общ ем-то не интересны для дальнейш его реш ения. Т аким образом, задача сводится к определению на графе множества подкритических путей, которы е будут не меньше заданной величины сокращ ения общ ей продолжительности выполнения работ. П онятно, что в зависимости от того, насколько заданное значение сокращ ения общ ей продолжительности б удет отличаться от максимально (минимально) возм ож ного, требуемые подкритические пути будут находиться в некоторой средней части сетевого представления. О тыскание путей заданной длины представляет собой достаточно слож ную задачу, решение которой в общем виде не найдено. Н о учиты вая невысокую точность требуемую при реш ении данной задачи, возможно предложить алгоритм, основанный на нахождении эфф ективностей для каж дой степени совмещения между рассматриваемыми работами, которы й заключается в следующ ем: 1 ш а г. Определение эффею'ивностей для каж дого варианта выполнения работ. 2 ш аг. Выделение подкритического пути, проходящ его через события графа, имеющ ие максимальную эфф ективность и определение величины сокращ ения общей продолжительности и затрат. к ы й ш аг. Улучш ение полученного решения, путем перебора значений близких к полученному. Рассмотрим применение этого алгоритма на примере. Найдем эффективность каж дого варианта совмещения. С оответствую щ ие данные представлены в табл. 3.6.3. П уть максимальной эфф ективности проходит через события 4 ~ б 14 20. П ри этом величина сокращ ения общ ей продолжительности выполнения ра99 |
строения графа путь, состоящий из верхних огибающих дуг будет соответствовать Таблица 4.6.2. Исходные данные \ ( ] \ (1-2) (2-3) (3-4) (4-5) он 1/3 1/3 2/4 2/2 н 2/5 3/5 5/7 4/4 с 4/10 5/10 6/16 7/8 в 5/17 17/7 9/26 10/12 ОВ 8/20 10/20 12/32 42/15 решению когда значения коэффициентов совмещения соответствуют множеству «очень низкая» степень совмещения работ, а путь, состоящий из нижних огибающих дуг будет соответствовать решению для «очень высокой»степени Рис. 4.6.2. Сетевое представление множества возможных решений совмещения. Естественно, что эти достаточно тривиальные решения будут в общем-то не интересны для дальнейшего решения. Таким образом, задача сводится к определению на графе множества подкритических путей, которые будут не меньше заданной величины сокращения общей продолжительности выполнения работ. Понятно, что в зависимости от того, насколько заданное значение сокращения общей продолжительности будет отличаться от максимально (минимально) возможного, требуемые подкритические пути будут находиться в некоторой средней части сетевого представления. Отыскание путей заданной длины представляет собой достаточно сложную задачу, решение которой в общем виде не найдено. Но учитывая невысокую точность требуемую при решении данной задачи, возможно предложить алгоритм, основанный на нахождении эффективностей для каждой степени совмещения между рассматриваемыми работами, который заключается в следующем: 1 шаг. Определение эффективностей для каждого значения степени совмещения. 2 шаг. Выделение подкритического пути, проходящего через события графа, имеющие максимальную эффективность и определение величины сокращения общей продолжительности и затрат. к-ый шаг. Улучшение полученного решения, путем перебора значений близких к полученному. Рассмотрим применение этого алгоритма на примере. Найдем эффективность каждого варианта совмещения. Соответствующие данные представлены в табл. 4.6.3. Таблица 4.6.3. Значения эффективностей \ i i \ (1-2) (2-3) (3-4) (4-5) он 3 3 2 1 н 2,5 1,67 1,6 1 с 2,5 2 2,7 1,1 В 3,4 2,4 2,9 1,2 ОВ 2,5 2 2,7 1,25 Путь максимальной эффективности проходит через события 4 6 14 20. При этом величина сокращения общей продолжительности выполнения работ составит 61 дн., а затраты 25. Учитывая, что сокращение продолжительности должно составлять не менее 50 дней, следует отметить, что полученная величина будет представляться избыточной, что связано с повышен |