Візуалізація алгоритму угорського методу розв’язку задачі про оптимальне призначення

Размещено на http://www.allbest.ru/

10

Размещено на http://www.allbest.ru/

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

Візуалізація алгоритму угорського методу розв'язку задачі про оптимальне призначення»

Вступ

Ключовою проблемою сучасної теорії управління є оптимізація. Розв?язання цієї проблеми вимагає розробки та практичного застосування методів оптимізації, що базуються на використанні сучасних ЕОМ. Серед прикладних задач оптимізації важливе місце займають задачі дискретного програмування. При цьому розрізняють задачі комбінаторного типу, допустима

множина яких має скiнченну кількість точок, задачі цiлочисельного програмування, де змінні приймають цiлочисельнi значення, та задачі частково

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

Для своєї курсової роботи ми обрали тему «Візуалізація алгоритму угорського методу розв'язку задачі про оптимальне призначення». Дана задача є типовим прикладом задач дискретного програмування. Хоча принцип роботи угорського методу описаний у багатьох джерелах, безпосередньо візуалізації для цієї задачі ще не розроблено.

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

Мета дослідження - вивчити принцип роботи угорського алгоритму, обґрунтувати його ефективність, здійснити програмну реалізацію та візуалізацію даного алгоритму.

Відповідно з метою дослідження нашої курсової роботи ставляться такі завдання:

1. Дослідити та вивчити принцип роботи алгоритму угорського методу.

2. Дослідити інші альтернативні алгоритми розв'язку задачі про оптимальні призначення.

3. Розробити програмний код, що розв'язує задачу оптимального призначення за алгоритмом угорського методу.

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

5. Перевірити ефективність даної програми для різних вхідних матриць даних та відповідність її дій відповідно алгоритму угорського методу.

Для комплексного вивчення предмету курсової роботи ми використовували такі методи дослідження:

· порівняння декількох різних алгоритмів, їхній аналіз;

· експеримент - реалізація алгоритму угорського методу та перевірка його ефективності на практиці;

· формалізація - відображення принципу дії угорського методу в знаковій формі мови програмування Delphi;

· аналіз алгоритму, його окремих етапів виконання.

Наукова новизна нашого дослідження полягає у розробці програми, яка дозволяє візуально простежити поетапну роботу алгоритму угорського методу. Угорський метод не є новим явищем, але його візуалізація до сьогодні ще не розроблена.

Логіка дослідження зумовила наступну структуру нашої курсової роботи: вступ, ІІ розділи, висновки, список використаних джерел. Також до роботи додається проект написаної програми та безпосередньо програма, готова до виконання.

Загальний обсяг курсової роботи - 37 ст.

1. Постановка та розв'язання задачі про оптимальне призначення

1.1 Умова задачі оптимального призначення. Алгоритми розв'язку

Задача про оптимальне призначення є однією з основних типових задач дискретного програмування. Дискретне програмування - розділ програмування, який передбачає роботу з дискретними (цілочисельними) даними. Також основними задачами дискретного програмування вважають задачі про рюкзак, вибір засобів доставки, знаходження найкоротших відстаней між вершинами графа та ін.

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

Є n видів робіт та n кандидатів для їх виконання. Вважається, що кожен з кандидатів і = 1… n може виконувати будь-яку роботу j = 1… n. При цьому C_ij - витрати, пов'язані з призначенням і-го кандидата на j-ий вид роботи.

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

Для розв'язку такої задачі існують різні методи та алгоритми, зокрема:

1. Алгоритм з використанням елементів комбінаторики.

2. Алгоритм методу Мака.

3. Алгоритм угорського методу [1, c. 4-6].

1.1.1 Алгоритм з використанням елементів комбінаторики

Комбінаторика - розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією [8, c. 412].

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

Перестановка - зміна положення елементів множини для створення нової комбінації цих елементів. З n елементів всього можна утворити n! різних комбінацій.

