ної здатності введемо корисність шляху, яка є зворотною величиною пропускної здатності. Матриця захищеності від перешкоди представлена ??в таблиці 2.
Таблиця 2. Матриця захищеності від перешкод
1234561-10080000230-075003060-00040060-1000500070-6560035250 -
Матриця вартості інформації представлена ??в таблиці 3.
Таблиця 3 - Матриця вартості передачі інформації
1234561-91700028-010003015-00040010-5050007-86001260 -
Вимоги на потоки інформації задається у вигляді матриці заданого кількості переданої інформації, представленої таблицею 4.
Таблиця 4. Матриця заданої кількості переданої інформації
12345610000002004500030000004000000500000060000220
Щоб побудувати математичну модель, необхідно виділити всі можливі шляхи передачі інформації, які представляють собою дерева шляхів. На малюнку 2 зображені дерева шляхів для потоків.
Малюнок 2. Дерева шляхів для потоків
? 2-3:? 1 (2-4-3); ? 2 (2-1-3);
? 6-5:? 3 (6-4-5); ? 4 (6-3-2-4-5);
де? i шлях між початковим і кінцевим пунктом через проміжні.
У якості змінних X i буде зручно вибирати кількість інформації, переданої по i-ому шляху. Число змінних визначається кількістю шляхів, по яких можлива передача інформації.
Для складання математичної моделі задачі зручно використовувати таблицю шляхів, де кожному потоку відповідає набір шляхів з кількістю переданої інформації X i. Вартість шляху складається з вартості передачі одиниці інформації по кожному з складових гілок.
Таблиця 5 являє собою таблицю шляхів, в ній показано перелік шляхів, необхідних для організації заданих потоків інформації в мережі, зв'язок між шляхами і гілками, що входять до них, а також обчислені відповідні корисності шляху.
Таблиця 5. Таблиця шляхів
? ПутіXi b 24 b 43 b 21 b 13 b 64 b 45 b 63 b 32756030802510035601010817651215 f 2-32-4-3Х11010202-1-3Х281725 f 6-56-4-5Х365116-3-2-4-5Х4105121542
3. Обчислення коефіцієнтів цільової функції і системи обмежень
Складемо систему обмежень, яка містить такі вимоги:
1) потоки переданої інформації не можуть приймати від'ємних значень, тобто X i? 0;
2) сумарний потік інформації між заданою парою вузлів, підставлений, у вигляді суми потоків по кожному з шляхів, повинен бути рівний необхідному потоку інформації? j між парою вузлів, тобто .:
X1 + X 2 =? 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. Рішення завдання симплекс - методом
Для вирішення завдання симплекс-методом складається вихідна симплекс-таблиця, що...
