Метод назначений

Cамарский государственный аэрокосмический университет имени академика С. П. Королева Международный институт рынка МЕТОДИЧЕСКИE УКАЗАНИЯ к лабораторной работе N6 М Е Т О Д Н А З Н А Ч Е Н И Й по курсу Принятие проектных решений в задачах производственного и операционного менеджмента Самара 1996 Cоставители В.И. Дровянников, М.А. Кораблин,

Е.В. Симонова ББК 65.050я73 Метод назначений Метод. указания к выполнению лабораторных и самостоятельных работ Самар. госуд. аэрокосм. ун-т, Междунар. инст-т рынка Cост.В.И. Дровянников. М.А. Кораблин, Е.В. Симонова Самара. 1996. 20с. Методические указания содержат краткие теоретические сведения о методе назначений, относящемся к числу методов линейного программирования, а также варианты заданий для выполнения самостоятельных

и лабораторных работ. Предназначены для использования при изучении курса Принятие решений в задачах производственного и операционного менеджмента. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О МЕТОДЕ НАЗНАЧЕНИЙ Метод назначений - это один из методов линейного программирования, который предназначен для оптимального подбора n предложений к n потребностям, например, для назначения вида работы машине, назначения вида

работы производственному отделу, назначения человека на должность и т.д. Метод назначений применяется при решении задач, имеющих следующие характеристики 1. Имеется n предметов, которые должны быть распределены по n пунктам назначения. 2. Каждый предмет должен быть назначен единственному пункту назначения. В понятие предмет и пункт назначения может вкладываться различное смысловое значение, определяемое

конкретной задачей менеджмента. Так в качестве предмета может выступать определенный вид деятельности работы, должность, человек и т.д. 3. Оптимальный подбор назначений должен быть достигнут за счет максимизации или минимизации определенной меры эффективности назначения прибыли или стоимости. Для каждого потенциального назначения оценивается мера эффективности. Если мерой эффективности является прибыль, то в процессе решения задачи о назначениях она максимизируется,

если мерой эффективности является стоимость, она минимизируется. Например, пусть имеются четыре должности, на которые необходимо назначить четырех кандидатов, которые в этом случае становятся работниками. Каждому работнику может быть назначена единственная должность. Заметим, что количество должностей равно количеству работников. Необходимо составить матрицу, чтобы показать все возможные взаимосвязи между четырьмя должностями и

четырьмя работниками. Работники представляются строками матрицы, а должности - столбцами, как показано в таблице 1. 16 ячеек матрицы содержат стоимости каждой возможной комбинации должность-работник. Например, стоимость назначения должности 2 работнику 2 составляет 19. Содержимое ячеек матрицы определяет интегральную меру эффективности, которая должна минимизироваться, поскольку является стоимостью. Если содержимое ячеек матрицы представляет собой прибыль, мера эффективности

должна максимизироваться. Таблица 1. Матрица назначений работников на должности Должности1234Канди-11691417даты5691041917114 Замечание Содержимое ячеек - стоимости соответствующих комбинаций должность-работник. Cтоимость в этом примере может зависеть от квалификации потенциального работника, его опыта и т.п. Одно из возможных решений приведенной выше задачи выглядит следующим образом

Назначить должность 1 работнику 2 - стоимость 7 Назначить должность 2 работнику 3 - стоимость 6 Назначить должность 3 работнику 1 - стоимость 14 Назначить должность 4 работнику 4 - стоимость 4 Общая стоимость этих назначений 31. Является ли эта стоимость наименьшей Может быть, да, а может быть, и нет. В этом примере существует 24 возможных назначения 4. Процедура, используемая в компьютерной модели, должна определять минимальную суммарную стоимость.

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

2. В столбце, не содержащем нулевых ячеек, найти наименьшее значение и вычесть его из содержимого всех ячеек этого столбца матрицы. 3. Линейный тест. В матрице назначений провести минимальное число линий горизонталей по строкам иили вертикалей по столбцам, вычеркивающих все нулевые ячейки матрицы. Если минимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено, т.к. назначения должны быть произведены в пункты, соответствующие нулевым ячейкам матрицы.

