Материал: ММвСС. Экзаменационные вопросы и ответы
34. Поиск самого надежного пути в сети. Постановка задачи, весовые коэффициенты ребер графа.
|
|
Граф |
|
|
|
|
2 |
p |
3 |
|
|
|
|
23 |
|
|
|
|
|
|
p |
|
|
p |
|
|
34 |
|
|
|
|
|
|
|
|
12 |
p26 |
|
|
|
4 |
|
|
|
|
||
|
|
|
p |
|
|
|
|
|
37 |
|
|
1 |
|
|
p |
|
p45 |
|
|
|
|
|
|
|
|
|
47 |
|
|
p |
|
|
|
|
|
71 |
|
|
|
|
|
|
7 |
|
p |
56 |
5 |
|
p |
|
|||
|
|
|
|||
|
|
|
|
|
|
|
|
67 |
|
|
|
|
|
|
6 |
|
|
Самый надежный путь
( ) = ∏ |
|
|
|
|
|
|
|
|
( , ) |
|
|
log ( ) = ∑ |
log |
= − ∑ |
log |
|
|
|
|
( , ) |
|
( , ) |
|
|
= − log |
|
|
|
|
|
|
Трехместная операция, в алгоритме Флойда-Уоршалла
= max | , + |
35. Задачи прогнозирования развития технологий связи (проникновения). Основные характеристики уровня развития. Линейная модель прогнозирования (линейная регрессия).
Основными показателями развития технологий телекоммуникаций являются степень и динамика их распространения. Обычно, этот показатель оценивается проникновением той или иной технологии, т.е. числом пользователей на 100 жителей. Динамика изменения проникновения характеризуется некоторой функцией =( 1, 2, … , , ), определяющей зависимость проникновения от времени. Для построения этой зависимости применяются методы аппроксимации исходных данных = { 1, … , } (временного ряда) некоторой функцией. Для этой цели может быть использован, например, метод наименьших квадратов или другие методы выбора параметров функции 1, … , путем минимизации отклонений ее значений, от значений определяемых исходным рядом .
Существенную роль при построении прогноза имеет выбор аппроксимирующей функции. Основным требованием к данной функции является непрерывность на интервале прогнозирования. Однако выполнения этого требования не достаточно для получения адекватного прогноза. Понятно, что выбираемая функция, по возможности, должна наилучшим образом, отражать процесс изменения прогнозируемой величины. Поэтому, при выборе функции следует руководствоваться знаниями об исследуемом процессе и подобных процессах, возможно в других областях знаний, т.е. использовать ассоциативный подход.
Практически, при построении краткосрочных прогнозов, часто используется линейная регрессия.
Линейная регрессия
Линейная регрессия |
|
|
|
|
|
Линейная регрессия с доверительным интервалом |
||||||
̂ = ( 0, 1, ) = 1 + 0 |
|
|||||||||||
= |
|
∑ ( ) − ̅ ̅ |
|
|||||||||
|
=1 |
|
|
|
|
|
|
|
|
|||
1 |
|
|
|
( |
2 |
|
|
|
2 |
|
|
|
|
|
|
∑ |
|
) − ̅ |
|
||||||
|
|
|
=1 |
|
|
|
|
|
|
|
|
|
|
|
|
0 = ̅ − 1 |
̅ |
|
|
||||||
|
1 |
|
|
|
|
|
|
|
1 |
|
||
̅= |
∑ , |
|
|
|
̅ = |
∑ |
|
|||||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
=1 |
|
|
|
|
|
=1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|||
Доверительный интервал для прогнозируемых значений ̂ будет определяться как: |
||||||||||||
( ) = ̂( ) ± |
( ) |
|
||||||||||
0 |
|
0 |
|
|
|
| |
0 |
−2,2 |
||||
|
|
|
|
|
|
|
|
|
|
|||
|
|
1 |
|
( |
|
− ̅)2 |
|
1 |
|
|
(∑ |
( |
− ̅)( |
− ̅))2 |
|
||
|
( ) = √ |
|
+ |
0 |
|
|
√ |
|
(∑( − ̅)2 |
− |
=1 |
|
|
|
|
) |
|
|
∑ |
( − ̅)2 |
|
− 2 |
∑ |
|
( − ̅)2 |
||||||||||
| |
0 |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
=1 |
|
|
|
|
|
=1 |
|
|
=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В этом случае предполагается, что имеет место линейная тенденция изменения прогнозируемой величины, а также сохраняется случайный характер ее изменения, поэтому результатом прогноза является доверительный интервал. Ширина доверительного интервала расширяется с увеличением интервала прогнозирования, а ее минимальное значение приходится на середину интервала исходных данных.
36. Задачи прогнозирования развития технологий связи (проникновения). Основные характеристики уровня развития. Логистическая модель прогнозирования (логистическая регрессия).
Логистическая регрессия — это статистическая модель, используемая для прогнозирования вероятности возникновения некоторого события путём подгонки данных к логистической кривой.
Логистическая регрессия
( ) = 1 + −− 0= 100, 0 = 10, = 2
Под логистической функцией понимают функцию, являющуюся решением дифференциального уравнения вида:
|
|
|
|
|
|
|
|
|
= (1 − |
|
) , |
, — постоянные |
|
|
|
|
||||
Параметр – характеризует скорость роста, а |
параметр |
– предельно достижимый уровень развития |
||||
(численности). |
|
|
|
|
|
|
Общий вид: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
= ( ) = + 0( − 1)
lim ( ) =
t→∞
Частным случаем логистической функции является S-функция
1( ) = 1 + −
которая является решением уравнения вида
Для практических целей часто используется логистическая функция в виде:
− 0
1 + −
где – предельно достижимый уровень развития (численности), – коэффициент, определяющий скорость роста, 0 – точка перегиба.
В 1962 г. Е.М. Роджерсом было предложено использование S-кривой для описания процесса внедрения инноваций (Diffusion of Innovations).
|
− |
− 0 |
|
|||
= |
|
|
|
|
||
(1 + − |
− 0 |
2 |
||||
|
||||||
|
|
) |
||||
Этапы:
1.Новаторы. На данном этапе происходит распространение технологии среди наиболее заинтересованных (передовых) пользователей (innovators), их доля определена как 2,5%.
2.Начальный выбор. На данном этапе происходит распространение технологии среди пользователей наиболее быстро откликающихся на предложение (early adopters). Их доля составляет 13,5%.
3.Раннее большинство. На данном этапе происходит распространение технологии среди половины основной массы пользователей, наиболее быстро принимающих предложение (early majority). Их доля составляет 34%.
4.Позднее большинство. На данном этапе происходит распространение технологии среди второй половины основной массы пользователей (late majority). Их доля составляет 34%.
5.Отстающие. На данном этапе происходит распространение технологии среди пользователей наиболее медленно реагирующих на предложение (laggards). Их доля составляет 16%.
37.Задачи оптимизации. Постановка задачи оптимизации – основные этапы: предметная область, параметры управления, показатели состояния, модель, целевая функция. Пример постановки задачи оптимизации для сети с коммутацией каналов. Оптимизации качества обслуживания (минимум потерь).
Качество обслуживания в сети с КК
Рассматривается сеть связи с коммутацией каналов (КК). Структура сети задана графом. Сеть состоит из узлов связи и направлений связи (ребер графа).
— число каналов в направлений связи— интенсивность нагрузки в направлений связи (Эрл)
— общее число каналов в сети
1. Формулировка задачи
• Предметная область – качество обслуживания (вероятность потерь вызовов).
• Состояние сети задано исходными данными.
• Требуется найти оптимальное число каналов в каждом из направлений связи для получения минимальных потерь вызовов в сети, при заданном общем числе каналов N.
2. Построение модели системы
• Полагаем, что в направлениях сети имеют место простейшие потоки вызовов.
• Модель направления связи может быть представлена первой формулой Эрланга.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
|
|
|
|
|
|
, = 1 … |
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
|
|
||||
|
∑ |
|
|
|
|
|
|
|
|
|
! |
|
|
||
|
=0 |
|
|
|
|||
3. Выбор параметров управления и показателей состояния
•Параметры управления: число каналов в каждом из направлений связи .
•Показатели состояния: потери в каждом из направлений связи .
4.Построение целевой функции
Выберем в качестве целевого показателя средневзвешенную вероятность потери вызова в сети
|
|
|
|
|
|
|
|
̅= ∑ |
|
, |
= ∑ |
|
|
|
|
|||||
|
=1 Σ |
|
|
Σ |
|
|
|
|
|
|
=1 |
||
Целевая функция: |
= arg min{ ̅( )} при ∑ |
|
|
= |
|
|
|
|
=1 |
|
|
|
|
|
xj |
|
|
|
|
|
5.Выбор метода оптимизации целевой функции.
6.Решение задачи.
38. Пример постановки задачи оптимизации надежности сети связи (максимум надежности).
Надежность сети связи
Рассматривается сеть связи с коммутацией каналов (КК). Структура сети задана графом. Сеть состоит из узлов связи и направлений связи (ребер графа).
— число каналов в направлений связи— надежность канала в направлений связи (вероятность исправного состояния)
= 0 … 1 — значимость направления связи, ∑=1 = 1— общее число каналов в сети
1. |
Формулировка задачи |
• |
Предметная область – надежность сети связи (вероятность исправного состояния). |
• |
Состояние сети задано исходными данными. |
• |
Требуется найти оптимальное число каналов в каждом из направлений связи для получения |
|
максимальной надежности сети, при заданном общем числе каналов N. |
2. |
Построение модели системы |
•Полагаем, что направление исправно, если исправен хотя бы один канал.
•Модель направления связи может быть представлена как вероятность исправного состояния.
= 1 − (1 |
− ) , |
= 1 … |
|
|
|
3. Выбор параметров управления и показателей состояния
•Параметры управления: число каналов в каждом из направлений связи .
•Показатели состояния: вероятность исправного состояния каждого из направлений связи .
4.Построение целевой функции
Выберем в качестве целевого показателя средневзвешенную вероятность исправного состояния сети
̅ |
, |
∑ = 1 |
|
= ∑ |
|||
|
|
|
|
|
=1 |
|
=1 |
Целевая функция |
|
|
|
|
|
|
|
|
= arg max{̅( )} при ∑ |
= |
|
|
|
|
xj |
=1 |
5.Выбор метода оптимизации целевой функции.
6.Решение задачи.
39. Задачи оптимизации. Безусловная оптимизация. Условная оптимизация.
Оптимизация — процесс нахождения экстремума (глобального максимума или минимума) определённой функции или выбора наилучшего (оптимального) варианта из множества возможных. Наиболее надёжным способом нахождения наилучшего варианта является сравнительная оценка всех возможных вариантов (альтернатив). Если число альтернатив велико, при поиске наилучшей обычно используют методы математического программирования. Применить эти методы можно, если есть строгая постановка задачи: задан набор переменных, установлена область их возможного изменения (заданы ограничения) и определён вид целевой функции (функции, экстремум которой нужно найти) от этих переменных. Последняя представляет собой количественную меру (критерий) оценки степени достижения поставленной цели.
Выбор оптимального решения или сравнение двух альтернативных решений проводится с помощью некоторой зависимой величины, которая называется целевой функцией (или критерием качества). В
процессе решения задачи оптимизации должны быть найдены такие значения параметров, при которых целевая функция имеет минимум (или максимум).
Задача безусловной оптимизации (задача не имеет ограничений) состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Многие алгоритмы решения задачи с ограничениями предполагают сведение ее к последовательности задач безусловной оптимизации. Другой класс методов основан на поиске подходящего направления и последующей минимизации вдоль этого направления.
Задача условной оптимизации (задача имеет ограничения) заключается в поиске минимального или максимального значения скалярной функции ( ). Решение задачи основывается на линейной или квадратичной аппроксимации целевой функции для определения приращений 1, … , на каждой итерации. Существуют также приближенные методы решения нелинейных задач, основанные на методе кусочно-линейной аппроксимации.
Аналитические методы оптимизации:
•Безусловная оптимизация (необходимые и достаточные условия существования экстремума функции).
•Условная оптимизация (метод множителей Лагранжа, условия Каруша-Куна-Таккера).
40. Экстремумы функций: определения локального и глобального экстремумов.
Экстремум — максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум — точка экстремума называется точкой минимума, а если максимум — точкой максимума.
Стационарная точка — точка, в которой значение производной функции равно 0.
Критическая точка — точка, в которой значение производной функции равно 0 (стационарная точка) или не существует (например, = | | при = 0 – минимум, но производной в этой точке не существует).
Теорема Ферма (необходимый признак существования экстремума функции). Если точка 0 – точка экстремума функции ( ), то в этой точке производная функции равна нулю ( ′( ) = 0) или не существует.
Теорема (первый достаточный признак существования экстремума функции). Критическая точка 0 является точкой экстремума функции ( ), если при переходе через эту точку производная функции меняет знак, причём, если знак меняется с "плюса" на "минус", то точкой максимума, а если с "минуса" на "плюс", то точкой минимума.
Теорема (второй достаточный признак существования экстремума функции). Критическая точка 0 является точкой экстремума функции ( ), если ( ) дважды дифференцируема в точке 0 и ′(0) = 0. Причём, если вторая производная меньше нуля ( ′′(0) < 0), то 0 – точка максимума, а если вторая производная больше нуля
( ′′(0) > 0), то 0 – точка минимума.
Функция (синяя) и её производная (красная).
Глобальный максимум функции — «звездочка» Глобальный минимум — «квадрат». Локальный максимум — «ромб».
Локальный минимум — «плюс».
Нуль производной без экстремума – «крест».
Видно, что остальные нули производной соответствуют точкам экстремума функции.
Пусть дана функция : → и 0 0 — внутренняя точка области определения . Тогда 0:
•Локальный максимум, если существует проколотая окрестность ̇(0), ( ) ≤ (0).
Т. е. если значение функции в этой точке больше значений функции в достаточно близких к ней точках, расположенных справа и слева от неё.
•Локальный минимум, если существует проколотая окрестность ̇(0), ( ) ≥ (0).
Т. е. если значение функции в этой точке меньше значений функции в достаточно близких к ней точках, расположенных справа и слева от неё.
•Глобальный максимум, если , ( ) ≤ (0).
•Глобальный минимум, если , ( ) ≥ (0).