Оптимизация потоков в сети связи

КУРСОВАЯ РАБОТА

«Оптимизация потоков в сети связи»

 

Аннотация

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

информация поток помехозащищенность

Содержание

Аннотация

Введение

1. Постановка задачи

2. Математическая модель операции

3. Вычисление коэффициентов целевой функции и системы ограничений

4. Решение задачи симплекс - методом

5. Двойственная задача

6. Экономическая интерпретация двойственности

7. Исследование чувствительности решения к изменению правых частей ограничений

8. Анализ чувствительности решения к изменению коэффициентов целевой функции

9. Граф оптимальных путей

10. Параметрический анализ

Заключение

Список используемой литературы

Введение

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

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

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

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

1. Постановка задачи

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

Большую роль в передаче информации играет пропускная способность кабеля. Именно от неё зависит достоверность, помехозащищённость и эффективность передачи информации. При передаче информации необходимо сохранить ее полностью без потерь.

Таким образом, задана структура связи между шестью коммутаторами: 2, 6- выступают в качестве передатчиков информации; 3, 5 - приёмники информации.

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

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

. Математическая модель операции

Сформируем два потока - два пути, по которым передается информация. Пусть требуется передать следующие два потока: 2→3, 6→5.

φ_2-3=45

φ_6-5=22

Граф сети связи.

Рисунок 1. Граф сети связи

Сформируем матрицу связанности C(i,j). Размер матрицы: 6х6 Элементы матрицы могут принимать только два значения 0 и 1.(i,j)=1 если путь есть,(i,j)=0 если пути нет

Матрица связанности представлена таблицей 1.

Таблица 1 - Матрица связанности

	1	2	3	4	5	6
1	-	1	1	0	0	0
2	1	-	0	1	0	0
3	0	1	-	0	0	0
4	0	0	1	-	1	0
5	0	0	0	1	-	1
6	0	0	1	1	0	-

Вместо пропускной способности введём полезность пути, которая является обратной величиной пропускной способности. Матрица защищенности от помехи представлена в таблице 2.

Таблица 2. Матрица защищенности от помех

	1	2	3	4	5	6
1	-	100	80	0	0	0
2	30	-	0	75	0	0
3	0	60	-	0	0	0
4	0	0	60	-	100	0
5	0	0	0	70	-	65
6	0	0	35	25	0	-

Матрица стоимости информации представлена в таблице 3.

Таблица 3 - Матрица стоимости передачи информации

	1	2	3	4	5	6
1	-	9	17	0	0	0
2	8	-	0	10	0	0
3	0	15	-	0	0	0
4	0	0	10	-	5	0
5	0	0	0	7	-	8
6	0	0	12	6	0	-

Требования на потоки информации задается в виде матрицы заданного количества передаваемой информации, представленной таблицей 4.

Таблица 4. Матрица заданного количества передаваемой информации

	1	2	3	4	5	6
1	0	0	0	0	0	0
2	0	0	45	0	0	0
3	0	0	0	0	0	0
4	0	0	0	0	0	0
5	0	0	0	0	0	0
6	0	0	0	0	22	0

Чтобы построить математическую модель, необходимо выделить все возможные пути передачи информации, которые представляют собой деревья путей. На рисунке 2 изображены деревья путей для потоков.

Рисунок 2. Деревья путей для потоков

φ _2-3: φ₁(2-4-3); φ₂(2-1-3);

φ _6-5: φ₃(6-4-5); φ₄(6-3-2-4-5);

где φ_i путь между начальным и конечным пунктом через промежуточные.

В качестве переменных X_i будет удобно выбирать количество информации, передаваемой по i-ому пути. Число переменных определяется количеством путей, по которым возможна передача информации.

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

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

Таблица 5. Таблица путей

φ	Пути	Xi	b24	b43	b21	b13	b64	b45	b63	b32
			75	60	30	80	25	100	35	60
			10	10	8	17	6	5	12	15
f2-3	2-4-3	Х1	10	10							20
	2-1-3	Х2			8	17					25
f6-5	6-4-5	Х3					6	5			11
	6-3-2-4-5	Х4	10					5	12	15	42

3. Вычисление коэффициентов целевой функции и системы ограничений

Составим систему ограничений, содержащую следующие требования:

