|
75 есть их степень захода больше I. Разделим произвольным образом затраты ф,(х)) на kj частей, где kj число заходящих дуг. Фактически мы как бы разделили вершину i на kj висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема. Теорема 2.3.1. Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий вид. Если в вершину, соответствующую переменной х,к заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи. Пример 2.3.1. Рассмотрим сеть рис. 2.3.1, 2.3.2. На рис. 2.3.6 приведено решение задачи. При этом затраты фг(х2) разделены на две части, поскольку переменная Х2 используется и при вычислении и при вычислении Гг. В данном случае общие затраты, равные 8, 12 и 20 при значениях переменной Х2равной 1,2 и 3, соответственно, поделены пополам. |
Xj, меньше на 2. За конечное число таких преобразований получим структуру с длиной цепи между этими вершинами либо 2 (тогда задача решена), либо 3 (тогда применяем преобразование, показанное на рис. 1.4.1в). Таким образом, имея одно представление, мы можем получить эквивалентное представление любой структуры. Таким образом, из дихотомического представления функции <р(х) мы можем получить дихотомическое представление этой же функции, но с такой же структурой, какую имеет дихотомическое представление функции f(x). Одинаковая структура дихотомического представления функции <р(х) и fl:x) позволяет применять метод дихотомического программирования. Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным Xj, i = 1,п. Рассмотрим множество конечных вершин, которые не являются висячими, то есть их степень захода больше 1. Разделим произвольным образом затраты ф,(х[) на к; частей, где к — число заходящих дуг. Фактически мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема. Теорема 1.4.3.[6%] Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. 1.5. Существующие методы построения комплексной оценки организациопно-технологнчсскнх решений Оценка организационно-технологических решений (ОТР) строительства любого объекта является важной составляющей всего комплекса задач теории принятия решений в строительстве. В современных экономических условиях часто оказывается недостаточным только личный опыт лица, принимающего решение. Недооценка каких-либо факторов на уровне организационнотехнологического проектирования может вызвать огромные затраты, выходящие 55 |