Розміщення - створення множин розмірністю в m елементів з множини з кількістю елементів n. Якщо множина m складається з різних, неповторюваних елементів, то загальна кількість множин розмірністю m, які відрізнятимуться між собою за розміщенням елементів, обчислюється за формулою:

.

Якщо ж умова задачі передбачає повторюваність елементів, то з n елементів можна скласти значно більшу кількість множин, які міститимуть m елементів. Тоді загальна кількість множин розмірністю m обчислюватиметься за формулою [2, c. 32]:

.

Комбінація - спосіб вибору декількох речей із більшої групи, де (на відміну від розміщення) порядок немає значення. Кількість можливих комбінацій розмірністю m з n елементів обчислюється за формулою [7, c. 167-168]:

Задача оптимального призначення працівників розв'язується із застосуванням методу перестановки.

Наприклад, якщо у задачі задано 4 працівники, то ми повинні скласти всі можливі комбінації із чисел 1, 2, 3, 4. Комбінація 3124 говорить про те, що 3-го працівника слід призначити на 1 (положення цифри 3 у комбінації) роботу, 1-го працівника на 2 роботу, 2-го працівника на 3 і 4-го на 4 роботу. Аналогічним чином відбуваються призначення працівників на певний вид роботи відповідно до інших комбінацій. Для кожної з комбінацій слід обчислити загальну суму витрат та в кінцевому результаті обрати ту, сума витрат для якої є мінімальною.

Покроковий алгоритм з врахуванням принципу формування комбінацій є такий:

1. Вводимо число n - це кількість робіт і працівників.

2. Генеруємо послідовність А(i)=1 2 3 … n - розподіл працівників на роботи від 1 до n.

3. Знаходимо суму зарплат для даної послідовності.

4. Йдемо з правого кінця послідовності А, поки не знайдемо цифру, меншу за попередню. Якщо така цифра знайдена, то переходимо до пункту 5. Якщо ні - до пункту 11.

5. Серед усіх цифр, що знаходяться праворуч від знайденої, шукаємо таку, яка є найменшою, але більшою за знайдену. Міняємо її місцями із знайденою.

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

7. Знаходимо загальну суму витрат для даної послідовності.

8. Переходимо до пункту 4.

9. Порівнюємо всі знайдені суми і знаходимо найменшу.

10. Виводимо найменшу суму зарплат, а також інформацію про те, якого працівника на яку роботу слід призначити (згідно комбінації, яка відповідає цій найменшій сумі).

11. Кінець.

1.1.2 Алгоритм методу Мака

Угорський метод (який описаний нижче) оснований на деяких доволі складних комбінаторних властивостях матриці. Його доволі важко програмувати. Метод Мака, порівняно з іншими, має перевагу простішого інтуїтивного обґрунтування. Це - логічний процес. Цей метод заснований на ідеї вибору в кожному рядку мінімального елементу. Мінімальні елементи рядків не розподілені по всіх n стовпцях матриці. Тут використовується ідея додавання (або віднімання) одного і того ж значення зі всіма елементами рядка чи стовпця, щоб розподілити мінімальні елементи рядків по стовпцях [3, c. 49-50].

1. Позначаємо мінімальний елемент кожного рядка матриці витрат позначкою *. Якщо таких елементів декілька, позначаємо будь який з них.

2. Для кожного рядка, що має інший мінімальний елемент, проглядаємо стовпець, до якого цей елемент належить. Можливі випадки:

а) стовпець не має позначених елементів;

б) стовпець має принаймні один позначений елемент.

3. У випадку а) позначаємо інший мінімальний елемент рядка позначкою *. Всі інші позначки в цьому рядку ліквідовуються. У випадку б) позначаємо інший мінімальний елемент рядка позначкою ^, якщо елемент цього рядка з позначкою * не є єдиним позначеним елементом у своєму стовпці.

4. Дiї пунктів 2 та 3 повторюємо послідовно для всіх рядків, що мають більше одного мінімального елемента.

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

6. Позначаємо (символом &) стовпці, що мають більше одного позначеного елемента. Вони утворюють множину В, інші стовпці матриці витрат утворюють множину А.

