Методи розв’язування задач про призначення

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

Методи розв'язування задач про призначення



Реферат

Курсова робота: загальний обсяг роботи - 37 сторінок, 5 рисунків, 36 таблиць, 1 додаток на 1 сторінці, 19 джерел літератури.

Об'єктом дослідження є процес знаходження розв'язків задачі про призначення.

Предметом дослідження є методи розв'язування задач про призначення.

Мета даної роботи - проаналізувати методи розв'язання задачі про призначення та обґрунтувати їх практичну реалізацію.

У роботі використано такі методи дослідження: економіко-математичного моделювання, метод порівняння, метод системного аналізу.

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

В даній роботі проаналізовано угорський метод та метод Мака розв'язування задач про призначення, а також реалізовано задачу про призначення в середовищі MS Excel.

БУЛЕВЕ ПРОГРАМУВАННЯ, Задача про призначення, метод Мака, Оптимізація, угорський метод.



Зміст

Вступ

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

1.1 Економічна інтерпретаціязадачі про призначення

1.2 Загальна постановка задачі про призначення

Розділ 2. Методи розв'язування задачі про призначення

2.1 Угорський метод розв'язування задачі про призначення

2.2 Модернізований угорський метод

2.3 Метод Мака

Розділ 3. Розв'язування задачі про призначення

3.1 Розв'язування задачі угорським методом

3.2 Розв'язування задачі методом Мака

3.3 Розв'язування задачі про призначення в середовищі MSExcel

Висновки

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

Додаток



Вступ

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

Мета даної роботи - проаналізувати методи розв'язання задачі про призначення та обґрунтувати їх практичну реалізацію.

Завдання даної роботи:

- Визначення ідеї методів розв'язування задачі про призначення;

- Побудова економіко-математичної моделі задачі про призначення;

- Дослідження напрямів практичного застосування задач про призначення;

- Виявлення недоліків та переваг в методах розв'язання задач про призначення.

Об'єктом дослідження є процес знаходження розв'язків задачі про призначення.

Предметом дослідження є методи розв'язування задач про призначення.

У роботі використано такі методи дослідження:

1) економіко-математичного моделювання - при побудові моделі задачі про призначення,

2) метод порівняння - порівняння задачі про призначення та транспортної задачі, а також методів розв'язування задач про призначення,

3) метод системного аналізу - усі елементи в системі вважаються взаємопов'язаними та сприймаються цілісно.



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

1.1 Економічна інтерпретаціязадачі про призначення

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

З іншого боку задача про призначення належить до задач лінійного програмування. Вона є спеціальним випадком транспортної задачі, яка у свою чергу може бути представлена як задача про потік мінімальної вартості[5].

Уперше задача про призначення булла розглянута в геометричній формі Гаспаром Монжем у 1784 році. Проте на початку ХХ століття булла встановлена некоректність розв'язку Монжа. Наступні кроки в розв'язанні задачі про призначення зроблені Кенігом і Егерварі в першій третині XX століття. Кеніг і Егерварі розглядали цю задачу як задачу пошуку досконалого паросполучення мінімальної ваги у зваженому дводольному графі. Їх роботи стали основою для угорського методу, розробленого Куном у 50-х роках минулого століття. У 1947 році Данциг запропонував симплекс-метод для розв'язання загальної задачі лінійного програмування, до якої легко зводиться задача про призначення. Задача про призначення, поставлена Данцигом і Фалкерсоном, може також розглядатися як задача про максимальний потік мінімальної вартості. У 1961 році Басакер і Гоуен опублікували алгоритм для її розв'язання. Цей алгоритм для загальної задачі, як і алгоритм симплекс-методу, має експоненціальну складність, а для задачі про призначення ? поліноміальну. Поліноміальний алгоритм для задачі про максимальний потік мінімальної вартості, заснований на алгоритмі Клейна, що був опублікований у 1967 році, вперше запропонований у 1987 році Гольбергом і Тар'яном[10].

У таблиці 1.1 представлені можливі варіанти практичного застосування задачі про призначення.

Таблиця 1.1

