Проверяемый текст
Крюков, Сергей Вениаминович; Оптимизационные модели и механизмы корпоративного управления (Диссертация, апрель 2005)
[стр. 49]

Пример.
Рассмотрим сеть, представленную на рис.

1.5.1 и 1.5.2.
На рис.
1.5.6 приведено решение соответствующей задачи.
Затраты ф2(х2) разделены на две части, поскольку переменная Х2 используется при вычислении функций и
{\9и р2.
Вданном случае общие затраты, равные 8, 12 и 20 при значениях переменной Х2, равных 1, 2 и 3, соответственно, поделены пополам.

49 /.
\°\гч СОN.
2У/ 2 7 2 / / 2 9 з X /Х37 2/ / и 1/ / \ 18 / 4 ) Х ^ 1/ / 9 / ® 1/ X * 8 2 У / 2 6 УУ / У2 1/ X 7 2 У / 9 3 X7 / \ 1 /о 3 28 2 20 1 16 3 Xх X 15 2 / / \ 9 3 / / 2 \ 3 / / 2 5 2 /X / о 1/ / и 1У/ 1 6 /4 1/ / 5 1 ~7 /о> 2 / / © 2У/ 1 5 Х\/ X Хг 1 / / 4 2 х 7^ X 6 3 / / ю /г \о\Н ГЛ 2У/ з / 4 3 / / 2 4 2 х 7 / 6 2 / / о > 2 X х / 1 3 3 х 7 / 2 0 1/ X 4 1 / /о> 1/ / 11 2 / / 8 * 2 / / Х1 1 / / 3 2 х 7 X 7 3 X х / 1 4 Рис.
1.5.6.
В каждой матрице кружками выделены клетки, соответствующие минимальным затратам на получение того или иного значения функций
$2 и йВ результате получены минимальные затраты ср(Го), требуемые для получения значений функции Го.
Если ^ “ 1, то ф (1 ) = 1 6 , если Го = 2 , то ф (2 ) = 2 0 , если 15)=3 , то ф (3 ) = 2 8 .
Рассмотрим случай ^ = 2.
Ему соответствует оптимальное решение модифицированной задачи: X] = 1,
Х21 = 2, х22= 2, хз = 1.
[стр. 92]

Общий случай Рассмотрим произвольное сетевое представление функции f(x), задаваемое сетью, выходом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным Xj, i = l,n .
Рассмотрим ^ множество конечных вершин, которые не являются висячими, т.е.
их степени захода больше 1.
Разделим произвольным образом затраты (pi(Xj) на ki частей, где kj число заходящих дуг.
Фактически мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат.
Далее применяем описанный выше алгоритм.
При этом каждый раз, когда встречается вершина со степенью захода больше 1, мы делим затраты на соответствующее число частей.
В результате применения алгоритма мы получим оптимальное решение для модифицированной сети.
Однако это решение может не быть решением исходной задачи.
Тем не менее, имеет место следующая Теорема.
Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи.
Доказательство.
Заметим, что множество решений модифицированной сети содержит все решения исходной задачи.
Эти решения имеют следующий # вид.
Если в вершину, соответствующую переменной xik, заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению.
Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи.
Пример.
Рассмотрим сеть, представленную на рис.

2.1 и 2.2.
На рис.
2.6 приведено решение соответствующей задачи.
Затраты ф2(х2) разделены на две части, поскольку переменная х2 используется при вычислении функций и
fj, и f2.
В данном случае общие затраты, равные 8, 12 и 20 при значениях переменной х2, равных 1, 2 и 3, соответственно, поделены пополам.

В каждой матрице кружками выделены клетки, соответствующие минимальным затратам на получение того или иного значения функций
f(>f2и fo.
В результате получены минимальные затраты (p(f0), требуемые для получения значений функции fo.
Если fo= 1, то ср(1) = 16, если fo = 2, то ф(2) = 20, если fo = 3 , T O ф(3) = 28.
Рассмотрим случай fo = 2.
Ему соответствует оптимальное решение модифицированной задачи: xi = 1,
x2i = 2, х22= 2, хз = 1.
Здесь x2i соответствует значению Х2 в левой нижней матрице, а х22—в правой нижней матрице.
Поскольку оба значения x2i = 2, х22= 2 вошли в опти92

[Back]