Хозяйственно-питьевой водопровод соединяет источник I со стоком S

Хозяйственно-питьевой водопровод соединяет источник I со стоком S. Имеется несколько путей, по которым можно доставлять воду из источника в сток. Вершины сети соответствуют пересечениям труб, а ребра и дуги – участкам труб между пересечениями. На сети указаны пропускные способности труб, т.е. максимальное количество воды в м3, которое можно пропустить по трубам за 1 ч. Также сформирован начальный поток с мощностью Z0 (м3/ч). Какой поток воды максимальной мощности можно пропустить по данному трубопроводу?
Требуется:
посчитать мощность начального потока воды;
построить на сети поток воды максимальной мощности, направленный из источника I к стоку S;
указать «узкое место» сети и найти его пропускную способность;
провести анализ результатов решения.
Решение:
1) Вершины 4,5 соединены ребром, поэтому надо заменить его на две противоположно ориентированные дуги u45 и u54 с одинаковой пропускной способностью d45 = d54 = 4 (м3/ч) (рис. 1)
1
2
3
4
6
5
I
S
14,5
6,2
9,2
6,3
5,2
12,4
6,6
3,1
4,0
4,0
Рис. 1
В сети имеется допустимый поток:
QUOTE (м3/ч)
2) Источник I получает метку (+), соседние непомеченные вершины 2 и 3. Присваиваем вершине 2 метку (1+), так как u12 прямая дуга и x12 < d12 (5<14). Присваиваем вершине 3 метку (1+), так как u13 прямая дуга и x13 < d13 (4<12).
Просматриваем соседние непомеченные вершины радом с вершиной 2. Это вершины 4 и 5. Присваиваем 4 метку (2+), так как u24 прямая дуга и x24 < d24 (3<6). Присваиваем 5 метку (2+), так как u25 прямая дуга и x25 < d25 (2<6).
Просматриваем соседние непомеченные вершины рядом с вершиной 4. Это вершины 6. Ставим метку вершине 6 (4+).
Получается путь от I до S:
Р1: 1-2-4-6
Выписываем множество прямых и обратных дуг.
Р+={u12; u24; u46} прямые дуги. Обратные дуги в увеличивающий путь не входят.
ɛ1=min(dij – xij)=min{(d12 – x12); (d24 – x24); (d46 – x46)}=min{14-5; 6-3; 3-1}=2.
Так как обратных дуг нет, то ɛ2 не рассматриваем.
Вдоль дуг увеличивающего пути изменяем поток на ɛ1 = 2 и получаем новый поток z1=z0+ɛ=5+2=7(м3/ч):
х12=5+2=7
х24=3+2=5
х46=1+2=3
Остальные остаются без изменений, так как не входят в увеличивающий путь Р1 (рис.2).
1
2
3
4
6
5
I
S
14,7
6,2
9,2
6,5
5,2
12,4
6,6
3,3
4,0
4,0
Рис.2
Источник I получает метку (+), соседние непомеченные вершины 2 и 3. Присваиваем вершине 2 метку (1+), так как u12 прямая дуга и x12 < d12 (7<14). Присваиваем вершине 3 метку (1+), так как u13 прямая дуга и x13 < d13 (4<12).
Просматриваем соседние непомеченные вершины радом с вершиной 2. Это вершины 4 и 5. Присваиваем 4 метку (2+), так как u24 прямая дуга и x24 < d24 (5<6). Присваиваем 5 метку (2+), так как u25 прямая дуга и x25 < d25 (2<6).
Просматриваем соседние непомеченные вершины рядом с вершиной 4. Это вершина 6. Вершине 6 нельзя поставить метку (3+), так как x36= d36=6.
Рассмотрим вершину 5. Непомеченная вершина рядом с 5 – это вершина 6 (сток). Ставим метку (5+) вершине 6, так как u56 прямая дуга и x56 < d56 (2<9).
Получается путь от I до S:
Р2: 1-2-5-6
Выписываем множество прямых и обратных дуг.
Р+={u12; u25; u56} прямые дуги. Обратные дуги в увеличивающий путь не входят.
ɛ1=min(dij – xij)=min{(d12 – x12); (d25 – x25); (d56 – x56)}=min{14-7; 6-2; 9-2}=4.
Так как обратных дуг нет, то ɛ2 не рассматриваем.
Вдоль дуг увеличивающего пути изменяем поток на ɛ1 = 4 и получаем новый поток z2=z1+ɛ=7+4=11 (м3/ч):
х12=7+4=11
х25=2+4=6
х56=2+4=6
Остальные остаются без изменений, так как не входят в увеличивающий путь Р2 (рис.3).
1
2
3
4
6
5
I
S
14,11
6,6
9,6
6,5
5,2
12,4
6,6
3,3
4,0
4,0
Рис. 3
Источник I получает метку (+), соседние непомеченные вершины 2 и 3. Присваиваем вершине 2 метку (1+), так как u12 прямая дуга и x12 < d12 (7<14). Присваиваем вершине 3 метку (1+), так как u13 прямая дуга и x13 < d13 (4<12).
Просматриваем соседние непомеченные вершины радом с вершиной 2. Это вершины 4 и 5. Присваиваем 4 метку (2+), так как u24 прямая дуга и x24 < d24 (5<6). Вершине 5 нельзя поставить метку (2+), так как x25= d25=6. Просматриваем соседние непомеченные вершины радом с вершиной 4. Это вершина 5 и 6. Вершине 6 нельзя поставить метку (4+), так как x46= d46=3. Вершина 5 обратная метку не ставим.
Просматриваем соседние непомеченные вершины радом с вершиной 3. Это вершина 6. Вершине 6 нельзя поставить метку (3+), так как x36= d36=6.
Так как мы не можем пометить сток S, то увеличивающегося пути нет и поток в сети является максимальным: zmax = z1 = 11 (м3/ч).
3) Проведем анализ сети. Проверим условие сохранения потока на примере 2-й вершины. Известно, что в промежуточных вершинах пути потоки не создаются и не исчезают, т.е.
∑xi2-∑x2j=0
x12-(x24+x25)=11-5-6=0 (м3/ч).
Минимальный разрез (R, R’) является «узким местом» сети. Найдем его пропускную способность:
C(R, R’) = ∑dij=d13+d24+d43=5+2+4=11(м3/ч).
что совпадает с величиной максимального потока воды в водопроводе.
Общее количество воды, вытекающей из источника I, совпадает с общим количеством воды, поступающей в сток S
-∑xiI+∑xIj=∑xis+∑xsj=zmax
-0+(5+4+2)=6-4+3+6=11(м3/ч).
4. Динамическое программирование
x g1 g2 g3 g4
0 0 0 0 0
1 0.21 0.26 0.19 0.17
2 0.4 0.38 0.41 0.43
3 0.58 0.61 0.61 0.63
4 0.81 0.76 0.79 0.77
5 0.98 0.99 1.03 0.96
Пусть Ck – переменная состояния (средства, выделенные на инвестирование предприятий с k-го по 4-ое), xk – переменная управления (средства, выделенные на инвестирование k-го предприятия).
Функция Беллмана для данной задачи имеет вид
Первый шаг. k = 4, C4 – средства, выделенные на инвестирование четвертого предприятия, x4 – средства, выделенные на инвестирование четвертого предприятия.
Рассмотрим возможности инвестирования четвертого предприятия. Составим вспомогательную таблицу, используя функцию Беллмана:
F4(C4) = g4(x4), x4 = C4.
Таблица 1
C4 x4 F4(C4) x4*
0 1 2 3 4 5
0 0
0 0
1
0,17
0.17 1
2
0,43
0.43 2
3
0,63
0.63 3
4
0,77
0.77 4
5
0,96 0.96 5
Второй шаг. k = 3, C3 – средства, выделенные на инвестирование третьего и четвѐртого предприятий, x3 – средства, выделенные на инвестирование третьего предприятия.
Рассмотрим возможности инвестирования третьего предприятия. Для получения максимума прибыли F3(C3) воспользуемся рекуррентным соотношением:
Составим вспомогательную таблицу 2
Таблица 2
C3 x3 F3(C3) x3*
0 1 2 3 4 5
g3(0)+
F4(C3-0) g3(1)+
F4(C3-1) g3(2)+
F4(C3-2) g3(3)+
F4(C3-3) g3(4)+
F4(C3-4) g3(5)+
F4(C3-5)
0 0+0=0            0 0
1 0+0,17=0,17  0,19+0=0,19         0,19 1
2 0+0,43=0,43 0,19+0,17= 0,36 0,41+0=0,41       0,43 0
3  0+0,63=0,63  0,19+0,43=0,62  0,41+0,17=0,58 0,62+0=0,62     0,63 0
4  0+0,77=0,77  0,19+0,63=0,82  0,41+0,43=0,84  0,62+0,17=0,79 0,79+0=0,79   0,84 2
5  0+0,96=0,96  0,19+0,77=0,96  0,41+0,63=1,04  0,62+0,43=1,05  0,79+0,17=0,96 1,03+0=1,03 1,05 3
Третий шаг. k = 2, C2 – средства, выделенные на инвестирование второго, третьего и четвѐртого предприятия, x2 – средства, выделенные на инвестирование второго предприятия.
Рассмотрим возможности инвестирования второго предприятия.
Для получения максимума прибыли F2(C2) воспользуемся рекуррентным соотношением
Составим вспомогательную таблицу 3
Таблица 3
C2 x2 F2(C2) x2*
0 1 2 3 4 5
g2(0)+
F3(C3-0) g2(1)+
F3(C3-1) g2(2)+
F3(C3-2) g2(3)+
F3(C3-3) g2(4)+
F3(C3-4) g2(5)+
F3(C3-5)
0 0+0=0
0 0
1 0+0,19=0,19 0,26+0=0,26
0,26 1
2 0+0,43=0,43 0,26+0,19=0,45 0,38+0=0
0,45 1
3 0+0,63=0,63 0,26+0,43=0,69 0,38+0,19=0,57 0,61+0=0,61
0,69 1
4 0+0,84=0,84 0,26+0,63=0,89 0,38+0,43=0,81 0,61+0,19=0,8 0,76+0=0
0,89 1
5 0+1,05=1,05 0,26+0,84=1,1 0,38+0,63=1,01 0,61+0,43=1,04 0,76+0,19=0,85 0,99+0=0,99 1,1 0
Четвѐртый шаг. k = 1, C1 – средства, выделенные на инвестирование первого, второго, третьего и четвѐртого предприятий, то есть C1 = 5 у.е., x1 – средства, выделенные на инвестирование первого предприятия.
Рассмотрим возможности инвестирования первого предприятия. Для получения максимума прибыли F1(C1) воспользуемся рекуррентным соотношением
Составим вспомогательную таблицу 4
Таблица 4
C1 x2 F1(C1) x1*
0 1 2 3 4 5
g1(0)+
F2(C3-0) g1(1)+
F2(C3-1) g1(2)+
F2(C3-2) g1(3)+
F2(C3-3) g1(4)+
F2(C3-4) g1(5)+
F2(C3-5)
5 0+1,1=1,1 0,21+0,89=1,1 0,4+0,69=1,09 0,58+0,45=1,03 0,81+0,26=1,07 0,98+0=0,98 1,1 0
Безусловная оптимизация
Определим компоненты оптимальной стратегии.
Первый шаг. По последней таблице 4 максимальный доход при распределении средств между всеми четырьмя предприятиями составляет
F1(C1 = 5) = 1,1. Для достижения такого результата первому предприятию нужно выделить x1* = 0
Второй шаг. Величина средств, оставшихся на второе, третье и четвертое предприятия:
C2 = (C1 – x1* ) = (5 – 0) = 5
По табл. 3 максимальный доход при распределении средств C2 = 5 между оставшимися тремя предприятиями составляет F2(C2 = 4). Для достижения такого результата второму предприятию нужно выделить
x2*= 2
Третий шаг. Величина средств, оставшихся на третье и четвѐртое
предприятия:
C3 = (C2 – x2* ) = (5-1) = 4
По табл. 2 максимальный доход при распределении средств C3 = 4 между оставшимися тремя предприятиями составляет F3(C3 = 2). Для достижения такого результата третьему предприятию нужно выделить x3*= 2
Четвѐртый шаг. Величина средств, оставшихся на четвертое предприятие:
C4 = (C3 – x3* ) = (4-2) = 2
По табл. 1 максимальный доход при распределении средств C4 = 2 между оставшимися тремя предприятиями составляет F4(C4 = 0). Для достижения такого результата четвертому предприятию нужно выделить x4= 2
Таким образом, получен оптимальный план инвестирования предприятий Х*(0; 1; 2; 2) , который обеспечивает максимальный доход в размере
F* = g1(0) + g2(1) + g3(2) + g4(2) = 0+0,26+0,41+0,43=1,1
Ответ: Х*(0; 1; 2; 2), F* = 1,1.