7. Для кожного рядка матриці витрат, в якому елемент з позначкою * належить множині В, знаходиться мінімальна різниця між елементами множини А i елементом з позначкою *.

8. Знаходимо найменшу з вказаних різниць, додаємо її до кожного елемента множини і повертаємось до пункту 2 [9, c. 33-34].

1.2 Алгоритм угорського методу

Угорський метод є одним з найцікавіших і найпоширеніших методів вирішення задач про призначення. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування [4, c. 211].

Сам алгоритм був розроблений і опублікований Гарольдом Куном в 1955 році. В 1957 році Джеймс Манкрес показав, що цей алгоритм працює за чіткий поліноміальний час (тобто, за час порядку поліному від n). Тому в літературі даний алгоритм відомий не лише як «угорський», але і як «алгоритм Куна-Манкреса» або «алгоритм Манкреса» [5, c. 18].

Безпосередньо алгоритм вирішення задачі складається з наступних кроків:

1. Віднімаємо у матриці С від кожного елемента і-го рядка мінімальний елемент цього рядка, і = 1…n.

2. Віднімаємо від кожного елемента j-го стовпця перетвореної матриці витрат його мінімальний елемент, j = 1… n. В результаті виконання двох пунктів кожний рядок і кожний стовпець матриці витрат мають принаймні один 0.

3. Проглядаємо послідовно рядки матриці витрат, починаючи з першого. Якщо рядок має лише один непозначений 0, позначаємо його символом * і закреслюємо (за допомогою символа ^) всі нулі у цьому ж стовпці. 0 вважається позначений, якщо він позначений символом *. Повторюємо ці дії, поки кожен рядок не буде мати непозначених нулів, або буде мати їх принаймі 2.

4. Дії пункту 3 повторюємо для всіх стовпців матриці витрат.

5. Дії пунктів 3 та 4 повторюємо послідовно (якщо необхідно), поки не одержимо один з трьох можливих випадків:

а) кожний рядок має призначення (має 0 з позначкою *);

б) є принаймні два непозначених нулі в деяких рядках і деяких стовпцях матриці витрат;

в) немає непозначених нулів і повне призначення ще не отримане (число нулів з позначкою * менше n).

6. У випадку а) задача про оптимальні призначення розв'язана: x_ij^*, що відповідають 0*, дорівнюють 1. решта - 0, кінець алгоритму. У випадку б) довільно вибираємо один з непозначених нулів, позначаємо його символом *, закреслюємо решту нулів у тому ж рядку і у тому ж стовпці і повертаємося до пункту 3. Якщо має місце випадок в), то переходимо до пункту 7.

7. Позначаємо символом # рядки, для яких не одержано призначення (в яких немає 0*). Такі рядки вважаємо позначеними, решту - непозначеними. Таку ж термінологію будемо використовувати і для стовпців матриці витрат.

8. Позначаємо символом # ще непозначені стовпці, які мають закреслений 0 (позначений символом ^) у позначених рядках.

9. Позначаємо символом # ще непозначені рядки, які мають призначення (тобто 0*) у позначених стовпцях.

10. Повторюємо дії пунктів 8 та 9 доти, поки більше не можна позначити рядків і стовпців матриці витрат.

11. Закреслюємо (за допомогою позначки &) непозначені рядки і позначені стовпці матриці витрат.

12. Знаходимо мінімальний не закреслений елемент матриці витрат, віднімаємо його від елементів кожного з не закреслених рядків, додаємо до елементів усіх закреслених стовпців і переходимо до пункту 3. При цьому позначки елементів матриці витрат (* та ^) втрачають свою силу.

Приклад 1. Розв'язати задачу оптимального призначення з матрицею витрат С.

