Профилактика девиантного поведения у подростков

Решение. Имеем:

s1 = 5, s2 = 8, s3 = 12, s4 = 7, s5 = 8;    R = 32.

Поскольку

налицо дефицит. Определяем коэффициент :

На это число и умножаются заявки. В итоге получаем

Ответ: x1 = 4; x2 = 6,4; x3 = 9,6; x4 = 5,6; x5 = 6,4.

Пример 5.

Пусть имеется пять Потребителей, приоритеты которых определяются числами 8, 6, 12, 15, 11. Ресурс Центра составляет 60. Определить равновесные стратегии (заявки) Потребителей, если ресурс распределяется в соответствии с механизмом обратных приоритетов.

Решение. Имеем:

А1 = 8, А2 = 6, А3 = 12, А4 = 15, А5 = 11;   R = 60.

Вычислим константу :

Определять необязательно, поскольку в формулы для можно подставить сразу :

Ответ: s1* = 10,7; s2* =9,2; s3* = 13,1; s4* = 14,6; s5* = 12,5.

 

Имеется шесть Потребителей, подавших заявки в размере 14,18,10,15, 8,14 и сообщивших Центру соответственно следующие показатели эффекта: 36, 38, 25, 42, 28, 29. Каким должно быть распределение ресурса объемом 60 в соответствии с конкурсным механизмом?

Решение. По условию имеем

 

s1 = 14,   s2 = 18,   s3 = 10,   s4 = 15,   s5 = 8,   s6 = 14;

w1 = 36,   w2 = 38,   w3 = 25,   w4 = 42,   w5 = 28,   w6 = 29.

Вычислим показатели эффективности для каждого Потребителя:

Расположим эти числа в порядке убывания:

Распределение ресурса начинаем с 5-го Потребителя:

Ресурса осталось 60 – 8 = 52. Дальше в порядке убывания показателей эффективности следует 4-й Потребитель:

Ресурса осталось 52 – 15 = 37. Далее:

Ресурса осталось 37 – 14 = 23. Далее:

Ресурса осталось 37 – 14 = 13.

Следующему, 2-му Потребителю требуется 18 единиц ресурса, а у Центра осталось лишь 15. Поэтому 2-ой, а также 6-й Потребители ничего не получают:

Ответ: х1 = 14, х2 = 0, х3 = 10, х4 = 15, х5 = 8, х6 = 0.

 

Восемь Потребителей подали Центру свои заявки. Они таковы: 12, 3, б, 1, 5, 7, 10, 2. Центр обладает ресурсом R = 40. Требуется распределить этот ресурс в соответствии с вышеописанным механизмом.

Решение. В данном случае на первом этапе получается следующее (R/n = 5):

s1 = 14,	S2 = 14,	S3 = 14,	S4 = 14,	S5 = 14,	S6 = 14,	S7 = 14,	S8 = 14,	R = 40.
5	5	5	5	5	5	5	5

 

Видно, что можно удовлетворить заявки второго, четвертого, пятого и восьмого Потребителей:

х2 = 3

х4 = 1

х5 = 5

х8 = 2

При этом R1 = 40 – 3 – 1 – 5 – 2 = 29, n1 = 4.

На втором этапе имеем :

s1 = 12,	s3 = 6,	s6 = 7,	s7 = 10,	R = 29.

Можно удовлетворить заявки третьего и шестого Потребителей:

х3 = 6

х6 = 7

При этом

s1 = 12,	s7 = 10,	R = 16.
8	8

Обе оставшиеся заявки превышают 8, поэтому и седьмой Потребители получают по 8 единиц ресурса:

х1 = 8

х7 =8.

Ответ: х1 = 8, х2 = 3, х3 = 6, х4 = 1, х5 = 5, х6 = 7, х7 = 8 х8 = 2.

Пусть 6 экспертов сообщили следующие оценки из промежутка [30, 90]: 65, 90, 45, 80, 75, 90. Определим итоговое решение в соответствии с механизмом открытого управления.

Решение. Выпишем числа :

v1 = 90,		v4 = 90 – 30 = 60,
v2 = 90 – 10 = 80,		v4 = 90 – 40 = 50,
v3 = 90 – 20 = 70,		v4 = 90 – 50 = 40.

Дальнейшее удобно изобразить в виде таблицы, в первой строке которой записаны упорядоченные по неубыванию оценки экспертов:

si:	45	65	75	80	90	90
vi:	90	80	70	60	50	40
:	45	65	70	60	50	40

В качестве итогового решения берется максимальное число в последней строке:

.

Пример 6.

Задана сеть, каждое ребро которой имеет вполне определенную ограниченную пропускную способность. Требуется определить максимально возможный поток в этой сети из заданного узла в другой узел.

Чтобы пояснить основную идею метода решения этой задачи, предположим, что исходный и конечный пункты, пункт А и пункт В, находятся на разных берегах разделяющей их реки (рис. 21). Множество мостов через реку образуют так называемое разделяющее сечение (если все мосты по каким-либо причинам выйдут из строя,

попасть из пункта А в пункт В будет просто невозможно). Ясно, что пропускная способность разделяющего сечения складывается из пропускных способностей всех мостов.

Подобных сечений, разделяющих пункты А и В, может быть несколько (рис. 22), и каждое из них обладает своей пропускной способностью. Из того, что поток из пункта А в пункт В должен проходить через каждое разделяющее сечение, вытекает, что максимально возможный поток не может превосходить пропускной способности ни одного из этих сечений.

