Некоммерческое акционерное общество

Некоммерческое акционерное общество

Алматинский УНИВЕРСИТЕТ энергетики и связи

Кафедра Автоматической электросвязи

ПРОЕКТИРОВАНИЕ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ

Методические указания к выполнению рассчетно - графических работ

(для обучающихся в профильной магистратуре по специальности 6M071900)

Алматы 2010

СОСТАВИТЕЛИ: Г. П. Данилина, П. В. Обухова. Проектирование телекоммуникационных систем. Методические указания к выполнению расчетно – графических работ (для обучающихся в профильной магистратуре по специальности 6M071900).- Алматы: АУЭС, 2010.-44 с.

Методические указания содержат описания заданий трех расчетно – графических работ, требования к их выполнению, иллюстрационные примеры решения задач и варианты заданий.

Первая работа посвящена задачам синтеза сетей связи и способствует изучению построения допустимых сочетаний технологических параметров проектирования топологии сетей, постановки задачи сетевого планирования. Вторая работа посвящена задачам распределения каналов сетей связи и способствует получению навыков построения плана распределения каналов вторичной некоммутируемой сети. Третья расчетно – графическая работа посвящена САПР (системам автоматического проектирования) и способствует получению навыков эффективности автоматизации проектирования. подсистемы.

Содержание

Введение 5

1 Расчетно – графическая работа №1 5

1.1 Задание к расчетно-графической работе №1 5

1.2 Указания к выполнения задания №1 6

1.3 Указания к выполнению задания №2 15

2 Расчетно – графическая работа №2 23

2.1 Задание к расчетно-графической работе №2 23

2.2 Указания к выполнению задания РГР 2 23

3 Расчетно – графическая работа №3 28

3.1 Задание к расчетно – графической работе №3 Автоматизированные системы проектирования 28

3.2 Указания к выполнению задания РГР 3 задача №1 28

3.3 Пример определения целесообразности автоматизации решения некоторой задачи R 32

3.4 Указание к выполнению задания РГР 3 задача №2 33

4 Приложение А 38

5 Приложение Б 40

6 Приложение В 41

7 Приложение Г 42

8 Список литературы 43

Введение

Цель курса «Проектирование ТКС» состоит в изучении принципов проектирования телекоммуникационных сетей, основ управления сетью, сетевого планирования, систем автоматического проектирования, математических методов анализа и расчета показателей сети.

Курс включает изучение теоретического материала согласно программе, выполнение практических и расчетно – графических работ.

Расчетно – графическая работа должна показать умение студентов делать самостоятельные выводы и обобщение изученного материала, способность построения фрагментов сетей выполнение анализа и расчета их показателей.

Расчетно – графическая работа выполняется на листах размера А4 в соответствии с ГОСТ. На титульном листе указывается номер варианта.

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

Работа, выполненная небрежно или по другому варианту, не принимается.

Номер варианта задания определяется по последней цифре номера зачетной книжки.

1 Расчетно – графическая работа 1

1.1 Задание к расчетно – графической работе №1

Настоящая расчетно – графическая работа состоит из выполнения 2 заданий:

1) Решение задачи синтеза транспортных сетей.

Задание к задаче 1:

- изучить постановку задачи исследования;

- выбрать вариант исходной информации;

- преобразовать сеть в сеть с одним источником и одним стоком;

- записать, модель;

- решить ее указанным методом;

- изобразить на чертеже оптимальный граф с распределением потока на его дугах;

- указать величину целевой функции.

2) Решение задачи синтеза централизованных сетей

Задание к задаче 2:

- изучить постановку задачи;

- выбрать вариант задания;

- решить задачу синтеза вручную. Результат представить в виде рисунка оптимальной схемы соединения терминалов с ЭВМ и концентраторами соответствующей этой схеме стоимости;

- разработать и описать блок- схему алгоритма.

1.2 Указание к выполнению задания 1

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

Варианты задания даны в приложении А (номер задания соответствует последней цифре зачетной книжке). Если сеть с несколькими источниками или стоками – произвести ее преобразование, записать экономико – математическую модель и решить ее. Привести чертеж оптимальной сети.

Алгоритм решения задачи 1

Задача имеет смысл, если интенсивности источника и стока равны по величине и противоположны по знаку

Алгоритм состоит из последовательности повторяющихся шагов.

Шаг 0. Произвести первоначальное распределение потока, удовлетворяющее ограничениям (1.1), (1.2) и (1.3)

, (1.1)

, (1.2)

_. (1.3)

Шаг 1. Построить дерево графа сети, состоящее из основных дуг (т. е. дуг, поток на которых удовлетворяет условию ). Если задача вырожденная и таких дуг меньше, чем должно быть ветвей дерева, то включаются дополнительно дуги с нулевым (х = 0) или насыщенным (х=r) потоком.

Шаг 2. Для каждой хорды (λ, μ)строится цикл из дуг дерева γ. Направление обхода этого цикла определяется из следующих условий:

а) если х_λμ =0, то поток по хорде (λμ) может только увеличиваться и
направление обхода никла совпадает с направлением (λμ);

б) если х_λμ = r_λμ , то поток на ней можно только уменьшить и направление
обхода цикла противоположно направлению хорды (λμ). Обозначим дуги цикла, направление которых совпадает с направлением цикла – положительной полуцепью γ+ , в противном случае - отрицательной γ -. На дугах положительной полуцепи полученная величина потока может быть увеличена на (1.4)

θ+=min{ r_ij - x_ij }, (1.4)

а на дугах отрицательной полуцепи γ- уменьшена на (1.5)

θ-=min{x_ij }. (1.5)

Изменение потока в цикле возможно только на меньшую из этих величин (1.6)

θ=min{ θ-; θ+ }. (1.6)

Шаг 3. Подсчет величин потока в цикле выразим следующим соотношением (1.7)

_. (1.7)

Шаг 4. Оценка целесообразности изменения потока в цикле производится следующим способом:

рассчитывается функция (1.8)

_(1.8)

_{где h(xij) определяется соотношением (1.9)}

_{.
(1.9)}

И функция _.

Значения F сравниваются: если то остается старое распределение и алгоритм продолжается для другой хорды с шага 2;

если то производится распределение потока в цикле по соотношению (1.6) и переход к шагу 1.

Расчеты закончены, если ни для одной хорды не произведено уменьшение целевой функции.

Обычно сеть описанного вида при решении заменяется сетью с одним источником и одним стоком, выполняя следующие преобразования. В сеть вводят две дополнительные вершины: источник S и сток T, которые соединяются так называемыми мнимыми дугами

(S, i₁), (S, i₂),… (S, i_N),

(j_1,T), (j_2,T),… (j_T,T).

Рисунок 1.1 – Сеть с несколькими источниками и стоками

Рисунок 1.2 – Сеть с одним источником и стоком

Для того чтобы суммарная стоимость и распределение потоков были на этих сетях адекватными, параметры мнимых дуг задаются следующим образом

r_si=d_i
,r_jT=-d_j, r_jT=-d_j.

_, _,