В противном случае, если минимальное число вычеркнутых строк и столбцов n, перейти к шагу 4. Среди невычеркнутых строк и столбцов найти ячейку с наименьшим значением. Вычесть это значение из содержимого всех невычеркнутых ячеек и добавить это значение к содержимому всех ячеек, находящихся на пересечении линий. Повторить шаг 3. Проиллюстрируем этот алгоритм на примере решения задачи о назначении 5 видов работ любой из 5 машин

n5. Матрица стоимостей каждой комбинации работамашина приведена в таблице 2-1. Таблица 2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной МашиныРабота Процедура решения задачи приведена в таблице 2-2. Таблица 2-2. Процедура решения задачи о назначениях Шаг 1 приведение строк - наименьшее значение вычитается из содержимого всех ячеек в строке матрицы

МашиныРаботы Шаг 2 приведение столбцов - наименьшее значение вычитается из содержимого всех ячеек в столбце матрицы МашиныРаботы Шаг 3 выполнение линейного теста - число линий, вычеркивающих все нулевые ячейки, равно 4 т.к.n5, перейти к шагу 4. МашиныРаботы Шаг 4 Наименьшее значение среди содержимого невычеркнутых ячеек равно 1, 1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется к содержимому ячеек, находящихся на пересечении линий

МашиныРаботы Оптимальное решение, найденное с помощью линейного теста МашиныРаботы Оптимальные назначения и их стоимости работа 1 - машине E 3 работа 4 - машине D 5 работа 2 - машине B 4 работа 5 - машине A 3 работа 3 - машине C 2 Суммарная стоимость 17 Нематематическое логическое обоснование метода назначения - минимизировать потери прибыли. Например, при назначении работы 1 машине

A вместо машины E убыток составит 2 5-3. Программа, реализующая метод назначений, эффективно выполняет сравнения стоимостей для всего множества альтернативных назначений посредством приведения строк и столбцов. Метод решения задачи назначений требует, чтобы количество должностей и кандидатов было равным. Если это условие не выполняется, компьютер должен увеличить матрицу так, чтобы она стала квадратной. Например, если 5 работников претендуют на 4 должности, компьютер дополнит матрицу до размера 55 за

счет введения фиктивной должности. Все значения стоимостей для фиктивной должности должны полагаться равными нулю, как показано в таблице 3. Заметим, что стоимость назначения работника 5 должна быть определена и включена в соответствующие ячейки матрицы. Если имеется больше должностей, чем работников кандидатов, компьютер также должен увеличить матрицу, чтобы она стала квадратной. Предположим, что имеется 6 должностей и только 4 работника кандидата.

Компьютер дополнит матрицу до размера 66, как показано в таблице 4. Заметим, что работники 5 и 6 являются фиктивными и стоимости назначений для фиктивных работников полагаются равными нулю. Таблица 3. Расширенная матрица назначений - 4 должности для 5 кандидатов Должности12345116914170Канди-27198140дат ы Замечание Ячейки содержат стоимости назначений. Таблица 4.

Расширенная матрица назначений - 6 должностей для 4 кандидатов Должности12345611691417811Канди-27198141 318даты ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ ПОДСИСТЕМЫ МЕТОД НАЗНАЧЕНИЙ ПРОГРАММЫ DSSPOM ПРИМЕР 1 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ В этом примере используется программа назначений для решения задачи назначения работника на должность.

Цель - назначить четыре должности четырем работникам так, чтобы минимизировать суммарную стоимость назначений. Стоимости назначений для этой задачи представлены в таблице 1. Загрузите программу DSSPOM в компьютер и выберите Assignment Method в главном меню. Через несколько секунд компьютер загрузит программу назначений и высветит Assignment Menu. Передвиньте указатель на опцию INPUT и нажмите клавишу

ENTER . Программа приступит к вводу данных, запрашивая ввод заголовка задачи. Выберите заголовок, который Вы считаете подходящим, м введите его в поле заголовка задачи. Нажмите ENTER , чтобы ввести следующий параметр. Следующим входным параметром является тип цели. Так как задача состоит в назначении должностей работникам и поэтому содержит стоимости, целью является минимизация стоимости. Напечатайте MIN и нажмите ENTER для продолжения.

Заметим, что в это поле программа может принять только MIN или MAX. Никакие другие значения не принимаются и поэтому программа в случае неправильного ввода не сможет продолжить выполнение. Во время ввода данных при помощи нажатия клавиши Стрелка вверх можно вернуться к предыдущему полю, чтобы исправить его значение. Для продолжения ввода данных нажмите клавишу Стрелка вправо и напечатайте 4 для количества кандидатов.

