ID задания #S56
Теги Дослідження операцій
На кінцевих станціях А і Б залізничної дільниці знаходяться пункти зміни локомотивних бригад, які обслуговують пасажирський рух. Потрібно закріпити поїзди за бригадами так, щоб одержати мінімальний загальний час знаходження їх в пунктах оберту. За технологією мінімальний час знаходження однієї бригади в пунктах оберту 2 години. Час відправлення поїздів пункту А та прибуття в пункт Б, а також відправлення поїздів з пункту Б та прибуття в пункт А відомий
Визначення можливих витрат часу бригадами в пунктах обороту.
Визначаємо можливі витрати часу бригад локомотивного депо А в пункті обороту Б. Наприклад, поїзд 1 прибуває в пункт Б в 07:00. Якщо бригада буде відправлена поїздом 2 у 02:00, то простій складе 19годин. Ця величина занесена в ліву верхню клітинку таблиці 1
...
Алгоритм рішення задачі про призначення
Маємо квадратну матрицю (таблицю). Для розв’язання задачі необхідно розмістити серед елементів матриці n одиниць так, щоб у кожному рядку та кожному стовпці було по одиниці, а сума вартостей у зайнятих одиницями клітинках була б мінімальною. Одиниця в клітинці (i,j) означає, що на i-ту роботу призначено j-го виконавця.
Дія 1. Побудувати початковий план: у кожному рядку в клітинку з мінімальною вартістю помістити одиницю. Якщо після цього усі стовпці виявляються зайнятими ( у кожному буде хоча б одна одиниця), то здобуто оптимальний план. Загальні затрати на виконання всіх робіт складатимуть суму елементів з тих клітинок, які зайняті одиницями.
Дія 2. Відмітити який-небудь стовпець, у якому зайнято одиницями більш ніж одну клітинку. Збільшити в ньому вартості на мінімальну величину так, щоб яка-небудь з вартостей у зайнятих клітинках дорівнювала якій-небудь вартості в цьому рядку. Елемент, що відповідає цій вартості, назвемо його альтернативним . Якщо він знаходиться в зайнятому стовпці, позначити його буквою а, стовпець також відмітити та аналогічно збільшити вартості в усіх відмічених стовпцях. З’явиться ще один альтернативний елемент, і якщо він також знаходиться в зайнятому стовпці, операцію повторювати доти, поки буде знайдено альтернативний елемент у вільному стовпці.
Дія 3. В останній альтернативний елемент перенести одиницю із зайнятої клітинки того ж рядку. Якщо число зайнятих стовпців збільшилося (на один), то ітерація закінчилася. Якщо число зайнятих стовпців не змінилося (один стовпець став зайнятим, а інший звільнився), то в альтернативний елемент, який знаходиться в одному стовпці з клітинкою, що звільнилася, перенести по рядку одиницю з зайнятого стовпця. Якщо цей останній стовпець став вільним, то операцію повторити.
Процес триває доти, поки в таблиці число зайнятих стовпців збільшилася на один.
Дії 2 й 3 (ітерація) повторювати доти, поки в таблиці не залишиться вільних стовпців.
Далі у роботі для зручності замість одиниць будемо клітини виділяти сірим кольором.
png - 1 шт.,
С нашими удобными сервисами без комиссии*
