Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 44
Текст из файла (страница 44)
Это станет видно тогда, когда в результате работы алгоритма дефекта обнаружится, что допустимого решения не существует. Таким образом, последнее нз найденных назначений является оптимальным решением задачи на узкие места. Обоснованием этого увверждения является тот факт, что с помощькэ алгоритма дефекта решается последовательность задач о назначениях, в которой минимальная эффективность постоянно увеличивается (в результате исключения дуг). Данный алгоритьв иллюстрируется на модельном примере, описанном в табл. 3.1(э. Таблица 8.10. Матрица эффективности Рабочее место Рабочий Элемент ап матрицы равен эффективности (числу деталей, из готавливаемых за 1 ч) выполнения задания 1-м рабочим при назначении его на 1-е рабочее место.
Нулевые значения элементов аы и аае указывают на то, что рабочие 1 и 3 не имеют нужной квалификации для выполнения работы 5. Решая задачу на узкие места как обычную задачу о назначениях (с 12 узлами и 36 дугами), с помощью алгоритма дефекта получаем следующее назначение: Назначение 1 Рабочий 1 — «-работа 2 с эффективностью 3 Рабочий 2 — «работа 4 с эффективностью 8 Рабочий 3 — «-работа ! с эффективностью 8 Рабочий 4 — иработа б с эффективностью 8 Рабочий 8 — иработа 3 с эффективностью 9 Суммарная эффективность равна 36; минимальная эффективность равна 3. Поэтому исключаем те элементы матрицы (и соответствующие им дуги сети), значение которых не превосходит 3. Теперь сеть состоит нз 12 узлов и 24 дуг.
Решая с помощью алгоритма дефекта задачу о назначениях для построенной сети, получаем следующее решение: 27! Алеоратм дефекта Ноэначение 2 Рабочий !†работа 4 с эффективностью 6 Рабочий 2 †.работа ! с эффективностью 4 Рабочий 3 в работа 2 с эффективностью 4 Рабочий 4 †«работа 5 с эффективностью 8 Рабочий 6 — ч-работа 3 с эффективностью 9 Суммарная эффективность теперь уменьшилась до 31, однако минимальная эффективность увеличилась до 4. Исключим далее те дуги сети, которым соответствует эффективность, не превосходящая 4. Теперь сеть содержит 12 узлов и 21 дугу.
С помощью алгоритма дефекта определяем, что допустимого решения для данной сети не существует. Следовательно, назначение 2 является оптимальным в исходной задаче на узкие места. По сравнению с первоначальным назначением получен выигрыш на 33'йЪ (узкое место стало шире), хотя суммарная эффективность уменьшилась. Это улучшение решения связано с тем, что из сети несколько раз удаляются дуги и задача решается заново. Таким образом, мы не только получаем оптимальное решение задачи на узкие места о назначениях, но и еще раз .подтверждаем общеизвестное правило: больше работаешь — больше получаешь.
3.2!. СОСТАВЛЕНИЕ ГРАФИКА ВЫПОЛНЕНИЯ ЗАДАНИИ С ИЗВЕСТНЫМИ ВРЕМЕННЫМИ ХАРАКТЕРИСТИКАМИ Рассмотрим задачу определения максимального числа рабочих, необходимого для выполнения фиксированного плана частично параллельных заданий. В другой постановке этой задачи требуется определить минимальное число станков, необходимое для выполнения плана заданий, если известно время наладки каждого станка, или определить минимальное число самолетов, необходимое для соблюдения заданного графика движения [1).
Решение данной задачи, найденное с помощью алгоритма дефекта, позволило определить для одного из районов минимальное число автобусов, требуемое для осуществления перевозок, маршрут и расписание которых были установлены местными властями (41. Сетевая постановка задачи станет очевидной при рассмотрении следующего примера (принадлежащего Полю Ленсену, конструкторско-технологический отдел Техасского университета в г. Остине).
Должны быть выполнены десять заданий. Моменты начала н завершения выполнения каждого задания, а также отрезки времени, необходимые для перехода с одних рабочих мест на другие (время на подготовку), приведены в табл. 3.11. Требуется найти минимальное число рабочих, необходимое для выполнения всех заданий. Используя табл. 3.11, можно определить, Глава 3' Таблица 211.
Матрица времен выполнения заданий зада. начало конец 1 а 3 4 $ а 7 8 в 10 ние какие задания являются «связанными». Два задания будем называть связанными, если выполнение одного из них и подготовку второго можно завершить до запланированного начала выполнения второго задания. Например, работа 1 связана с каждой из работ 2, 3, 7, 8 и 9, но не связана с работами 4, 5, 6 и !О (работа 1 завершается в 13.30, а время подготовки для работы 4 равно 230 мин.
или 3 ч. 50 мин. Складывая эти времена и учитывая, что работа 4 должна начаться в 16.00, получаем, что работы 1 и 4 не связаны). Аналогичным образом можно показать, что 1 связана с работами 2, 3, 7, 8, 9. 2 связана с работами 3, 8, 9. 3 не связана ни о одной работой. 4 связана с работами 2, 3, 8, 9.
5 связана с работами 3, 8. 5 связана с работами 2, 3, 4, 5, 7, 8, 9, 10. 7 связана с работами 2, 3, 8, 9. 8 не связана ни с одной работой. 9 связана с работами 3, 8. !О связана с работами 2, 3, 4, 8, 9. Отметим, что минимально допустимое число рабочих равно максимальному числу (несвязанных) заданий, никакие два иэ которых не могут быть выполнены одним и тем же человеком.
Для решения данной задачи с использованием алгоритма дефекта мы построим «сеть назначений», с помощью которой одни задания будут «назначаться» на другие задания (этн назначенные задания объединяются таким образом, что они могут быть выполнены одним человеком). Кроме источника и стока, в сети должны быть два «столбца» узлов; число узлов е каждом столбце равно числу заданий. Наличие в сети дуги, соединяюшей два заданных узла, зависит от того, являются ли эти узлы 1 2 3 5 6 7 8 9 10 13.00 13.30 18.00 20.00 22.30 23.00 16.00 17.00 16.00 19ьЭ 12.00 13.00 14.00 17.00 23.00 24.00 20.10 21.00 13.45 15.00 Работа Работа Работа Работа Работа Работа Работа Работа Работа Работа — 60 10 70 ЗО 0 50 200 240 20 15 15 30 20 35 26 60 60 60 10 230 180 20 40 75 40 5 О 70 30 75 — 20 15 750 70 — 15 20 75 120 60 45 ЗО 15 15 129 75 30 15 Ы 100 70 30 30 120 40 15 40 120 ЗЮ 30 60 5 15 20 5 120 70 10 20 60 то 5 240 90 65 30 30 15 45 — 10 5 Ф 45 — 20 10 80 60 — 120.
50 60 70 Алгоритм дефекта связанными или нет. Так, узел в первом столбце, соответствующий заданию 1, соединен дугами с узлами второго столбца, соответствующими заданиям 2, 3, 7, 8 и 9. Узлы, соответствующие заданиям 3 и 8, можно не включать в первый столбец (но следует включать во второй столбец), поскольку эти задания не связаны нн с каким другим заданием (однако другие задания связаны с ним). Верхняя граница потока ~по «возвратной» дуге„ или дуге «циркуляции» (т.
е. дуге, соединяющей главный сток с главным источником), равна разности между общим числом заданий и числом заданий, не связанных ни с какими другими заданиями. Верхняя граница потока по всем остальным дугам равна 1. Нижняя граница потока по каждой дуге равна О.
Цель — найти максимальный поток в построенной сети с ограниченной пропускной способностью. Для этого стоимость единицы потока по возвратной дуге полагается равной некоторому отрицательному числу (например, — 10), а стоимость потока по всем остальным дугам — равной О. Максимальный поток (оптимальное решение) в построенной сети определяет минимальное число рабочих, необходимое для выполнения плана заданий. В частности, с помощью дуг, поток по которым положителен, можно определить, какие задания следует объединить для выполнения их одним человеком. Число таких групп равно минимальному числу рабочих, требуемому для выполнения плана заданий.
По следующим «назначающим дугам» поток, соответствующий оптимальному решению,,положителен. Задание Задание Задание Задание Задание Задание Задание 1 †~задан 7 4 †.задание 2 5- задание 3 8 в задание !О 7 в задание 9 9 в задание 8 10 в задание 4 Задание 8 †+ задан 10 — л-задание 4л-задание 2 Задание 5 — г-задание 8 !8 †16 Напомним, что дуга в сети строится только в том случае, если соответствующие узлы связаны.
Поэтому найденное решение можно интерпретировать следующим образом: задание 1 связано с заданием 7, которое связано с заданием 9, которое связано с заданием 8. Задание 1 †+задан 7 †»задание 9 — з-задание 8. Эти четыре задания являются «объединенными» (каждое овязано с последующим) и могут быть последовательно выполнены одним человеком. Эта «строка» заданий обрывается тогда, когда задание 8 не удается связать ни с одним другим заданием.
Кроме. того, имеются еще две «строки» заданий: Глава 3 Таким образом, каждую из этих трех групп, или строк, заданий может выполнить один человек. При заданных ограничениях на время начала и время конца выполнения заданий, а также на время их подготовки меньше, чем трое рабочих, не смогут выполнить все 10 заданий. 3.22. ЗАДАЧА О ХРАНЕНИИ И СБЫТЕ ТОВАРА Рассмотрим следующую задачу управления запасами. Владелец магазина приобрел 50 радиоприемников, заплатвв по 20 долл.
за каждый. Из-за непостоянства спроса на эти радиоприемники продажная цена их изменяется каждый месяц. Кроме того, каждый месяц изменяются затраты на хранение радиоприемников, поскольку .изменяется их количество и условия хранения. Соответствующие данные приведены в табл. 3.12. Таблица З.зр. Исходные данные в задаче о хранендн н сбыте товара Задача формулируется следующим образом: сколько радиоприемников надо продать в каждый из месяцев 1, 2, 3 и 4, чтобы максимизировать прибыль. На рис. 3.21 изображена сеть для .данной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