1)       потоки передаваемой информации не могут принимать отрицательных значений, т.е. X_i≥0;

2)      суммарный поток информации между заданной парой узлов, подставленный, в виде суммы потоков по каждому из путей, должен быть равен требуемому потоку информации φj между парой узлов, т.е.:

X1 +X2 = φ_2-3 =45;

X3 +X4 = φ_6-5 =22;

3)      для любой ветви сети связи суммарный поток информации, образованный путями, проходящими через эту ветвь, не может превышать пропускной способности этой ветви, поэтому из таблицы путей следует:

Х1+Х4≤ 75;

X3+Х4≤ 100;

X1 ≤ 30;

X2 ≤ 60;

X3 ≤ 25;

X4 ≤ 35.

Так как необходимо минимизировать стоимость передачи информации по сети, целевую функцию следует максимизировать. Это объясняется следующим образом: чем ниже стоимость передачи для ветви, тем выше ценность данной ветви. Таким образом, получим:

 Xi ³ 0, i = 1, 4;

X1 +X2=45;

X3 +X4 =22;

Х1+Х4≤ 75;

X3+Х4≤ 100;

X1 ≤ 30;

X2 ≤ 60;

X3 ≤ 25;

X4 ≤ 35.

F = 0,05 X1 + 0,04X2 + 0,091X3 + 0,024X4 → max

В данной системе присутствуют два равенства, а для решения задачи методами линейного программирования лучше использовать все неравенствами. Поэтому необходимо вести две вспомогательные переменные, которые войдут в целевую функцию с нулевыми коэффициентами. После этого знак равенства можно заменить на знак «меньше или равно»:

Xi ³ 0, i = 1, 4;

X1 + X2 + Х5 ≤ 45;

X3 + X4 + Х6 ≤ 22;

Х1+Х4≤ 75;

X3+Х4≤ 100;

X1 ≤ 30;

X2 ≤ 60;

X3 ≤ 25;

X4 ≤ 35.

F = 0,05 X1 + 0,04X2 + 0,091X3 + 0,024X4 → max

4. Решение задачи симплекс - методом

Для решения задачи симплекс-методом составляется исходная симплекс-таблица, содержащая М строк и N столбцов. В нее заносятся коэффициенты системы ограничений и целевой функции с соответствующими знаками. Переменные, расположенные в верхней строке симплекс-таблицы, являются свободными, т.е. независимыми переменными, а переменные в крайнем левом столбце таблицы называются базисными. Так как у нас имеется два равенства, то введем две дополнительные переменные.

Таблица 6. Исходная симплекс-таблица:

	-x1	-x2	-x3	-x4	-x5	-x6	B
Y1	1	1	0	0	1	0
Y2	0	0	1	1	0	1	22
Y3	1	0	0	0	0	0	30
Y4	0	1	0	0	0	0	60
Y5	0	0	1	0	0	0	25
Y6	0	0	0	1	0	0	35
Y7	1	0	0	1	0	0	75
Y8	0	0	1	1	0	0	100
Fmax	-0,05	-0,04	-0,09	-0,02	0	0	0

Таблица 7. Конечная симплекс-таблица:

	-Y1	-X2	-Y2	-X4	-X5	-X6	B
Х1	1	-1	0	0	1	0	45
Х3	0	0	1	-1	0	1	22
Y3	-1	1	0	0	-1	0	5
Y4	0	1	0	0	0	0	15
Y5	0	0	-1	1	0	-1	25
Y6	0	0	0	1	0	0	30
Y7	0	-1	-1	1	0	-1	40
Y8	0	-1	0	0	0	-1	70
Fmax	0,05	0,01	0,09	0	0,04	0,02	4.25

Имеем оптимальные пути решения задачи:

По пути Х1 (2 - 4 - 3) = 45,

По пути Х3 (6 - 4 - 5) = 22

Значение целевой функции F _max = 4.25 - максимальная ценность передачи информации

. Двойственная задача

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

В двойственной задаче необходимо найти значения переменных Y_i*(i=1,M-1), удовлетворяющие системе , где Y_i*≥0(i=L+1,M-1), Y_i*(i=1,L) не ограничены в знаке, и обеспечивают минимальное значение целевой функции , при этом Fmax = -Фmin. Таким образом, для данной задачи двойственная ей будет иметь вид.