Виконуючи дії пунктів 1, 2 алгоритму, які інколи називають попередніми перетвореннями, одержуємо еквівалентну матрицю С₁. Позначаємо нулі матриці С₁ у відповідності з пунктами 3, 4, 6 алгоритму. Оскільки кількість нулів, позначених *, менше n = 5, то переходимо до пункту 7. Виконуючи дії пунктів 7-10, позначаємо символом # спочатку другий рядок, потім перший стовпець та перший рядок матриці С₁. Після виконання пункту 11 алгоритму одержуємо матрицю С₂.

Мінімальний незакреслений елемент матриці С₂ дорівнює 1. Після виконання пункту 12 алгоритму одержуємо матрицю витрат С₃, до якої також внесені позначки у відповідності з діями пунктів 3-10 алгоритму. Виконання пунктів 11, 12 приводить, відповідно, до матриць С₄ та С_5.



Матриця С₅ містить також позначки, що відображають дії пунктів 3-5 алгоритму на наступній ітерації. Так як кількість 0* дорівнює 5, то одержано оптимальний розв'язок х*:

тобто перший працівник призначається на виконання першої роботи, другий - четвертої, третій - п'ятої, четвертий - третьої, п'ятий - другої. При цьому L (x*) = 25 [9, c. 31-33].

1.3 Формулювання вимог і постановка задачі

Одним із завдань проведеного нами дослідження є розробка програми для візуалізації алгоритму угорського методу. Для цього слід врахувати деякі вимоги до роботи цієї програми:

1. Програма повинна нести універсальний характер. Тобто, кількість працівників та витрати, пов'язані із їхнім призначенням, наперед невідомі. Ці дані повинен вводити користувач.

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

3. Результат призначення подається у вигляді таблиці з нулів та одиниць (наприклад, як матриця х* у пункті 2, ст. 11).

4. На екран також повинна виводитись загальна сума витрат при оптимальному призначенні працівників.

5. Програма повинна містити коментарі та пояснення.

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

Вхідними даними для роботи програми є:

· n - кількість працівників та, відповідно, робіт;

· С - матриця витрат;

Вихідні дані:

· С* - деформована вхідна матриця С, яка демонструє результат виконання програми;

· Suma - сумарні витрати відповідно до призначення працівників;

Проміжні дані:

· всі інші змінні, необхідні для виконання проміжних етапів алгоритму.

2. Програмна реалізація алгоритму угорського методу

2.1 Обґрунтування вибору засобів програмування

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

Тепер на ринку ПО пропонується кілька систем візуального програмування. У першу чергу це Delphi, C++ Builder, Visual Basic, Visual C++. Найбільш повними, універсальними і часто використовуваними системами є Delphi і Builder C++ від Borland. Ці мови мають найбільшу і наймогутнішу бібліотеку візуальних компонентів. Крім того, ця бібліотека постійно поповнюється за рахунок інших компаній, що створюють програмне забезпечення. Система Delphi є ще й однією з найпростіших у вивченні, що дає їй перевагу над іншими візуальними мовами. Delphi має прекрасні засоби для обробки і збереження як локальних так і мережевих баз даних. Виходячи із цього я зупинила свій вибір на системі Delphi-7.0.

Вибір пакету Borland Delphі 7.0 обумовлений наступними його особливостями:

· можливість повторного використання готових програмних компонентів;

· наявність великої кількості стандартних компонентів, а також достатня кількість бібліотек від сторонніх фірм, що розширюють і доповнюють можливості стандартних;

· можливість генерації коду під платформу wіn32;

· підтримка технологій ActіveX, OLE, COM, ІnterNet-технологій;

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

· орієнтація на «візуальні» методи розробки програм, що дозволяє швидко і якісно спроектувати і реалізувати стандартний користувальницький інтерфейс;

· перспективність, популярність і широка поширеність середовища розробки у світі.

2.2 Розробка структури програми та системи її візуалізації

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

Найпоширенішими способами подання алгоритмів є словесний та блок-схеми. Словесний алгоритм угорського методу описаний у пункті 2 (ст. 10). Таким чином для максимально продуктивного та швидкого написання програми на базі словесного алгоритму я розробила блок-схему для даної задачі.

