Формальное описание алгоритма построения наибольшего паросочетания

 

Ввод:

a [ i, j ] – массив с элементами типа Boolean, задающий ребра в двудольном графе;

 

Инициализация:

Nas_u[ x ] – рабочий массив с элементами типа Boolean, содержащий насыщенные ребра, размерность массива x =Min(M, N), элемент nas _ u [ i ]= j если i -ый кандидат назначен на j –ую должность. Изначально присвоить nas _ u [ i ]=-1;

Nas _ I [ M ], Nas _ J [ N ] – рабочие массивы с элементами типа Boolean, содержащие информацию о насыщенности вершин из мн-в I и J, все элементы изначально равны false;

u [ M + N, M + N ] – массив, представляющий собой матрицу смежности ориентированного графа, изначально заполнить нулями;

Общий шаг:

1.(построение начального M * при помощи "жадного" алгоритма)

В цикле по i от 1 до M

В цикле по j от 1 до N

если (nas_I [ i ]=false and u [ i, j ]=1 and

n as_ J [ j ]=false) то

     n as_ I [ j ]=true, n as_ J [ i ]=true, nas_u [ I ]:= j;

2.(построение орграфа G Последнее изменение: понедельник 8 Март 2004, 17:29

Условие задачи для самостоятельного решения Среди 12 работников есть 6 мужчин: 2 инженера, 2 технолога и 2 прораба и 6 женщин тех же специальностей. Нужно сформировать максимальное число групп по 2 человека (1 мужчина и 1 женщина, разных специальностей), с учетом их психологической совместимости. Известно, что инженер Иванов и прораб Федоров смогут работать только с кем-то из технологов, технолог Сидоров –только с кем-то из прорабов, а технолог Петров – напротив, с прорабами работать не может. Подразумевается, что остальные работники не имеют предпочтений Примечание:размерность задачи такова, что решение может быть получено "на глаз", как результат несложного перебора вариантов. Несмотря на это, при решении задачи необходимо продемонстрировать знание основных алгоритмических шагов.

 

Последний срок сдачи: вторник 21 Март 2006, 23:55

Проанализируйте тему и ответьте на вопрос: Какова методика увеличения оборота промышленного предприятия, иными словами, что и в какой последовательности должно сделать руководство, чтобы за год поднять оборот на 50%? Исходные условия: расположение: г. Москва тип пр-ва: мелкосерийный выпуск различных взломостойких сейфов активы: произ площадь в аренде, коэфф использования 80% оборот: 50 000 у.е. в месяц предполагаемая доходность - 8-10% кол-во работающих: 25 чел кол-во единиц продукции: 300-500 шт в месяц     ЛЕКЦИЯ 6. ХАРАКТЕРИСТИКА ЗВЕНА ЗАКУПКА Теория: Характеристика звена "Закупка" Практика: Оптимальные назначения Задачи закупочной логистики   Закупочная логистика – область логистики, связанная с закупкой материальных ресурсов (сырья, материалов, комплектующих изделий и т. д.). Назначение - управление материальными потоками в процессе обеспечения предприятия материальными ресурсами. Область действия - часть материального потока логистической цепи от поставщиков материальных ресурсов до производственных подразделений (звена «Производство»). Цель - удовлетворение потребностей производства необходимыми материальными ресурсами в требуемом временном режиме при оптимальных затратах, что включает в себя: · выдерживание обоснованных сроков заготовления сырья и комплектующих изделий; · обеспечение точного соответствия между количеством поставок и потребностями в них; · соблюдение требований производства по качеству сырья и комплектующих изделий; · обеспечение сбалансированности трат для нужд производства в соответствии с выполнением имеющихся задач.   В отделе снабжения различают задачи двух категорий специалистов.   Типичные фу нкции рядового специалиста по закупочной логистике: · заключить договор, · проконтролировать исполнение договора, · организовать доставку, · организовать складирование.   Типичные функции ведущего специалиста по закупочной логистике: · решить что лучше: закупать комплектующее или производить его самостоятельно; · определить что закупить и правильно выбрать способ поиска нужного комплектующего; · выбрать метод определения потребности в комплектующих (метод снабжения); · решить сколько и когда закупить; · выбрать условия поставок (с учетом используемого метода снабжения); · выбрать поставщика нужного комплектующего.   Рассмотрим эти вопросы подробнее в применении к промышленному предприятию, т.е. речь будет идти о налаживании долгосрочных контактов с целью осуществления регулярных закупок.   А надо ли вообще закупать   Вопрос “а надо ли вообще закупать” заключается в принятии одного из двух альтернативных решений - делать комплектующее изделие самим (если это в принципе возможно) или же покупать у другого производителя. В англоязычной литературе эта задача встречается под названием make-or-buy problem. Как это часто бывает, у каждого варианты есть свои плюсы. Самостоятельное производство комплектующих: + снижает зависимость предприятия от возможного возникновения дефицита; + устраняет проблему своевременной поставки продукции в требуемых объемах. Закупка комплектующих: + обеспечивает, как правило, более высокое качество (за счет того, что для стороннего производителя этот вопрос является профильным); + за счет более низкой себестоимости при условии невысоких торговых наценок может быть дешевле собственного производства (если конечно закупать через оптовые фирмы). Кроме того, на самих предприятиях могут действовать факторы, обусловливающие отказ от собственного производства. Решение в пользу закупок комплектующих и соответственно против собственного производства должно быть принято в случае, если: · отсутствуют необходимые для производства финансовые средства, а взятие кредита под него является нерентабельным; · вследствие небольшой потребности производства в конкретном виде комплектующих собственное производство нерентабельно; · использование имеющихся необходимых для производства комплектующего мощностей нерентабельно.   Решение против закупок и в пользу собственного производства принимается в случае, когда производство конкретного комплектующего, согласно достоверным маркетинговым исследованиям, является рентабельным и производитель имеет финансовые ресурсы или возможности по рентабельному кредитованию его запуска. Также дополнительным стимулом к тому, чтобы начать собственное производство являются: · недозагруженность имеющегося штата работников; · географическая удаленность поставщиков, приводящая к повышению стоимости комплектующих за счет доставки и рискам резкого изменения таможенных сборов и акцизов, регулируемых государствами поставщика и покупателя.   Что закупить и как найти   В процессе принятия решения о том, какие комплектующие необходимо закупить, следует определить: · какие материалы требуются; · наличие альтернативных комплектующих для снижения риска возникновения ситуации невозможности выпуска конечного продукта из-за отсутствия выбранного уникального элемента в его составе; · ценовую категорию выбранных комплектующих для обеспечения сбалансированности по составу комплектующих итогового изделия.   Существуют несколько методов поиска необходимых комплектующих, каждый из которых имеет свои достоинства и недостатк и может быть рекомендован для определенных целей. · Объявление конкурса (тендера):           + получение гарантированно самой низкой цены на рынке               за товар нужного класса;           - необходимость составления ТЗ для тендера;           - нерентабельность данного вида для покупателя (при                закупке мелких партий);           - непривлекательность предложения для поставщика (при                закупке мелких партий). Вывод:оптимально для закупок больших партий комплектующих. Выбор наиболее устойчивого брэнда:           + высокое качество;           + привлекательность для потребителя конечного изделия               за счет репутации изготовителей комплектующих;           - высокая стоимость комплектующих. Вывод: оптимально для обеспечения высокого качества комплектующих в составе изделия. Выбор на основе анализа соответствия технических характеристик комплектующих их ценам по изучению образцов комплектующих, рекламных материалов производителей, фирменных каталогов, информации в доступных местах и обзорах:           +соответствие цены качеству и потребительским               характеристикам;           - необходимость высокой квалификации для корректного               выбора и оценки;           - большие временные затраты.  Вывод: оптимально для выхода на рынок с итоговым продуктом с низкой себестоимостью и высоким итоговым качеством.   Методы определения потребности в материалах   Принятие решений о том, сколько и когда закупать, производится на основании различных методов, которые теоретически можно разделить на три основные группы. Практически в чистом виде использование этих методов встречается редко: как правило, применяются комбинированные методики. Основные теоретические методы определения потребности в материалах: · детерминированный метод - известны определенный период выполнения заказа и потребность в материалах по количеству и срокам; · стохастический метод - основой для расчета являются математико-статистические методы, дающие ожидаемую потребность; · эвристический метод - потребность определяется на основе опыта административного состава службы снабжения. За последние годы разработан ряд специализированных методов снабжения, ориентированных на конкретную потребность производства: · метод “Канбан”, разработанный в Японии с целью управления поставками в условиях поточного производства – этот метод учитывает потребность, возникающую на конечном этапе производства; · система планирования материальных потребностей, охватывающая планирование на трех уровнях: предварительном (на основе опыта предыдущих периодов), текущем (при распределении материалов по производственным участкам) и будущем (на основе тенденций роста объема производства и продаж); · метод “Точно в срок” (J UST- IN -T IM E), с помощью которого в результате частых поставок резко сокращаются накопленные запасы; · система запросов, по которой с поставщиками заключаются типовые контракты на длительный период существования потребностей, а данные по фактической потребности запрашиваются на основе поэтапного уточнения; · метод прогнозных показателей, в рамках которого спрос на большие партии закупок формируется на определенном уровне, а затем конкретный объем поставок приводится в соответствие со спросом; · электронно-информационный метод коммуникации клиента и поставщика на основе передачи необходимых данных, когда запрос поступает в виде заказа, а данные о поставке и транспортировке уточняются при прямом онлайновом контакте.   Конкретный метод выбирают специалисты, занимающиеся логистической организацией деятельности предприятия, на основании комплексного анализа ситуации с закупками, производством и сбытом. Только оценка деятельности предприятия в целом может обеспечить основу для принятия адекватного решения по поводу методов ведения закупок. Выбранный метод закупок в значительной степени определяет наиболее предпочтительные для производителя условия поставок.   Сколько закупить и когда закупить?   В процессе принятия решения о том, сколько комплектующих необходимо закупить, следует определить: · количество комплектующих, которые потребуются для производства продукции в конкретные периоды времени; · требуемые площади складских помещений предприятия; · издержки на закупки, доставку и хранение комплектующих.   В процессе принятия решения о том, когда конкретные комплектующие необходимо закупить, следует определить: · периодичность закупок конкретных комплектующих для планомерного обеспечения ими нужд основного производства (ориентировочно для расходных материалов и часто используемых комплектующих и точно для конкретных штучных заказов); · возможности поставщиков или производителей, у которых могут быть куплены комплектующие (с учетом возможных перебоев в поставках, каникул производителей, государственных праздников и выходных – особенно если предприятие работает в ежедневном / круглосуточном режиме).   Типовые условия поставок   Оптимальный выбор условий закупок прямо или косвенно зависит от используемого метода снабжения, а также от состава комплектующих в конечном продукте, устойчивости спроса на него и серийной или штучной направленности производства. Существуют следующие типы условий поставок.   Поставка товара одной партией: +большие оптовые скидки, +гарантия поставки всей партии, +простота оформления документации, -большая потребность в складских помещениях, -замедление оборачиваемости капитала.   Регулярные поставки мелкими партиями: +ускорение оборачиваемости капитала (как правило, оплачивается товар по поступлению), +экономия складских площадей, + простота оформления документации (оформляют документы на весь заказ сразу), - вероятность заказа избыточного количества товара, - необходимость оплаты товара, даже если к моменту поставки потребность в нем отсутствует. Ежедневные (ежемесячные) поставки по котировочным ведомостям: +автоматизация процедуры заказа товара (удобно при регулярно закупаемой устойчивой номенклатуре), +экономия складских площадей, +гарантия своевременности поставок, -не подходит при наличии сезонных колебаний спроса и при изготовлении штучной продукции. Получение товаров по мере необходимости: +ускорение оборачиваемости капитала (как правило, оплачивается товар по поступлению), +экономия складских площадей, +отсутствие твердых обязательств по покупке определенного количества товара, - необходимость регулярно связываться с поставщиками для уточнения количества товара, - вероятность возникновения ситуации, когда необходимого количества товара у поставщика нет. Единовременная закупка товара с немедленной поставкой: +получение точно необходимого товара в нужный момент, +наибольшая оборачиваемость капитала (купил и сразу использовал), -более высокие (розничные) цены, -увеличение издержек при транспортировке товара, -больший объем оформляемой документации.   Выбор поставщика   После того, как решена задача “покупать ли вообще” и определено, какое сырье и какие материалы и в каком количестве необходимо закупить, решают задачу выбора поставщика. Для этого первоначально производится поиск потенциальных поставщиков, а затем их комплексный анализ.   Как правило, критерии анализа потенциальных поставщиков следующие: · основные: · цена поставляемой продукции; · качество поставляемой продукции; · сроки поставок. · дополнительные: · результаты работы по уже заключенным договорам (соблюдение поставщиком обязательств по срокам поставки, ассортименту, комплектности, качеству и количеству поставляемой продукции); · удаленность поставщика от потребителя; · гибкость ценовой политики (наличие системы накопительных скидок от объемов закупаемой продукции, специальные прайс - листы для постоянных покупателей); · наличие у поставщика возможности обеспечить доставку продукции своими силами; · возможность получения товаров в рассрочку, без предоплаты либо с отсроченным платежом; · сроки выполнения текущих и экстренных заказов; Последнее изменение: понедельник 8 Март 2004, 17:47

ЗАДАЧА 6. ОПТИМАЛЬНЫЕ НАЗНАЧЕНИЯ   Обращаясь к сформулированной в предыдущей задаче проблеме, ребрам двудольного графа можно поставить в соответствие веса, обозначающие степень полезности или вредности данного кандидата на этой должности. Такая ситуация будет больше соответствовать прикладным целям, когда рассматривается проблема не максимизации собственно числа назначений, а получения оптимальных назначений с точки зрения их итоговой эффективности.   ВВЕДЕНИЕ В ПРОБЛЕМУ Возможные типы задач · Максисуммная постановка. Даны M кандидатов на N должностей, и матрица A [ i, j ], которая характеризует степень полезности i -го кандидата при назначении его на j -ю должность. Найти назначение, максимизирующее суммарную полезность. · Минисуммная постановка. Даны M кандидатов на N должностей, и матрица A [ i, j ], которая характеризует степень вредности i -го кандидата при назначении его на j -ю должность. Найти назначение, минимизирующее суммарную вредность.   Дополнительные размышления Ясно, что обе задачи решаются одним алгоритмом. В первой задаче нужно максимизировать функционал f, рассчитываемый как сумма по i и j от 1 до m и n соответственно произведений элементов a[i,j] и x[i,j]. Изменим матрицу A на A ' следующим образом: найдем в ней максимальный элемент (обозначим его r) и вычтем из него каждый элемент: a '[ i, j ] = r - a [ i, j ]. Если A состояло из неотрицательных чисел, то A ' сохраняет это свойство. Значит f`=const-f. Ясно, что максимизируя f, мы минимизируем f ' и наоборот. Поэтому рассмотрим одну из задач, минисуммную.   Постановка задачи Дан двудольный граф GM , N с взвешенными ребрами и матрицей весов A [ i, j ]. Найти паросочетание M * такое, что сумма a [ i, j ] по ребрам u (ij), принадлежащим M *, будет минимальна. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОБ ОПТИМАЛЬНОМ НАЗНАЧЕНИИ   Основная идея Суть алгоритма в том, чтобы привести матрицу по строкам и столбцам с целью получения наибольшего числа нулей. Ясно, что если в задаче минимизации с неотрицательной матрицей удается провести "нулевое" назначение (только по тем клеткам, где b [ i, j ]=0), то будет достигнуто значение функционала f =0, и меньше быть не может. Если нет, то надо построить двудольный граф, где ребра соответствуют нулям (а не единицам, как в задаче №5) приведенной матрицы. Затем найти наибольшее паросочетание, используя метод чередующихся цепей, описанный в задаче №5. Если оно оставляет некоторые вершины ненасыщенными, то его следует увеличить. Для этого преобразовать матрицу и затем повторно пытаться строить наибольшее паросочетание. И так до тех пор, пока все вершины не станут насыщенными. Возможные сложности Как преобразовать матрицу, чтобы стало возможным увеличение полученного паросочетания?   Способы преодоления Ранее было показано, что минимум в задаче, где из всех элементов строки (или столбца) вычитается некоторое число, достигается на той же перестановке, что и в исходной задаче. Это свойство остается верным, если заменить вычитание сложением. Введем так называемую операцию Егервари. Пусть I ' принадлежит I, J ' принадлежит J и d - число. Будем говорить, что к матрице применяется операция Егервари E(I ', J ',d), если из каждой строки i из множества I ' вычитается d, а к каждому столбцу j из множества J ' прибавляется d. Эта операция не меняет оптимальной перестановки. Кроме того, элементы матрицы на пересечении строк из I ' и столбцов J ' не меняются, так как из них вычитается и к ним прибавляется одно и то же число d. Найдем множества вершин, достижимых из ненасыщенных вершин, принадлежащих множеству I (по алгоритму нахождения достижимых вершин в орграфе, рассмотренному в задаче №5). Пусть I ' и J ' – такие множества вершин, входящие соответственно в I и J. Среди элементов b [ i, j ], где i принадлежит I ', а j принадлежит J "= J \ J ', найдем элемент минимального веса, пусть это b [ i, j ]=d. Проведем над матрицей операцию Егервари E(I ', J ',d), после чего станет возможно повторное приведение матрицы по строками и/или столбцам, а полученное на основе такой матрицы паросочетание окажется больше предыдущего.  Описанный ниже aлгоритм решения задачи о назначениях называется венгерским, потому что он основан на идеях работы венгра Егервари, написанной еще в 1931 г.   Формальное описание венгерского алгоритма   Ввод: a[ i, j ] – массив, задающий степень вредности (ну или размер зарплаты) при назначении i -ого кандидата на j -ую должность;   Инициализация: dob – рабочая переменная, хранящая сумму коэффициентов приведения по строкам и столбцам; cost _ min – минимальная суммарная вредность (размер зарплаты) при произведенных назначениях; mass _ I [ j ], mass _ J [ j ]–список строк Î I ` и столбцов Î J `; Nas _ u [ i, j ]- найденное на очередной итерации максимальное паросочетание; Nas _ I [ M ], Nas _ J [ N ] – рабочие массивы с элементами типа boolean, содержащие информацию о насыщенности вершин из мн-в I и J, все элементы изначально равны false; Общий шаг: 1.Привести массив а [ i, j ] в цикле по i от 1 до M (по строкам): в цикле по j от 1 до N найти мин.элемент min[ i ] в цикле по j от 1 до N a [ i, j ]:= a [ i, j ]- min[ i ] dob:= dob + min[ i ]; в цикле по j от 1 до N (по столбцам): в цикле по i от 1 до M найти мин. элемент min[ j ] в цикле по i от 1 до M a[ i, j ]:=a[ i, j ]- min[ j ]      dob:= dob + min[ j ]; cost _ min:= dob; 2. Использовать АЛГОРИТМ нахождения максимального числа паросочетаний, ввод: a [ i, j ], вывод Nas _ u [ i ], u [ i, j ]. 3. Выбрать ненасыщенные вершины и сформировать множество I ` и J `. 3.1. В цикле по i от 1 до M если Nas _ I [ i ]=false то использовать АЛГОРИТМ нахождения вершин, достижимых из данной, ввод: Nas _ I [ i ], u [ i, j ]; вывод: P i [ k ]). 3.2. На основе всех P i [ k ] сформировать p [ k ] – указать в нем номера вершин таких что P i [ k ]<>-1 хотя бы для какого - нибудь i. 3.3. i:=1, j:=1. В цикле по k от 1 до N + M если P[ k ]¹-1    Если k < M то m ass_ I [ i ]:= k, i:= i +1  иначе m ass_ J [ j ]:= k - M, j:= j +1, i _max:= i, j _max:= j; 3.4. Среди элементов b [ i, j ], где i Î m ass_ I [ i ], а j Ï m ass_ J [ j ] определить min. flag:=true; В цикле по i от 1 до i _ max     В цикле по j от 1 до N         В цикле по <