Ресурси	Об'єкти	Критерії ефективності
Працівники Грузові машини Верстати Екіпажи Комівояжер	Робочі місця Маршрути Ділянки Рейси Міста	Час Витрати Кількість переробленої продукції Час простою Товарообіг

1.2 Загальна постановка задачі про призначення

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

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

Вихідні параметри моделі задачі про призначення:

1. n - кількість ресурсів, m - кількість робіт.

2. ai=1 - одинична кількість ресурсу Ai (i=1,2,…,n), наприклад: один працівник;один транспортний засіб; одна наукова тема і т.д.

3. bj=1 - одинична кількість роботи Bj (j=1,2,…,m),наприклад: одна посада; один маршрут; одна лабораторія.

4. cij - характеристика якості виконання роботи Bj за допомогою ресурсу Ai. Наприклад, компетентність i-го працівника при роботі на j-й посаді; час, за який i-ий транспортний засіб перевезе вантаж по j-му маршруту; ступінь кваліфікації i-ої лабораторії при роботі над j-ою науковою темою.

Шукані параметри:

1. xij - факт призначення або непризначення ресурсуAi на роботуBj :

xij=

2. L(x) - загальна (сумарна) характеристика якості розподілу ресурсів по роботах[2, с. 95]

Математична модель задачі про призначення:

= (1.1)

(1.2) - (1.4) - система обмежень. (1.2) - обмеження на виконання однієї роботи не більше ніж одним працівником; (1.3) - обмеження на виконання одним працівником не більше однієї роботи; (1.4) - обмеження на булевість змінних [17].

У деяких випадках, наприклад, коли cij - це компетентність, досвід роботи або кваліфікація працівників, умова задачі може потребувати максимізації цільової функції, на відміну від (1.1). У цьому випадку цільову функцію L(x) заміняють на L1(x)=-L(x) і розв'язують задачу з цільовою функцією L1(x)>min, що рівносильно розв'язанню задачі з цільовою функцією L(x)>max[3, с.227].

У таблиці 1.2 представлено загальний вигляд транспортної матриці задачі про призначення[7,с 51].



Таблиця 1.2

Ресурси, Ai	Роботи, Bj	Кількість ресурсів
	B1	B2	…	Bm
A1	c11	c12	…	c1m	1
A2	c21	c22	…	c2m	1
…	…	…	…	…	…
An	cn1	cn2	…	cnm	1
Кількістьробіт	1	1	…	1	=

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

n = m,

.

При цьому умова xij?{0,1} означає виконання вимоги цілочисельності змінних xij. Це пов'язано з тим, що потужності всіх джерел і стоків дорівнюють одиниці, звідки випливає, що в припустимому цілочисельному рішенні значеннями змінних можуть бути тільки 0 та 1. Як окремий випадок класичної транспортної задачі, задачу про призначення можна розглядати як задачу лінійного програмування (ЗЛП). Тому в даномувипадку використовують термінологію і теоретичні результати лінійного програмування. У задачі про призначення змінні xij, можуть приймати значення 0 або 1.

При цьому, відповідно до (1.2) - (1.4), в будь-якому припустимому рішенні лише n змінних можуть приймати значення 1. Отже, будь-яке припустиме базисне рішення задачі про призначення буде виродженим, так що алгоритм розв'язання транспортної задачі застосувати можливо, але неефективно.[1. с. 46-47]

Зауважимо, що задачі математичного програмування, в яких на змінні накладаються умови (1.4), називаються задачами з булевими змінними. Отже, задача про оптимальні призначення є ЗЛП з булевими змінними.

Квадратні матриці С=|||| та D=|||| ( i , j =1,..., n ) будемо називати еквівалентними, якщо елементи однієї з них одержуються з елементів другої шляхом додавання певних чисел до кожного рядка і кожного стовпця. Ці числа можуть бути різними для різних рядків та стовпців. Отже, матриці С та D еквівалентні, якщо, наприклад,

(1.5)

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

Доведення. Нехай матриця С еквівалентна матриці (1, j1), (2, j2),...,( n , jn) -- оптимальні призначення у задачі з матрицею витрат С, тобто i-й виконавець призначається на виконання j-ї роботи, (і, j=1,..., n ). Припустимо, що це призначення не є оптимальним у задачі з матрицею витрат D .