Таким образом, отыскание макси-потока (максимально возможного потока) сводится к отысканию мини-сечения (разделяющего сечения с наименьшей пропускной способностью).

Рассмотрим сеть, заданную на рис. 23. Требуется найти максимально возможный поток из узла 1 в узел 7.

Вычислим пропускную способность ключевых сечений. Имеем: пропускная способность сечения {(1,2), (1,3)} равна 4, пропускная способность сечения {(2,4), (3,5)} равна 4, пропускная способность сечения {(1,3), (2,3), (6,7)} равна 5, пропускная способность сечения {(5,7), (6,7)} равна 2.

Сравнивая пропускные способности сечений, получаем, что максимальный поток от вершины 1 к вершине 7 равен 2.

Пример 7. Дана сеть, каждое ребро которой помечено числом, равным его длине. Требуется найти кратчайший маршрут, ведущий от выделенного узла к каждому из узлов сети.

Алгоритм решения этой задачи состоит из двух частей.

Покажем, как он работает, на следующем примере.

Рассмотрим сеть, заданную на рис. 24, с выделенным узлом 1.

Рис. 24

Прямой ход алгоритма

1-й шаг. Все узлы, которые соединены с выделенным узлом 1 одним ребром, метятся так, как это показано на рис. 25 — первое число в метке равно расстоянию от помеченного узла до узла 1.

Ребро, связывающее узлы 1 и 3, является кратчайшим маршрутом от узла 1 к узлу 3 (любой другой маршрут от узла 1 к узлу 3 длиннее), и поэтому узлу 3 приписывается постоянная метка (15,1).

Таким образом, по окончании 1-го шага узлы 1 и 3 имеют постоянные метки, узлы 2 и 4 — временные метки, а узлы 5, б и 7 никаких меток не имеют (рис. 26).

Замечание. При получении постоянной метки узел 3 выделяется так же, как и узел 1.

2-й шаг. Отбираются все узлы, которые соединены с узлом 3 одним ребром и не имеют постоянных меток. Это узлы 2, 4 и 6

 

Рис. 25	Рис. 26

 

Сравнивая длины маршрутов 1-2 и 1-3-2, замечаем, что длина первого (20) меньше длины второго (15 + 10 = 25). Поэтому метка (20,1) узла 2 остается неизменной.

Сравнивая длины маршрутов 1-4 и 1-3-4, замечаем, что длина первого (25) больше длины второго (15 + 8 = 23). Поэтому временная метка (25,1) узла 4 меняется на метку (23,3).

Узел 6 получает метку (45,3).

Замечание. Первое число в метке указывает длину маршрута от узла 1, а второе — номер предшествующего узла.

Ребро, связывающее узлы 1 и 2, является кратчайшим маршрутом от узла 1 к узлу 2 (любой другой маршрут от узла 1 к узлу 2 длиннее), и поэтому узлу 2 приписывается постоянная метка (20,1).

Таким образом, по окончании 2-го шага узлы 1, 2 и 3 имеют постоянные метки, узлы 4 и 6 — временные метки, а узлы 5 и 7 никаких меток не имеют (рис. 27).

3-й шаг. Отбираются все узлы, которые соединены с узлом 2 одним ребром и не имеют постоянных меток. Это узлы 5 и 7.

Узел 5 получает метку (40,2).

Узел 7 получает метку (60,2).

Маршрут 1-3-4, связывающий узлы 1 и 4, является кратчайшим маршрутом от узла 1 к узлу 4 (любой другой маршрут от узла 1 к узлу 4 длиннее); поэтому узлу 4 приписывается постоянная метка (23,3).

Таким образом, по окончании 3-го шага узлы 1, 2, 3 и 4 имеют постоянные метки, а узлы 5, б и 7 — временные метки (рис. 28).

 

Рис. 27	Рис. 28

4-й шаг. Отбираются все узлы, которые соединены с узлом 4 одним ребром и не имеют постоянных меток. Это узел 6.

Сравнивая длины маршрутов 1-3-6 и 1-3-4-6, замечаем, что длины первого (45) и третьего (45) больше длины второго (43). Поэтому временная метка (45,3) узла 6 меняется на метку (43,4).

Маршрут 1-2-5, связывающий узлы 1 и 5, является кратчайшим маршрутом от узла 1 к узлу 5 (любой другой маршрут от узла 1 к узлу 5 длиннее), и поэтому узлу 5 приписывается постоянная метка (40,2).

Таким образом, по окончании 4-го шага узлы 1, 2, 3, 4 и 5 имеют постоянные метки, а узлы 6 и 7 — временные метки (рис. 29).

Рис. 29	Рис. 30

 

Следующие два шага позволяют дать постоянные метки узлам 6 и 7 — (43,4) и (49,5) соответственно (рис. 30).

Замечание. На каждом шаге временная метка одного из узлов меняется на постоянную по следующему правилу: рассматриваются все узлы с временными метками и выбирается тот из них, длина маршрута до которого от узла 1 является наименьшей.

Обратный ход алгоритма

Используя вторую компоненту метки, определяем последовательность вершин в каждом кратчайшем маршруте. Например: метка (49,5) узла 7 указывает на предшествующий узел 5, метка (40,2) узла 5 указывает на предшествующий узел 2, метка (20,1) узла 2 указывает на предшествующий узел 1.

В результате обратная последовательность  узлов кратчайшего маршрута от узла 1 к узлу 7 имеет вид

Ответ:

Узел	Маршрут	Длина
2	1-2	20
3	1-3	15
4	1-3-4	23
5	1-2-5	40
6	1-3-4-6	43
7	1-2-5-7	49