d_i=0, d_j=0,

c_si=0, c_jT=0,

p_si=0, p_jT=0,

Пример решения задачи синтеза транспортных сетей

Задан некоторый граф сети (см. рисунок 1.3) представляющий собой избыточную конструкцию, имеющий вершину – источник 1, сток – вершину 5. с интенсивностями d₁=30, d₅=-30.

Рисунок 1.3 – Граф сети G=(A,U)

Шаг 0. Произвести первоначальное распределение потока (см. рисунок 1.2), удовлетворяющее ограничениям (1.10), (1.11) и (1.12)

_, (1.10)

_, (1.11)

_. (1.12)

d₁=20,

d₅=-20.

Рисунок 1.4 – Первоначальное распределение потока

На каждой дуге записаны исходные данные: первое число – пропускная способность , второе число – стоимость перемещения единицы потока с_ij, третье – стоимость создания ребра p_ij. Если на ребре есть поток, то он записывается как числитель над величиной пропускной способности.

Шаг 0: Произведем первоначальное распределение потока, удовлетворяющее соотношениям (1.10-1.12).

Будем насыщать последовательно дуги, исходящие из вершины 1.

На дуге 1-2 пропускная способность r₁₂=20, следовательно, х₁₂ полодим равным r₁₂ , т.е.

х₁₂=min{d₁,r₁₂}=r₁₂=20.

В вершине 1 осталось нераспределнным d₁-x₁₂=30-20=10 единиц потока, а (см. рисунок 1.4).

Следующая рассматриваемая дуга (1-3) с пропускной способностью r₁₃=15. Поток определяется формулой

Далее распределяется поток от вершин с нулевой интенсивностью:

Распределение потока приведено на рисунке 1.4

Шаг 1 .Построить дерево графа, включив в него основные дуги, т.е. дуги, поток на которых удовлетворяет условию .На графе рисунка 1.4 таких дуг три: (1-3), (2-5), (3-5). Поскольку рассматриваемый граф имеет пять вершин, то дерево состоит из n-1=5-1=4 дуг, поэтому включим еще одну дугу, поток на которой равен r_ij или 0 и которая не образует с ранее выделенными замкнутого цикла. Этим условиям удовлетворяет любая из дуг (1-4), (4-3), (4-5). Пусть это будет дуга (1-4). Дуги дерева на рисунке 1.4 выделены жирными линиями.

Шаг 2. Для каждой хорды (λ, μ)строится цикл из дуг дерева γ и определяется величина возможного изменения. Для хорды (1-2) цикл γ состоит из дуг (2-5), (3-5) и (1-3). Направление обхода этого цикла определяется из следующих условий:

- если x_λ_µ=0, то на этом ребре поток может быть увеличен, и направление обхода цикла совпадает с направлением ребра (λµ)

- если x_λ_µ=r_λ_µ, то поток можно уменьшить, и направление цикла противоположно направлению дуги λµ

Например, поток х₁₂=r₁₂, значит цикл γ₁₂={1-2; 2-5; 1-3; 3-5} имеет направление обхода против часовой стрелки.

Определим возможную величину изменения потока в цикле γ₁₂по формулам (1.4-1.6)

Шаг 3. Подсчитывается величина нового распределения потока в цикле γ₁₂ по формуле (1.7).

Шаг 1. Оценим целесообразность изменения потока в цикле. Для этого подсчитываются значения функций стоимости при старом и новом распределении потока и сравниваются

f^c=670,

f^н=690,

f^c< f^н.

Так как f^c< f^н остается старое распределение и алгоритм продолжается для хорды (2-3) с шага 2;

γ₂₃={2-3; 2-5; 3-5}.

Шаг 2. Поток на хорде (2-3) равен нулю, поэтому обход цикла совпадает с направлением хорды (2-3). Следовательно,

Определим возможную величину изменения потока в цикле γ₂₃по формулам (1.4-1.6).

Шаг 3. Подсчитывается величина нового распределения потока в цикле γ₁₂ по формуле (1.7).

Шаг 4. Определяются значения функций стоимости при старом и новом распределении потока и сравниваются

f^c=350,

f^н=150,

f^c> f^н.

Полученное неравенство говорит о целесообразности изменения потока в цикле. Новое распределение потока приведено на рисунке 1.5.

Проверим оптимальность приведенного распределения, проанализировав циклы для всех хорд.

Рисунок 1.5 – Второе распределение потока и соответствующее ему дерево

Шаг 2. Рассмотрим хорду (1-4). Ей соответствует цикл γ₁₄=(1-4; 1-3;4-3).

Т.к. х₁₄=0, то направление обхода цикла совпадает с направлением (1-4)

Определим возможную величину изменения потока в цикле γ₁₄по формулам (1.4-1.6).

Шаг 3. Новый поток в цикле γ₁₂определим по формуле (1.7).

Шаг 4. Определяются значения функций стоимости при старом и новом распределении потока и сравниваются

f^c=200,

f^н=60,

f^c> f^н.

Полученное неравенство говорит о целесообразности изменения потока в цикле.

Шаг 1. Новое распределение потока приведено на рисунке 1.6.

а) б)

Рисунок 1.6 – Третье распределение потока (а), оптимальный граф (б)

Проверим целесообразности изменения потоков для всех циклов сети

γ₁₂:

γ₂₅:

γ₁₄:

γ₄₅:

Произведя расчеты, аналогичные описанным выше, выясним, что никакое перераспределение потока в циклах не уменьшает значение целевой функции. Значит, полученное распределение потока – наилучшее, а соответствующий ему граф – оптимальный. Затраты на построение и эксплуатацию сети составляют

1.3 Указание к выполнению задания 2

Варианты задания даны в приложении Б (номер задания соответствует последней цифре зачетки). Кроме того, все стоимости C_ij и f_j следует умножать на последнюю цифру года (в 2011- на 1, в 2012- на 2 и т.д.).

Рассмотрим алгоритм синтеза двухуровневой сети, включающей заданное число терминалов T_i, i=1,..n, некоторое допустимое множество концентраторов K_j(j=1,..m), места расположения которых известны, а количество должно быть выбрано в результате решения задачи. Центральное обрабатывающее устройство (ЭВМ) обозначим К₀. Заданы стоимости создания концентраторов f_j и количество терминалов, которые можно подключить к каждому концентратору, r_j. Если к концентратору подключен хотя бы один терминал, то он называется открытым, в противном случае – закрытым.

Каждый терминал может быть подключен к ЭВМ или любому концентратору, но только одному. Задача состоит в построении сети минимальной стоимости, учитывающей все описанные технологические ограничения.

Итак, заданными являются:

- множества терминалов Т_i и концентраторов K_j (i=1,..n; j=1,2,…m), ЭВМ – К0;

- стоимости линий связи, заданные матрицей стоимости С=С_ij, i=1,..n; j=0,1,…m;

- стоимости создания концентраторов f₁,f₂,…f_m;

- количество возможного подключения терминалов r_j.

Определить:

- количество открытых концентраторов;

- схему подключения к ним терминалов;