Нажмите ENTER , чтобы ввести количество должностей. Нажмите клавишу Стрелка вправо, напечатайте 4 и нажмите ENTER . Максимальная размерность задачи - 30 на 30, стоимости назначений должны быть в диапазоне от 0 до 9999. Заполненный экран исходных данных показан ниже. Problem title JOB CONTRACT Objective type MINMAX MIN

Number of candidates rows 4 Number of jobs columns 4Enter problem parametrs as requested. Press RETURN to accept, or ESC to exit. Maximum problem size is 30 by 30 assignment costs should be within 0 and 9999. Затем программа продолжит выполнение, запрашивая, хотите ли Вы ввести стоимости назначений. Continue with assignment costs YN Y После нажатия Y на экране появится отформатированная таблица для ввода стоимостей назначений.

Заполненная таблица исходных данных показана ниже. B1Job1ABCD E1Job1Job2Job3 Job42Candid116914 173Candid27198 144Candid31569 105Candid4191711 4 Если Вы хотите использовать более содержательные имена для работников отличные от Candid1, Candid2 и т.д переместите указатель в колонку A таблицы и выполните ссответствующие изменения. Вы можете также поместить указатель в первую строку

и изменить названия должностей. После завершения процесса ввода нажмите F10 для запоминания данных и выхода из табличного редактора. Теперь Вы можете распечатать входные данные, для этого необходимо установить указатель на опцию PRINT и нажать ENTER . Предварительно проверьте готовность принтера к работе. Вы можете также сохранить задачу на диске для будущих обращений.

Для этого установите указатель на опцию FILE и выберите подопцию Save current file, опуская подсвеченный прямоугольник на одну строку. Нажмите ENTER . Программа высветит название текущего устройства и директории и попросит Вас ввести имя файла. Введите имя файла в соответствии с соглашениями DOS. Теперь все готово для решения задачи. Установите указатель на опцию

SOLVE и выберите под-опцию Display output. Через несколько секунд программа выдаст оптимальное назначение, как показано ниже. Problem Title JOB CONTRACTOptimal Solution Objective value 29 Candid1 assigned to Job2 Candid2 assigned to Job1 Candid3 assigned to Job3 Candid4 assigned to Job4 Полученное оптимальное назначение минимальной стоимости предписывает назначить работника 1 на должность 2,

работника 2 на должность 1, работника 3 на должность 3 и работника 4 на должность 4. Общая стоимость этого назначения 29. ПРИМЕР 2 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ НЕСБАЛАНСИРОВАННАЯ Предположим, что имеется дополнительный работник, но должностей по прежнему четыре. Стоимости назначений представлены в таблице 3. Этот тип задачи назначения называется несбалансированной

задачей. Для решения несбалансированной задачи, компьютер добавляет дополнительные фиктивные должности или кандидатов, чтобы привести матрицу к квадратной форме. Стоимости назначений для фиктивных должностей или работников полагаются равными нулю. Установите указатель на опцию EDIT и нажмите ENTER для изменения условий задачи. Программа начнет процесс редактирования с установки указателя в поле названия задачи.

Измените название задачи на EXAMPLE 2 и нажмите ENTER . Снова нажмите ENTER , чтобы сохранить тип цели. Измените количество кандидатов на 5. Для этого передвиньте указатель на одну позицию, напечатайте 5 нажмите ENTER . Нажмите ENTER , чтобы сохранить существующее значение количества должностей. Заполненный экран исходных данных показан ниже. Problem

Title EXAMPLE 2 Objective type MINMAX MIN Number of candidates rows 5 Number of jobs columns 4Continue with assignment costs YN Y Нажмите ENTER для внесения изменений в таблицу стоимостей назначения. Заметим, что новая таблица содержит дополнительного кандидата, стоимости назначения которого равны нулю. Установите указатель на последнюю строку Candid 5 и введите стоимости назначения в стобцы

B - E. Заполненная таблица показана ниже. E616ABCD E1Job1Job2Job3Job42Candid116914 173Candid27198 144Candid31569 105Candid4191711 46Candid5141118 16 После завершения ввода данных для нового кандидата нажмите F10 , чтобы сохранить исходные данные и выйти из табличного редактора. Теперь все готово для решения задачи. Установите указатель на опцию