Нехай ( 1 , j1'), (2, j2'),...,( n , jn') -- оптимальні призначення у задачі з матрицею витрат D , причому

В силу (1.5) звідсимаємо

Або

Проте

бо в обох випадках це є сума чисел, які додаються до стовпців матриці С. Отже, з (1.6) маємо

що протирічить тому, що для задачі з матрицею витрат С призначення ( i , ji ), i= 1,..., n , є оптимальним.

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

Доведена теорема дозволяє, якщо це необхідно, переходити від даної задачі про оптимальні призначення до задачі з еквівалентною матрицею витрат. Тому вихідну задачу завжди можна звести до задачі про оптимальні призначення з матрицею витрат, яка має лише невід'ємні елементи. Оскільки найменше можливе значення суми n елементів такої матриці, очевидно, дорівнює нулю, то наша задача зводиться до вибору у матриці витрат, або еквівалентнійїй, n нульових елементів, по одному в кожному рядку і кожному стовпці. В цьому, власне, полягає неформальний зміст алгоритму угорського методу, що викладається нижче, де матриці, еквівалентні вихідній матриці витрат С, називаються просто матрицями витрат. [11, с. 104-105]

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

Cпецифіка задачі про призначення дозволяє розв'язати її більш простими методами, ніж узагальненими методами для задач лінійного програмування. Одними з таких методів є угорський метод та метод Мака[6].



Розділ 2. Методи розв'язування задачі про призначення

2.1 Угорський метод розв'язування задачі про призначення

Сутність угорського методу

Угорський метод - алгоритм комбінаторної оптимізації, що розв'язує задачу про призначення в поліномному часі і який передує пізнішому симплекс-методу (пряма і двоїста задачі).

Метод був вперше запроваджений в 1955 році Гарольдом Куном у його статті "Угорський метод для задачі про призначення" на основі праць угорських математиків Денеша Кьоніга та Ейгена Егерварі (що і дало назву методу). В 1957 році Джеймс Манкрес переглянув алгоритм і дійшов висновку, що він є (строго) поліномним. З того часу алгоритм більш відомий як алгоритм Куна-Манкреса або задача про призначення Макреса. Лестер Рандольф Форд молодший та Делберт Рей Фулкерсон розширили метод до загальних транспортних задач. У 2006 році було відкрито, що Карл Густав Якобі розв'язав задачу про призначення в 19 сторіччі, а його розв'язок було опубліковано посмертно в 1890 році латинською мовою[16].

Алгоритм угорського методу складається з попереднього етапу і не більше, ніж (п-2) послідовно виконуваних ітерацій. Кожна ітерація пов'язана з еквівалентними перетворюваннями матриці, отриманої внаслідок проведення попередньої ітерації, а також з вибором в ній максимального числа незалежних нулів. Кінцевим результатом ітерації є збільшення числа незалежних нулів на одиницю. Як тільки число незалежних нулів досягне n, то проблему набору вирішено, а оптимальний варіант призначення визначається позиціями незалежних нулів в останній матриці [12].

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

Попередній етап. Розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Цю операцію проробляють над всіма стовпцями матриці С. У результаті утвориться матриця з ненегативними елементами, у кожному стовпці якої є, принаймні, один нуль.

Далі розглядають i-тий рядок отриманої матриці, розшукують її мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Цю процедуру повторюють із усіма рядками. У результаті одержимо матрицю С0 (С0~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С0 називається приведенням матриці.

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

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

Кожна ітерація починається першим і закінчується другим етапом. Між ними може кілька разів проводитися пари етапів: третій - перший. Перед початком ітерації знаком '+' виділяють стовпці матриці Ск , які містять нулі із зірочками.

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

1) рядок, що містить невиділений нуль, містить також і нуль із зірочкою;

2) цей рядок не містить нуля із зірочкою.

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

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

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

Цей процес за кінцеве число кроків закінчується одним з наступних результатів:

1) всі нулі матриці Ск виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