Целевая функция:

Ф_min=45Y1*+22Y2*+30Y3*+60Y4*+25Y5*+35Y6*+75Y7*+100Y8*→min

Ограничения:

Y1*+Y3*+Y7*≥0,05;*+Y4*≥0,04;

Y2*+Y5*+ Y8*≥0,09;

Y2*+Y6*+Y7*+Y8*≥0,02;

Y1≥0;

Y2≥0;

Yi*≥0, где i=1,8

Если исходную симплекс-таблицу прямой задачи представить в матричном виде:

  

А - матрица коэффициентов ограничений.

Исходную симплекс-таблицу двойственной задачи можно записать в виде:

  

Отсюда следует, что решение двойственной задачи определяется из конечной симплекс-таблицы прямой задачи и наоборот. Если формально в качестве дополнительных переменных для ограничений задачи использовать переменные , а в качестве дополнительных переменных для ограничений двойственной задачи - переменные Хj*, то при решении двойственной задачи симплекс-таблицу на любой итерации симплекс-метода можно рассматривать как транспонированную симплекс-таблицу прямой задачи. При этом коэффициенты строки целевой функции и столбца свободных членов транспонируются без изменения, а все остальные коэффициенты таблицы одновременно с транспонированием меняют знаки на противоположные.

Таблица 8. Исходная симплекс-таблица двойственной задачи:

	-Y1*	-Y2*	-Y3*	-Y4*	-Y5*	-Y6*	-Y7*	-Y8*	B
X1*	-1	0	-1	0	0	0	-1	0	-0,05
X2*	-1	0	0	-1	0	0	-1	0	-0,04
X3*	0	-1	0	0	-1	0	0	-1	-0,09
X4*	0	-1	0	0	0	-1	0	-1	-0,02
X5*	-1	0	0	0	0	0	0	0	0
X6*	0	-1	0	0	0	0	0	0	0
Фmin	45	22	30	60	25	35	75	100	0

Таблица 9. Конечная симплекс-таблица двойственной задачи:

	-X1*	-X3*	-Y3*	-Y4*	-Y5*	-Y6*	-Y7*	-Y8*	B
X2*	-1	0	1	-1	0	0	0	0	0,01
Y1*	-1	0	1	0	0	0	1	0	0,05
X4*	0	-1	0	0	1	-1	0	0	0
Y2*	0	-1	0	0	1	0	0	1	0,09
X5*	-1	0	1	0	0	0	1	0	0,04
X6*	0	-1	0	0	0	0	0	0	0,02
Фmin	45	22	5	15	25	30	40	70	-4.25

Решение двойственной задачи:* =0,05; Y2* =0,09; Y3* =0; Y4* =0; Y5* =0; Y6* =0; Y7* =0; Y8* =0;

Значение целевой функции для двойственной задачи: Фmin= - 4,25.

. Экономическая интерпретация двойственности

Полученные значения переменных двойственной задачи: Y1*=0,05 и Y2*=0,09 показывают, насколько изменится целевая функция прямой задачи при изменении на единицу полезности соответственно первой и второй ветвей. Значения Y3*=0; Y4*=0; Y5*=0; Y6*=0; Y7*=0 и Y8*=0 свидетельствуют о том, что изменение данного вида ресурса (пропускных способностей соответствующих путей) не приводит к изменению целевой функции. Это свидетельствует о том, что данный ресурс использован не полностью для получения оптимального решения, т.е. имеет место скрытый запас этого вида ресурса. Величина скрытого запаса определяется значением дополнительных переменных Y3=5; Y4=15; Y5=25; Y6=30; Y7=40; Y8=70 в оптимальном решении прямой задачи. Таким образом, положительную, отличную от нуля двойственную оценку имеют те ресурсы, которые полностью используются при оптимальном плане передачи информации, поэтому двойственные оценки определяют дефицитность используемых ресурсов (полезность путей). Левые части ограничений двойственной задачи определяют стоимость каждого пути.

Если в рассматриваемой задаче подставить полученные значения Y1* и Y2* двойственной задачи в ограничения, то имеют место соотношения:

,05=0,05;

,05>0,04;

,09=0,09;

,09>0,024;

