Оптимизация сетевого графика по критериям время - стоимость

из "Экономико-математические модели и методы "

Ниже будет использоваться линейная модель (3.1). [c.35]
Пример 3. Провести минимизацию стоимости проекта, сетевой график которого при заданных значениях продолжительности a(i, j), ty, b(i, j), стоимости (i, j) и коэффициентов затрат на ускорение hy представлен на рис. 3.4. Первоначальная стоимость проекта 1216 усл. р. [c.35]
Решение. Исходные и расчетные значения представлены в табл. 3.3. Заметим, что в таблице приводятся только те работы, для которых R (i, j) 0. В результате оптимизации стоимость нового проекта при том же времени выполнения снизилась на 293 единицы и стала равна 923, т.е. уменьшилась почти на 25%. В результате снижения стоимости проекта появились новые критические пути с tKp = 6l 0-1-3-4-7-10-11, 0-3-5-8-9-11, 0-1-3-4-6-7-10-11, 0-3-5-6-8-9-11 и т.д. В новом графике из 64 полных путей 28 путей будут критическими. [c.36]
Минимизация времени выполнения проекта возможна только за счет сокращения продолжительности выполнения работ, лежащих на критическом пути Lkp. При этом стоимость этих работ и всего проекта увеличится согласно соотношениям (3.1) и (3.6). Для решения этой задачи проводится расчет исходного сетевого графика, а затем выполняется его оптимизация. В начальном сетевом графике продолжительность всех работ может считаться равной максимальному значению (ty = by). Далее выполняются следующие действия. [c.36]
Сверху над каждой работой записывается hy, а снизу - (ty- iy) (возможное сокращение ее длительности). [c.36]
Увеличиваем шаг на единицу, т.е. полагаем k равным k + 1 и осуществляем переход к шагу 4 до тех пор, пока kфn. Иначе идем к 6. [c.37]
Список этих работ обозначим через Q = (р, q . Определяется длительность сокращения выбранных работ At по формуле (3.8) для всего списка Q. [c.38]
Увеличиваем шаг k на 1 (k + 7) и осуществляем переход к 4 до тех пор, пока k Ф п. Иначе идем к 6°. [c.38]
Сделаем ряд замечаний к данному алгоритму. Дополнительные затраты, связанные с сокращением времени выполнения проекта с tj до t2, равны 0/2) — (ti). Для учета шагов алгоритма следует вести таблицу длительности и стоимости работ и длительности полных путей. [c.38]
Другим вариантом данного алгоритма является случай, когда начальный сетевой график построен при минимальных сроках выполнения каждой работы, а затем последовательно увеличивают длину критического пути, увеличивая сроки выполнения некритических, а затем и критических работ по критерию максимума коэффициента напряженности hy. [c.38]
Пример 4. Провести минимизацию времени выполнения проекта при заданных затратах на его осуществление и построить зависимость стоимости от критического времени С = (f). Исходные данные задачи сведены в табл. 3.4. [c.38]
Для удобства дальнейших расчетов представим эти пути графически в виде цепочек, в которых цифры над каждой работой показывают коэффициенты затрат на ускорение работ hy, а под стрелками - максимально возможные величины уменьшения продолжительности работ Ац = by - ay. [c.39]
согласно (3.15) получаем (t) = 300 + 2(99-0,89 t 99. Новые длины путей равны t(Lj) = t(L2) = 89, t(L3) = t(L4) = 50, tKp = 89. [c.40]
Продолжительность работы (6,7 можно уменьшить не более чем на 5 дней. Действительно, At = min b67 - а67, Tkp - Т2 = min 5, 89 - 50 = 5. На эту величину уменьшатся длины критических путей t(Lj) и t(L2), a следовательно, и срок выполнения проекта. При этом стоимость работы (6, 7) возрастет на 5 -5 = 25 усл. единиц, а для всего проекта она увеличится с 320 до 345 усл.ед. Согласно (3.15), получаем (t) = 320 + 5(89 -0,84 t 89. [c.40]
Стоимость работы (О, 1) и всего проекта возрастет на 6-10 = 60 единиц, С01 = 35 + 60 = 95. Новые значения стоимости проекта и длин критических путей С = 345 + 6-10 = 405, t(Lj) = t(L2) = 74. [c.40]
Согласно (3.15) получаем (i) = 405 + 8(74 - 0,69 t 74. Стоимость работы (1, 3) и всего проекта возрастет на 8-5 =40 единиц, С13 = Ю + 40 = 50. Новое значение С = 405 + 8-5 = 445, t(L2) = t(L2) = 69. [c.41]
Согласно (3.15) получаем (t) = 445 + 9(69 - 0,64 t 69. Стоимость работы (7, 8) и всего проекта возрастет на 9 -5 = 45 единиц, С78 = 20 + 45 = 65. Новое значение С = 445 + 9-5 = 490, t(Lj) =t(L2) = 64. [c.41]
Стоимость работы (4, 6) возрастет на 4-5 = 20, а работы (5, 6) на 4-5 = 20 единиц С46 = 40 + 20 = 60, С56 = 30 + 20 = 50. Новые значения С = 490 + 8-5 = = 530, t(L2) = t(L2) = 59. [c.41]

Вернуться к основной статье