2) є такий невиділений нуль у рядку, де немає нуля із зірочкою. Тоді переходять до другого етапу, відзначивши цей нуль штрихом.

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

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

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

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

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

Блок-схема реалізації угорського методу представлена в додатку А.

2.2 Модернізований угорський метод

У цьому методі попередній етап - такий же як і у класичному методі, а перший та другий етапи змінюються на наступний: переглядаємо стовпчики. Якщо у стовпчику є лише 1 нуль, позначаємо його зірочкою. Умовно викреслюємо рядочок і стовпчик, у якому знаходиться нуль із зірочкою. Далі розглядаємо матрицю розмірністю (n-1)x(n-1). Знову переглядаємо стовпчики. Якщо залишилися стовпчики що містять більше одного нуля, переглядаємо рядочки. Якщо у рядочку є лише 1 нуль, позначаємо його зірочкою. І знову переходимо до розгляду стовпчиків.

Якщо кількість виділених нулів дорівнює розмірності матриці, тобто, n, - задача вирішена.

Якщо ні - переходимо до третього етапу класичного методу[4].



2.3 Метод Мака

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

Виділити в кожному рядку по одному мінімальному елементу. Стовпці, у яких немає виділених елементів називаються вільними, а інші-зайнятими[19].

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

Крок 1. Перевірка оптимальності плану. Якщо в таблиці немає жодного вільного стовпця, то отримане рішення є оптимальним, інакше перейти до кроку 2.

Крок 2. Позначити * (зірочкою) будь-який стовпець, у якому більш одного виділеного елемента.

Крок 3. Для всіх рядків, у яких є виділені елементи в позначених * (зірочкою) стовпцях, знайти різницю між мінімальним елементом серед непозначених * (зірочкою) стовпців ai і мінімальним елементом серед позначених * стовпців bi (Di = ai - bi).

Крок 4. Знайти мінімальну різницю D=min{Di} серед знайдених на кроці 3 різниць.

Крок 5. Перетворити поточну таблицю, додавши до всіх елементів усіх позначених * стовпців D. Непозначені стовпці залишаються без змін.

Крок 6. Елемент ai у непозначеному стовпці який використовувався для розрахунку мінімальної різниці виділити підкресленням як альтернативний (тепер він має ту ж вартість, що й елемент bi у позначеному стовпці).

Крок 7. Якщо альтернативний елемент ai, отриманий на кроці 6, знаходиться у зайнятому стовпці, то позначити цей стовпець * і перейти до кроку 3, інакше перейти до кроку 8.

Крок 8. У вільний стовпець в клітку з альтернативним елементом показати стрілочкою перенесення по рядку виділеного елементу в альтернативну клітину.

Крок 9. Якщо стовпець, з якого було перенесено виділений елемент, став вільним, перейти до кроку 8, інакше перейти до кроку 10.

Крок 10. Кінець даної ітерації. Перетворити таблицю, зробивши виділеними відповідні альтернативні елементи. Прибрати всі позначки * і підкреслення та перейти до кроку 1[8,9].



Розділ 3. Розв'язування задачі про призначення

3.1 Розв'язування задачі угорським методом

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

Таблиця 3.1

Студент Дисципліна	Петро	Оля	Юра	Юля	Катя
Дослідження операцій	48	36	43	45	39
Дискретний аналіз	40	41	49	38	32
Маркетинг	47	47	44	48	40
СППР	50	46	38	36	41
ПСЕП	43	35	32	34	25

Потрібно так закріпити предмети за студентами, щоб Тарас склав іспити з найкращим з можливих сумарним результатом.

Математична модель задачі

F=48x11+36x12+43x13+45x14+39x15+40x21+41x22+49x23+38x24+32x25+47x31+

+47x32+44x33+48x34+40x35+50x41+46x42+38x43+36x44+41x45+43x51+35x52+

+32x53+34x54+25x55>max

Поетапний розв'язок задачі

Таблиця вихідних умов (табл. 3.2).

Таблиця 3.2

С=	48	36	43	45	39
	40	41	49	38	32
	47	47	44	48	40
	50	46	38	36	41
	43	35	32	34	25

У таблиці 3.2 n=m, тому її можна розв'язати угорським методом.

