Реферат: Метод назначений
Cамарский государственныйаэрокосмический
университет имени академика С.П. Королева
Международный институт рынка
МЕТОДИЧЕСКИE УКАЗАНИЯ
к лабораторной работе N6
М ЕТ О Д Н А З Н А Ч Е Н И Й
покурсу
«Принятие проектных решений в задачахпроизводственного и операционного менеджмента»
Самара 1996
Cоставители В.И.Дровянников, М.А. Кораблин, Е.В. Симонова
ББК 65.050я73
Метод назначений: Метод. указания к выполнению
лабораторных и самостоятельныхработ / Самар. госуд. аэрокосм.
ун-т, Междунар. инст-т рынка;
Cост.В.И. Дровянников. М.А.Кораблин, Е.В. Симонова;
Самара. 1996. 20с.
Методические указания содержат краткиетеоретические сведения о
методе назначений, относящемся к числу методов линейного
программирования, а также варианты заданий для выполнения
самостоятельных и лабораторных работ.
Предназначены для использования при изучении курса
«Принятие решений в задачах производственного и операционного
менеджмента».
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ О МЕТОДЕ НАЗНАЧЕНИЙ
Метод назначений — это один из методов линейного программирования, которыйпредназначен для оптимального подбора n «предложений» к n«потребностям», например, для назначения вида работы машине,назначения вида работы производственному отделу, назначения человека надолжность и т.д.
Метод назначений применяется при решениизадач, имеющих следующие характеристики:
1. Имеется n «предметов», которыедолжны быть распределены по n «пунктам назначения».
2. Каждый «предмет» долженбыть назначен единственному «пункту назначения». В понятие«предмет» и «пункт назначения» может вкладываться различноесмысловое значение, определяемое конкретной задачей менеджмента. Так в качествепредмета может выступать определенный вид деятельности (работы), должность,человек и т.д.
3. Оптимальный подбор назначенийдолжен быть достигнут за счет максимизации или минимизации определенноймеры эффективности назначения: прибыли илистоимости. Для каждого потенциального назначения оценивается мераэффективности. Если мерой эффективности является прибыль, то в процессе решениязадачи о назначениях она максимизируется, если мерой эффективности являетсястоимость, она минимизируется.
Например, пусть имеются четыредолжности, на которые необходимо назначить четырех кандидатов, которые в этомслучае становятся работниками. Каждому работнику может быть назначенаединственная должность. Заметим, что количество должностей равно количествуработников. Необходимо составить матрицу, чтобы показать все возможныевзаимосвязи между четырьмя должностями и четырьмя работниками. Работникипредставляются строками матрицы, а должности — столбцами, как показано втаблице 1. 16 ячеек матрицы содержат стоимости каждой возможной комбинациидолжность-работник. Например, стоимость назначения должности 2 работнику 2составляет $19. Содержимое ячеек матрицы определяет интегральную меруэффективности, которая должна минимизироваться, поскольку является стоимостью.Если содержимое ячеек матрицы представляет собой прибыль, мера эффективностидолжна максимизироваться.
<span Arial",«sans-serif»;mso-fareast-font-family:«Times New Roman»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-fareast-language: RU;mso-bidi-language:AR-SA">Таблица 1. Матрица назначений работников на должности
Должности
1
2
3
4
Канди-
1
16
9
14
17
даты
2
7
19
8
14
3
15
6
9
10
4
19
17
11
4
Замечание: Содержимое ячеек — стоимостисоответствующих комбинаций должность-работник. Cтоимость в этом примере можетзависеть от квалификации потенциального работника, его опыта и т.п.
Одно из возможных решений приведенной вышезадачи выглядит следующим образом:
Назначить должность 1 работнику 2 — стоимость: $ 7
Назначить должность 2 работнику 3 — стоимость: $ 6
Назначить должность 3 работнику 1 — стоимость: $14
Назначить должность 4 работнику 4 — стоимость: $ 4
Общая стоимость этих назначений $31.Является ли эта стоимость наименьшей? Может быть, да, а может быть, и нет. Вэтом примере существует 24 возможных назначения (4!). Процедура, используемая вкомпьютерной модели, должна определять минимальную суммарную стоимость.Приведенная выше задача может быть сформулирована как задача линейногопрограммирования и решена с использованием модуля линейного программирования.Однако, легче и эффективнее для решения задач подобного типа использовать методназначений, который состоит из следующих четырех шагов.
1. В каждой строке найти наименьшеезначение и вычесть его из содержимого всех ячеек этой строки матрицы.(Получится по крайней мере один нуль в каждой строке.)
2. В столбце, не содержащем нулевыхячеек, найти наименьшее значение и вычесть его из содержимого всех ячеек этогостолбца матрицы.
3. «Линейный тест». Вматрице назначений провести минимальное число линий (горизонталей (по строкам)и/или вертикалей (по столбцам)), вычеркивающих все нулевые ячейки матрицы. Еслиминимальное число вычеркнутых строк и столбцов равно n, оптимальное решение найдено,т.к. назначения должны быть произведены в «пункты», соответствующиенулевым ячейкам матрицы. В противном случае, если минимальное число вычеркнутыхстрок и столбцов< n, перейти к шагу 4.
4. Среди невычеркнутых строк истолбцов найти ячейку с наименьшим значением. Вычесть это значение изсодержимого всех невычеркнутых ячеек и добавить это значение к содержимому всехячеек, находящихся на пересечении линий. Повторить шаг 3.
Проиллюстрируем этот алгоритм напримере решения задачи о назначении 5 видов работ любой из 5 машин (n=5).Матрица стоимостей каждой комбинации работа/машина приведена в таблице 2-1.
Таблица2-1. Матрица назначений, содержащая затраты на выполнение работ каждой машиной
Машины
Работа
A
B
B
D
E
1
$5
$6
$4
$8
$3
2
$6
$4
$9
$8
$5
3
$4
$3
$2
$5
$4
4
$7
$2
$4
$5
$3
5
$3
$6
$4
$5
$5
Процедура решения задачи приведена втаблице 2-2.
Таблица 2-2. Процедура решения задачи о назначениях
Шаг 1: приведение строк — наименьшее значение вычитается из содержимоговсех ячеек в строке матрицы
Машины
Работы
A
B
B
D
E
1
$2
$3
$1
$5
$0
2
$2
$0
$5
$4
$1
3
$2
$1
$0
$3
$2
4
$5
$0
$2
$3
$1
5
$3
$6
$4
$5
$5
Шаг 2: приведение столбцов — наименьшее значение вычитается изсодержимого всех ячеек в столбце матрицы
<span Arial",«sans-serif»;mso-fareast-font-family:«Times New Roman»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-fareast-language:RU;mso-bidi-language: AR-SA">Машины
Работы
A
B
C
D
E
1
$2
$3
$1
$3
$0
2
$2
$0
$5
$2
$1
3
$2
$1
$0
$1
$2
4
$5
$0
$2
$1
$1
5
$0
$3
$1
$0
$2
Шаг 3: выполнение «линейного теста» — число линий,вычеркивающих все нулевые ячейки, равно 4; т.к.n=5, перейти к шагу 4.
Машины
Работы
A
B
C
D
E
1
$2
$3
$1
$3
$0
2
$2
$0
$5
$2
$1
3
$2
$1
$0
$1
$2
4
$5
$0
$2
$1
$1
5
$0
$3
$1
$0
$2
Шаг 4: Наименьшее значение среди содержимого невычеркнутых ячеек равно 1,1 вычитается из содержимого всех невычеркнутых ячеек матрицы, 1 добавляется ксодержимому ячеек, находящихся на пересечении линий
Машины
Работы
A
B
C
D
E
1
$1
$3
$0
$2
$0
2
$1
$0
$4
$1
$1
3
$2
$2
$0
$1
$3
4
$4
$0
$1
$0
$1
5
$0
$4
$1
$0
$3
Оптимальное решение, найденное спомощью «линейного» теста
Машины
Работы
A
B
C
D
E
1
$1
$3
$0
$2
$0
2
$1
$0
$4
$1
$1
3
$2
$2
$0
$0
$3
4
$4
$0
$1
$0
$1
5
$0
$4
$1
$0
$3
Оптимальные назначения и их стоимости
работа 1 — машине E $3 работа 4 — машине D $5
работа 2 — машине B $4 работа 5 — машине A $3
работа 3 — машине C $2 Суммарная стоимость $17
Нематематическое логическоеобоснование метода назначения — минимизировать потери прибыли. Например, приназначении работы 1 машине A вместо машины E убыток составит $2 ($5-$3). Программа,реализующая метод назначений, эффективно выполняет сравнения стоимостей длявсего множества альтернативных назначений посредством приведения строк истолбцов.
Метод решения задачи назначенийтребует, чтобы количество должностей и кандидатов было равным. Если это условиене выполняется, компьютер должен увеличить матрицу так, чтобы она сталаквадратной. Например, если 5 работников претендуют на 4 должности, компьютердополнит матрицу до размера 5*5 за счет введения фиктивной должности. Всезначения стоимостей для фиктивной должности должны полагаться равными нулю, какпоказано в таблице 3. Заметим, что стоимость назначения работника 5 должна бытьопределена и включена в соответствующие ячейки матрицы.
Если имеется больше должностей, чемработников (кандидатов), компьютер также должен увеличить матрицу, чтобы онастала квадратной. Предположим, что имеется 6 должностей и только 4 работника(кандидата). Компьютер дополнит матрицу до размера 6*6, как показано в таблице4. Заметим, что работники 5 и 6 являются фиктивными и стоимости назначений дляфиктивных работников полагаются равными нулю.
Таблица3. Расширенная матрица назначений — 4 должности для 5 кандидатов
Должности
1
2
3
4
5
1
16
9
14
17
Канди-
2
7
19
8
14
даты
3
15
6
9
10
4
19
17
11
4
5
14
11
18
16
Замечание: Ячейки содержат стоимостиназначений.
Таблица 4. Расширенная матрица назначений — 6должностей для 4 кандидатов
Должности
1
2
3
4
5
6
1
16
9
14
17
8
11
Канди-
2
7
19
8
14
13
18
даты
3
15
6
9
10
17
5
4
19
17
11
4
9
14
5
6
ИНСТРУКЦИЯ ПО ИСПОЛЬЗОВАНИЮ ПОДСИСТЕМЫ «МЕТОД НАЗНАЧЕНИЙ» ПРОГРАММЫ DSSPOM
ПРИМЕР 1 — ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ
В этом примере используется программаназначений для решения задачи назначения работника на должность. Цель — назначить четыре должности четырем работникам так, чтобы минимизироватьсуммарную стоимость назначений. Стоимости назначений для этой задачи представленыв таблице 1.
Загрузите программу DSSPOM в компьютери выберите Assignment Method в главном меню. Через несколько секунд компьютерзагрузит программу назначений и высветит Assignment Menu. Передвиньте указательна опцию INPUT и нажмите клавишу . Программа приступит к вводуданных, запрашивая ввод заголовка задачи. Выберите заголовок, который Высчитаете подходящим, м введите его в поле заголовка задачи. Нажмите, чтобы ввести следующий параметр.
Следующим входным параметром является«тип цели». Так как задача состоит в назначении должностей работниками поэтому содержит стоимости, целью является минимизация стоимости. НапечатайтеMIN и нажмите для продолжения. Заметим, что в это поле программаможет принять только «MIN» или «MAX». Никакие другиезначения не принимаются и поэтому программа в случае неправильного ввода несможет продолжить выполнение. Во время ввода данных при помощи нажатия клавиши«Стрелка вверх» можно вернуться к предыдущему полю, чтобы исправитьего значение.
Для продолжения ввода данных нажмитеклавишу «Стрелка вправо» и напечатайте «4» для количествакандидатов. Нажмите , чтобы ввести количество должностей. Нажмитеклавишу «Стрелка вправо», напечатайте «4» и нажмите. Максимальная размерность задачи — 30 на 30, стоимости назначенийдолжны быть в диапазоне от 0 до 9999. Заполненный экран исходных данных показанниже.<span Arial",«sans-serif»;mso-fareast-font-family:«Times New Roman»; mso-bidi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-fareast-language: RU;mso-bidi-language:AR-SA">
<span TextBook",«sans-serif»"> Problem title: JOB CONTRACT
<span TextBook",«sans-serif»"> Objective type (MIN/MAX): MIN
<span TextBook",«sans-serif»"> Number of candidates (rows): 4
<span TextBook",«sans-serif»"> Number of jobs (columns): 4
<span TextBook",«sans-serif»">
<img src="/cache/referats/542/image001.gif" " v:shapes="_x0000_s1026"><span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">Enter problem parametrs as requested. Press RETURN to
<span TextBook",«sans-serif»">accept, or ESC to exit. Maximum problem size is 30 by 30
<span TextBook",«sans-serif»">assignment costs should be within 0 and 9999.
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
Затем программа продолжит выполнение,запрашивая, хотите ли Вы ввести стоимости назначений.
Continue with assignment costs (Y/N) Y
После нажатия на экранепоявится отформатированная таблица для ввода стоимостей назначений. Заполненнаятаблица исходных данных показана ниже.
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">B1
<span TextBook",«sans-serif»">Job1
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">A
<span TextBook",«sans-serif»">B
<span TextBook",«sans-serif»">C
<span TextBook",«sans-serif»">D
<span TextBook",«sans-serif»"> E
<span TextBook",«sans-serif»">1
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">Job1
<span TextBook",«sans-serif»">Job2
<span TextBook",«sans-serif»">Job3
<span TextBook",«sans-serif»"> Job4
<span TextBook",«sans-serif»">2
<span TextBook",«sans-serif»">Candid1
<span TextBook",«sans-serif»">16
<span TextBook",«sans-serif»">9
<span TextBook",«sans-serif»">14
<span TextBook",«sans-serif»"> 17
<span TextBook",«sans-serif»">3
<span TextBook",«sans-serif»">Candid2
<span TextBook",«sans-serif»">7
<span TextBook",«sans-serif»">19
<span TextBook",«sans-serif»">8
<span TextBook",«sans-serif»"> 14
<span TextBook",«sans-serif»">4
<span TextBook",«sans-serif»">Candid3
<span TextBook",«sans-serif»">15
<span TextBook",«sans-serif»">6
<span TextBook",«sans-serif»">9
<span TextBook",«sans-serif»"> 10
<span TextBook",«sans-serif»">5
<span TextBook",«sans-serif»">Candid4
<span TextBook",«sans-serif»">19
<span TextBook",«sans-serif»">17
<span TextBook",«sans-serif»">11
<span TextBook",«sans-serif»"> 4
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
Если Вы хотите использовать болеесодержательные имена для работников (отличные от Candid1, Candid2 и т.д.),переместите указатель в колонку A таблицы и выполните ссответствующиеизменения. Вы можете также поместить указатель в первую строку и изменить названиядолжностей. После завершения процесса ввода нажмите для запоминанияданных и выхода из табличного редактора.
Теперь Вы можете распечатать входные данные,для этого необходимо установить указатель на опцию PRINT и нажать. Предварительно проверьте готовность принтера к работе. Вы можететакже сохранить задачу на диске для будущих обращений. Для этого установитеуказатель на опцию FILE и выберите подопцию «Save current file»,опуская подсвеченный прямоугольник на одну строку. Нажмите .Программа высветит название текущего устройства и директории и попросит Васввести имя файла. Введите имя файла в соответствии с соглашениями DOS.
Теперь все готово для решения задачи.Установите указатель на опцию SOLVE и выберите под-опцию «Displayoutput». Через несколько секунд программа выдаст оптимальное назначение,как показано ниже.
<span TextBook",«sans-serif»">Problem Title: JOB CONTRACT
<span TextBook",«sans-serif»">Optimal Solution: Objective value = 29
<span TextBook",«sans-serif»"> Candid1 assigned to Job2
<span TextBook",«sans-serif»"> Candid2 assigned to Job1
<span TextBook",«sans-serif»"> Candid3 assigned to Job3
<span TextBook",«sans-serif»"> Candid4 assigned to Job4
Полученное оптимальное назначение (минимальнойстоимости) предписывает назначить работника 1 на должность 2, работника 2 надолжность 1, работника 3 на должность 3 и работника 4 на должность 4. Общаястоимость этого назначения $29.
ПРИМЕР2 — ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ (НЕСБАЛАНСИРОВАННАЯ)
Предположим, что имеется дополнительныйработник, но должностей по прежнему четыре. Стоимости назначений представлены втаблице 3.
Этот тип задачи назначения называется«несбалансированной задачей». Для решения несбалансированной задачи,компьютер добавляет дополнительные фиктивные должности (или кандидатов), чтобыпривести матрицу к квадратной форме. Стоимости назначений для фиктивныхдолжностей (или работников) полагаются равными нулю.
Установите указатель на опцию EDIT и нажмитедля изменения условий задачи. Программа начнет процессредактирования с установки указателя в поле названия задачи. Измените названиезадачи на EXAMPLE 2 и нажмите . Снова нажмите , чтобысохранить тип цели. Измените количество кандидатов на 5. Для этого передвиньтеуказатель на одну позицию, напечатайте «5» нажмите .Нажмите , чтобы сохранить существующее значение количествадолжностей. Заполненный экран исходных данных показан ниже.
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»"> Problem Title: EXAMPLE 2
<span TextBook",«sans-serif»"> Objective type (MIN/MAX): MIN
<span TextBook",«sans-serif»"> Number of candidates (rows): 5
<span TextBook",«sans-serif»"> Number of jobs (columns): 4
<img src="/cache/referats/542/image002.gif" " v:shapes="_x0000_s1027"><span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">Continue with assignment costs (Y/N) Y
<span TextBook",«sans-serif»">
<span TextBook",«sans-serif»">
Нажмите для внесенияизменений в таблицу стоимостей назначения. Заметим, что новая таблица содержитдополнительного кандидата, стоимости назначения которого равны нулю. Установитеуказатель на последнюю строку (Candid 5) и введите стоимости назначения встобцы B — E. Заполненная таблица показана ниже.
<span TextBook",«sans-serif»">E6
<span TextBook",«sans-serif»">16
<span TextBook",«sans-serif»"></s