Зміст
Введення стор 3
1. Постановка задачі 5
2. Віртуальні Семо 6
3. Маршрутні матриці віртуальних Семо 9
4. Методи побудови маршрутних матриць віртуальних Семо 14 e. Загальне рішення 14
6. Приклад знаходження спільного рішення 16
7. Метод формування маршрутної матриці 20
8. Пошук по статистичному градієнту 22
9. Метод "важкого кульки" 22
10. Формування матриці. Опис методу 23
11. Алгоритм програми, що реалізує метод 25
12. Призначення та опис програми OPTIM 29
Висновок 31
Список літератури 32
Додаток 1. Список ідентифікаторів 33
Додаток 2. Текст програми 34
Введення
Широке результативне застосування мереж масового обслуговування (Семо)різних класів [1-2] в якості математичних моделей дискретних системз мережевою структурою і стохастичним характером функціонуванняобумовлює подальший інтенсивний розвиток теорії мереж масовогообслуговування, методів вирішення завдань їх аналізу, синтезу та оптимізації, аяк же методології моделювання дискретних систем мережами масовогообслуговування. Мережі обслуговування, що є моделями відповіднихдискретних систем будемо вважати об'єктними.
При рішенні задач аналізу, синтезу та оптимізації об'єктних частовикористовується поняття деякої "оптимальною" Семо. Зміст терміна
"Оптимальна" в значній мірі визначається змістом розв'язуванихзавдань. Наприклад, багато задач аналізу Семо пов'язані з пошуком "вузьких" місцьв Семо, тобто систем масового обслуговування, м.о. числа перебуваютьвимог у яких перевищують деякі допустимі значення. Післязнаходження вузьких місць їх усувають, наприклад, збільшується інтенсивністьобслуговування у відповідних Семо, або змінюючи маршрутні матриці Семо.
Таким чином як оптимальної можна розглядати, наприклад, Семо,у всіх системах якій математичні очікування тривалостей обслуговуванняоднакові. Часто метою вирішення задач синтезу і оптимізації єформування Семо можливо більшої пропускної спроможності.
При цьому особливий інтерес представляє клас задач такого типу, колирішення досягається за рахунок зміни матриці маршрутної мережі, залишаючинезмінними задані інтенсивності обслуговування в системах масовогообслуговування.
Метою цієї дипломної роботи є розробка методуформування маршрутних матриць однорідної замкнутої експоненційної мережімасового обслуговування.
1. Постановка завдання
Нехай задана об'єктна Семо, що визначається набором [1]
Нехай так само задані - концептуальний вектор, побудованийна підставі теорем, наведених у [1] і S - матриця суміжності,визначається наступним чином:
- несформованою матриця.
Необхідно побудувати віртуальну Семо еталонного типу, а якщо ценеможливо, то мережу стандартного або симетричного видів [1]. Для цьогонеобхідно задати набір
[1-2], яким визначається однорідна замкнута Експоненціальнамережу. Цей набір відрізняється від набору тільки тим, що для ньогосформована маршрутна матриця. Т.ч. завдання полягає в тому, щобзнайти невідомі маршрутні ймовірно, це завданняназивається завданням синтезу [1].
2. Віртуальні Семо
Можна очікувати високої пропускної здатності від Семо з параметрами,забезпечують в стаціонарному режимі функціонування Семо значенняматематичних очікувань числа перебувають в системах вимог,пропорційні інтенсивності обслуговування в даних Семо.
При рішенні задач аналізу, синтезу та оптимізації об'єктних Семовикористовують Семо, які будемо називати віртуальними. Параметри віртуальних
Семо формуються на основі параметрів, відповідних об'єктних Семо. УЗокрема, віртуальні Семо можуть відрізнятися від відповідних об'єктних
Семо тільки своїми маршрутними матрицями. Розглядаються віртуальні Семотрьох видів: еталонні, стандартні і симетричні [1].
Віртуальні Семо різних видів, що відповідають деякої об'єктної
Семо відрізняються топологіями, обумовленими їхніми маршрутними матрицями.
Віртуальні Семо кожного виду можуть бути одного з наступних типів:консервативного, регулярного, рівномірного [1]. Тип визначаєтьсявимог, що пред'являються при формуванні мережі до деяких їїхарактеристиками.
Виходячи з міркувань, наведених у [1], при дослідженні дискретнихсистем в багатьох випадках як їх моделей (об'єктних Семо) можутьвельми ефективно використовуватися експоненціальні Семо.
Як віртуальних Семо розглядаються експоненціальні,однорідні, замкнуті Семо, що визначаються набором
(1)
Основні стаціонарні характеристики розглянуті в [1], [2].
Вважаючи відомими вектор імовірностей переходувимог системи в мережі обслуговування при їх чергових переходах (вектор є рішенням рівняння з умовою нормування
) і безлічі величині (- безлічномерів Семо). Маршрутні матриці віртуальних Семо,
, визначаються рішенням системи рівнянь (2) - (4) з можливимвикористанням умов (5) - (6).
(2)
(3)
(4)
(5)
(6)
Рішення системи (2) - (4) у випадку, коли всі рівні 1,а умови (5) - (6) не використовуються визначає матрицю длявіртуальних Семо симетричного виду, що мають повнозв'язну топологію зпетлями.
Використання при вирішенні (2) - (4) лише умов (5) даєповнозв'язну топологію без петель стандартного вигляду.
При визначенні маршрутних матриць еталонних віртуальних Семовикористовуються умови (5) - (6). Очевидно, використання даних умовдозволяє в загальному випадку задати довільну топологію еталонної мережі, вякої не допускаються петлі. Тобто маршрутна матриця еталонної мережі можемати структуру, тотожну (у відношенні числа і розташування нульовихелементів) структурі маршрутної матриці, відповідної об'єктної Семо.
Ці матриці можуть відрізнятися тільки значеннями ненульових елементів.
Зауважимо, що підсистема (4) визначає відносини відноснихінтенсивностей зустрічних потоків вимог з сi в сj і назад.
Визначення 1. Маршрутні матриці і однорідних,замкнутих Семо і з однопріборнимі СМО, обумовлениминаборами
називаються подібними, якщо вони мають однакову кількість і розташуваннянульових елементів і відрізняються тільки значеннями ненульових елементів.
Визначення 2. Семо і, певні наборами
називаються подібними, якщо їх маршрутні матриці і подібні,а інші елементи наборів рівні відповідно.
Визначення 3. Однорідна замкнута Експоненціальна Семо зоднопріборнимі СМО, яка визначається наборомі задовольняє умовам: називається віртуальної Семоконсервативного типу.
Визначення 4. Однорідна замкнута Семо з однопріборнимі
СМО, яка визначається наборомі задовольняє умовіназивається віртуальної Семо регулярного типу.
Визначення 5. Семо, що визначається наборомі задовольняє умові
(- М. о. Тривалості перебування вимоги в сi) називаєтьсявіртуальної Семо рівномірного типу.
В [1] розглянуті основні характеристики віртуальних Семо різнихтипів і доведено ряд теорем, на підставі яких можуть бути побудовані ціхарактеристики. (В тому числі вектор.)
2.1 Маршрутні матриці віртуальних Семо.
Вирішення питання про існування віртуальних Семо відповідних видів і типів залежить від значень параметрів L, N, вектора
. При цьому для виключення тривіальних випадків досить вимагати, щоб отримати установки L і N задовольняли очевидним співвідношенням
(7), а значення компонент вектора задовольняли нерівності
(8).
Для віртуальної Семо рівномірного типу на значеннянакладається додаткове обмеження
(9), де
(10)
В [1] показано, що ймовірність має такожзадовольняють вимогам:
(11) для віртуальних Семо консервативного та регулярного типів привиконання обмежень (7), (8), а для віртуальних Семо рівномірного типу
(7), (8), (9). Тому будемо вважати, що для представляють теоретичнийінтерес віртуальних Семо параметри L, N, і такі, що (7), (8), (9)виконуються і існує векторпобудований на підставі теорем, наведених у [1].
Визначення 6. Віртуальні Семо, параметри L, N, якихзадовольняють обмеженням (7), (8), (9), а вектор визначається напідставі теорем [1] і відповідає умовам (11) називаютьсяконцептуальними віртуальними Семо, а вектор - концептуальнимвектором.
Таким чином, концептуальними є всі віртуальні Семо дляяких ще не сформульована або не може бути сформульована маршрутнаматриця, така, що концептуальний вектор є рішеннямрівняння (12) з умовою нормування
(13).
Іншими словами віртуальна Семо не існує поки невизначені всі елементи набору, в тому числі й. Томуінтерес представляє умова існування маршрутних матриць длякоцептуальних Семо.
Маршрутні матриці концептуальних віртуальних Семо істотнозалежать від їх топології. Позначимо концептуальну віртуальну Семо через
, Де відповідно для мережі симетричного, стандартного іеталонного видів.
Введемо в розгляд Орграф, що відображає топологію Семо.
Вершини відповідають СМО, а дуги - траєкторіях переходів вимогміж системами.
I - ту вершину Орграф позначимо через, а дугу з'єднуєза допомогою. Очевидно, - сільносвязний. Використовуючипозначення і, відповідно для полустепеней результату ізаходу, позначимо матрицю суміжності Орграф і,враховуючи, що сума елементів i - го рядка матриці рівна, асума елементів i - ого стовпця -. У Орграф
За визначенням має повнозв'язну топологію з петлями. Т. о. вОрграф (- концептуальна симетрична Семо). Кожна вершиназ'єднана дугою з усіма іншими й має петлю. Всі елементи рівні 1.
Концептуальна стандартна Семо має повнозв'язну топологію безпетель. Всі елементи матриці суміжності рівні одиниці, крімелементів головної діагоналі.
Топологія концептуальної еталонної Семо може бутидовільною і повинна задовольняти лише одному вимогу - бутитотожною топології відповідної об'єктної Семо. Томутотожний Орграф об'єктної Семо, матриці ітотожні. З зв'язку з слід:
1) якщо не суміжно з, то.
2) якщо суміжно з, то якщо,.
3) число невідомих мережі
(14).
Введемо в розгляд безліч констант
якщо не суміжно з і, якщо суміжно з і потужність Інодідля може бути задано безліч констант,
, потужності, що використовується при формуваннімаршрутної матриці. У цьому випадку, якщо суміжно з і
, то при наявності в безлічі елемента
, Що відповідає належить, що.
Об'єднання множини і дає безліч
, елементи якого визначають значення відповідних маршрутнихймовірностей.
Для визначення маршрутних ймовірностей мережі значнийінтерес представляють можливо наявні дані про порівняльну величиноюзустрічних потоків між і. Відносні інтенсивності потоківвимог з в рівні. Позначимо ставленняінтенсивностей через, тобто
. Величина називається коефіцієнтом обміну, а рівняння
- рівнянням обміну.
Позначимо через безліч коефіцієнтів обміну.
Завдання цієї безлічі визначає рівнянь обміну,які можуть бути використані при визначенні
.
Отже для вирішення невідомих маршрутних ймовірностей можебути використана система Е лінійних алгебраїчних рівнянь, що включаєтри підсистеми: d) підсистема рівнянь потоків (L рівнянь):
e) підсистема рівнянь нормування (L рівнянь):
f) підсистема рівнянь обміну (рівнянь):
Число рівнянь обміну залежить від топології мережі і значень
, І може бути менше [1].
Теорема 1. Для концептуальної симетричної віртуальної Семоконсервативного, регулярного або рівномірного типу з концептуальнимвектором маршрутна матриця завжди існує і їїелементи визначаються співвідношеннями
. Доказ наведено в [1].
Теорема 2. Для концептуальної стандартної віртуальної Семоконсервативного, регулярного або рівномірного типів маршрутна матрицяіснує, якщо спільна система рівнянь:
(15)
(16)
(17)
Значення елементів матриці визначаються рішенням цієї системи.
Теорема доведена в [1].
Зауваження Загальне рішення системи (15) - (17) визначає нескінченнечисло подібних матриць. Для конкретизації матриці задаютьконкретні значення вільних невідомих.
Теорема 3. Для концептуальної еталонної віртуальної мережі будь-якоготипу з концептуальним вектором, заданої топологією, яка визначаєтьсяОрграф, матриці суміжності, заданим безліччюкоефіцієнтів обміну, маршрутна матриця існує, якщоспільна система рівнянь
(18)
(19)
(20)
(21)
(22)при обмеженнях (23)
Доказ см. в [1].
Приклади віртуальних Семо різних видів розглянуті в [1].
3. Методи побудови маршрутних матриць Семо.
3.1. Загальне рішення.
Завдання побудови маршрутної матриці віртуальної Семо може бутивирішена наступним чином:
Нехай дана концептуальна еталонна віртуальна Семо, що складаєтьсяз L СМО. Для якої визначено вектор, Орграф, матрицясуміжності, безліч, безліч коефіцієнтів обміну.
Необхідно сформулювати маршрутну матрицю, тобто знайти L2невідомих,.
З рівнянь (22) - (23) отримали значення невідомих
, де Х визначається (14).
В результаті отримали систему лінійних алгебраїчних рівнянь (18)
- (20) від Х невідомих (індекс зверху - порядковий номерневідомою).
Розв'язуючи систему методом Гауса, отримаємо один з трьох можливихваріантів: a) Система нерозв'язна. У цьому випадку сформувати маршрутну матрицю
, а отже і віртуальну еталонну Семо неможливо. b) Система розв'язано однозначно. У цьому випадку необхідно перевірити, чи задовольняють отримані значення нерівностей
(23). Якщо нерівності виконуються, то отримане рішення дає значення залишилися Х невідомих, т. о. закінчується формування маршрутної матриці. Якщо (23) не виконується, то сформувати неможливо. c) Система розв'язано неоднозначно. Загальне рішення системи (18) - - (20) фактично визначає нескінченну безліч подібних матриць для конкретної концептуальної Семо. Завдання конкретних значень вільних змінних визначає конкретну маршрутну матрицю для такої Семо. Очевидно, що це конкретне рішення має задовольняти обмеженням (23).
Нехай перший m змінних - вільні, тоді якщо
, то інші, можна записати як
. Тобто решта (Х-m) змінних можуть бути лінійно виражені через
. Підставляючи отримані вирази в нерівності
(24) отримаємо систему нерівностей:
(25)
Ця система нерівностей утворює так зване багатогранне безлічв m - мірному просторі. Якщо це безліч не пусто, то, так як вонообмежена, воно є опуклим багатогранників. Точка називаєтьсявершиною опуклого багатогранника в, якщо вона є допустимою іє точкою перетину m лінійно незалежних гіперплоскостей.
(Кожне лінійне рівняння задає гіперплоскость, кожному лінійномунерівності з (25) зіставляється обмежене гіперплоскостьюпівпростір; гіперплоскость отримують, замінюючи знак нерівності на знакрівності.) Вершина виродження, якщо вона є точкою перетину більшеніж m гіперплоскостей.
Вершину не можна уявити у вигляді опуклоюлінійної комбінації двох інших точок допустимої областідля всіх допустимих точок (). Усякебагатогранне безліч має кінцеве число вершин. Якщо допустима областьутворена n нерівностями і m рівняннями, то вона можемати найбільше вершин. Так як допустима область в даномувипадку є опуклим багатогранників, то кожна допустима точка маєщонайменше одне подання:
(26),де - вершини багатогранника;
.
Таким чином, якщо ми знайдемо всі вершини багатогранника (якщо вониіснують. В іншому разі рішення не існує), то ми отримаємо загальнерішення задачі формування матриці.
де - допустима точка, знайдена за формулою (26).
Отримаємо що залишилися Х невідомих і завершимо побудову маршрутної матриці.
3.2. Приклад знаходження спільного рішення.
Дана концептуальна еталонна віртуальна Семо, з L = 5, дляякій визначені концептуальний вектор, Орграф, матрицясуміжності.
Безліч.
З рівнянь (21), (22) отримаємо значення 15 невідомих маршрутнихймовірностей з 25. Решта невідомі занумеруем
, отримаємо:
Розглянемо систему лінійних рівнянь (18), (19), (17). Застосовуючи доній алгоритм Гауса отримаємо: a) система спільно. b) рішення неоднозначно 10-8 = 2 невідомих можуть бути обрані довільно.
Вирішуємосистему і отримуємо:
(()
Підставимо результати в (25). Отримаємо систему типу (26):
(27) < p> Ця система нерівностей утворює багатогранне безліч, зображенена рис. 1.
Будь-яка пара належить допустимої області задовольняєсистемі (27).
Многогранники має 5 вершин:
Будь-яка точка допустимого безлічі має уявлення,де - вершини,,,. Нехай, наприклад,
, тоді
. Підставимо значення і в ((),отримаємо
Малюнок 1.
3.3. Метод формування маршрутної матриці віртуальної Семо.
Завдання побудови віртуальної Семо може бути зведена до задачінелінійного програмування.
Нехай задана концептуальна віртуальна Семо, для якої заданоконцептуальний вектор, Орграф, матриця суміжності,безліч.
Завданням нелінійного програмування загального вигляду називається завдання:
Знайти
(2.1)при обмеженнях
(2.2)
Введемо в розгляд функцію;очевидно, що якщо знайдеться така, що, тобтошукана маршрутна матриця. Т. о. ми отримали завдання:
(2.3)при обмеженнях
(2.4)
Задача (2.3) - (2.4) є задачею нелінійного програмування.
Її можна віднести до задач квадратичного програмування - клас задач дляяких цільова функція квадратична, а всі обмеження лінійний.
Вирішуючи задачу (2.3) - (2.4) одним із методів, розглянутих в [3-5]можна отримати один з результатів:
1), де. У цьому випадку сформувати маршрутну матрицю неможливо.
2). У цьому випадку є шукана маршрутна матриця віртуальної Семо.
Для вирішення ЗНП розроблений ряд методів, які дозволяють, відправляючись віддеякого початкового рішення, отримувати послідовно значення, якізнаходяться всі ближче до шуканої точці максимуму (мінімуму). Група методів,заснованих на обчисленні та порівнянні значень цільової функції в ряді точокперед наступним кроком, називається пошуковими методами оптимізації.
У задачі можна уявити цільову функцію як гіперповерхность.
Максимальне значення досягається в вершині самого високого пагорба. Пошукекстремуму починають з будь-якій зручній точки, причому рухаються в напрямкунайшвидшого підйому, поки не досягають або вершини, або кордону. Придосягненні кордону необхідно виключити переміщення за межі обмежень.
Досягши вершини, яка зустрілася в напрямку якнайшвидшогопідйому повертають щоб знову обраному напрямку найшвидшого підйому.
Таким чином досягають точки, де рух в будь-якому напрямку призводить доспуску. У цьому випадку стверджують, що знайдено принаймні локальнийекстремум.
На практиці, при реалізації цього методу виникають дві труднощі. По -перше, це відносна мала швидкість збіжності. Для подолання цьогослужать методи перебування більш ефективних напрямків, ніж напрямнайшвидшого підйому. Друга складність полягає в тому, що цей методдозволяє виявити локальні максимуми, але не дає гарантії досягненняабсолютного (глобального) екстремуму. Щоб подолати ці труднощі зазвичайпочинають пошук з різних точок, і, якщо обчислення сходяться до різнихвершин, то вибирають найбільш високу з них. Також можна використовуватиметод, відомий під назвою "метод важкого кульки", при якомурух точки нагадує рух важкого кульки по горбистоюповерхні. Розглянемо деякі з методів пошукової оптимізації.
3.4. Пошук по статистичному градієнту.
Нехай треба знайти максимум. У точці робиться mвипадкових випробувань і обчислюються збільшення цільової функції
де - випадкові величини, - випадковий крок.
Далі визначають величину
Усереднена по всіх реалізацій значення співпадає зістинним напрямом найшвидшого підйому, тобто
Далі з точки відбувається черговий робочий крок:
3.5. Метод "важкого кульки".
Розглянемо найпростіший варіант випадкового пошуку: нехай - довільна точка. З здійснюється рух з кроком у випадковому напрямку з рівномірним розподілом.
Рух представляє точки описується так:
Цей алгоритм без пам'яті може бути вдосконалений. Напрямоквдалих проб запам'ятовується і ймовірність кроку в цих напрямкахзростає. Для цього введемо вектор пам'яті, проекції якого накоординатні осі визначають ймовірність вибору позитивногонапрямку з i - ої осі. - Монотонна, неубивающая функція,тоді, а змінюється так:
де
- параметр запам'ятовування, - характеризує швидкість навчання,
.
Цей метод називається методом " важкого кульки ".
3.6. Формування маршрутної матриці.
Нехай поставлена задача (2.3) - (2.4). Для знаходження рішеннязастосуємо метод послідовної оптимізації.
Опис методу.
1. Початковий крок до = 0.
В якості початкового наближення виберемо деяку матрицю. Матриця повинна задовольняти умови 2.4. Задамо точність.
Зауваження. Вище було сказано, що для того, щоб підвищити ймовірність знаходження глобального екстремуму вибирають кілька початкових наближень. може бути вибрана випадково, або область визначення може бути розбита на інтервали і як вибираються вузли отриманої сітки. Методи вибору числа випадкових проб або розмірності сітки описані в [3] - [7].
2. к-ий крок. Вибір напрямку руху.
Для кожного елемента, де обчислимо значення цільової функції, де
- матриця, в якій всі елементи рівні елементів матриці, крім одного цього елемента, що дорівнює. Значення величини вибирається з міркувань про точність, з якою шукається
. Методи вибору величини описані в [3] - [7].
Таким чином отримаємо безліч значень цільової функції. (Може бути позитивною і негативною). Для всіх елементів.
Виберемо тепер. Відповідний елемент матриці запам'ятовуємо. Нехай це буде. Виберемо тепер у рядку i1 елемент, такий, що
. Запам'ятаємо також цей елемент.
Розглянемо два можливих варіанти: а) Якщо, то запам'ятовуємо компоненти, і переходимо до 3. б) Якщо
, то, переходимо до 4.
3. к-ий крок. Рух у вибраному напрямку.
З точки переходимо до наступним чином:
Якщо, то визначається наступним чином:
до: = до 1, переходимо до 3.
Якщо, то, на: = до 1, переходимо до 2.
4. Кінцевий крок.
Якщо (- величина, що визначає точність обчислення екстремуму), то - шукана маршрутна матриця.
Якщо, то вибирають інше початкове наближення і переходять до 2. Якщо безліч початкових наближень вичерпано, то вважають, що сформувати маршрутну матрицю неможливо.
4. Алгоритм програми, що реалізує метод побудови маршрутної матриці.
Алгоритм складається з 6 функціональних блоків, які виконуються в порядку,який схематично зображено на малюнку 2 "Схема алгоритму". Нижче наведенопризначення і зміст усіх 6-ти функціональних блоків. Алгоритм реалізуєописаний вище метод.
Блок 1.
Призначення: Введення даних, необхідних для побудови маршрутноїматриці.
Зміст: Введення даних, що конкретизують вирішувану завдання (тобтозавдання побудови маршрутної матриці віртуальної Семо (2.3) - (2.4)). Цідані повинні містити число СМО в мережі і матрицю суміжності вихідноїконцептуальної віртуальної Семо, а також концептуальний вектор.
Блок 2.
Призначення: Завдання початкового наближення.
Зміст: Матриця формується шляхом присвоєння випадковихзначень елементів таких, що, де I - безліч номерівелементів матриці суміжності, таких що
При цьому необхідно дотримуватися стохастичності матриці, тобто умови
(2.4). Інші елементи одержують у такий спосіб:
(- елементи матриці суміжності).
Т. о. блок 2 реалізує пункт 1 розглянутого вище методу.
Блок 3. Реалізує пункт 2 методи формування маршрутної матриці.
Призначення: Вибір напрямку, в якому буде здійснюватися пошукекстремуму.
Зміст: 3.1) Обчислення цільової функції поточної матриці.
3.2) Вибір таких елементів і і величини
, (позитивної або негативної), що
Після того як ці умови виконані і елементи знайдені переходять доумові 1:
1) Якщо, то передаються в якості вихідних даних у Блок 4 і керування передається
Блоку 4.
2) Якщо 1) не виконується, то поточна матриця запам'ятовується які управління переходить на Блок 5.
Докладно вибір елементів і описаний вище в пункті 2 методиформування матриці.
Блок 4. Реалізує пункт 3.
Призначення: Здійснює рух у напрямку вибраному Блоком 3 дотих пір, поки не буде досягнута межа (умови (2.4)), або вершина нацьому напрямку.
Зміст: Поки не буде досягнута межа, тобто не перестанутьвиконуватися умови:
(- вибрані Блоком 2)
Або не буде досягнута вершина для поточного напрямку, тобто
(()
((() - умова досягнення вершини в точці). Повторюють робочийкрок: присвоюють значення.
Як тільки рух припиняється поточна матриця запам'ятовується іуправління передається в Блок 3.
Блок 5.
Призначення: Визначити чи сягнуть глобальний екстремум в точці,певної Блоком 2. Тобто досягнуто чи рішення задачі (2.3) - (2.4).
Зміст: Перевіряються умови 2:
Якщо (- величина, що визначає точність, з якоюшукається екстремум, міститься у вхідних даних), то робиться висновок, що
- Рішення задачі (2.3) - (2.4);
Якщо, то якщо раз не було досягнуто один і той жемінімум, управління передається до Блоку 2 (може бути задана у вихіднихданих).
В іншому випадку слід, що рішення задачі (2.3) - (2.4)досягти неможливо.
Після перевірки умови 2 управління передається в Блок 6.
Блок 6.
Призначення: Формування вихідних даних.
Зміст: Формується повідомлення , наступним чином:
Якщо рішення знайдено, то вихідними даними є.
Якщо прийнято рішення про неможливість досягти рішення, то вихідними даними буде повідомлення про те, що рішення не існує.
Малюнок 2. Структурна схема алгоритму реалізує метод формування маршрутної матриці.
5. Призначення програми OPTIM та опис програми.
Програма OPTIM написана на мові Turbo Pascal. Програмапризначена для вирішення задачі формування маршрутної матрицівіртуальної Семо. Програма являє собою реалізацію алгоритмунаведеного в попередньому розділі. Програма проста у використанні, вимагаєнезначний обсяг оперативної пам'яті. Недоліком програми єнедостатньо висока швидкодія, як і в багатьох інших програм,реалізують подібні методи оптимізації.
Маршрутні матриці і матриці суміжності є вбранимиматрицями, тобто матрицями, що містять відносно мале число ненульовихелементів. Тому для дослідження віртуальних Семо великої розмірності впрограмі OPTIM передбачено подання матриць суміжності у виглядівектора, що містить номера стовпців, що містять елементи ненульовізаписані в порядку зростання номерів стовпців і рядків. Номер останньогопозитивного елемента в рядку береться зі знаком "-". Подібнепредставлення матриці суміжності дозволяє підвищити швидкість введення вихіднихданих.
Програму можна умовно розбити на функціональні блоки, виконаніу вигляді окремих процедур і функцій.
1. Введення вихідних даних. Реалізує пункт 1 алгоритму. Виконаний у виглядіпроцедури InputData.
Зміст: зчитує вихідні дані з файлу OPT.DAT. Вихіднідані вибираються в наступному порядку: до - число ненульових елементів матриці суміжності.
L - число СМО.
Svect - упакована матриця суміжності (вектор розмірності к).
- концептуальний вектор (розмірності L).
2. Завдання початкової матриці реалізує Блок 2 алгоритму.
Виконаний у вигляді процедур MatrSmez і TetaMatr. Процедура MatrSmez формуєматрицю суміжності на підставі вектора Svect. Процедура TetaMatrперетворює матрицю суміжності в матрицю (детально описано в алгоритмів Блоці 2).
3. Вибір напрямку спуску. Реалізує Блок 3 алгоритму. Виконано увигляді процедури IndLocate. Для роботи використовує функції target (teta) іstepish, яка обчислює значення цільової функції та ступінь полуісхода вершинивідповідно.
4. Здійснює рух у вибраному напрямку. Реалізує Блок 4алгоритму, виконана у вигляді процедури Move.
5. Обробка результатів і формування файлу вихідних даних.
Реалізує Блоки 5 і 6 алгоритму. Виконаний у вигляді процедури OutputData.
Зміст: Обробляє результати роботи Блоків 2, 3, 4. Вихіднідані формуються у вигляді вихідного файлу OPT. REZ
Вихідний файл містить або отриману маршрутну матрицю віртуальної
Семо, або повідомлення про неможливість сформувати її.
Текст програми поміщений у додатку.
Висновок.
Метою даної роботи була розробка методу розв'язання задачіформування маршрутних матриць віртуальної Семо.
Були розглянуті деякі методи оптимізації і на їх основізапропонований метод формування маршрутної матриці.
Для нього був розроблений алгоритм і написана програма. Програма булавипробувана на контрольних прикладах.
Так само був запропонований метод одержання спільного рішення поставленоїзавдання.
Список літератури.
Митрофанов Ю. И., Синтез мереж масового обслуговування .- Саратов: Изд-во
Гунца "Коледж", 1995 -168 с.
Башарин Г. П., Бочаров П. П., Коган Я. А. Аналіз черг в обчислювальнихмережах. Теорія та методи розрахунку. - М. Наука. Гол. ред. фіз.-мат. лит., 1989 -
336 с.
Жіглявскій А. А., Жілінскас А. Т. Методи пошуку глобального екстремуму. -М.
Наука, Гл. ред. фіз.-мат. лит., 1991 - 248 с.
Поляк Б. Т. Введение в оптимізацію. - М. Наука, 1983 - 384 с.
Зайченко Ю. П. Дослідження операцій. - Київ, Вища школа, 1975, 320 с.
Митрофанов Ю. И., Брагина И. Т., Тананко І. Є., Юдаева Н. В. Аналіз таоптимізація мереж масового обслуговування. Програмне забезпечення. -
Саратов, Изд-во "Коледж", 1995 - 144 с.