SOLVE и выберите подопцию Display output. Через несколько секунд программа выдаст сообщение о несбалансированности задачи и о добавлении дополнительного фиктивного столбца. Since there are fewer columns than rows, additional dummycolumns will be added with zero value in each cell Нажмите ENTER , чтобы продолжить процесс решения. Оптимальное решение будет выглядеть следующим образом.

Problem Title EXAMPLE 2Optimal Solution Objective value 29 Candid1 assigned to Job2 Candid2 assigned to Job1 Candid3 assigned to Job3 Candid4 assigned to Job4 Candid5 assigned to Dummy 5 Полученное оптимальное назначение такое же, как в примере 1 и имеет такую же стоимость 29. Отличие состоит только в том, что новый работник должен быть назначен на фиктивную должность 5.

Это означает, что новому работнику не предоставляется ни одна из существующих четырех должностей. ПРИМЕР 3 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ НОВЫЕ ОГРАНИЧЕНИЯ Теперь предположим, что по некоторым причинам дополнительный пятый работник должен быть назначен на реальную, а не на фиктивную должность. Как решить эту задачу Одно из возможных решений - точно так же ввести фиктивную должность и определить

стоимость назначения пятого работника самыми большими. Стоимости назначения остальных четырех работников на эту должность полагаются равными нулю. Установите указатель на опцию EDIT и нажмите ENTER для изменения условий задачи. Программа начнет процесс редактирования с установки указателя в поле названия задачи. Измените название задачи на EXAMPLE 3 и нажмите ENTER .

Нажмите ENTER дважды, чтобы установить указатель на поле количество должностей. Измените значение на 5, чтобы добавить дополнительную должность, и нажмите ENTER для сохранения нового значения. Заполненный экран исходных данных показан ниже. Problem Title EXAMPLE 3 Objective type MINMAX MIN Number of candidates rows 5 Number of jobs columns 5Continue with assignment costs

YN YНажмите Y для ввода стоимостей назначения. Заметим, что добавлена новая фиктивная должность номер 5 со стоимостями назначения, равными нулю. Установите указатель на ячейку F6, представляющую стоимость назначения работника 5 на фиктивную должность и измените значение на 1000. Эта большая стоимость назначения предотвратит назначение кандидата 5 на фиктивную должность. Заполненная таблица показана ниже. F61000ABCDE F1Job1Job2Job3Job4Dummy52Candid11691417 03Candid2719814 04Candid3156910 05Candid41917114 06Candid5141118161000

Нажмите F10 , чтобы сохранить исходные данные и выйти из табличного редактора. Теперь все готово для решения задачи назначений с ограничениями. Установите указатель на опцию SOLVE и выберите подoпцию Display output для того, чтобы решить задачу и получить результаты, которые приведены ниже. Problem Title EXAMPLE 2Optimal Solution Objective value 29

Candid1 assigned to Dummy Candid2 assigned to Job1 Candid3 assigned to Job3 Candid4 assigned to Job4 Candid5 assigned to Job2 Это решение отличается от решения, полученного в примере 2. Работник или кандидат 1 назначен на фиктивную должность. Кандидат 2 назначен на должность 1, кандидат 3 - на должность 3, кандидат 4 - на должность 4 и работник 5

- на должность 2. Суммарная стоимость этого нового решения 31, что несколько больше стоимости, полученной ранее 29. ЗАДАНИЯ К ЛАБОРАТОРНОМУ ПРАКТИКУМУ 1. Корпорации RMC требуется назначить пятерых работников на пять должностей. Найдите оптимальное решение на основе матрицы стоимостей, приведенной ниже. Должности1234511151581747596Канди-216014 8165127142даты 2.

Назначить пятерых рабочих на пять должностей на основе матрицы стоимостей, приведенной ниже. Должности1234511415191817Рабо-2161418131 5чие 3. Корпорация BKW - фирма, состоящая из нескольких подразделений, которая предлагает работу. Прибыль от выполнения пяти видов работ каждым из пяти подразделений показана ниже. Разработать оптимальную стратегию предложения работы.

Виды работ1234517555506576Отделы 4. Назначить четыре вида работ пяти машинам, чтобы минимизировать стоимость. Виды работ1234119182542213113514Маши-34132161 9ны414391926533214032 5. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль. Должности1234511981921Канди-2174171126да ты3161971044822122317 6. Назначить четыре вида работы пяти машинам, чтобы максимизировать прибыль.

