Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

УСТОЙЧИВОСТЬ РЕШЕНИЙ В ЗАДАЧЕ ОПТИМИЗАЦИИ ИНВЕСТИЦИОННОЙ ФАЗЫ ПРОЕКТА

АЛГОРИТМ ПОЛУЧЕНИЯ ОБЛАСТЕЙ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РЕШЕНИЙ

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

Рассмотрим возможные подходы к анализу данной ситуации.

Пусть длительность каждого этапа / (/ = 1,..., п) проекта может принимать любое значение t из интервала [/', /2]. Поскольку задача планирования выполнения проекта является общей задачей теории расписаний, анализ влияния на оптимальный план (расписание) выполнения проекта изменения значений исходных параметров выполняется в рамках исследования устойчивости задачи. Далее этапы проекта будем называть работами.

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

Пусть имеется множество работ d{, ..., dn, последовательность выполнения которых задана ациклическим орграфом G, у которого отсутствуют транзитивные дуги, поэтому каждой работе d{ может быть поставлено в соответствие множество работ R. — {dR}, в которое входят те и только те работы, которые должны быть выполнены прежде, чем может быть начата работа dr

Каждая работа характеризуется интервалом длительности выполнения [tj, Г2]. Продолжительность работы dj может быть любым числом из интервала [tj, /2].

Ресурсы, необходимые для выполнения работы dp задаются вектором — (ап,ajm), где а~ — количество ресурсов/, необходимых для выполнения работы / (/= 1,..., nj= 1,..., т).

Общий объем ресурсов, который может привлекаться к выполнению работ, задается вектором b = {,..., Ьт).

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

Выполнение работ происходит по допустимому расписанию, которое определяется следующим образом.

Допустимым расписанием выполнения работ dv ..., d назовем набор множеств работ X,, ..., Хк и набор интервалов времени [т}, х] , ..., [ip т*] длиной Гр ..., Тк соответственно такие, что в интервале времени [т'р т^] выполняются работы только из множества X (/ = 1, ..., к; к < п). При этом должны соблюдаться следующие ограничения:

  • 1) к работе dt можно приступить только в том случае, если выполнены все работы множества Rj (отметим, что последовательность выполнения работ может быть задана также матрицей R размерности п х п);
  • 2) общий объем используемых ресурсов в каждый момент времени интервалов [ij, т^] не должен превышать значения b. (j = 1,..., m)
  • 3) все работы d{ (1, ..., п) должны непрерывно выполняться в течение времени Г, где /. — продолжительность работы dr

Задача составления оптимального расписания заключается в том,

чтобы для каждого вектора длительности работ

найти расписание минимальной длины. Обозначим через Р

я-мерный параллелепипед . Тогда задача отыскания

минимального по длительности расписания для каждого t е Р (t = (tр ..., tn)) может быть сформулирована следующим образом.

Для каждого t е Р найти минимум функционала при ограничениях:

Если , то

для всех d е Rp и, кроме того,

где 7) — величина интервала времени [т',, т^]-

Здесь t е P(t = (tv ..., t)) задает длительность работ, для которых находится оптимальное расписание, а X/ и с принимают следующие значения:

Прежде чем перейти к описанию метода решения поставленной задачи, докажем вспомогательное утверждение. Зафиксируем какой- либо вектор t е Р, задающий длительность выполнения работ.

Среди всех допустимых расписаний задачи (8.1)—(8.5) рассмотрим те, которые могут быть получены по следующей схеме. При первом назначении работ на выполнение выделим все подмножества работ, которые могут выполняться на интервале [т}, т^], не нарушая ресурсных ограничений и ограничений на последовательность работ. Пусть векторы Х,..., соответствуют этим подмножествам работ так, что

Введем отношение частичного порядка на множестве векторов ,..., XБудем считать, что X1 > Xj, если Xj > X}f (i = 1,..., п).

Заданное отношение частичного порядка разбивает множество

векторов {Х, ..., Х^} на классы, в каждом из которых существует

максимальный элемент. Оставим среди множества векторов {Х,...,

X1} только максимальные элементы и выберем какой-либо из них, к1 ,