Последнее изменение: понедельник 8 Март 2004, 17:52

Условие задачи 6.2 для самостоятельного решения Необходимо закрепить за шестью участками начальников цехов, так чтобы итоговая эффективность работы была максимальна. Итоговая эффективность определяется объемом выпускаемой продукции. Ожидаемый объем выпуска продукции на участках при условии назначения сотрудников имеющегося штата работников на эти должности следующий (для каждого сотрудника указан объем выпуска при назначении их на 1,2,3,4,5,6 участки): Сотрудник 1: 12, 11, 10, 8, 14, 6 тыс. шт. в месяц Сотрудник 2: 13, 8, 6, 8, 8, 9 тыс. шт. в месяц Сотрудник 3: 11, 9, 14, 3, 15, 8 тыс. шт. в месяц Сотрудник 4: 5, 7, 12, 8, 6, 10 тыс. шт. в месяц Сотрудник 5: 8, 12, 10, 7, 6, 11 тыс. шт. в месяц Сотрудник 6: 9, 11, 6, 12, 9, 10 тыс. шт. в месяц

 

Последний срок сдачи: вторник 28 Март 2006, 23:55

Проанализируйте тему и попробуйте ответить на вопросы: 1. Попробуйте проанализировать типовые условия поставок комплектующих и разделить их на три группы: 1. наиболее благоприятные условия для поставщиков 2. наиболее благоприятные условия для покупателей 3. компромиссные условия. Аргументируйте свое мнение. 2. Какой метод определения потребности в материалах наиболее разумно выбрать на первое время сразу после образования предприятия (или открытия в рамках действующей фирмы нового направления)и к какому методу стоит стремиться в дальнейшем? От каких параметров зависит принятие этих решений? 3. Какой метод поиска комплектующих является наиболее предпочтительным в том случае, если сравнительно молодое небольшое предприятие, занимающееся сборкой кухонной мебели по индивидуальным заказам, планирует расширить предлагаемый ассортимент?

 

ЛЕКЦИЯ 7. ХАРАКТЕРИСТИКА ЗВЕНА "ПРОИЗВОДСТВО"

Теория: Характеристика звена "Производство"