,05>0;

,09>0.

Второе, четвёртое, пятое и шестое ограничения двойственной задачи в соотношении выполняются, как строгие неравенства. Это означает, что помехозащищенность этих ветвей оказалась ниже, т.е. передача информации по этим путям нерентабельна, и, как следует из решения прямой задачи, путь четвёртый не предусмотрен сетью (Х4=0). Его необходимо использовать из-за отсутствия других вариантов.

Первое и третье ограничения в соотношении выполняются как строгие равенства. Это означает, что двойственная оценка полезности соответствующих путей в точности соответствует их ценам. Отсюда следует, что передача информации по первому и третьему пути экономически целесообразна и предусмотрена графом путей (Х1=45; Х3=22).

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

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

Анализ чувствительности полученного решения прямой задачи к изменению коэффициентов Вi предполагает, что вычисляются пределы изменения каждого из коэффициентов, при которых опорное решение прямой задачи существует или оптимальное значение переменных двойственной задачи Yi* постоянно.

Решение прямой задачи можно записать через матрицу перехода для конечной симплекс-таблицы в виде:

(*),

[X_В] - столбец базисных переменных конечной симплекс-таблицы;

[P] - матрица переход;

[B₁, …, B_i, …, B_M-1]^T - матрица-столбец свободных членов исходной симплекс таблицы;

[B] - матрица-столбец свободных членов конечной симплекс-таблицы;

Для оценки пределов изменения правых частей ограничений и коэффициентов целевой функции достаточно информации, содержащейся в конечной симплекс-таблице. Для любой итерации симплекс-метода значения базисных переменных могут быть вычислены с помощью матрицы перехода [P]. Матрица перехода [P] формируется из коэффициентов симплекс-таблицы для данной итерации. Это квадратная матрица размерностью (М-1)х(М-1) для прямой задачи и (N-1)x(N-1) - для двойственной. Столбцы матрицы соответствуют дополнительным переменным  прямой задачи или дополнительным переменным  двойственной задачи и располагаются в прямом порядке Y1,Y2, ... ,YM-1 или X1*,X2*, … ,XN-1*. Если дополнительные переменные Yi (или Xj*) для прямой или двойственной задачи на данной итерации являются базисными переменными, то соответствующие им столбцы матрицы перехода [P] состоят из нулей во всех строках, кроме одной, в которой присутствует единица. Номера этих строк совпадают с номерами строк, в которых находятся эти переменные в столбце базисных переменных. Столбцы матрицы перехода [P] для дополнительных переменных Yi (или Xj*), которые для рассматриваемой итерации являются свободными, соответствуют столбцам симплекс-таблицы для данной итерации для этих же переменных. Используя соотношение (*) для конечной симплекс-таблицы прямой задачи и задавая приращения исходным значениям правых частей ограничений Вi+∆Вi можно найти величины этих приращений. Вектор устойчивости опорного решения можно записать в виде:

где [P] - матрица перехода для конечной симплекс-таблицы.

Так как

 

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

 

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

Условие не отрицательности компонент вектора [∆B] приводит к системе неравенств:

+ ∆B1 ³ 0;

+ ∆B2 ³ 0;

-∆B1+30+∆B3 ³ 0;

+∆B4 ³ 0;

- ∆B2 +25 +∆B5 ³ 0;

+ ∆B6 ³ 0;

-∆B1 +75 + ∆B7³ 0;

- ∆B2 + 100 + ∆B8 ³ 0.

Свободные члены данной системы неравенств повторяют столбец свободных членов конечной симплекс-таблицы прямой задачи.

Анализ всех коэффициентов одновременно затруднителен и требует решения сложных систем неравенств. Будем рассматривать изменение только одного коэффициента, например ∆B1, и тогда ∆B1¹0, а остальные ∆Bi=0, i=2, М-1, при таких условиях решается система неравенств для определения допустимых пределов изменения ∆B1. Аналогично исследуются пределы изменения остальных коэффициентов ∆Bi.Для определения пределов изменения целевой функции F прямой задачи, при соответствующих приращениях ∆Bi, используется полученное значение переменных двойственной задачи Yi*. Ранее установили, что каждому i-ому ограничению прямой задачи соответствуют переменные двойственной задачи. Если двойственная переменная Yi* в последней симплекс - таблице двойственной задачи находится в числе свободных и, следовательно, Yi*=С, то приращение целевой функции определяется как ∆F= Yi*∆Bi. Если Yi* находится в числе базисных переменных последней симплекс - таблицы и вычислены допустимые пределы изменения коэффициентов ∆Bi, то есть ∆Bi_min≤∆Bi≤∆Bi_max, то пределы изменения будут ∆Bi_min Yi* ≤∆F≤∆Bi_max Yi*.