Попередній етап. Цільова функція задачі направлена на максимум, тому розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Отримаємо таблицю 3.3:

Таблиця 3.3

С=	2	11	6	3	2
	10	6	0	10	9
	3	0	5	0	1
	0	1	11	12	0
	7	12	17	14	16

Далі розглядають i-тий рядок таблиці 3.3, розшукують в ній мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Отримують таблицю 3.4, яка еквівалентна таблиці 3.2:

Таблиця 3.4

С=	0	9	4	1	0
	10	6	0	10	9
	3	0	5	0	1
	0	1	11	12	0
	0	5	10	7	9

Відзначаємо систему незалежних нулів:

Таблиця 3.5

С0=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0	1
	0	1	11	12	0*
	0	5	10	7	9

Якщо кількість 0* дорівнює n, тоді задачу можна вважити розв'язаною. У цій задачі 0*<n, тому переходять до (к+1)-ої ітерації.

Зауваження. Перед початком кожної ітерації знаком '+' виділяють стовпці, які містять нулі із зірочками(табл. 3.6).

Таблиця 3.6

С0=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0	1
	0	1	11	12	0*
	0	5	10	7	9
	+		+		+



Перший етап. У таблиці 3.6 виділяють штрихом нуль, який знаходиться одночасно у невиділеному стовпці та у рядку з нулем із зірочкою. З нуля з зірочкою і з стовпця, в якому він знаходиться, знімають виділення. Відмічають рядок, в якому знаходиться нуль зі штрихом (табл.. 3.7).

Таблиця 3.7

С1=	0*	9	4	1	0
	10	6	0*	10	9
	3	0*	5	0?	1	+
	0	1	11	12	0*
	0	5	10	7	9
	+		+		+

Всі нулі матриці виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу, пропускаючи другий.

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

Таблиця 3.8

С'1=	0*	8	4	0	0
	10	5	0*	9	9
	4	0*	6	0?	2
	0	0	11	11	0*
	0	4	10	6	9

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



Таблиця 3.9

С?1=	0*	8	4	0?	0	+
	10	5	0*	9	9
	4	0*	6	0?	2	+
	0	0?	11	11	0*	+
	0?	4	10	6	9
			+

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

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0' ) ставимо зірочки, знищуючи їх над парними елементами (0* ). Потім знищуємо всі штрихи над елементами С1 і знаки виділення '+'. Перша ітерація закінчена. Отримали матрицю С2 (табл. 3.10)

Таблиця 3.10

С2=	0	8	4	0*	0
	10	5	0*	9	9
	4	0*	6	0	2
	0	0	11	11	0*
	0*	4	10	6	9

Після цієї ітерації кількість незалежних нулів стало дорівнювати 5 (розмірності матриці 5) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці С2 (тобто 0*).

L(x) = 43+47+49+45+41=225

Відповідь. Щоб Тарас склав іспити з максимально можливим результатом, одногрупники повинні допомагати йому в підготовці у такій відповідності:

Петро - ПСЕП;

Оля - маркетинг;

Юра - дискретний аналіз;

Юля - дослідження операцій;

Катя - СППР.

3.2 Розв'язування задачі методом Мака

Постановка задачі така ж сама, як і в розділі 3.1, але коефіцієнти цільової функції записуємо зі знаком ?-?, тому що задача на максимум.

Покроковий розв'язок задачі

Матриця вихідних умов разом з виділеними мінімальними елементами у рядках (табл. 3.11).

Таблиця 3.11

-48	-36	-43	-45	-39
-40	-41	-49	-38	-32
-47	-47	-44	-48	-40
-50	-46	-38	-36	-41
-43	-35	-32	-34	-25

Перша ітерація

Крок 1. В таблиці немає вільних стовпців, тому заданий план не єоптимальний.

Крок 2. Позначаємо * (зірочкою) перший стовпець, тому що у ньому 3 виділених елемента (табл. 3.12).

Таблиця 3.12

-48	-36	-43	-45	-39
-40	-41	-49	-38	-32
-47	-47	-44	-48	-40
-50	-46	-38	-36	-41
-43	-35	-32	-34	-25
*

