Главная | Обратная связь | Поможем написать вашу работу!

Задача про призначення

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

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

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

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

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

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

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

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

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

– цільова функція

– умови

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

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

Угорський метод

Цей метод був запропонований угорським математиком Егерварі у 1931 р. і подалі розвинутий Г. Куном у 1953 р.

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

– попереднє перетворення матриці ;

– пошук оптимального розв’язку.

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

Алгоритм угорського методу спрямований на знаходження т базисних нульових елементів. Кожний базисний нуль відображує конкретний зв’язок , тобто „робота-об’єкт”, а сукупність базисних нульових елементів відображує допустимий або, у найкращому випадку, оптимальний варіант розв’язку.

Якщо матриця перетворена тільки за колонками, то вона називається зведеною за колонками, коли за рядками – зведеної за рядками, коли за колонками та рядками разом – повністю зведеною матрицею.

Основна ідея угорського методу базується на твердженні:

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

Алгоритм розв’язування

1. Перетворення початкової матриці на матрицю, яка зведена за колонками. Для цього у кожній -й колонці матриці вибирають мінімальний елемент

і по кожній колонці обчислюють елементи нової матриці

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

3. Аналіз на оптимальність. Якщо , де т – кількість рядків матриці, то розв’язок вважається оптимальним.

4. У випадку, коли , знаходиться мінімальне покриття матриці, до якого мають увійти всі нулі – базисні та вільні, тобто треба начебто „накрити” всі нулі. Правило побудови такого покриття наступне:

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

– позначають колонки, які мають вільні нулі у позначених рядках:

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

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

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

5. Складання нової сукупності нульових елементів. З частини матриці, яка не увійшла до покриття, вибирають мінімальний елемент . Величина віднімається від елементів матриці, які не увійшли до покриття, та додається до елементів, які стоять на перетині рядків і колонок покриття. Інші елементи не корегуються. Потім виконується перехід до п.2 алгоритму.

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

– якщо , то необхідно вводити фіктивних об’єктів, для яких

– якщо , то ця ситуація зводиться до попередньої, при цьому треба транспонувати початкову матрицю ;

– якщо за умовами , то необхідно зробити перетворення початкової матриці

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

– якщо має місце заборона на призначення і -ї роботи до -го об’єкта, то , де – завідомо велике число.

Блок-схема алгоритму угорського методу наведена на рис. 7.4.

Приклад

Згідно із замовленням треба обробити чотири деталі на чотирьох верстатах. Тривалість обробки (у хвилинах) кожної деталі на кожному верстаті наведено у матриці:

Деталі	Верстати
1-й	2-й	3-й	4-й

Оптимальний розв’язок

Фіксація

- рядків без базисних нулів

Рис.7.4

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

Виконаємо попереднє перетворення матриці: знайдемо по кожній колонці мінімальні елементи 10, 15,10, 5 та побудуємо наступну матрицю:

Деталі	Верстати
1-й	2-й	3-й	4-й
	0			0	1
					5
					4
	20

2 3

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

Знаходимо мінімальне покриття:

─ позначаються рядки, які не мають базисних нулів (1-й рядок);

─ позначаються колонки, які мають вільні нулі у позначених рядках (1-ша та 4-та);

─ позначаються рядки з базисними нулями у позначених колонках (2-й та 3-й).

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

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

Деталі	Верстати
1-й	2-й	3-й	4-й

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

Оптимальна прив’язка пар: (1,4), (2,3), (3,1), (4,2), цільова функція .

⇐ Предыдущая 2 3 4 5 6 7 8910 11 Следующая ⇒