назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [ 98 ] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


98

оптимальным, обязательно будет больше чем номер предыдущего допустимого решения, бывшего оптимальным при меньшем уровне инфляции.

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

11.2. Задача оптимизации времени выполнения проекта

11.2.1. Постановка задачи и метод решения. При реализации подавляющего большинства инвестиционных проектов на фазе предынвестиционного ана-

Задача оптимизации времени выполнения проекта является NP-полной. Для решения задач этого класса применяются схемы направленного перебора, лиза для инвестора немаловажным к которым относится мод в-представляется такой показатель, как вей и границ, время его реализации.I=

Рассмотрим задачу оптимизации выполнения проекта, в которой при анализе плана реализации этапов проекта учитывают ресурсные ограничения. Пусть необходимо выполнить проект, состоящий из п этапов, технологическая последовательность выполнения которых задана ациклическим ориентированным графом G(m, п), где т - число дуг графа, п - число вершин. Для выполнения этапа i проекта ему должны быть выделены ресурсы нескладируемого вида в объеме а, = (а/1, Щщ), Прерывать выполнение этапа до его полного завершения нельзя.

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

Задан также общий объем упомянутых нескладируемых ресурсов всех видов, которые используются исполнителями проекта Ъ = {Ъх

Кроме того, известно время выполнения каждого из этапов /,(/=!,..., п). Выполнение каждого этапа i должно осуществляться непрерывно в



течение времени г,, при условии, что для его выполнения выделены ресурсы в объеме а, = (а, Л/т) и все этапы, предшествующие этапу / согласно ориентированному графу G(m, п\ уже выполнены. Необходимо выбрать такую последовательность выполнения всех этапов проекта, которая не нарушала бы технологических ограничений заданных графом G(w, п) и ограничений на объем используемых ресурсов в каждый момент времени t реализации проекта и была бы минимальной по продолжительности.

Данная задача принадлежит, как показано в [40], к классу ТР-полных задач, которые будут рассмотрены в последующей главе. Точными методами решения подобных дискретных оптимизационных задач является, в частности, метод ветвей и границ.

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

Шаг 1. Вычисление нижней оценки целевой функции задачи. Рассмотрим формулу для вьшисления нижней оценки для трех случаев. 1. Ресурсы, рассматриваемые в задаче, являются ресурсами типа станков или приборов, и для вьшолнения одного этапа необходим один станок. Всего станков М Тогда нижняя оценка вычисляется по следующей формуле:

Г„ =тах

(11.13)

где Step- длина критического пути графа G(m, п). Суть нижней оценки состоит в том, что время вьшолнения проекта, с одной стороны, не может бьггь меньше чем продолжительность критического пути, так как все этапы, входящие в этот путь, должны выполняться последовательно и не допускают вьшолнения двух различных этапов в один и тот же момент времени, а с другой - продолжительностью такого плана реализации проекта, когда все станки (приборы) непрерывно работают в течение всего времени реализации проекта, т.е. плана,

продолжительность которого -.

2, В этом случае для вьшолнения каждого этапа необходимо (зД1 а, < АО единиц ресурсов (оборудования, транспортных единиц, обслужи-302



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

(11.14)

3. в общем случае, т.е. когда л, = (лл, Щт), нижняя оценка может быть вычислена таким образом:

Г„ =тах

/•,Sp,max

y=l,w bj

(11.15)

Шаг 2. Вычисление верхней оценки осуществляется путем построения какого либо допустимого плана реализации проекта, и продолжительность этого плана выбирается в качестве верхней оценки Те.

Если выполняется равенство Г„ = Г, то решение задачи получено и им будет тот план, который соответствует оценке Те. В противном случае переходим к шагу 3.

Шаг 3. Выполнение шага 3 заключается в построении очередного допустимого плана выполнения проекта, в процессе которого после завершения очередного этапа проекта вычисляется нижняя текущая оценка

Тн{т) по следующей формуле:

7;"(r) = r + max

l=\,k

(11.16)

к-число путей в графе G(w, п)\

т- момент завершения какого либо из этапов проекта;

tf - продолжительность этапа / с учетом его частичного или полного выполнения к моменту времени г (в последнем случае полагаем tj = О); Sj - продолжительность пути S/k моменту времени г с учетом полного или частичного выполнения этапов, входящих в путь S/.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [ 98 ] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]