Вычислим коэффициенты неравенств для решаемой задачи:

) Пусть ∆B1¹0, ∆Bi=0, i=2…8, тогда получим систему неравенств:

∆B1 ³ -45;

∆B1 ≤ 9;

∆B1 ≤ 63;

отсюда следует, что ∆B1:

≤ ∆B1 ≤ 9, т.е. изменение значений целевой функции будет происходить в пределах ∆B1_min Y1* ≤ ∆F_max≤∆B1_max Y1*, т.е.:

.25 ≤ ∆F_max ≤ 0,45.

) Пусть ∆B2¹0, ∆Bi=0, i=1,3…8, тогда получим систему неравенств:

∆B2 ³ -22;

∆B2 ≤ 3;

∆B2 ≤ 78;

отсюда следует, что ∆B2:

≤ ∆B2 ≤ 3, т.е. изменение значений целевой функции будет происходить в пределах ∆B2_min Y2* ≤ ∆F_max≤∆B2_max Y2*, т.е.:

,98 ≤ ∆F_max ≤ 0,27.

) Пусть ∆B3¹0, ∆Bi=0, i=1,2,4…8, тогда получим систему неравенств:

∆B3 ³ 15;

так как Y3*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

) Пусть ∆B4¹0, ∆Bi=0, i=1..3,5…8, тогда получим систему неравенств:

∆B4 ³ -60;

так как Y4*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

) Пусть ∆B5¹0, ∆Bi=0, i=1..4,6…8, тогда получим систему неравенств:

∆B5 ³ -3;

так как Y5*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

) Пусть ∆B6¹0, ∆Bi=0, i=1..5,7…8, тогда получим систему неравенств:

∆B6 ³ -35;

так как Y6*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

) Пусть ∆B7¹0, ∆Bi=0, i=1..6,8, тогда получим систему неравенств:

∆B7 ³ -30;

так как Y7*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

) Пусть ∆B8¹0, ∆Bi=0, i=1..7, тогда получим систему неравенств:

∆B5 ³ -78;

так как Y8*=0, то изменение значений целевой функции при этом будет равно: ∆F_max=0.

Пусть ∆B1¹0, ∆B2¹0 ∆Bi=0, i=3,4..8, тогда получим систему неравенств:

≤ ∆B1 ≤ 9;

≤ ∆B2 ≤ 3.

Графически решение данной системы можно представить следующим образом:

Рисунок 2. Графическое решение системы

Изменение значений целевой функции будет происходить в пределах

,98 ≤ ∆F_max ≤ 0,27.

Возьмем, для примера, из найденной области точку с координатами ∆B1=-10, ∆B2=-15. Произведем решение задачи с новыми значениями В1=35 и В2=7

Таблица 9. Конечная симплекс-таблица двойственной задачи:

	-X1*	-X3*	-Y3*	-Y4*	-Y5*	-Y6*	-Y7*	-Y8*	B
X2*	-1	0	1	-1	0	0	0	0	0,01
Y1*	-1	0	1	0	0	0	1	0	0,05
X4*	0	-1	0	0	1	-1	0	0	0
Y2*	0	-1	0	0	1	0	0	1	0,09
X5*	-1	0	1	0	0	0	1	0	0,04
X6*	0	-1	0	0	1	0	0	1	0,02
Фmin	35	7	40	60	40	35	85	115	-3,25

Значение рабочей точки не изменилось: Y1*=0,05 и Y2*=0,09.

. Анализ чувствительности решения к изменению коэффициентов целевой функции

Анализ чувствительности полученного решения к изменению коэффициентов целевой функции предусматривает нахождение пределов изменений коэффициентов целевой функции Сj при условии неизменности полученного оптимального решения, т. е. Хi=const.