- стоимость сети.

Для реализации этой задачи разработано большое число методов, рассмотрим алгоритм одного из них.

Алгоритм решения задачи 2

Алгоритм представляет собой итерационный процесс последовательного уменьшения целевой функции за счет открытия дополнительных концентраторов и рационального прикрепления к ним терминалов.

Централизованной будем называть сеть, состоящую из двух уровней: первый уровень – терминальный, второй уровень – уровень концентраторов.

-терминалы Тi , могут подключаться к концентратору или непосредственно к ЭВМ;

- концентраторы Кj, соединяемые с центральной ЭВМ.

Для решения задачи необходимо выполнять условия (1.13), (1.14), (1.15), (1.16), (1.17)

_{, (1.13)}

, если к концентратору присоединен терминал (открытый)

_{,
(1.14)}

f_n– стоимость

_(1.15)

_(1.16)

_(1.17)

Заданными являются:

- множество терминалов Т_i и концентраторов К_j (i=1,2,…,n; j=1,2,…,m), ЭВМ – К₀;

-стоимость линий связи, заданных матрицей стоимости (см. таблицу 1.1),

Определить:

- схему подключения терминалов к концентраторам или ЭВМ;

- число и расположение задействованных концентраторов;

- стоимость сети, учитывая,что каждый терминал может быть соединен только с одним концентратором (или ЭВМ), а каждый концентратор только с тем числом терминалов, которое определено пропускной способностью r_j, j=1,2,…,m;

- стоимость создания концентраторов f_j_,j=1,2,…,m.

В таблице 1.1 приведена структурная матрица затрат на подключение терминалов к концентраторам

Таблица 1.1 – Структурная матрица затрат

	К₀	К₁	К₂	…	К_n
Т₁	C₁₀	C₁₁	C₁₂	…	C_1n
Т₂	C₂₀	C₂₁	C₂₂	…	C_1n
Т₃	C₃₀	C₃₁	C₃₂	…	C_1n
Т_n	C_n0	C_n1	C_n2	…	C_nn

Шаг 0. Первоначально считаем, что все концентраторы закрыты, а терминалы присоединены к ЭВМ - к К₀. Затраты на создание такой сети равны сумме соединения терминалов с ЭВМ формула (1.18), т. е. сумме элементов столбца, соответствующего К₀, т. е.

_(1.18)

Итерация 1.

Действия этой итерации оценивают решения открытия одного концентратора (сначала К1 затем К2,...), при этом к нему должны быть присоединены те терминалы, для которых такое присоединение даст наибольший эффект, который возникает за счет уменьшения стоимости линий связи. Итерация состоит из числа шагов, равного числу концентраторов.

Шаг 1. Откроем К1. Эффект от изменения присоединения Si к К1 вместо К0 определим по формуле (1.19):

_{. (1.19)}

Очевидно, что присоединить к К1 целесообразно только те Si, для которых подсчитанные разности (1.20) будут положительными. Однако число таких присоединяемых Si ограниченно r1. Подсчитаем эффект, учитывая затраты f1 на создание концентратора К1.

_{. (1.20)}

Таким образом, выбранные Т_r, терминалы с наибольшей разностью с, будут присоединены к концентратору К1.

Шаг 2. Откроем К2 соотношение (1.21)

_{. (1.21)}

Выбираем r наибольших разностей и подсчитываем новое значение функции стоимости по формуле (1.22):

_(1.22)

Таким образом, выбранные Т_r, терминалы с наибольшей разностью с, будут присоединены к концентратору К2.

Шаги продолжаются пока не будут открыты все n концентраторы К_n.

Последним шагом будет выбор наилучшего варианта с наименьшей стоимостью.

Шаг 3. Выбираем наилучший вариант прикрепления по соотношения (1.23):

_(1.23)

что соответствует терминалам, которые подсоединены к концентратору→Кn , привести рисунок.

Итерация 2.

Считая открытым концентратор К1, будем открывать по очереди еще по
одному концентратору.

Шаг 1. При открытом в итерации 1 концентраторе К_n1 откроем все неоткрытые концентраторы по очереди ( аналогично предыдущей итерации).

(C_i₀-C_i₁), для i, не присоединенных к K_j;

(C_gi-C_g₁), для g=1,…,k, т.е. для тех T_i, которые присоединены к K_j.

Выбираем r наибольших разностей и подсчитываем новое значение функции стоимости:

Шаги продолжаются, пока не будут открыты все n концентраторы К_n при одном открытом.

Последним шагом будет выбор наилучшего варианта с наименьшей стоимостью.

Шаг 3. Выбираем наилучший вариант прикрепления:

что соответствует терминалам, которые подсоединены к концентратору→Кn , привести рисунок.

Итерация 3.

Откроем концентратор К при открытых двух из предыдущих итераций. Подсчитаем целесообразность подсоединения к ним оставшихся терминалов.

Шаг 1. При открытых двух терминалах открываем оставшиеся по очереди.

Выбираем r наибольших разностей и подсчитываем новое значение функции стоимости:

Шаги продолжаются, пока не будут открыты все n концентраторы К_n при одном открытом.

Последним шагом будет выбор наилучшего варианта с наименьшей стоимостью.

Шаг 3. Выбираем наилучший вариант прикрепления:

Проверяем целесообразность открытия последнего концентраторы и его влияние на целевую функцию( если его открытие увеличивает ее значение, в качестве оптимального можно принять вариант сети с открытыми предыдущими концентраторами, а этот оставить закрытым).

Пример решения задач синтеза централизованных сетей

Пусть задано 5 терминалов и 3 концентратора, к каждому из которых можно присоединить по 2 терминала. В таблице 1.2 приведена матрица затрат.

Таблица 1. 2 – Матрица затрат

	К₀	К₁	К₂	К₃
Т₁	8	4	6	6
Т₂	10	5	3	8
Т₃	3	4	0	7
Т₄	4	12	6	1
Т₅	12	10	8	0

f1=4; f2=3; f3=2; r=2.

Шаг 0. Присоединим все терминалы к ЭВМ (см. рисунок 1.5) и подсчитаем затраты:

F0=∑С_i0=8+10+3+4+12=37.

Рисунок 1.7 – Схема подключения всех терминалов к ЭВМ

Итерация 1.

Шаг 1. Откроем К1.

C₁₀- C₁₁=8-4=4;

C₂₀- C₂₁=10-5=5;

C₃₀- C₃₁=3-4=-1;

C₄₀- C₄₁=4-12=-8;

C₅₀- C₅₁=12-10=2.

Выберем две наибольших разности и подсчитаем новое значение функции стоимости:

F₁₁=37-(C10-C11)-(C20-C21)+f1=37-4-5+4=32,

T₁, T₂=>K₁.

Шаг 2. Откроем К₂:

C₁₀- C₁₂=8-6=2;

C₂₀- C₂₂=10-3=7;

C₃₀- C₃₂=3-0=3;

C₄₀- C₄₂=4-6=-2;

C₅₀- C₅₂=12-8=4;