Крок 3. Знаходимо мінімальний елемент серед позначених по рядках (bi), та мінімальний елемент серед непозначених по рядках (ai). Знаходимо різницю ai - bi(табл. 3.13).

Таблиця 3.13

ai - bi						bi
-45-(-48)=3	-48	-36	-43	-45	-39	-48
	-40	-41	-49	-38	-32
	-47	-47	-44	-48	-40
-46-(-50)=4	-50	-46	-38	-36	-41	-50
-35-(-43)=8	-43	-35	-32	-34	-25	-43
	*

Крок 4. Мінімальна різниця = 3.

Крок 5. Додаємо до усіх елементів першого стовпця число 3 (табл. 3.14).

Таблиця 3.14

-45	-36	-43	-45	-39
-37	-41	-49	-38	-32
-44	-47	-44	-48	-40
-47	-46	-38	-36	-41
-40	-35	-32	-34	-25
*

Крок 6. Виділяємо елемент таблиці a1, як альтернативний (він має тепер таку саму вартість як елемент b1) (табл. 3.15).

Таблиця 3.15

-45	-36	-43	-45	-39
-37	-41	-49	-38	-32
-44	-47	-44	-48	-40
-47	-46	-38	-36	-41
-40	-35	-32	-34	-25
*

Крок 7. Елемент a1 pнаходиться у рядку разом з виділеним елементом. Позначаємо стовпець 4 *(зірочкою) та вертаємося до кроку 3.

Крок 3?. Повторюємо аналогічні дії.

Таблиця 3.16

-43-(-45)=2	-45	-36	-43	-45	-39	-45
	-37	-41	-49	-38	-32
-47-(-48)=1	-44	-47	-44	-48	-40	-48
-46-(-47)=1	-47	-46	-38	-36	-41	-47
-35-(-40)=5	-40	-35	-32	-34	-25	-40
	*			*

Крок 4?. Мінімальна різниця = 1, причому у двох рядках. Обираємо довільну, наприклад, у третьому рядку.

Крок 5?. Додаємо до елементів 1 та 4 стовпців одиничку.

Таблиця 3.17

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*			*

Крок6?. Виділяємо елемент таблиці a3.

Таблиця 3.18

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*			*

Крок 7?. Елемент a3 знаходиться у вільному стовпці, тому переходимо до кроку 8.

Крок 8. Елемент a3 виділяємо, а з елементу b3 виділення знімаємо.

Таблиця 3.19

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Крок 9. Стовпець 4 став вільним.

Крок 10. Кінець першої ітерації.

Друга ітерація

Крок 1.

Таблиця 3.20

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 2.

Таблиця 3.21

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Крок 3.

Таблиця 3.22

-44-(-44)=0	-44	-36	-43	-44	-39	-44
	-36	-41	-49	-37	-32
	-43	-47	-44	-47	-40
-46-(-46)=0	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*

Крок 4. Мінімальна різниця 0 в четвертому рядку.

Крок 5.

Таблиця 3.23

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 6.

Таблиця 3.24

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 7 . Елемент b1 знаходиться у вільному стовпці.

Крок 8.



Таблиця 3.25

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25

Крок 9. Стовпець 1 залишився зайнятим.

Крок 10. Кінець другої ітерації.

Третя ітерація

Виконують аналогічні дії, що і в попередніх ітераціях.

Кроки 1-6.

Таблиця 3.26

	-44	-36	-43	-44	-39
	-36	-41	-49	-37	-32
	-43	-47	-44	-47	-40
-46-(-46)=0	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*

Крок 7.

Таблиця 3.27

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*

Кроки 3?-6?.



Таблиця 3.28

	-44	-36	-43	-44	-39
	-36	-41	-49	-37	-32
-47-(-47)=0	-43	-47	-44	-47	-40	-47
-41-(46)=5	-46	-46	-38	-35	-41	-46
-35-(-39)=4	-39	-35	-32	-33	-25	-39
	*	*

Крок 7? .

Таблиця 3.29

-44	-36	-43	-44	-39
-36	-41	-49	-37	-32
-43	-47	-44	-47	-40
-46	-46	-38	-35	-41
-39	-35	-32	-33	-25
*	*