При исследовании на чувствительность решения к изменению коэффициентов целевой функции Сj прямой задачи удобно использовать решение двойственной задачи. Для двойственной задачи конечная симплекс-таблица в матричном виде может быть записана:

где [Y_B] - матрица-столбец базисных переменных конечной симплекс-таблицы двойственной задачи;

[P*] - матрица перехода базисных переменных конечной симплекс-таблицы двойственной задачи;

[-C1…-Cj…-C_N-1]^T - матрица-столбец исходных коэффициентов целевой функции прямой задачи (в двойственной задаче они играют роль правых частей ограничений);

[C] - матрица столбец конечных значений коэффициентов Сj двойственной задачи (для прямой задачи это конечное значение коэффициентов целевой функции).

Вектор устойчивости оптимального решения двойственной задачи к коэффициентам Сj равен:

Вектор устойчивости коэффициентов Сj может быть записан через матрицу преобразования двойственной задачи [P*] в виде:

Анализ легко осуществлять отдельно для изменения каждого коэффициента Сj.

Матрица перехода  для конечной симплекс-таблицы двойственной задачи имеет вид:

Условие не отрицательности компонент вектора [∆С] приводит к системе неравенств:

0,01 + ∆С1-0,05 -∆С2 ³ 0;

,01 +∆С1 ³ 0;

∆С3 - 0,09 - ∆С4 ³ 0;

∆С3³ 0;

,01 + ∆С1 - 0,04 - ∆С5 ³ 0;

∆С3 - 0,02 - ∆С6 ³ 0.

Свободные члены неравенств совпадают со значениями коэффициентов последнего столбца конечной симплекс-таблицы двойственной задачи.

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

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

) Пусть ∆С1¹0, ∆Сi=0, i=2..6, решая систему неравенств, получим:

∆С1 ³ 0,04;

∆С1 ³ -0,01;

При изменении значения первого коэффициента целевой функции на ∆С1 ³ 0,04, значение целевой функции изменится на   ∆F_max ³ 1,8.

) Пусть ∆С2¹0, ∆Сi=0, i=1,3..6, решая систему неравенств, получим:

∆С2 ≤ -0,04.

Изменение С2 в указанном пределе не приведет к изменению как оптимального решения, так и значения целевой функции (так как X2=0), значит изменение значение целевой функции будет ∆F_max=0.

) Пусть ∆С3¹0, ∆Сi=0, i=1,2,4..6, решая систему неравенств, получим:

∆С3 ³ 0,09;

∆С3 ³ 0;

∆С3 ³ 0,02;

При изменении значения третьего коэффициента целевой функции на ∆С3 ³ 0,09, значение целевой функции изменится на   ∆F_max ³ 1,98.

) Пусть ∆С4¹0, ∆Сi=0, i=1..3,5,6, решая систему неравенств, получим:

∆С4 ≤ -0,09.

Изменение С4 в указанном пределе не приведет к изменению как оптимального решения, так и значения целевой функции (так как X4=0), значит изменение значение целевой функции будет ∆F_max=0.

) Пусть ∆С5¹0, ∆Сi=0, i=1..4,6, решая систему неравенств, получим:

∆С5 ≤ -0,03.

Изменение С5 в указанном пределе не приведет к изменению как оптимального решения, так и значения целевой функции (так как X5=0), значит изменение значение целевой функции будет ∆F_max=0.

) Пусть ∆С6¹0, ∆Сi=0, i=1..5, решая систему неравенств, получим:

∆С6 ≤ -0,02.

Изменение С6 в указанном пределе не приведет к изменению как оптимального решения, так и значения целевой функции (так как X6=0), значит изменение значение целевой функции будет ∆F_max=0.

Пусть ∆С1¹0, ∆С3¹0 ∆Сi=0, i=2,4,5,6, тогда получим систему неравенств:

∆С1 ³ 0,04

∆С3 ³ 0,09

Графически решение данной системы можно представить следующим образом:

Рисунок 3. Графическое решение системы

Изменение значений целевой функции будет происходить в пределах

∆F_max ³ 1,98.

Возьмем, для примера, из найденной области точку с координатами ∆С1=0,05, ∆С3=0,1. Произведем решение задачи с новыми значениями С1 и С3 (0,1, 0,19).