Выберем две наибольшие разности, соответствующие варианту прикрепления Т₂ и Т₅ к К₂.

F₂₁=37-(C₂₀-C₂₂)-(C₅₀-C₅₂)+f₂=37-7-4+3=29,

T₂, T₅=>K₂.

Шаг 3. Откроем концентратор К₃:

C₁₀- C₁₃=8-6=2;

C₂₀- C₂₃=10-8=2;

C₃₀- C₃₃=3-7=-4;

C₄₀- C₄₃=4-1=3;

C₅₀- C₅₃=12-0=12.

F₃₁=37-(C₄₀-C₄₃)-(C₅₀-C₅₃)+f₃=37-3-12+2=24,

T₄, T₅=>K₃.

Шаг 4. Выберем наилучший вариант прикрепления:

{F₁’, F₂’, F₃’}= {32,29,24}=24,

что соответствует T₄, T₅=>K₃ (см. рисунок 1.6).

Рисунок 1.6 – Открытие концентратора К₃

Итерация 2.

Шаг 1. При открытом К₃ откроем К₁: подсчитаем C_i0-C_i1 для i=1,2,3; C_i3-C_i1 для i=4,5.

C₁₀- C_i1=8-4=4, C₄₃- C₄₁=1-12=-11,

C₂₀- C₂₁=10-5=5, C₅₃- C₅₁=0-10=-10,

C₃₀- C₃₁=3-4=-1,

F₃,₁₂=24-(C₁₀-C₁₁)-(C₂₀-C₂₁)+f₁=24-4-5+4=19,

T₁, T₂=>K₁.

Шаг 2. При открытом К₃ откроем К₂: подсчитаем C_i0-C_i2 для i=1,2,3; C_i3-C_i2 для i=4,5.

C₁₀- C_i2=8-6=2, C₄₃- C₄₂=1-6=-5,

C₂₀- C₂₂=10-3=7, C₅₃- C₅₂=0-8=-8,

C₃₀- C₃₂=3-0=3,

F_3,22=F₃₁-(C₂₀-C₂₂)-(C₃₀-C₃₂)+f₂=24-7-3+3=17,

T₂, T₃=>K₂.

Шаг 4.

{F₃₁₂, F₃₂₂}= {19,17}=17, T₂, T₃=>K₂ (см. рисунок 1.7).

Рисунок 1.9 – Открытие двух концентраторов К₂ и К₃

Итерация 3.

Откроем концентратор К₁ при открытых К₂ и К₃. Подсчитаем целесообразность подсоединения к нему всех терминалов:

C₁₀- C₁₁=8-4=4;

C₂₂- C₂₁=3-5=-2;

C₃₂- C₃₁=0-4=-4 ; C₄₃- C₄₁=1-12=-11;

C₅₃- C₅₁=0-10=-10;

Положительная разность только одна:

F_33,2,1=F_23,2=(C₁₀-C₁₁)+f₁=17-4+4=17.

Поскольку открытие К₁ не уменьшит целевую функцию, в качестве оптимального можно принять любой вариант сети- при открытых концентраторах К₂и К₃ (см. рисунок 1.9) или открытых всех трех концентраторах (см. рисунок 1.10), F_3,2,13=17.

Рисунок 1.10 – Открытие всех концентраторов

2. Расчетно – графическая работа 2

2.1 Задание к расчетно – графической работе 2

Построить план распределения каналов вторичной сети для первичной сети, структура которой определена графом с учетом дополнительных ограничений.

Варианты задания приведены в приложении В. Вариант выбирается по последней цифре зачетной книжки.

2.2 Указание к выполнению задания РГР 2

Задача создания вторичных некоммутируемых сетей актуальна как для сетей передачи индивидуальных сообщений, так и для сетей передачи массовых сообщений. При синтезе некоммутируемых вторичных сетей необходимо на базе каналов заданной емкости первичной сети образовать путем кроссирования в узлах пучки прямых каналов необходимой емкости.

Сформулированная задача называется задачей построения плана распределения каналов вторичной некоммутируемой сети. Для ее формирования и решения введем некоторые обозначения.

Структуру первичной сети будем изображать в виде графа (см. рисунок 2.1), ребрам которого приписывают некоторые значения веса (стоимости, длины) и пропускные способности в числе каналов. Для примера рассмотрим сеть, состоящую из 6 вершин и 8 ребер. Пусть емкость каждого ребра равна 20 каналам. Необходимо построить план распределения каналов, при котором емкость пучка между вершинами 1 и 3 равнялась 18, между вершинами 3 и 6 равнялась 16, между вершинами 2 и 4 равнялась 15, между вершинами 5 и 6 равнялась 16, т.е. Y₁₃=18, Y₃₆=16, Y₂₄=15, Y₅₆=16; при этом число транзитных участков в каждом пути не должно превышать трех.

Путь между вершинами i и j будем представлять упорядоченным набором узлов (или набором ребер).

Рисунок 2.1 – Исходная сеть

Например, вершины 3 и 6 могут быть соединены путями:

µ¹₃₆={3,2,6}; µ²₃₆={3,5,1,2,6}; µ³₃₆={3,5,1,4,6};

µ⁴₃₆={3,2,1,4,6}; µ⁵₃₆={3,4,6}; µ⁶₃₆={3,4,1,2,6}.

Рангом пути называется количество входящих в него ребер. В соответствии с определением:

r(µ¹)=2; r(µ²)=4; r(µ³)=4; r(µ⁴)=4; r(µ⁵)=2; r(µ⁶)=4.

По соображениям качества связи ранг пути часто ограничивается, в частности, для рассмотрения задачи необходимо при построении пучка прямых каналов использовать только пути, ранг которых не превышает 3, т.е. пути µ¹₃₆ и µ⁵₃₆.

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

Шаг 1. Для каждой пары вершин (i и j), для которой необходимо построить пучок прямых каналов, строится множество путей и выбираются те из них, чей ранг удовлетворяет ограничению.

Шаг 2. Требуемое количество каналов Y_ij делится поровну между путями.

Шаг 1 – 2 выполняется для всех пар (ij).

Шаг 3. Строится матрица емкостей допустимых путей, представляющая собой таблицу, строки которой соответствуют путям µ_i,…,k, а столбцы – ребрам графа. На пересечении строки µ_ij,…,k, и столбца (ij) записывается число каналов заданного ребра соотношение (2.1), выделенных для данного пути, т.е.

x^ij_µij,…,k. (2.1)

Сумма элементов каждого столбца показывает количество каналов этого ребра. Этот план распределения каналов построен без учета ограничений на количество каналов и называется идеальным.

Шаг 4. Проверяются выполнения ограничений на каждом ребре. Если они выполняются, задача решена, переход к шагу 6 – конец решения. В противном случае переход к шагу 5.

Шаг 5. Для перенасыщенных ребер производится нагрузка (если возможно) и переход к шагу 4. Если разгрузить некоторые ребра невозможно – переход к шагу 7.

Шаг 6. Решение окончено. Выдается план распределения каналов.

Шаг 7. Решение невозможно из – за недостаточной емкости сети.