Кроки 3?-6??.

Таблиця 3.30

-43-(44)=1	-44	-36	-43	-44	-39	-44
	-36	-41	-49	-37	-32
-44-(-47)=3	-43	-47	-44	-47	-40	-47
-41-(-45)=5	-46	-46	-38	-35	-41	-46
-32-(-39)=7	-39	-35	-32	-33	-25	-39
	*	*		*

Крок 7?

Таблиця 3.31

-43	-35	-43	-43	-39
-35	-40	-49	-36	-32
-42	-46	-44	-46	-40
-45	-45	-38	-34	-41
-38	-34	-32	-32	-25
*	*		*

Кроки 3???- 6???

Таблиця 3.32

-39-(-43)=4	-43	-35	-43	-43	-39	-43
-32-(-49)=17	-35	-40	-49	-36	-32	-49
-40-(-46)=6	-42	-46	-44	-46	-40	-46
-41-(-45)=4	-45	-45	-38	-34	-41	-45
-25-(-38)=13	-38	-34	-32	-32	-25	-38
	*	*	*	*

Крок 7???

Таблиця 3.33

-43	-35	-43	-43	-39
-35	-40	-49	-36	-32
-42	-46	-44	-46	-40
-45	-45	-38	-34	-41
-38	-34	-32	-32	-25

Крок 8.

Таблиця 3.34

-43	-35	-43	-43	-39
-35	-40	-49	-36	-32
-42	-46	-44	-46	-40
-45	-45	-38	-34	-41
-38	-34	-32	-32	-25

Крок 9. Стовпець 1 зайнятий

Крок 10. Кінець 3-ї ітерації.

В таблиці немає жодного вільного стовпця. Це означає цей план оптимальний. Розв'язок задачі аналогічний розв'язку задачі угорським методом (див. пункт 3.1) оптимальний угорський мак призначення

3.3 Розв'язування задачі про призначення в середовищі MSExcel

Задачу, постановку якої здійснено в пункті 3.1 можна розв'язати за допомогою середовища MS Excel. На рисунку 3.1. задані вихідні дані задачі про розподіл студентів за дисциплінами. Ефективність допомоги кожного зі студентів Тарасові по дисциплінам розташована в комірках B3:F7. Змінні знаходяться в комірках B10:F14. В комірках B16:F16 - обмеження на допомогу студентом Тарасові лише з однієї дисципліни, H10-H14 - обмеження на те, що з дисципліни може надати допомогу у підготовці лише один студент. В комірці F18 розраховано загальну ефективність п'ятьох студентів за формулою = СУММПРОИЗВ (B3:F7;B10:F14).

Рис. 3.1. Вхідні дані задачі

Щоб знайти оптимальне значення такої задачі в середовищі MSExcel треба застосувати надбудову "Поиск решений" (рис. 3.2). У вікні "Поискрешений" встановлюємо напрям цільової функції, в цьому випадку шукають максимум цільової функції, а також вводимо систему обмежень. На рисунку 3.3 показано як накладати обмеження на буле вість змінних.

Рис. 3.2. Обмеження при пошуку розв'язку задачі про призначення

Рис. 3.3 Додавання обмежень на булеві змінні

У вікні "Поиск решений" відкриваємо вікно "Параметры" (рис. 3.4) та застосовуємо до нашої задачі параметри "Линейная модель" і "Неотрицательные значения".

Рис. 3.4. Додаткові параметри пошуку розв'язків

На рисунку 3.5 представлено результати розв'язку, які є ідентичними до результатів розв'язку задачі за допомогою угорського методу та методу Мака [15].

Рис. 3.5. Розв'язок задачі про призначення



Висновки

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

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

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

У цій роботі застосовано середовище MS Excel для розв'язування задачі про призначення за допомогою надбудови "Поиск решений", що дозволяє уникнути великих розрахунків та довгих ітераційних процесів.

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



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

1. Ачкасов, А. Є. Конспект лекцій з курсу "Дослідження операцій"