Виды работ1234119182542Маши-213113514ны 7. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы минимизировать стоимость. Должности12345Канди-11981921даты 8. Корпорации RMC требуется назначить пять должностей пятерым работникам, причем должность 1 должна быть назначена второму работнику. Найдите оптимальное решение на основе матрицы стоимостей, приведенной ниже. Должности1234511151581747596Канди-216014 8165127142даты 9.

Назначить пятерых рабочих на пять рабочих мест на основе матрицы стоимостей, приведенной ниже так, чтобы рабочий 2 не был назначен на рабочее место 4 или 5. Виды работ1234511415191817Рабо-21614181315чие 10. Корпорация BKW - фирма, состоящая из нескольких подразделений, которая предлагает работу. Прибыль от выполнения пяти видов работ каждым из шести подразделений показана ниже.

Найдите оптимальное решение. Какое подразделение не получит работу Почему Виды работ Отделы 11. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль, причем должность 4 должна быть обязательно назначена. Должности1234511981921Работ-2174171126ни ки3161971044822122317 12. К матрице прибыли, приведенной ниже, добавить дополнительного работника , который может выполнять виды

работ 1,3 и 5 с прибылью 50,20 и 100 соответственно. Этот работник, однако, не способен выполнять виды работ 2 или 4. Найти оптимальное решение. Виды работ1234511981921Работ-2174171126ники31 61971044822122317 13. Найти минимальное и максимальное решение для задачи назначений, приведенной ниже. Виды работ12345A92981Работ-B89154никиC34749D4 7668E25725 14. 6 претендентов на 5 должностей проходят

собеседование. Оценка каждого претендента и его ежемесячная зарплата при выполнении различных видов работ показаны ниже в двух отдельных матрицах. Определите назначение на работу на основе оценки и отдельно на основе зарплаты. Какова разница в стоимости наилучшего назначения, если вместо минимизации зарплаты максимизировать оценку Содержимое ячеек матрицы не обязательно выражается в долларах или каких-либо денежных единицах. Оценка претендента за месяц Должности1234511318192118Претен-21415171 819денты

Ежемесячная зарплата претендента Должности123451800850775750700Претен-211 00100010509501000денты 15. В цехе шесть рабочих были специально подготовлены для обслуживания определенных станков. Эти рабочие могут работать на любом из пяти станков. Цех имеет много заказов и все пять станков постоянно заняты. Один из рабочих, не занятых обслуживанием станка, обычно выполняет канцелярскую работу.

На основе приведенного ниже плана стоимости обслуживания каждого станка каждым из пяти рабочих определить оптимальные назначения. Станки12345A6550605580Рабо-B30751255040ч ие 16. Некий продавец собирается продать 4 автомобиля. Основываясь на ценах, предложенных четырьмя потенциальными покупателями, определить, какую машину должен получить каждый из них, чтобы максимизировать прибыль продавца.

ChevyFordDodgePontiacCarol5,0004,0003,20 04,900John3,5003,5003,1005,000Harry4,200 3,7002,9504,750Paul3,8004,1003,0004,600 17. Некий продавец собирается продать 4 автомобиля. Потенциальными покупателями являетесь Вы и Ваши партнеры. Предложенные Вами и Вашими партнерами цены приведены ниже. Решите эту задачу так, чтобы минимизировать Ваши расходы и расходы Ваших партнеров. ChevyFordDodgePontiacCarol5,0004,0003,20 04,900John3,5003,5003,1005,000Harry4,200 3,7002,9504,750Paul3,8004,1003,0004,600 18.

Hot Rocks Fire Company только что получила 4 пожарных вызова и 2 вызова медицинской помощи. Компания может отправить только 4 из 5 имеющихся в наличии пожарных машин и 2 из 3 машин скорой помощи. На основе информации о расстояниях, на которых находятся машины от пунктов вызова, отправить пожарные машины и машины скорой помощи, чтобы минимизировать время ожидания. При решении задачи использовать единственную матрицу назначения.

Расстояние до пожараРасстояние до пункта вызоваскорой помощи1234AB14325 23542 Маши-32661 ны43647 57358 A 108B 96C 79