Проиллюстрируем выполнение алгоритма описанным примером.

Шаг 1. Построим множество путей рагном r≤3

µ¹₁₃={1,2,3}; µ²₁₃={1,5,3}; µ³₁₃={1,4,3};

µ¹₃₆={3,2,6}; µ²₃₆={3,4,6};

µ136={2,3,4}; µ224={2,1,4}; µ324={2,6,4};

µ¹₅₆={5,1,2,6}; µ²₅₆={5,1,4,6}; µ³₅₆={5,3,2,6}; µ⁴₅₆={5,3,4,6}.

Шаг 2. Количество каналов делится поровну на все пути

X₁₂₃=x₁₅₃=x₁₄₃=18/3=6;

X₃₂₆=x₃₄₆=16/2=8;

X₂₃₄=x₂₁₄=x₂₆₄=15/3=5.

Шаг 3. Построим матрицу емкости (см. таблица 2.1)

Столбцы матрицы соответствуют ребрам заданной емкости: (1 – 2), (1–4), (1 – 5), (2 – 3)…, а строки путям µ^k_i,j: в 1 строке в столбцах (1 – 2) и (2 – 3) записано число каналов, равное 6, во II строке - в столбцах (1 – 4) и (3 – 4) и т.д.

Шаг 4. Просуммируем количество каналов в каждом столбце и, учитывая, что емкость каждого ребра равна 20, проверим условие (2.2)

_(2.2)

где М – множество всех допустимых путей, проходящих через ребро (i-j).

Подсчитаем _{по формуле (2.3)}

_(2.3)

И запишем в строку. Отрицательная величина говорит о недопустимости анализируемого плана распределения каналов и необходимости его корректировки. Например, в столбце, соответствующему ребру (1-2), число каналов равно

6+5+4=15.

И в строке поставим

20 – 15=5,

а в столбце (2-3)

6+8+5+4=23,

=20 – 23=-3.

Следовательно, ребро (2-3) перегружено.

Дальнейшие действия – последовательно переместить каналы с перегруженного пути на недогруженный путь того же потока (шаг 5).

Шаг 5 (I). Снимаем лишнюю нагрузку (3 канала) с ребра (2-3), входящего в путь µ_1,2,3, и, следовательно, со всех ребер этого пути (в матрице зачеркнули цифры 6 и записали 3). Добавим эти каналы (3) к недогруженным ребрам пути этого же пучка Y₁₃, т.е. к каналам ребер (1-5) и (3-5).

Шаг 4 (II). Подсчитаем элементы строки ² . Отрицательными являются ²_2-6 и ²_4-6.

Шаг 5(II). Уменьшим на 1 количество каналов в пути µ_2,4,6, добавив в пути µ_2,1,4, на ребрах (1-2) и (1-4).

Шаг 4 (III). Подсчитав ³, видим, что перегружено только ребро (3-4).

Таблица 2.1 – Матрица емкости

Y_ij	Емкость пути	Ребра
Y_ij	Емкость пути	1-2	1-4	1-5	2-3	2-6	3-4	3-5	4-6
Y₁₃	X_1,2,3	6 3			6 3
	X_1,4,3		6 3				6 3
	X_1,5,3			6 9 12				6 9 12
Y₃₆	X_3,2,6				8	8
Y₃₆	X_3,4,6						8		8
Y₂₄	X_2,3,4				5		5
	X_2,1,4	5 6	5 6
	X_2,6,4					5 4			5 4
Y₅₆	X_5,1,2,6	4		4		4
	X_5,1,4,6		4	4					4
	X_5,3,2,6				4	4		4
	X_5,3,4,6						4	4	4
	∆X¹_ij	+5	+5	+6	-3	-1	-3	+6	-1	ПРК не допустим
	∆X²_ij	+8	+5	+3	0	-1	-3	+3	0	ПРК не допустим
	∆X³_ij	+7	+4	+3	0	0	-3	+3	0	ПРК не допустим
	∆X⁴_ij	7	7	0	0	0	0	0	0	ПРК допустим

Шаг 5 (III). Уменьшив количество каналов в пути µ_1,4,3, увеличим в µ_1,5,3.

Шаг 4 (IV). Проверка показала, что перегруженных ребер нет, следовательно, план допустим.

Шаг 6. Решение окончено: построен план распределения каналов, удовлетворяющий заданным условиям.

Следует отметить, что полученное решение не единственное: поскольку мы не оценивали его никакими экономическими показателями, то нельзя говорить об оптимальности решения – получено одно из допустимых решений.

Решение можно не описывать так подробно, но в таблице должны быть отражены все шаги.

3. Расчетно – графическая работа 3

3.1 Задание к расчетно – графической работе 3 Автоматизированные системы проектирования.

Настоящая расчетно – графическая работа состоит в выполнении 2 заданий:

1) расчет целесообразности и (или) эффективности автоматизации проектирования подсистемы Х;

2) для задачи решаемой в магистерской диссертации описать:

-техническое предложение и ТЭО (технико экономическое обоснование необходимости решения задач);

- техническое задание (наименование, область применения и требование к задаче);

- технический проект;

- рабочий проект (блок схемы программы с распечаткой программы);

- ввод в действие САПР – организационное обеспечение (кто внедряет, кто принимает, где информация и пр.);

Варианты задания приведены в приложении В. Вариант выбирается по последней цифре зачетной книжки.

3.2 Указание к выполнению задания РГР 3 задача №1

Системы автоматизированного проектирования - сложные системы, создание которых сопряжено с затратами больших стоимостных и временных ресурсов, поэтому прежде, чем приступать к их разработке, необходимо оценить затраты и ожидаемый эффект. Целесообразность построения конкретной САПР оценивается по специальной методике [7].

Цель работы: ознакомиться с методическими материалами по экономической оценке САПР, соответствующими ГОСТами, и освоить алгоритмы расчета целесообразности и экономической эффективности САПР. Методика расчета экономической эффективности САПР зависит от стадии создания или использования этой системы. В начале проектирования должен решаться вопрос о целесообразности создания САПР. При этом учитываются следующие сферы проявления эффекта:

- период проектирования (или конструирования);

- период строительства (создания) объекта;

- период эксплуатации объектов, спроектированных с помощью САПР.

Применение САПР в процессе проектирования позволяет сократить сроки и стоимость проектирования за счет автоматизации проектных процедур, но главное повысить качество проектирования за счет многовариантной проработки и оптимизации проектных решений, приводящих к сокращению капитальных вложений во время строительства и текущих затрат в период эксплуатации.

Экономическая эффективность использования САПР характеризуется следующими основными показателями, такими, как:

1) экономическая эффективность использования САПР:

- годовой экономический эффект, Э_ГОД ;

- срок окупаемости капитальных вложений, Т_ОК;

2) показатели влияния САПР на характеристики производственно–хозяйственной деятельности проектной организации:

- рост производительности труда проектировщика, L;

- общее изменение трудозатрат в расчетном году, ∆Q;

- общее изменение себестоимости проектирования, ∆C;

