Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Вказівки до виконання






 

Введемо такі визначення:

1. Нульові елементи Z 1, Z 2, …, Zk квадратної матриці С називаються незалежними нулями, якщо для будь-якого 1 £ i £ k рядок і стовпчик, на перетині яких знаходиться елемент Zi, не містить елементів Zk для всіх k ¹ i.

2. Дві прямокутні матриці С =(сij) і С¢ ¢ =(с¢ ¢ ij) розміром m ´ n назвемо еквівалентними (C ~ C¢ ¢), якщо с¢ ¢ ij = сij +a i + bj; i =1, 2, …, m; j =1, 2, …, n. Задачі вибору, обумовлені еквівалентними матрицями, є еквівалентними, тому що можна довести, що безліч оптимальних призначень двох задач вибору з еквівалентними матрицями збігаються.

3. У процесі вирішення задачі деякі рядки (стовпчики) матриці С та еквівалентних їй матриць будуть виділятися значком «+», що ставиться праворуч від відповідного рядка (над відповідним стовпчиком). Елементи, розташовані у виділених рядках чи стовпцях, називаються виділеними елементами.

Угорський алгоритм розв’язання задачі про призначення складається з попереднього етапу і не більше ніж n –2 послідовно проведених ітерацій.

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

Перше перетворення роблять з усіма стовпцями матриці С. З максимального елемента j -го стовпця (i =1, 2, …, n) віднімаються елементи цього стовпця:

 

С = (сij) ® С¢ = (с¢ ij) = (max сij - сij). (10.2)

 

Отримана матриця С¢ є ненегативною, в кожному стовпці цієї матриці є хоча б один нуль.

Друге перетворення роблять з рядками матриці С¢. З елементів і -го рядка матриці С¢ віднімають мінімальний елемент цього рядка:

 

С¢ = (с¢ ij) ® С¢ ¢ = (с¢ ¢ ij) = (с¢ ij – min с¢ ij). (10.3)

 

Якщо в кожному рядку матриці С¢ = (с¢ ij), отриманої після першого перетворення матриці С, уже є хоча б один нуль, то друге перетворення не роблять.

У результаті попередніх перетворень відбувається перехід від задачі вибору на максимум з матрицею С до задачі вибору на мінімум з матрицею С¢ ¢. Найменше можливе значення суми n елементів ненегативної матриці дорівнює, очевидно, нулю. Отже, задача зводиться до вибору в матриці С¢ ¢ (чи в еквівалентній їй матриці з ненегативними елементами) n нульових елементів, по одному в кожному рядку і кожному стовпці.

Відзначаємо довільний нуль у першому стовпці зірочкою (*). Потім переглядаємо другий стовпець, і якщо в ньому є нуль, розташований у рядку, де немає 0*, то відзначаємо його зірочкою. Аналогічно переглядаємо один за одним всі інші стовпці матриці С¢ ¢. Очевидно, що нулі матриці C¢ ¢, відзначені зірочкою, за побудовою є незалежними.

(k+1)-а ітерація

Припустимо, що k -а ітерація проведена й у результаті отримана матриця Сk. Якщо в матриці Сk є рівно n нулів із зірочкою, то процес вирішення закінчується. Якщо ж число нулів із зірочкою менше n, то переходять до (k +1)-ої ітерації. Кожна ітерація починається першим і закінчується другим етапом. Між ними можна кілька разів проводити пари етапів: третій-перший. Перед початком ітерації знаком «+» виділяють стовпці матриці Сk, що містять нулі з зірочкою.

Перший етап. Переглядають невиділені стовпці матриці Сk. Якщо серед них не виявиться нульових елементів, то переходять до третього етапу. Якщо ж невиділений нуль матриці Сk виявлено, то можливий один із двох випадків: а) рядок, що містить невиділений нуль, містить також нуль із зірочкою; б) цей рядок не містить нуля із зірочкою.

У випадку (а) невиділений нуль відзначають штрихом і виділяють рядок, у якому він знаходиться, знаком «+» праворуч від нього. Потім знищують знак «+», обводячи його рамкою, над тим стовпцем, на перетині якого з даним виділеним рядком міститься нуль із зірочкою. Далі знову переглядають невиділені стовпці, відшукуючи в них невиділені нулі. Цей процес за кінцеве число кроків закінчується одним з таких випадків:

I А – є невиділений нуль у рядку, де немає нуля із зірочкою. У цьому випадку переходять до другого етапу, відзначивши останній один по одному нуль штрихом;

I В – усі нулі матриці Сk виділені, тобто знаходяться у виділених рядках чи стовпцях. При цьому переходять до третього етапу;

У випадку (б), відзначивши невиділений нуль штрихом, відразу переходять до другого етапу.

Другий етап. Будують наступний ланцюжок з нульових елементів матриці Сk: відзначений останнім нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з ним, нуль зі штрихом, розташований в одному рядку з попереднім нулем із зірочкою, і т.д. Отже, ланцюжок утворюється пересуванням від 0¢ до 0* по стовпцю, від 0* до 0¢ по рядку і т.д.

Ланцюжок завжди починається і закінчується нулем зі штрихом (можливо, він буде складатися з одного нуля зі штрихом). Далі над елементами ланцюжка, що знаходяться на непарних місцях (0¢), ставлять зірочки, знищуючи їх над парними елементами (0*). Потім знищують усі штрихи над елементами матриці Сk і знаки «+». При цьому кількість незалежних нулів буде збільшено на одиницю; (k +1)-а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Сk виділені, тобто знаходяться у виділених стовпцях чи рядках. У такому випадку серед невиділених елементів матриці Сk вибирають мінімальний і позначають його h > 0. Далі величину h віднімають з усіх елементів матриці Сk, розташованих у невиділених рядках, і додають до всіх елементів, розташованих у виділених стовпцях. Одержують нову матрицю Сk (1), еквівалентну Сk.

Оскільки серед невиділених елементів матриці Сk (1) з'являються нові нулі, переходять до першого етапу, при цьому замість матриці Сk розглядають матрицю Сk (1). Закінчивши перший етап, переходять до другого етапу або знову повертаються до третього етапу, якщо всі нулі матриці Сk (1) виявляються виділеними.

Після кінцевого числа побудов черговий перший етап обов'язково закінчиться переходом на другий етап і кількість незалежних нулів збільшиться на одиницю, тобто (k +1)-а ітерація буде закінчена.

У результаті вирішення задачі встановлюють оптимальний варіант призначень.

 

Контрольні питання

 

1. Принципи угорського методу.

2. Що таке продуктивність?

3. Що включає у себе попередній етап?

4. До якого критерію розрахунку прагнемо?

5. Як розраховується оптимальна продуктивність?

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.