Таблица 10. Конечная симплекс-таблица прямой задачи:

	-Y1	-Х2	-Y2	-Х4	-X5	-X6	B
Х1	1	1	0	0	1	0	65
Х3	0	0	1	1	0	1	38
Y3	-1	-1	0	0	-1	0	9
Y4	0	1	0	0	0	0	56
Y5	0	0	-1	-1	0	-1	5
Y6	0	0	0	1	0	0	33
Y7	-1	0	0	0	-1	0	63
Y8	0	0	-1	0	0	-1	35
Fmax	0,10	0,06	0,19	0,1	0,09	0,12	6,5

Значение рабочей точки не изменилось: Х1=45 и Х3=22.

. Граф оптимальных путей

В соответствии с приведенным решением видно, что потоки φ_2-3, φ_6-5 передаются по оптимальным путям. Можем составить следующий граф:

Рисунок 4. Графическое представление оптимального решения задачи

В результате решения получили следующие значения для потоков:

Х1=45; Х2=0; Х3=22; Х4=0; Х5=0; Х6=0.

Из полученного решения следует, что пропускные способности некоторых путей используются не полностью для передачи двух потоков информации. В результате возникают скрытые запасы соответствующих пропускных способностей, величины которых определяются значением дополнительных переменных Y3=5; Y4=15; Y5=25; Y6=30; Y7=40; Y8=70 в оптимальном решении прямой задачи.

. Параметрический анализ

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

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

Приведем данную задачу и её решение на Excel. Опираясь на условия задачи, введем исходные данные в форму, а также необходимые формулы для расчета левой части и целевой функции, эти данные представлены на рисунке 5.

Рисунок 5 - Формула для расчета целевой функции

После этого заходим в меню СЕРВИС, ПОИСК РЕШЕНИЯ. На экране появляется окно представленное на рисунке 6.

Рисунок 6 - Окно «Поиск решения»

В окне «Поиск решения» устанавливаем целевую ячейку B13. Выбираем направление целевой функции равной: Максимальному значению. Добавляем необходимые ограничения, нажимаем кнопку ВЫПОЛНИТЬ и получаем результат решения представленный на рисунке 7.

Рисунок 7 - Результат поиска решения

В Excel анализ оптимального решения можно осуществить, пользуясь различными отчётами. Так отчёт по устойчивости представлен на таблица 11.

Таблица 11. Отчёт по устойчивости

Изменяемые ячейки
	Ячейка	Имя	Результ. значение	Нормир. градиент
	$A$2	x1	45	0
	$B$2	x2	0	-0,030241933
	$C$2	x3	22	0
	$D$2	x4	0	-0,001315787
	$E$2	x5	0	-0,062499996
	$F$2	x6	0	-0,02631579
Ограничения
	Ячейка	Имя	Результ. значение	Множитель Лагранжа
	$B$4	x2	45	0,0625
	$B$5	x2	22	0,02631579
	$B$6	x2	45	0
	$B$7	x2	0	0
	$B$8	x2	0
	$B$9	x2	0	0
	$B$9	x2	0	0
	$B$11	x2	22	0

В таблице «Изменяемые ячейки» приводятся следующие значения для переменных:

o   результат решения задачи («Результ. значение»);

o   нормированный градиент.

В таблице «Ограничения» приведены аналогичные значения для ограничений:

o   величина используемых ресурсов («Результ. значение»);

o   множитель Лагранжа.

Отчёт по результатам представлен на таблица 12.

Таблица 12 Отчет по результатам

Целевая ячейка (Максимум)
	Ячейка	Имя	Исходное значение	Результат
	$B$13	Fmax x2	4,25	4,25
