1. Вычесть наименьшее значение в каждом ряду из каждого числа в этом ряду Сведите результаты в новую таблицу.

2. Вычесть наименьшее значение в каждом столбце новой таблицы из каждого числа в этом столбце. Сведите результаты в следующую таблицу.

3. Проверьте, можно ли сделать оптимальное назначение. Для этого нужно определить минимальное число линий, необходимое, чтобы покрыть все нули. Если число линий равно числу строк в таблице, то оптимальное назначение возможно. В этом случае, переходите к пункту 6. В противном случае переходите к пункту 4. Обратите внимание, что «покрыть» в данном случае означает «перечеркнуть».

4. Если число линий меньше, чем число строк, измените таблицу следующим образом:

а) вычтите наименьшее непокрытое число из каждого непокрытого числа в таблице;

б) прибавьте наименьшее непокрытое число к числам на пересечениях покрывающих линий.

5. Повторяйте пункты 3 и 4 до тех пор, пока не будет получена оптимальная таблица.

6. Произведите назначения. Начните со строк или столбцов, которые содержат только один ноль. Объедините попарно элементы, которые содержат нули, используя только одну пару для каждой строки и каждого столбца. После этого вычеркните данную строку и столбец.

Как видите, эта процедура достаточно проста по сравнению с некоторыми другими методами линейного программирования. Полезно знать, что можно использовать одно дополнение к венгерскому методу, чтобы избежать нежелательных назначений. Например, профсоюзное законодательство может запретить назначение одного рабочего на какую-то работу, или руководитель хочет избежать повторного назначения на вредную или неприятную работу того работника, который делал ее последним. В любом случае, определенной комбинации можно избежать, определив ей относительно высокий показатель расходов. Например, в предыдущем примере: если мы хотим избежать комбинации 1-А, назначим ей стоимость $50. Это позволит нам добиться желаемого эффекта, поскольку $50-это гораздо больше всех остальных показателей затрат. Если в качестве критерия вместо затрат использовать прибыль, то ее можно преобразовать в относительные затраты: вычитаем каждое число в таблице из наибольшего числа, а затем продолжаем процедуру как для задачи минимизации.

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

j ПРИМЕР 1

j Определите оптимальное назначение работ на станки для следующих данных (из I табл. 15-1).

Решение:

а. Для каждой строки: вычтите наименьшее число в строке из каждого числа в этой строке. Результаты поместите в новую таблицу. Результатом будет таблица:

Станок

Задание

Минимум столбца

б. Для каждого столбца: вычтите наименьшее число в столбце из каждого числа в столбце и сведите результаты в новую таблицу. Результатом будет таблица:

Станок

Задание

в. Определите минимальное число линий, необходимое для покрытия (вычеркивания) всех нулей. (Когда чертите линии, постарайтесь вычеркнуть как можно больше нулей.)

Станок

Задание

. 6-3 - О-----О -

.0---о-5--2-

0 14 1

0 4 7 2

Г. Поскольку только три линии требуются, чтобы покрыть все нули, это не оптимум.

д. Вычтите наименьшее непокрытое значение (в данном случае 1) из каждого непокрытого числа и прибавьте его к числам, которые стоят на пересечениях покрывающих линий. В результате получим:

Станок

Задание

е. Определите минимальное число линий, необходимое чтобы покрыть все нули (че- I тыре). Поскольку оно равно числу строк, оптимальное назначение возможно. !

i Станок \

Задание

7-----3---------О

1 О

-О-0-

о......-

ж. Сделайте назначения: начните со строк и столбцов, содержащих только один ноль. Свяжите попарно станки и операции, которые имеют нулевые затраты:

Станок

Последовательность операций

Хотя решения по нагрузке определяют станки или производственные участки, которые будут использованы для выполнения определенных работ, они не показывают/70-

рядок вьпюлнения этих работ. Определение последовательности операций- определение порядка выполнения работ на производственном участке. При этом определяется также и порядок, в котором работы выполняются на отдельных рабочих местах в пределах производственного участка.

Если производственные участки загружены в облегченном режиме и если все операции требуют одинакового времени для выполнения, то определение их последовательности не представляет особых трудностей. Однако для сильно загруженных производственных участков (особенно в том случае, когда задействованы достаточно продолжительные операции) последовательность выполнения операций особенно важна. Ее значение определяется стоимостью ожидания для операций и стоимостью простоев на производственных участках. В данном разделе мы рассмотрим некоторые способы, которыми определяют последовательность операций.

Определение последовательности операций - определение порядка, в котором будет выполняться работа на производственном участке.

Рабочее место - производственная площадь, где работает один человек. Обычно он работает на специальном оборудовании и выполняет специализированную работу.