допустим Хр. Среди работ, соответствующих ненулевым координатам вектора Хр, выберем такую работу d , у которой время выполнения минимально. Положим Т{ = t и будем считать, что работа d выполнена. После этого перейдем к построению сово- купности векторов {,..., Хк }, соответствующих множеству работ, готовых к выполнению после завершения работы d .

Выбирая один из максимальных элементов, находим минимальную по продолжительности работу d с учетом ее возможного выполнения на предьщущем шаге. Будем считать Т2 = t' , где

t'=tn, еслиХ2пп = 0, и t' =t-tn, еслиX2 = 1.

Рг Pi РРг Р2 Pi Р PPi

Через к(к<п) шагов получим некоторое допустимое расписание задачи (8.1)—(8.5). Рассмотрев все возможные варианты выбора максимальных элементов на всех этапах построения допустимого расписания, получим множество допустимых расписаний, которое назовем базовым множеством расписаний.

Каждое базовое расписание может быть представлено следующим образом. Сопоставим каждому вектору Хг задающему множество выполняемых работ на интервале [т'1? т^], номер ЛГ самой короткой работы среди работ, соответствующих ненулевым координатам вектора Хр учитывая при этом время выполнения этих работ на интервалах [xj, т^],[x'j-1, х^-1]. Получим, что множество векторов Xj и номеров /V. (/ = 1,..., к) однозначно определяет допустимое базовое расписание.

Значение функционала (8.1) рассчитывается по формуле

где t'N продолжительность работы dN с учетом ее возможного выполнения на этапах 1,...,/— 1.

Если в задаче (8.1)—(8.5) интервалы времени [tj, t2] таковы, что t} = t2 для всех /= 1,...,«, то получена задача оптимального распределения ресурсов с фиксированным временем выполнения работ. В силу построения среди базовых расписаний будет хотя бы одно расписание минимальной длины.

Докажем следующее утверждение.

Лемма 8Л. Длина оптимального расписания задачи (8.1)—(8.5) при фиксированном времени выполнения работ может быть представлена как

Доказательство. Пусть Ху..., Хк векторы оптимального расписания. Построим разбиение всех работ на к классов ..., Lk следующим образом: е ?у., если^. = 1 (/ = 1,..., к). Сопоставим оптимальному расписанию орграф G, заданный следующим образом:

  • • если dt е Lv то = 0 (/ = 1,..., п);
  • • если dt еХ^и для d{ еще не построено R., то проверяем, существует ли ку

В случае если (8.6) выполняется, то в множество Щ войдет работа dN , где N_j — номер кратчайшей работы для вектора Х^_у Если р - 1 = 1, то в Rj войдет только работа dN , в противном случае в Rf войдут еще и все работы множества RN . В построенный орграф, учитывающий ресурсные ограничения, будет входить исходное множество работ d{, ..., dn, и длина критического пути будет равна продолжительности соответствующего базового расписания. Лемма доказана.

Рассмотрим свойства допустимых расписаний задачи (8.1)—(8.5) для случая, когда время выполнения работ dj заключено в интервалах [t),tf] (/ = 1,...,«).

Выберем какую-либо точку t е Р и построим для нее систему базовых расписаний у ..., AN}. Пусть Ак. — одно из базовых расписаний, которому соответствует набор векторов к ,...,Хк J и набор номеров работ jjVf ,..., Nk}. Отметим, что для работы dkN^ выполняется одно из условий:

где min 1 — номер работы с минимальной левой границей.

Выберем все остальные работы:

Включим в множество Мх те работы, которые удовлетворяют условию (8.7), и работу Нетрудно видеть, что для всякого /е^кратчайшими среди работ, соответствующих ненулевым координатам вектора Х, могут быть только те работы, которые принадлежат множеству Му