3) показатели влияния САПР на качество проектных решений:

- годовая экономия от снижения сметной стоимости строительства, ∆K;

- годовая экономия от снижения эксплуатационных расходов, ∆S;

- общая экономия от повышенная качества проектных решений, ∆K+∆S.

В настоящей расчетно – графической работе будет рассмотрено 2 аспекта: оценка целесообразности создания компонента САПР (I стадия) и оценка экономической эффективности внедрения САПР (II стадия).

Алгоритм оценки целесообразности создания компонента САПР

Алгоритм оценки целесообразности создания САПР для некоторой задачи (подсистемы) состоит из следующей последовательности операции:

- оценить общее изменение себестоимости проектирования, (тыс.тенге);

- оценить годовую экономию от снижения сметной стоимости строительства, (тыс. тенге);

- оценить годовую экономию от снижения эксплуатационных затрат на объектах,_;

- оценить затраты, связанные с САПР, W.

Подсчитать показатели эффективности по формуле (3.1) и период окупаемости (3.2).

(тыс. тенге), (3.1)

. (3.2)

Таблица 3.1 – Описание параметров

Показатели	Размерность	Обозначение
Число реализаций рассматриваемой задачи в год	шт/год	А
Число задач в год	шт/год	Н
Средняя зарплата проектировщика	тыс.тенге/день	Z
Стоимость Эксплуатации САПР	тыс.тенге/год	Э
Число реализаций проекта	шт/год	N
Трудозатраты: базовой вариант, вариант САПР	чел-час/реал	Q₁ Q₂
Сметная стоимость объекта: базовый вариант, вариант САПР	тыс.тг.	K₁ K₂
Эксплуатационные расходы: базовый вариант, вариант САПР	тыс.тг.	S₁ S₂
Коэффициент загрузки ЭВМ: базовая технология, САПР		β₁ β₂
Цена ЭВМ	тыс.тг.	Ц
Затраты на разработку САПР	тыс.тг.	F
Затраты на подготовку специалистов	тыс.тг.	P
Коэффициент загрузки ЭВМ		β
Дополнительные затраты на ВТ	тыс.тг.	C
Срок строительства объекта	лет	T₁
Срок эксплуатации	лет	T₂
Объем машинного времени: базовая технология, САПР	час/реал	M₁ M₂
Цена 1 часа машинного времени	тыс.тг/час	Z₁

Описанные показатели рассчитываются по следующим формулам (3.3)

(3.3)

где Q₁,Q₂– трудозатраты на выполнение проектирования подсистем в традиционном и автоматизированном режиме, чел. – час/реал.;

А – количество реализаций задач, шт/год;

Н – количество задач решаемых в год, шт/год;

Z – среднедневная зарплата проектировщика, тыс.тенге/год.

Описание параметров приведено в таблице 3.1.

Эффект в сфере строительства и эксплуатации подсчитывается по формулам (3.4) и (3.5)

(3.4)

(3.5)

где ∆S и ∆К – разность эксплуатационных и капитальных затрат по подсистеме в базовом (S₁, K₁) и автоматизированном вариантах, тыс. тг.;

А – количество реализаций;

Н – количество задач;

λ_1,λ₂– коэффициенты приведения капитальных и эксплуатационных затрат в зависимости от сроков продолжительности строительства и эксплуатации Т₁ и Т₂. Значения λ приведены в таблице 3.2.

Таблица 3.2 - Капитальные и эксплуатационные затраты

Т	λ₁	λ₂
1	0,8264	0,8264
2	1,5777	0,7513
3	2,2607	0,6830
4	2,8316	0,6209
5	3,4461	0,5645
6	3,9593	0,5132
7	4,4598	0,4665

Капитальные затраты, связанные с внедрением САПР, определяются по формуле (3.6)

(3.6)

где F – затраты на разработку САПР, тыс.тг;

P – затраты на подготовку специалистов;

С – приобретение вычислительной техники, строительство помещений и прочее, тыс.тг;

β – коэффициент загрузки ЭВМ.

Целесообразность создания САПР определяется продолжительностью Э_год (формула 3.1) и величиной срока окупаемости Т_ок, которая должна быть меньше 7 лет (для объектов связи).

Для иллюстрации описанной методики рассмотрим небольшой пример.

3.3 Пример определения целесообразности автоматизации решения некоторой задачи R

3.3.1 Стадия I

Дано:

А=2; Н=10; Q₁=10; Q₂=0,5; Z=1000 тг/день; Э=5000 тг/год; F=60000 тг/год; Р=2000тг; С=130000 тг; β=0,002.

Подсчитаем:

Поскольку речь в примере идет об автоматизации решения задач, а не о проектировании объекта, ∆S и ∆К равны нулю.

Тогда по формуле 3.1

Определим срок окупаемости по формуле 3.2.

Срок окупаемости капитальных затрат меньше нормативного, следовательно, автоматизация решения задачи R целесообразна.

3.3.2 Стадия II

Определение экономической эффективности использования САПР на II стадии проектирования производится по следующим формулам (3.7-3.11):

(3.7)

(3.8)

(3.9)

(3.10)

(3.11)

3.3.3 Вариант задания определяется следующим образом:

а) если предпоследняя цифра зачетной книжки нечетная, решается задача на стадии I, четная – на II стадии;

б) последняя цифра определяет номер варианта исходной информации в приложении Г.

3.4 Указание к выполнению задания РГР 3 задача №2

3.4.1 ТЭО (технико экономическое обоснование необходимости решения задач)

Стадии создания САПР.

Различают внешнее и внутреннее проектирование (см. рисунок 3.1). К внешнему пректированию относятся следующие стадии:

- предпроектные исследования – производится обследование проектной организации, оформление технического отчета, а также его согласование и утверждение;

- разработка согласование и утверждение технического задания – выполняются совместно разработчиком и заказчиком.

К внутреннему проектированию относятся следующие стадии:

- разработка технического предложения – выбирают и обосновывают оптимальный вариант САПР. Производится разработка комплекта документации, а также согласование и утверждение технического предложения;

- эскизный проект – разрабатывают принципиальные решения по созданию САПР и документации, согласовывают и утверждают эскизный проект;

- технический проект – разрабатывают окончательные решения по созданию САПР и документации, согласовывают и утверждают технический проект;

- рабочий проект – разрабатывают рабочую документацию по САПР, согласовывают и утверждают рабочий проет;

- изготовления отладка и испытания – изготовляют и отлаживают компоненты САПР, производят монтаж, наладку и испытание КСАП, осуществляют подготовку организации к вводу системы в действие;

- ввод в действие – производят опытное функционирование и приемочные испытания САПР.

Рисунок 3.1 – Процесс создания САПР

Рассмотрим более подробно основные стадии создания САПР.

3.4.2 Техническое предложение и ТЭО

Целью технического предложения (ТП) является выбор рациональных вариантов САПР, учитывающих требования технического задания (ТЗ). При разработке ТП выполняются следующие работы:

- анализ процессов автоматизированного проектирования;

-выявление возможных вариантов структуры для САПР на основе разработки модулей, реализующих процессы проектирования;