Блок-схема - це графічний спосіб представлення алгоритму, кожна дія якого представлена у вигляді послідовності блоків, з'єднаних між собою [6, c. 11].

Для реалізації алгоритму угорського методу ми використовували такі елементи блок-схеми:

· початок/кінець, який позначає початок та кінець алгоритму;

· введення / виведення, який позначає введення вхідної інформації та виведення проміжної інформації чи результату;

· блок обробки даних, який позначає дію, яку треба виконати;

· блок умови, який позначає перевірку значення логічного виразу деякої умови; служить для реалізації розгалуження та циклів з передумовою та після умовою;

· блок циклу, який позначає цикл з наперед відомою ітерацією.

Блок-схема для алгоритму угорського методу наведена у «Додатку А».

Для розробки програми середовище Borland Delphi передбачає такі компоненти:

1. Вікно форми (Form). Саме форма створює уявлення про те, як виглядатиме програма візуально. На ній розміщуються зображення, кнопки, таблиці та все інше, що повинно бути у вікні майбутньої програми. Форма володіє різними властивостями - користувач може задавати заголовок форми, її колір, положення, розміри та ін.

2. Вікно коду програми (Unit). У цьому вікні міститься код програми, процедури та функції, які виконує програма, чи її елементи.

Для візуалізації алгоритму угорського методу ми використовували такі компоненти середовища Borland Delphi

· StringGrid - таблиця даних стрічкового типу. За умовою задачі програма має працювати з цілочисельними даними, для такого випадку передбачені функції StrToInt та ІntToStr, які змінюють дані з стрічкового типу в цілочисельний і навпаки.

· Image - компонент призначений для завантаження зображень у програму. В даному випадку використався виключно для надання графічної оболонки програмі.

· Label - компонент, призначений для відображення статично тексту, тобто надписів, міток на формі, які не змінюю на протязі всієї роботи програми. Текст надпису можна змінити в ході програми, використовуючи властивість Caption. Текст може містити максимум 255 символів стрічкового типу.

· BitBtn - кнопка, яка крім текстового заголовку може також відображати растрові зображення. Виглядом і розміщенням зображення на поверхні кнопки можна керувати за допомогою властивостей кнопки.

· SpinEdit - компонент, призначений виключно для введення цілих чисел. Дві кнопки, що знаходяться в правій частині компонента, надають можливість покрокової зміни значення числа [10].

2.3 Розробка програмного коду

Код програми в Delphi ми записували у вікні Unit, яке складаєься з таких частин:

1. Uses - в цьому розділі описані бібліотеки, які використовуються при роботі програми. В нашій програмі це такі біблотеки: Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, Grids, StdCtrls, Spin, Buttons, ExtCtrls, jpeg;

2. Type - розділ, в якому описуються типи даних, з якими працює програма, зокрема: TForm1 = class(TForm), SpinEdit1: TSpinEdit; StringGrid1: TStringGrid; Label2: TLabel; Label1: TLabel; BitBtn1: TBitBtn; BitBtn2: TBitBtn; Image2: TImage; Label3: TLabel; Label4: TLabel; procedure SpinEdit1Change (Sender: TObject); procedure BitBtn1Click (Sender: TObject); procedure BitBtn2Click (Sender: TObject);

3. Var - розділ, який описує глобальні змінні та вказує їхній тип. В нашій програмі використовувались такі змінні: Form1: TForm1; i, j, kinets, k1, kin1, poz, k, v1, v2, v3, v5, nepnul, i2, step, d, a1, x, d1, y, a2, v4, b, n, n1, min, Suma: Integer; C, M: array [0.. 30,0..30] of Integer;

Після цього йде безпосередньо текст програми. Так як ми використовували 2 компоненти BitBtn і 1 компонент SpinEdit, то текст нашої програми поділений на 3 процедури. Перша з них відповідає за здійснення функцій при активації SpinEdit, інші дві відповідають за дії при натисканні кнопок BitBtn.