(для студентів галузі знань0306 - "Менеджмент і адміністрування" напряму 6.030601 - "Менеджмент" заочної форми навчання) / А. Є. Ачкасов, О. О. Воронков; Харк. нац. акад. міськ. госп-ва. - Х.: ХНАМГ, 2012. - 132 с.

2. Банди Б. Б23 Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. - 176 с.: ил. ISBN 5-256-00186-8.

3. Вагнер Г. Основы исследования операций: в 3 т. / Г. Вагнер - М. : Мир, 1972. - Т.1. - 336 с.

4. Гужевська Л. А. Модернізований угорський метод вирішення задачі про призначення / Л. А. Гужевська // Управління проектами, системний аналіз і логістика. Технічна серія. - 2010. - Вип. 7. - С. 70-75. - Режим доступу:

http://nbuv.gov.ua/j-pdf/Upsal_2010_7_15.pdf.

5. Задача про призначення[Електронний ресурс]/ Вільна енциклопедія "Вікіпедія". - Режим доступу : http://uk.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BF%D1%80%D0%BE_%D0%BF%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%BD%D1%8F

6. КононенкоА.І., ХраповицькийІ.С., ЩелкуноваЛ.І.. Математичне про- грамування: Текстилекцій - Харків, ХДТУБА, 2010. - 114 с.

7. Кутковецький В.Я. Методи розв'язання задач дослідження операцій: Монографія. - Миколаїв: Вид-во ЧДУ імені Петра Могили, 2010. - 164 с. -ISBN 978-966-336-174-1

8. Лекція № 6. Задача про призначення, постановка задачі. Метод Мака рішення задачі про призначення[Електронний ресурс]. - Режим доступу :

http://studopedia.org/6-94437.html

9. Модели и методы оптимизации в экономике и менеджменте: учеб. пос. для практ. занятий / В. И. Муравьев [и др. ]; Балт. гос. техн. ун-т. - СПб. , 2008. 197 с

10. Недобачій С. І., Гвоздик Д. М. Новий метод розв'язання задачі про призначення // Математичні машини і системи №1. Інститут проблем математичних машин і систем НАН України, 2010. - С.55-59.

11. Попов Ю.Д., Тюптя В.І., Шевченко В.І. Методи оптимізації. Навчальний електронний посібник для студентів спеціальностей "Прикладна математика", "Інформатика", "Соціальна інформатика". ? Київ: Електронне видання. Ел. бібліотека факультету кібернетики Київського національного університету імені Тараса Шевченка, 2003.?215 с.

12. Саманцов О.О., Пірус Є.М. Використання середовища MS Excel для

розв'язання оптимізаційних задач вибору [Електронний ресурс]. Режим доступу:

http://www.slavdpu.dn.ua/fizmatzbirnyk/2010/p127-131.pdf

13. Самовик С. М. Розробка алгоритму та програмного забезпечення тренажера з теми "Угорський метод в задачі про призначення" дистанційного навчального курсу "Методи оптимізації та дослідження опрацій" С. 273-275 в збірнику тез Інформатика та системні науки (ІСН-2014): матеріали VВсеукр. наук.-практ. конф., (м. Полтава, 13-15 березня 2014 року) / за ред. О.О. Ємця. - Полтава: ПУЕТ, 2014. - 335 с.

14. Сіраш О. В. Дослідження операцій [Електронний ресурс]. Режим доступу:

http://lubbook.net/book_386.html

15. Трусов А. Ф.Excel 2007 для менеджерів та економістів: логістичні, виробничі та оптимізаційні розрахунки (+ CD) - СПб: Питер, 2009 - 256 с: Ил

16. Угорський алгоритм [Електронний ресурс]/Вільна енциклопедія "Вікіпедія". - Режим доступу :

http://uk.wikipedia.org/wiki/Угорський_алгоритм

17. Burkard Rainer Assignment Problems (Revisedreprint). -- SIAM, 2012. -- ISBN 978-1-61197-222-1.

18. Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253--258, 1956.

19. Mack, C. The Bradford Method for the Assignment Problem, The New J. of Stats, and Op. Res., 1, Part 1, 17-29, 1969.



Додаток

Рис. А.1 Блок-схема алгоритму угорського методу

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