- выбор рациональных вариантов (варианта) структуры САПР;

-технико – экономическое обоснование выбранного варианта;

- составление дополнительных по сравнению с ТЗ требований к САПР;

- уточнение требований к содержанию работ на последующих стадиях САПР.

Техническое предложение разрабатывает организация, являющаяся главным разработчиком системы, его согласовывают с заказчиком и со всеми заинтересованными организациями. ТП на создание САПР должно содержать следующие разделы:

- общие положения – цель разработки ТП, наименование и дата утверждения ТЗ; назначение, характеристика, область и условия применения создаваемой САПР; описание объекта проектирования в САПР; описание процесса автоматического проектирования; характеристика и анализ вариантов структуры САПР;

- обоснование и описание выбранного варианта;

- технико – экономическое обоснование – основные технико – экономические показатели создаваемой САПР;

- предложения по содержанию и организации работ на последующих стадиях – уточненные по сравнению с ТЗ данные по очередности и содержанию работ.

3.4.3 Техническое задание (наименование, область применения и требование задач)

Техническое задания (ТЗ) является исходным и обязательным документом для создания, приемки или сдачи системы и должно содержать все исходные данные и требования, необходимые для создания САПР. Техническое задание на создание САПР разрабатывает организация – разработчик системы с учетом выполнения предпроектных исследований на основе требований заказчика. ТЗ на создание САПР утверждает заказчик. Полное ТЗ на создание САПР должно содержать следующие разделы:

- наименование и область применения;

- основание для создания;

- характеристика объектов проектирования;

- цель и назначение;

- характеристика процесса проектирования;

- требования к САПР;

- технико – экономические показатели – оценены затраты на создание САПР, источники экономии, ожидаемая эффективность от применения САПР;

- стадии и этапы;

- порядок испытаний и ввода в действие;

- источники разработки;

- приложения.

ТЗ на создание САПР оформляют в соответствии с общими требованиями к текстовым документам.

3.4.4 Технический проект.

На стадии эскизного проекта (ЭП) выполняют:

-принятие основных решений по взаимодействию САПР с другими системами;

-принятие основных технических решений по структуре подсистем САПР, разработку вопросов функционирования подсистем на уровне компонентов;

-описание исходных данных и требований на разработку языков проектирования, алгоритмов, компонентов ИО по подсистемам;

-оформление и утверждение ЭП.

На стадии технического проекта выполняют:

-принятие решений по новому процессу проектирования с обеспечением взаимодействия и совместимости автоматических и автоматизированииых процедур, получение окончательной схемы функционирования САПР в целом;

- разработку структуры и состава подсистем САПР;

-получение окончательной структуры всех видов обеспечений САПР;

-выбор математических моделей объекта проектирования и его элементов;

- разработку алгоритмов проектных операций;

-разработку требований на создание программ реализации процедур проектирования;

-разработку алгоритмов, языков проектирования, компонентов ИО, формирование общесистемного программного обеспечения;

-расчет производительности и выбор режимов работы средств технического обеспечения; определение требований к представлению исходных данных, результатов проектирования и проектных документов;

-оформление и утверждение совокупности документов, составляющих технический проект.

Технический проект включает в себя следующие основные документы:

- ведомость, пояснительную записку;

-схемы процессов проектирования, подсистем и средств обеспечения, спецификации компонентов всех видов обеспечений;

-смету затрат на создание САПР;

-ТЗ на разработку соисполнителями по отдельным компонентам; расчет ожидаемых технико – экономических показателей.

3.4.5 Рабочий проект (блок схемы программы с распечаткой программы)

Рабочий проект (РП) создается на основании технического проекта организацией – разработчиком САПР.

На стадии рабочего проекта проводят:

-разработку детальной структуры САПР, ее подсистем, взаимосвязи с другими системами и ее уточнение;

-построение алгоритмов и структурных схем автоматизированных процессов проектирования;

-формирование МО, ПО,ИО,ОО;

-разработку документации для монтажа, настройки и эксплуатации КСАП;

-создание проектов программ и методик испытаний и опытной эксплуатации;

-оформление и утверждение.

Рабочий проект содержит:

1) ведомость РП; пояснительную записку; спецификацию – перечислены подсистемы, спецификации видов обеспечений; документацию технического обеспечения;

2) документацию ИО – включены спецификация, описание базы данных, инструкции по ее заполнению и введению массивов данных;

3) документацию ПО – приведены спецификация, тексты программ, описание программ, методика испытаний;

4) документацию МО, МТО, ЛО – содержит спецификацию, пояснительную записку, описание языка, подсистемы управления САПР;

5) документацию ОО – даны спецификация программы подготовки специалистов – пользователей САПР;

6) программу и методику испытаний КСАП - содержит технические данные, подлежащие проверке при испытании компонентов САПР, методы контроля;

7) программу и методику опытного функционирования системы и подсистем;

8) комплект эксплуатационных документов.

Изготовление отладку и испытания САПР проводят на основании документации РП.

3.4.6 Ввод в действие САПР – Организационное обеспечение (кто внедряет, кто принимает, где информация и пр.).

Работы на стадии ввода в действие САПР предназначены для обеспечения возможности промышленного функционирования САПР и определения технико – экономических показателей системы. На этой стадии проводят опытное функционирование, приемочные испытания, корректировку, доработку и выпуск эксплуатационных документов, промышленную эксплуатацию и развитие САПР.

Опытное функционирование САПР предполагает проверку работоспособности и взаимодействия подразделений организации с подсистемами САПР, выявление неисправностей и отказов, определение фактических технико – экономических показателей системы и корректировку документации, устранение дефектов, оформление протокола.

Приемочные испытания включают в себя оценку качества разработки КСАП, проверку готовности организации к промышленному функционированию САПР, оценку качества опытного функционирования, проверку документации на САПР. Работа оканчивается вводом в действие системы, оформлением и утверждением протокола опытного функционирования и акта приемки САПР в промышленное функционирование.

ПРИЛОЖЕНИЕ А

1		6
	d₁=20; d₅=-20		d₁=25; d₅=-25
2		7
	d₁=d₂=10; d₃=15; d₄=d₆=-10; d₅=-15		d₁=5; d₂=10; d₃=20; d₄=-25; d₅=d₆=-5;
3		8
	d₁=d₂=15; d₄=d₅=-15		d₁=12; d₂=15 d₆=-27
4		9
	d₁=20; d₂=10 d₇=-30		d₁=40; d₅=-40

ПРИЛОЖЕНИЕ А

(Продолжение)

Продолжение приложения А

d₁=20; d₅=-20

d₁=30; d₅=-30

Приложение Б

№1

	К₀	К₁	К₂	К₃
Т₁	7	4	6	9
Т₂	5	2	0	8
Т₃	2	4	6	5
Т₄	1	4	2	10
Т₅	8	7	4	12
Т₆	7	5	9	0
Т₇	10	6	11	4

r=3; f₁=4; f₂=2; f₃=5

№2

	К₀	К₁	К₂	К₃	К₄
