Оптимизация структуры стохастического графа c переменной интенсивностью выполнения работ (стр. 5 из 6)
. Теорема1 Для того чтобы продолжительность выполнения всех работ многопроектной разработки с учетом ресурсов равнялась бы продолжительности критического пути, необходимо и достаточно, чтобы между работами ресурсного графа были установлены связи по ресурсам при соблюдении технологических условий предшествования работ в качестве ограничений.
Доказательство теоремы дается в предпололожении, что чило ресурсов для каждой работы фиксировано.
. Достаточность.Пусть продолжительность критического пути ресурсного графа равна продолжительности выполнения всех работ с.учетом ресурсов. Предположим, что при этом между работами ресурсного графа не установлены связи по ресурсам. В таком случае не для всех цепочек работ, образуемых ресурсными связями, гарантировано 
Найдется хотя бы одна такая цепочка, для которой 
что противоречит предположению.
. Необходимость. Пусть между работами ресурсного графа установлены связи по ресурсам. Продолжительность самого длинного пути L, который назван критическим, определит продолжительность выполнения всех работ многопроектной разработки.
Получение экстремального графа алгоритмом, включающим пункты 
, следует из теоремы 2, где под математическим построением сетевой модели будем понимать нахождение графа согласно критерию (1) в области, определяемой ограничениями (2) 
(5).
Теорема 2. Если все функции 
, n2, . . . , 
), 
вогнуты и аддитивны, то математическое построение сетевой модели многопроектной разработки обеспечивает получение экстремального графа.
Cостояние системы меняется в моменты времени 
2, . . . , что соответствует времени обеспечения работ ресурсами. Причем при распределении участвуют все ресурсы, выделенные на выполнение многопроектной разработки, и все работы, свободные в данный момент времени от технологических условий. Для всех значений к, 
состояние системы
постоянно. Распределение ресурсов среди работ множества 
2, . . . , осуществляется по одной и той же схеме, включающей пункты алгоритма 1 
для всех 
и для всех 
2, . . . , В свете сказанного необходимо доказать, что переменные ni , Zj обеспечивают максимальное значение функции (1) при фиксированных значениях i, 
. Зафиксируем значения i, , приняв i=1, 
. Не теряя общности рассуждений, доказательство теоремы проведем для случая, когда число работ множества A2, выполняемых 1-м видом ресурсов, равно 2. Для общего случая теорема доказана в работе [19] .Пронумеруем работы множества А2 . функция (1) примет вид (52)
(52) 
Пусть в соответствии с условием теоремы
(53) 
.
(54) 
Рассмотрим матрицу (55).
(55) 
Физически 
означает приращение функции (52) за счет того, что на выполнение работы множества А1 дополнительно назначается одна единица ресурса при условии, что на эту же самую работу уже было назначено 
единиц ресурсов.
В силу вогнутости функций 
справедливы соотношения (56).
(56) 
С вводом элементов матрицы (55) функция (52) примет вид (57).
(57) 
Это следует из (53), если представить
(58) 
Преобразуем матрицу 
в вектор-строку 
p=1, 2, . . ., b1 так, чтобы элементы вектора образовали вариационный ряд по невозрастанию.
(59) 
Элементы ряда (59) обладают тем важным свойством, вытекающим из (56), что если 
, то найдется такое 
, для которого 
. Это свойство имеет место только для вогнутых функций и позволяет предложить конструктивный метод решения задачи. Составим сумму первых J элементов вектора 
(60) 
.
В силу отмеченного выше свойства (59) очевидно, что
(61) 
Значение 
определяется числом наибольших элементов столбца с номером 
матрицы 
, попавших в последовательность 
.
Таким образом, при распределении ресурсов последовательно двигаясь по наибольшим приращениям функции (52) мы на каждом шаге получаем оптимальный план.
Ресурсы на работу , 
1, 2 переходят с работ множества 
согласно критерию (52), что обеспечивает получение оптимальной структуры графа. При J=b1 получаем оптимальное распределение всех ресурсов. В свете сказанного граф (1) является экстремальным.
Список литературы
1 . Х. Ахьюджа. Cетевые методы управления в проектировании и производстве. М.: Наука, 1979.
2. Cборник III-го Bcесоюзного симпозиума по проблемам планирования и управления научными исследованиями и разработками. М.: ЦЭМИ. 1975.
3. Применение пакетов прикладных программ по экономико - математическим методам в АСУ. М.: Статистика, 1980.
4 Глушков В. М. , Михалевич В. C. и др. Управляющий этап // Управляющие системы и машины. Киев: Ин-т кибернетики АН УССР, 1989. N3. С. 5-7.
5. Основные положения по разработке и применению систем сетевого планирования и управления. М. , Экономика. 1974.
6. Костина Л. П. Причины парадоксов при распределении ресурсов на сетях в книге Х. Ахьюджа ? Сетевые методы управления в проектировании и производстве¦ (под ред. В.В Калашникова. М. , 638 c). Деп. организацией п / а А - 1420 МРС
?ТТЭ¦. Сер.0. Вып. 18, Д05134 от 5 августа 1982 г.
7. Fersko-Weis H. Projekt management software // PC Magazine. 1988. November 15. p. 178-226.
8. Fersko-Weis H. High-end proekt managers make the plans // PC magazine 1989 May 16 p. 155-195.
9. С. В. Кохова. Некоторые динамические задачи распределения ресурсов на сетевых графиках с переменными объемами работ // Вестник Московского университета.
сер.15. Вычислительная математика и кибернетика. 1991. N1. C. 48-57.
10. Kouveles P., Lee H.L. Block angular structures and the loading problem in flexible manufakcturing systems // Oper. Res. 1991.V.39. N4. P. 666- 676.
11. Rogers V.R. White K. P. Algebraic, Mathematical Programming, and Notwork Models of the Deterministig Job-shop Scheduling Problem //IEEE Trans. on Systems, Man, and Cybernetics.1991.V. 21. N3. P.693-697.
12. В. И. Левин. Оптимизация расписаний в системах с неопределенными временами обработки // Автоматика и телемеханика. 1995. N2. C. 99-110.
13. В.Н.Калачев, Б. В. Немчинов, В.Е. Кривоножко. Зфдачи планирования в гибких производственных системах // Автоматика и телемеханика. 1995. N6. C. 155-164.
14. П. И. Шарыгин. Оценки приближенного решения одной задачи календарного планирования // Дискретный анализ и исследование операций. Новосибирск: Ин-т математики СО РАН, 1995, т. 2. N1, 57-67.