При введені числа в SpinEdit програма присвоює n введене число, тобто кількість працівників. Також задається кількість стовпців і рядків таблиці - n+2. Два останні рядки і стовпці не призначені для введення зарплат і слугують виключно для наочного відображення роботи алгоритму угорського методу. Значення в комірках таблиці присвоюються `', комірки у двох останніх рядках і стовпцях таблиці позначаються символом «0». Ці дії ми реалізували у вигляді такого коду:

procedure TForm1. SpinEdit1Change (Sender: TObject);

begin

step:=1;

n:=SpinEdit1. Value;

StringGrid1. RowCount:=n+2;

StringGrid1. ColCount:=n+2;

for i:=0 to n-1 do

for j:=0 to n-1 do

StringGrid1. Cells [j, i]:=' ';

for i:=0 to n+1 do

begin

StringGrid1. Cells [n, i]:=IntToStr(0);

StringGrid1. Cells [n+1, i]:=IntToStr(0);

StringGrid1. Cells [i, n]:=IntToStr(0);

StringGrid1. Cells [i, n+1]:=IntToStr(0);

end;

end;

Наступною в програмі описана процедура, яка виконується при натисканні однієї з кнопок. Ця кнопка має назву «Розрахувати призначення» і в кінці виконання на екран виводить безпосередньо розв'язок задачі, не демонструючи її поетапного вирішення.

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

Після цього відбувається безпосередня реалізація алгоритму угорського методу.

Пошук мінімального елемента в рядку та віднімання значення цього елемента від всіх елементів рядка реалізується таким кодом:

for i:=1 to n do

begin

min:=C [i, 1];

for j:=1 to n do

if C [i, j]<min then min:=C [i, j];

for j:=1 to n do

C [i, j]:=C [i, j] - min;

end;

програма алгоритм візуалізація

Аналогічно здійснюються такі ж дії зі стовпцями матриці. У коді лічильники циклів з i змінюється на j, і навпаки. Значенню min присвоюється не С [i, 1], а С [1, j].

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

Наступний пункт алгоритму звучить так - проглядаємо послідовно рядки матриці витрат, починаючи з першого; якщо рядок має лише 1 непозначений 0, позначаємо його символом * і закреслюємо за допомогою символа ^ всі нулі у цьому ж стовпці; повторюємо ці дії, поки кожен рядок не буде мати непозначених нулів, або буде мати їх принаймі два.

У нашій програмі замість позначення * ми використували позначення «1000», а замість ^ - «2000».

Цей пункт описую таким кодом програми:

repeat

begin

for i:=1 to n do

begin

nepnul:=0;

for j:=1 to n do

if C [i, j]=0 then nepnul:=nepnul+1;

if nepnul=1 then

begin

for j:=1 to n do

if C [i, j]=0 then

begin

poz:=j;

C [i, j]:=1000;

end;

for i2:=1 to n do

if C [i2, poz] = 0 then C [i2, poz]:=2000;

end;

end;

k1:=0;

for i:=1 to n do

begin

nepnul:=0;

for j:=1 to n do

if C [i, j]=0 then nepnul:=nepnul+1;

if (nepnul=0) or (nepnul=2) then k1:=k1+1;

end;

if k1=n then kin1:=1;

end

until kin1=1; n

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

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

v1:=0;

for i:=1 to n do

for j:=1 to n do

if C [i, j]=1000 then v1:=v1+1;

if v1=n then kinets:=1;

Коли змінна kinets набуває значення 1, то загальний цикл з післяумовою завершується. Якщо ж перша умова не виконується, то перевіряється наступна умова:

v2:=0;

d:=0;

d1:=0;

for i:=1 to n do

for j:=1 to n do

if C [i, j]=0 then v2:=v2+1;

if v2>=2 then

begin

i:=1; j:=1;

repeat

begin

repeat

begin

if C [i, j]=0 then

begin

x:=i;

y:=j;

C [x, y]:=1000;

d:=1;

d1:=1;

for i2:=1 to n do

if C [x, i2]=0 then C [x, i2]:=2000;

for i2:=1 to n do

if C [i2, y]=0 then C [i2, y]:=2000;

end

else

begin

j:=j+1;

if (j=n) then d1:=1;

end;

end

until d1=1;

i:=i+1;

end

until d=1;

end;

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

v3:=0;

v4:=0;

for i:=1 to n do

for j:=1 to n do

begin

if C [i, j]=0 then v4:=v4+1;

if C [i, j]=1000 then v3:=v3+1;

end;

Реалізація 7 кроку, в якому символом # позначаються рядки, для яких не одержано призначення (замість # програма ставить символ «1» в комірку в n+1 стовпці):

if (v3<n) and (v4=0) then

begin

for i:=1 to n do

begin

v5:=0;

for j:=1 to n do

if (C [i, j]<1000) or (C [i, j]>1000) then v5:=v5+1;

if v5=n then C [i, n+1]:=1;

end;

8 та 9 крок передбачають позначення символом # непозначені стовпці, які мають призначення у позначених стовпцях і непозначені рядки, які мають призначення у позначених стовпцях. Позначення стовпців реалізується аналогічно як позначення рядків символом «1». Ці дії повторюються доти, поки більше не можна позначити рядків і стовпців. Для цього використовуємо цикл з післяумовою. При позначенні рядка чи стовпця до змінних а1 і а2 відповідно додається 1. Цикл завершується, якщо позначення ні рядків не стовпців не відбулось. Тобто, коли а1 і а2 дорівнюють нулю.

В пункті 11 алгоритму угорського методу необхідно закреслити за допомогою позначки & непозначені рядки і позначені стовпці матриці витрат. Замість символу & програма проставляє «1» у n+2 рядках і стовпцях:

for i:=1 to n do

if C [i, n+1]=0 then C [i, n+2]:=1;

for j:=1 to n do

if C [n+1, j]=1 then C [n+2, j]:=1;

Останній пункт алгоритму - знаходимо мінімальний не закреслений елемент матриці витрат, віднімаємо його від елементів кожного з не закреслених рядків, додаємо до елементів усіх закреслених стовпців і переходимо до пункту 3.

У формі коду цей пункт набуває наступного вигляду:

- знаходження мінімального не закресленого елементу матриці (так як максимальне число в матриці може бути 2000, значенню min ми присвоюємо 3000, що означає, що в будь-якому випадку знайдеться елемент, менший за min):

min:=3000;

for i:=1 to n do

for j:=1 to n do

if (C [i, n+2]=0) and (C [n+2, j]=0) then

if C [i, j]<min then min:=C [i, j];

- віднімання min від усіх елементів незакреслених рядків та додавання до елементів усіх закреслених стовпців, а також заміна усіх значень 1000 та 2000 на 0:

for i:=1 to n do

for j:=1 to n do

if (C [i, j]=1000) or (C [i, j]=2000) then

C [i, j]:=0;

for i:=1 to n do

for j:=1 to n do

if C [i, n+2]=0 then

C [i, j]:=C [i, j] - min;

for j:=1 to n do

for i:=1 to n do

if C [n+2, j]=1 then

C [i, j]:=C [i, j]+min;

Наприкінці коду йде перевірка умови, чи змінна kinets дорівнює 1. Якщо так-то загальний цикл з післяумовою завершується, дані з матриці С копіюються в таблицю програми.

Так як матриця С наприкінці програми набуває значень в комірках або 0, або 1, то, відповідно підрахувати загальні витрати неможливо. Тому відбувається звернення до матриці М. Якщо комірка матриці С дорівнює 1, то до загальної суми додається значення такої ж комірки з матриці М.

З допомогою зміни в програмі текстового наповнення компонентів Label на екран виводиться загальна сума витрат.

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

2.4 Тестування та верифікація програми

Перевіримо роботу програми для матриці витрат такого вигляду:

13	23	18
54	32	45
79	12	53

Задаємо кількість працівників (3) та заповнюємо таблицю (рис. 1). Віднімаємо від кожного елементу в рядку мінімальний елемент цього рядка (рис. 2). Виконуючи дальше послідовно кроки алгоритму угорського методу в кінцевому результаті ми отримуємо такий результат (рис. 3). Якщо задати таку ж таблицю вихідних даних, але натиснути кнопку «Розрахувати призначення», не спостерігаючи за покроковим виконанням програми, ми отримаємо такий самий результат (рис. 4).

Рис. 1.



Рис. 2.

Рис. 3.



Рис. 4.

Для того, що перевірити роботу програми, спробуємо розглянути всі можливі варіанти призначення працівників, тобто розв'яжемо цю задачу комбінаторним методом.

Розглянемо можливі призначення та сумарні витрати пов'язані з цим призначенням:

123 - 13 + 32 + 53 = 98;

132 - 13 + 12 + 45 = 70;

213 - 54 + 23 + 53 = 130;

231 - 54 + 12 + 18 = 84;

312 - 79 + 23 + 45 = 147;

321 - 79 + 32 + 18 = 129;

Очевидно, що найменші сумарні витрати пов'язані з призначенням 1 працівника на 1 роботу, 2 працівника на 3 і 3 працівника на 2. Такий же результат ми отримали, використовуючи програму.

Висновки

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

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

Для реалізації алгоритму угорського методу у вигляді програмного продукту ми обрали середовище Borland Delphі 7.0. Це середовище має ряд переваг порівняно з іншими та відповідає усім вимогам для виконання завдань нашого дослідження.

За мету ми ставили не лише розробити програму, яка вірно розв'язуватиме задачу оптимального призначення, а й розробити візуалізацію алгоритму угорського методу. Таким чином в програму передбачені компоненти, які дозволяють по кроках простежити виконання алгоритму та переконатись у справності роботи програми.

Програма містить деякі обмеження. Наприклад, кількість працівників не може перевищувати 100, а сума заробітної плати для кожного з них не може перевищувати 999. Якби дана програма розроблялась з метою практичного застосування, такі умови були б некоректними. Але так як завданням є саме візуалізація алгоритму угорського методу, то діапазон вхідних даних не є таким суттєвим. Основне завдання - наочно продемонструвати як працює алгоритм і воно, безперечно, виконано. Про це свідчить тестування та верифікація даної програми.

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

Список використаних джерел

1. Грызина, Н.Ю. Математические методы исследования операцій. / Н.Ю. Грызина. - Москва: МЭСИ, 2005. - 12 с.

2. Наследов, А.Д. Математические методы. / А.Д. Наследов. - СПб: Речь, 2004. - 38 с.

3. Попов Ю.Д. Методические рекомендации для выполнения практических, лабораторных и самостоятельных работ по методам оптимизации и математического программирования на персональных компьютерах для студентов факультетов кибернетики, информационных технологий, компьютерных наук и менеджмента. / Ю.Д. Попов. - Киев: Издательско-полиграфический центр «Киевский університет», 2006. - 65 с.

4. Сакович В.А. Исследование операций (детерминированные методы и модели). / В.А. Сакович. - Мн.: Выш. шк., 1984. - 256 с.

5. Цирель С.В. Венгерский способ. / С.В. Цирель. - Москва: УРСС, 2007. - 120 с.

6. Шапкин А.С. Математические методы / А.С. Шапкин. - Москва, 2004. - 104 с.

7. Агальцов В.П. Математические методы в программировании. / В.П. Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006 г. - 224 с.

8. Волков И.К. Исследование операцій. / И.К. Волков, Е.А. Загоруйко. - М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. - 436 с.

9. Тюптя В.І. Дискретне програмування. [Електронний ресурс] / В.І. Тюптя, В.І. Шевченко, В.К. Стрюк. - Київ: Електронна бібліотека факультету кібернетики, 2003. - 37 ст. - Режим доступу:

http://www.cyb.univ.kiev.ua/library/books/tiuptia-27.pdf

10. Уроки делфи начинающим с нуля. [Електронний ресурс]. - Режим доступу: http://www.delphi-manual.ru.

Размещено на Allbest.ru