Т₁	7	8	0	6	4
Т₂	4	5	2	5	3
Т₃	9	7	12	3	6
Т₄	12	7	9	0	10
Т₅	4	5	7	3	2
Т₆	7	0	5	4	13
Т₇	10	5	10	11	15

r=2; f₁=1; f₂=5; f₃=4; f₄=2.

№3

	К₀	К₁	К₂	К₃
Т₁	7	4	5	3
Т₂	5	4	7	9
Т₃	12	8	11	0
Т₄	10	4	5	7
Т₅	14	8	6	9
Т₆	8	3	2	4

r=3; f₁=5; f₂=6; f₃=4.

№4

	К₀	К₁	К₂	К₃	К₄
Т₁	5	7	3	0	4
Т₂	6	7	4	2	8
Т₃	8	5	0	10	11
Т₄	10	8	9	13	15
Т₅	15	11	8	12	0
Т₆	8	3	4	5	6

r=3; f₁=4; f₂=5; f₃=6; f₄=2.

№5

	К₀	К₁	К₂	К₃
Т₁	4	0	3	5
Т₂	3	4	2	1
Т₃	2	4	0	6
Т₄	3	2	4	5
Т₅	5	6	3	2

r=2; f₁=2; f₂=3; f₃=2.

№6

	К₀	К₁	К₂	К₃
Т₁	4	2	5	3
Т₂	2	5	3	6
Т₃	5	8	0	7
Т₄	7	4	4	2
Т₅	3	4	5	1

r=2; f₁=6; f₂=2; f₃=3.

№7

	К₀	К₁	К₂	К₃
Т₁	4	0	2	3
Т₂	8	5	4	10
Т₃	7	4	1	2
Т₄	4	5	2	0
Т₅	3	4	2	5
Т₆	9	7	4	3

r=3; f₁=4; f₂=4; f₃=2.

№8

	К₀	К₁	К₂	К₃	К₄
Т₁	4	0	2	2	3
Т₂	8	5	6	4	10
Т₃	7	4	3	1	2
Т₄	4	5	11	2	0
Т₅	3	4	9	2	5
Т₆	9	7	10	4	3

r=2; f₁=3; f₂=2; f₃=3; f₄=4.

№9

	К₀	К₁	К₂	К₃
Т₁	4	0	2	3
Т₂	8	5	4	10
Т₃	5	4	7	9
Т₄	7	4	1	2
Т₅	14	8	6	9
Т₆	3	4	2	5

r=2; f₁=2; f₂=2; f₃=2.

№10

	К₀	К₁	К₂	К₃
Т₁	4	0	3	5
Т₂	3	4	2	1
Т₃	2	4	0	6
Т₄	3	2	4	5
Т₅	5	6	3	2
Т₆	8	3	2	4

r=3; f₁=2; f₂=4; f₃=5.

Приложение В

Задание к РГР 2

№	Структура сети	Y_ij	№	Структура сети	Y_ij
1		Y₂₅=18 Y₁₄=12 Y₁₃=14	6		Y₁₃=41 Y₁₄=28 Y₃₅=17
2		Y₁₃=16 Y₁₅=24 Y₂₄=30	7		Y₁₄=24 Y₂₅=20 Y₃₆=16
3		Y₁₃=16 Y₂₄=18 Y₃₅=32	8		Y₁₃=13 Y₂₆=20 Y₄₆=33
4		Y₁₄=20 Y₂₆=33 Y₃₅=15	9		Y₁₃=32 Y₂₄=18 Y₃₅=12
5		Y₁₄=10 Y₂₆=20 Y₃₅=16	10		Y₁₃=24 Y₅₆=18 Y₁₄=10

Приложение Г

Задание на РГР 3

Показатели	Обоз наче ние	0	1	2	3	4	5	6	7	8	9
Число реализаций	А	1	2	3	5	2	4	3	5	4	2
Число задач в год	Н	15	10	7	3	8	6	12	10	9	6
Средняя зарплата	Z	1	1,5	3	2	1,5	2	1,5	1	2	1
Стоимость Эксплуатации САПР	Э	0,1	0,2	0,2	0,3	0,1	0,2	0,8	0,1	0,2	0,1
Число реализаций проекта	N	1	2	1	1	1	1	2	1	2	1
Трудозатраты: базовой вариант, вариант САПР	Q₁ Q₂	12 5	15 6	20 2	10 5	100 20	10 8	30 8	40 7	16 3	20 8
Сметная стоимость объекта: базовый вариант, вариант САПР	K₁ K₂	1000 800	700 500	8000 7000	3000 2500	2000 1500	4300 3000	1000 700	4000 3500	900 700	4200 3000
Эксплуатационные расходы: базовый вариант, вариант САПР	S₁ S₂	800 600	1000 700	500 400	700 450	600 400	800 550	750 540	400 350	1000 800	850 700
Коэффициент загрузки ЭВМ: базовая технология, САПР	β₁ β₂	0 0,2	0,1 0,4	0,5 0,5	0 0,2	0,2 0,5	0,1 0,6	0,3 0,5	0,4 0,6	0 0,2	0,1 0,3
Цена ЭВМ	Ц	60	120	110	70	80	50	65	80	40	70
Затраты на разработку САПР	F	5	7	4	3,5	8	6	11	20	12	10
Затраты на подготовку специалистов	P	2	3,1	1,7	1,2	3	2	4,1	7	3	3,5
Дополнительные затраты на САПР	C	2	5	4	3,5	6	1,7	2	3,6	4	2
Срок строительства объекта	T₁	1,5	0,9	1,2	2	1,7	3	2,4	3,1	3,7	2,2
Срок эксплуатации	T₂	7	6	4	5	8	10	7	6	9	11
Объем машинного времени: базовая технология, САПР	M₁ M₂	0 3	0 5	0 2,4	1 1	0 4	0 3	2 5	0 4	0 3	0 2
Цена 1 часа машинного времени	Z₁	1	1	1	1	1	1	1	1	1	1

Список литературы

1. Теория сетей связи /Под ред. В. Н. Рогинского. – М.: Радио и связь, 1981.

2. Шварц М. Сети ЭВМ. Анализ и проектирование. – М.: Радио и мвязь, 1981.

3. САПР ЭВМ. Варианты заданий и методические указания. Сост. Земсков Ю. В. – ВПИ ВолгГТУ, 2002.

4. Крук Б.И, Попантонопуло В.Н., Шувалов В.П. Телекоммуникационные системы и сети. Современные технологии. – М.: Горячая линия – Телеком, 2003.

5. Давыдов Г. Б., Рогинский В. Н., Толчан А. Я., Сети электросвязи. – М.: Связь, 1997. – 260 с.

6. Берж К. Теория графов и ее применения. – М.: Иностранная литература, 1962.

7. Методика определения экономической эффективности использования в народном хозяйстве новой техники.

8. Теоретические основы САПР: Учебник для вузов/В.П. Корячко, И. П. Курейчик, И. П. Норенков. – М.: Энергоатомиздат,1987. – 400 с.