|
nt г г /=/ !=i m n (3-6.2) Ы1 j l 96 Y , ^ y = l. i = l, m J=‘ Здесь Т д —директивное значение продолжительнос1’и. Задачи (3.6.1) и (3.6.2) относится к классу задач ком бинаторного программирования. Для и х решения применим ы метод ветвей и границ, метод динамического программирования, метод д ихотом ического программирования. Рассмотрим решение поставленной задачи на основе теории графов. Предположим, что сущ ествующ ее значение продолжительности последовательно выполняемых работ оценивается величиной равной X q , и поставлена задача снижения общей продолжительности выполнения работ до величины X™. Очевидно, что это возможно различны м и способами. Будем о’ф аж ать все возможные варианты перехода системы из одного состояния в другое с пом ощ ью фафа, то есть составим сетевую модель данного процесса. П ри этом сеть будет состоять из начальной верш ины Хо, конечной верш ины Х „ характеризую щ их начальное и конечное состояния системы и т 1 слоев, каж ды й из ко торых содержит п верш ин, характеризую щ их возможны е значения сокращ ения продолжительности выполнения работ. Каждая верш ина сетевой модели (i, j ) будет описывать изменение общей продолжительности выполнения работ в том случае, если выбран j -ы й конкретны й вариант производства работ. В озм ож ны е переходы системы из одного состояния в другое будут отражаться дугам и сетевой модели. П ри построений сетевой модели должно быть обеспечено то, что общая продолжительность сф оительства должна быть сокращ ена не менее, чем на заданную величину. П ри этом любой путь по сетевому граф ику, соединяю щ ий начальную верш ину с конечной, определяет некоторы й вариант производства работ на |
условии достижения приемлемых значений по критерию продолжительности определяемых договорными условиями. В этом случае возникает несколько постановок оптимизационных задач. Дадим их форм&чьное описание. Для этой цели введем двоичную переменную xip которая определяется следующим образом: х(/ = 1, в том случае, если для i-ro объекта прият j-ый вариант содержания и ноль в противном случае. Затраты на реализацию j-ro варианта выполнения i-ому объекту обозначим через S-,j. Тогда возможно сформулировать следующие задачи: Задача 1. При заданном уровне затрат получить варианты выполнения работ на каждом объекте обеспечивающие минимальную продолжительность строительства. Формальная постановка задачи может быть записана в следующем виде Е Ё гл ->ш/н2>»=i > /«I.». (4.4.1) (-1 ] • I /=1 у 1 У=1 где В размер средств, имеющихся в распоряжении строительной организации на данные цели. Последнее ограничение в выражении (4.4.1) означает, что для каждого из объектов обязательно должен быть принят какой либо вариант выполнения работ. Задача 2. Определить варианты выполнения работ на каждом из объектов, при котором достигалось бы нормативное значение продолжительности выполнения и при этом обеспечивалось бы минимальное значение затрат. ± ± S fy -> m b . / = Ън (4.4.1) /-1 > 1 1-1 УI У-1 Здесь Тд нормативное значение продолжительности; // количество объектов; m количество вариантов выполнения работ. Задачи (4.4.1) и (4.4.2) относится к классу задач комбинаторного программирования. Для их решения применимы метод ветвей и границ, метод динамического программирования, метод дихотомического программирова мештую X/j, которая определяется следующим образом: х0= 1, в том случае, если для /-ой работы приято значение коэффициента совмещения из у-го множества и ноль в противном случае. Тогда возможно сформулировать следующие задачи: Задача 1. При заданном уровне затрат получить величину коэффициентов совмещения выполнения работ обеспечивающих максимальное сокращение продолжительности строительства. Формальная постановка задачи может быть записана в следующем виде т 1 я /п -1 л п ____________ Z И 1ч х ч ^ т а х > в > 1 ] х 9 = 1 > (4-6.i) /=1 )=\ ы ;=i !=\ где В размер средств, имеющихся в распоряжении строительной организации на данные цели. Последнее ограничение в выражении (4.6.1) означает, что для каждой работы обязательно должен быть принят какое либо значение коэффициента совмещения. Задача 2. Определить коэффициенты совмещения для каждой из выполняемых работ, при котором достигалось бы нормативное значение продолжительности выполнения и при этом обеспечивалось бы минимальное значение затрат. т-l н т-\ п п _________ Y L C4X4 ->т'т' Ё Ё ' Л 7’?’ / = (4.6.2) 1*1 /= I i* l у-1 Здесь Тд нормативное значение продолжительности. Задачи (4.6.1) и (4.6.2) относится к классу задач комбинаторного программирования. Для их решения применимы метод ветвей и границ, метод динамического программирования, метод дихотомического программирования. Рассмотрим решение поставленной задачи на основе теории графов. Предположим, что существующее значение продолжительности последовательно выполняемых работ оценивается величиной равной Хо, и постав лена задача организовать совмещенное выполнение работ с целью снижения общей продолжительности выполнения работ до величины Х,„. Очевидно, что это возможно различными способами. Будем отражать все возможные варианты перехода системы из одного состояния в другое с помощью графа, то есть составим сетевую модель данного процесса. При этом сеть будет состоять из начальной вершины Хо, конечной вершины Хт характеризующих начальное и конечное состояния системы и т -1 слоев, каждый из которых содержит п вершин, характеризующих возможные значения коэффициентов совмещения между каждой из работ. Каждая вершина сетевой модели (/, J) будет описывать изменение общей продолжительности выполнения работ в том случае, если коэффициент совмещения между работами i и i+1 принимает значение изу'-го множества и будет характеризоваться числом, дающим величину общего сокращения продолжительности выполнения работ. Возможные переходы системы из одного состояния в другое будут отражаться дугами сетевой модели. При построении сетевой модели должно быть обеспечено то, что общая продолжительность строительства должна быть сокращена не менее, чем на заданную величину. Пример такой сети для случая двух коэффициентов совмещения и четырехуровневой шкалы оценок степени совмещения выполняемых работ, то есть m = 3, Хт = 3 приведен на рис. 4.6.1. Рис. 4.6.1. Сетевая модель При этом любой путь по сетевому графику, соединяющий начальную |