Область наук:
  • Математика
  • Рік видавництва 2000
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Матрична інтерпретація і матричне рішення задачі агрегування'

    Текст наукової роботи на тему «Матрична інтерпретація і матричне рішення задачі агрегування»

    ?і 0 - з (8) - (9), а робота I має ступінь критичності 0 відповідно до (5) - (6) і

    0.25.- з (8) - (9).

    Проаналізуємо розраховані показники. Як видно, роботи A, B, D, G, J, L мають ступінь критичності, рівну одиниці. З них роботи A, B, D і L є критичними при будь-якому наборі можливих тривалостей робіт, так як вони належать усім шляхах, які мають ненульовий ступінь критичності. Крім того, в залежності від тривалості будуть критичними або роботи G і J або F і K. Цим роботам слід приділити особливу увагу при управлінні, оскільки затримка їх виконання спричинить за собою затримку виконання проекту в цілому. Роботи C, E, F і H мають узагальнену ступінь критичності 0, тому вони не є критичними при будь-яких можливих ситуаціях і мають резерв.

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

    ЛІТЕРАТУРА.

    1. Chanas S., Radosinski E. Time pattern of activities performance in the light of fuzzy sets theory // Problemy organizacji. - 1976. - №2. - C. 68-76.

    2. Prade, H. Using fuzzy set theory in a scheduling problem: a case study // Fuzzy Sets and Systems. - 1979. - №2. - C. 153-165.

    3. Chanas S., Kuchta D. Discrete fuzzy optimization / Fuzzy sets in decision analysis, operations research and statistics. Edited by R.Slowinski. - Kluwer Academic Publishers. - 1998. - C. 249-280.

    4. Дюбуа Д., Прад А. Теорія можливостей. Додатки до подання знань в інформатиці. - М .: Радио и связь, 1990. - 208с.

    5. Kamburowski J. Fuzzy activity duration times in critical path analysis // Inter. Symp. On Project Management. - New Delphi, 1983. - C. 194-199.

    6. Buckley J.J. Fuzzy PERT / Applications of fuzzy set methodologies in industrial engeniring. Edited by G.Evans, W.Karwowski, M.Wilhelm. - Elsevier, 1989. - C. 103-114

    7. . ., . .

    // -

    ліз. - 1999. - Вип. 3. - С. 158-170.

    УДК 621.03

    В.І. Кодачігов, Н.В. Кодачігова

    МАТРИЧНА ІНТЕРПРЕТАЦІЯ І матричних РІШЕННЯ ЗАВДАННЯ

    агрегування

    У дуже багатьох випадках при рішення різнорідних завдань, що допускають гра,

    зважені графи без кратних ребер. Доводиться стикатися із завданням агрегування [1]. До неї зводяться завдання: розміщення графів, розрізування (кластеризація графів) і т.д.

    Було відмічено [1,2], що вдале їх рішення призводить до графів, що характеризується матрицями суміжності, тотожними вихідним, але мають спе-

    :

    виявляється поблизу її головною діагоналі, або всередині стрічки заданої ширини, або всередині блоків заданих розмірів.

    Зазвичай рішення цих задач проводиться прямо, тобто виконуються графові перетворення. Матриця ж використовується як структура даних, що задає граф [3].

    Відомо і зворотне рішення: перетворюється чисто матриця. Результату перетворення відповідає граф [2,4] .

    Цікаво, що така постановка має сенс і для неграфових завдань, особливо описуються так званими дозволеними матрицями [4].

    Розцяцькованої називають матрицю, що має невеликий відсоток ненульових .

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

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

    1. Діагональні блокові форми матриці. Діагональна блокова форма являє собою матрицю, у якій для всіх 1 Ф] подматріци А [у] і все діагоналі подматріци А [у] є квадратними подматріца.

    , , , , складається з незв'язних подграфов, і кожен підграф відповідає окремому диагональному блоку (рис.1).

    , -складно. Для цього треба, використавши всі можливі тотожні Перетворюва-, , , -. , .

    Нижче описується три евристичних алгоритму, що призводять матрицю до цікавого для нас виду, і оцінюється їх ефективність. Перш, ніж перейти до їх розгляду, зазначимо, які саме форми розріджених матриць взагалі можуть нас зацікавити в зв'язку з виділеними вище завданнями.

    рис.1.

    На рис. 1 представлена ​​перша з них. Це так звана повна діагональна блокова форма. Вона відповідає випадку, коли вихідний граф складається з повних незв'язаних подграфов. Кожен підграф характеризується блоком по діагоналі. Якщо підграфи пов'язані, то має місце неповна діагональна блокова форма. Тут в діагональних блоках присутні ненульові елементи, а поза ними

    є і ненульові (рис.2). Нас цікавить випадок, коли між блоками буде мінімум одиничних елементів.

    1 2 3 4 5 6 7 8

    1 + 1 1 + 1

    1 1 + 1

    1 1 + 1

    1 + 1

    1 + 1

    1 1 + 1

    1

    1 + 1 1 + 1

    рис.2.

    На рис.3 представлена ​​так звана повна стрічкова матриця. Ширина її стрічки в = 7.

    1 23456789 10

    1 + 1 1 + 1

    1 1 1 1 1

    1 + 1 1 + 1 1 + 1

    1 1 1 1 1 1 1

    1 1 1 1 1 1 1

    1 1 1 1 1 1 1

    1 1 1 1 1 1 1

    1 + 1 1 + 1 1 + 1

    1 1 1 1 1

    1 + 1 1 + 1

    рис.3.

    На рис.4 показана неповна стрічкова матриця. Тут Р = 5. Неповну стрічкову матрицю називають зазвичай просто стрічкової матрицею. Нас цікавить випадок стрічкової матриці з мінімально можливою шириною стрічки.

    1 2 3 4 5 6 7 8

    1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1 1 + 1

    1 + 1 1 + 1

    1 1 + 1

    1 1 1 1 1

    1 + 1

    рис.4.

    На рис.5 показана часткова стрічкова матриця. У ній одиниці присутні і поза стрічки. Нас цікавить так звана мінімальна часткова стрічкова матриця, тобто неповна стрічкова матриця, у якій можливе найбільше число одиниць наведено в стрічку заданої ширини. Введемо в розгляд мінімум -. , -Ріна стрічки мінімально можлива.

    Нагадаємо, що всі виділені види матриць характеризують "хороші" рішення таких різновидів завдання агрегування, як розміщення графів, розрізування графів і т.д. Як приклад на рис.5 показаний результат рішення задачі

    розміщення. На рис.5а наведено вихідний граф, а на рис. 56 -результірующій. Їм відповідають матриці, наведені на ріс.б і 66 відповідно. В якості алгоритму використаний алгоритм [3].

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    1 + 1 1 + 1

    1 1 1 1 1 1 1 1 1

    1 + 1 1 + 1

    1 1 1 1 1

    1 1 1 1 1

    1 1 1 1 1

    1 + 1 1 + 1

    1 1 1 1 1

    1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 1 1 1 1

    1 + 1 1 + 1

    рис.5 а

    5 6 10 7 16 2 4 9 3 8 12 11 13 14 1 15

    1 1 1 1 1

    1 1 1 1 1

    1 + 1 1 + 1

    1 1 1 1 1

    1 + 1 1 + 1

    1 1 1 1 1 1 1 1 1

    1 1 1 1 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 1 1 1 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    1 + 1 1 + 1

    .5

    , ,

    , , вихідного графу, "притискаються" до головної діагоналі.

    ЛІТЕРАТУРА

    1. Браверман Е.М. та ін. Структурні методи обробки емпіричних даних. - М .: Наука, 1982.

    2. Кодачігов В.К, Бондарєв Л.І. Мінімальні матриці і деякі їх застосування // Автоматизація проектування, програмування і конструювання. - Таганрог: Вид-во ТРТІ, 1982.

    3. Курейчик В.М. і ін. Методи розбиття схем РЕА на конструктивно-закінчені частини. - М .: Сов. Радіо, 1978.

    4. ТьюарсонД. Розріджені матриці. - М .: Мир, 1975.

    5. Курі йчік В.М. Генетичні алгоритми. - Таганрог: Вид-во ТРТУ, 1998..


    Завантажити оригінал статті:

    Завантажити