Выберем какую-либо работу dk е М{ и «назначим» ее самой короткой работой. Тогда очевидно, что длительность остальных работ должна быть такой, что tj > tk для всех dt е Мх (1 < / < п). Поэтому преобразуем tj по формуле

С другой стороны, понятно, что если dk кратчайшая работа, то tk не может быть больше любого из t? (di е Мх)

После того как работа dk будет выполнена, интервалы, задающие длительность работ dp для которых Xxj ф 0, будут удовлетворять следующим условиям:

Будем считать tj и tf равными правым частям в выражениях (8.10) и (8.11). Сформируем далее множество максимальных векторов,, характеризующих возможность выполнения остальных работ орграфа G после того, как завершена работа dk, и выберем один из них: Х2к. Затем аналогично тому, как это было сделано ранее, формируем множество кратчайших работ М2, назначаем кратчайшую работу и преобразовываем интервалы [tj, tf ] (/: Х2[ф 0). Когда все работы будут выполнены, получим допустимое решение для всех точек t е Р, удовлетворяющих системе неравенств:

где X1 вектор (Х! = {0, 1}, / = 1, у которого ненулевые координаты соответствуют работам, выполняемым после завершения (/- 1)-й работы.

При этом

Здесь тI — число интервалов, предшествующих интервалу [ip tJ, на которых выполнялась работа dk или dr, к{ номер кратчайшей работы, выполняемой на интервале /(/

Рассмотрев все возможные варианты назначения кратчайших работ из множества А/,,..., Мп при фиксированном способе выбора максимальных векторов, получим такое множество базовых расписаний, что каждое из расписаний остается допустимым для всех точек многогранника, полученного из исходного параллелепипеда добавлением системы ограничений (8.12). Этот результат можно сформулировать в виде леммы.

Лемма 8.2. Пусть необходимо выполнить работы, последовательность которых задана орграфом G и длительность dj может изменяться в интервалах [t},tf,i= 1,...» п. Тогда существует конечный набор базовых расписаний {Av ..., AN} и разбиение параллелепипеда Рсистемой гиперплоскостей на многогранники В{, ..., BN такое, что:

1)

2) для любого многогранника В. существует такое базовое расписание А; с= {Ар ..., An), что оно остается допустимым для всех точек t е 2?..

Непосредственно используя лемму 8.2, можно доказать следующую теорему.

Теорема 8.1. Для любого орграфа G, задающего последовательность выполнения работ, и любого параллелепипеда Р продолжительностей работ задачи (8.1)—(8.5) существует множество гиперплоскостей, проходящих через начало координат и разбивающих параллелепипед Р на конечное число многогранников, и множество таких допустимых расписаний {Av ..., AN}, что каждому многограннику В. (/ = 1,..., N) взаимно однозначно соответствует некоторое допустимое расписание Ai с: {Av ..., Ам), которое остается оптимальным для всех точек многогранника 2?..

Доказательство. Как было показано ранее, при фиксированном времени выполнения работ для каждого базового расписания можно построить такой орграф G' из работ исходного орграфа G, что длина базового расписания будет равна длине критического пути орграфа G. Построим для базового расписания Ai соответствующий орграф G., отображающий последовательность выполнения работ по расписанию Аг Пусть D‘,..., DlN — все пути орграфа G’, соответствующего базовому расписанию Аг Тогда среди путей ..., D‘n существует по крайней мере один критический путь такой, что для точки t е Bj длина расписания А. равна ^ tj.

jeD'k

Интервал изменения длины пути Dlk, а значит, и интервал изменения длины расписания [Г1, Т?] могут быть оценены, если будут вычислены максимум и минимум функционала

при ограничениях:

где t = (/р ..., tn); с1 матрица ограничений размерности к х п;

v=t).

Неравенства (8.14), (8.15) задают многогранник Вг

Пусть [Т}, Т2] (/ = 1,..., N) — верхнее и нижнее значения соответствующего базового расписания А{ на многограннике Вг Определим для заданного разбиения величины Tj. и Т2. по формулам:

Рассмотрев все возможные разбиения параллелепипеда Р на систему многогранников {Bv ..., BN.}, / = 1,Ь2, где Ь2 количество разбиений при всех возможных вариантах выбора максимальных векторов на всех этапах построения допустимого расписания, получим возможность попарно сравнивать значения расписаний на общей части многогранников Вг На каждом шаге / (1 < / < п) построения допустимого базового расписания при новом разбиении параллелепипеда Р можем оценить снизу значение этого расписания.

Пусть Dk все пути орграфа G, задающего последовательность выполнения работ. Вычислим минимум следующего выражения:

при ограничениях:

где D'j — невыполненные работы пути Dr,

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

Ограничения (8.16) задают построенный многогранник при составлении базового расписания.

Обозначим. Если окажется, что , где

t} — нижняя оценка на этапах 11, то прекращаем дальнейшее построение допустимого расписания, так как оно заведомо хуже составленного ранее.

После того как построено очередное разбиение, на пересечении многогранников можно оценить длину нового допустимого расписания и составленного ранее, при этом возможны следующие случаи:

  • 1) интервалы длительности допустимых расписаний не пересекаются;
  • 2) интервалы длительности пересекаются.

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

Во втором случае проводится дополнительная разделяющая гиперплоскость вида

где в левой части равенства (8.17) стоит сумма длительностей работ соответствующего критического пути для нового, ав правой части — для старого, ранее полученного допустимого расписания. Таким образом, мы разделили гиперплоскостью (8.17) общую часть многогранников для решения Ан и Лст на два многогранника и поставили каждому из них в соответствие решения Лн и Аст.

После того как будут выбраны все возможные максимальные векторы при построении допустимых расписаний, получим такое разбиение параллелепипеда Р на многогранники Bv ..., BN , что каждому многограннику В. будет поставлено в соответствие расписание Ар которое является наилучшим среди базовых допустимых расписаний для всех t е Вр и поэтому оно будет оптимальным для этих точек.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>