Изменяемые ячейки
	Ячейка	Имя	Исходное значение	Результат
	$A$2	x1	45	45
	$B$2	x2	0	0
	$C$2	x3	22	22
	$D$2	x4	0	0
	$E$2	x5	0	0
	$F$2	x6	0	0
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$B$4	x2	65	$B$4<=45	связанное	0
	$B$5	x2	38	$B$5<=22	связанное	0
	$B$6	x2	65	$B$6<=30	не связан.	5
	$B$7	x2	0	$B$7<=60	не связан.	15
	$B$8	x2	38	$B$8<=25	не связан.	25
	$B$9	x2	0	$B$9<=35	не связан.	30
	$B$9	x2	0	$B$10<=75	не связан.	40
	$B$11	x2	38	$B$11<=100	не связан.	70
	$A$2	x1	65	$A$2>=0	не связан.	45
	$B$2	x2	0	$B$2>=0	связанное	0
	$C$2	x3	38	$C$2>=0	не связан.	22
	$D$2	x4	0	$D$2>=0	связанное	0
	$E$2	x5	0	$E$2>=0	связанное	0
	$F$2	x6	0	$F$2>=0	связанное	0

Таблица «Целевая функция» приводит сведения о целевой функции. В столбце «Исходное значение» приведены значения целевой функции до начала вычислений.

Таблица «Изменяемые ячейки» приводит значения искомых переменных, полученных в результате решения задачи;

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

В графе «Значение» приведены величины использованной пропускной способности; в графе Разница показано количество неиспользованного ресурса ветви сети. Если пропускная способность используется полностью, то в графе «Состояние» указывается связанное; при неполном использовании - не связанное.

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

Отчёт по пределам представлен на таблица 13. В нем показано, в каких пределах может изменяться объем передаваемой информации, вошедший в оптимальное решение, при сохранении структуры оптимального решения.

Таблица 13 Отчет по пределам

	Целевое
Ячейка	Имя	Значение
$B$13	Fmax x2	4,25
Ячейка	Изменяемое имя	Значение	Нижний предел	Целевой результат	Верхний предел	Целевой результат
$A$2	x1	45	0	1	45	4,25
$B$2	x2	0	0	4,25	0	4,25
$C$2	x3	22	0	3,25	22	4,25
$D$2	x4	0	0	4,25	0	4,25
$E$2	x5	0	0	4,25	0	4,25
$F$2	x6	0	0	4,25	0	4,25

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

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

Таблица 14 - Варианты изменения оценки

Вариант	1	2	3	4
Поток	45	49	53	57

Исходные варианты подставим в правую часть второго ограничения. Полученные значения сохраним в отдельных сценариях (b4=45, b4=49, b4=53, b4=57) и занесем их в таблицу 15.

Таблица 15 - Значения целевой функции

Вариант	1	2	3	4
Поток	45	49	53	57
Значение	4,25	4,5125	4,7625	4,9218

В результате получим итоговый сценарий, который представлен на Таблица 16.

Таблица 16 - Итоговый сценарий

Структура сценария
		Текущие значения:	b4=45	b4=49	b4=53	b4=57
Изменяемые:
	$A$2	54	45	49	53	54
	$B$2	3	0	0	0	3
	$C$2	22	22	22	22	22
	$D$2	0	0	0	0	0
	$E$2	0	0	0	0	0
	$F$2	0	0	0	0	0
Результат:
	$B$4	57	45	49	53	57
	$B$6	54	45	49	53	54
	$B$10	57	45	49	53	57
	$B$13	4,921774194	4,25	4,5125	4,7625	4,921774194

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

Рисунок 8 - Стоимость передачи при различных значениях потока

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

Заключение

Значения целевой функции совпали и в симплекс-методе, и при решении двойственной задачи, и при выполнении расчётов на Excel. Из полученного решения следует, что пропускные способности некоторых путей используются не полностью для передачи двух потоков информации. В результате возникают скрытые запасы соответствующих пропускных способностей, величины которых определяются значением дополнительных переменных в оптимальном решении прямой задачи.

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

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

Список используемой литературы

1) Линейное и целочисленное программирование. Методические указания к лабораторным работам. РГРТА; сост.: Дондик Е.М., Илюхина Г.И. и др., Разань, 2008.

) Линейное и динамическое программирование. Методические указания к лабораторным работам по курсу «Исследование операций». РГРТА; сост.: Дондик Е.М., Илюхина Г.И., Рязань, 1983.

) Вычислительные основы принятия решений. Учебное пособие. Дондик Е.М., РГРТА, Рязань, 2009.

) Математические основы принятия решений. Учебное пособие. Дондик Е.М., РГРТА, Рязань, 2011.

) Системный анализ информационно-управляющих систем. Учебное пособие. Дондик Е.М., РГРТА, Рязань, 2009.