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

Должности

1

2

3

4

Канди-

1

16

9

14

17

даты

2

7

19

8

14

3

15

6

9

10

4

19

17

11

4

Машины

Работа

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

Машины

Работы

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

Машины

Работы

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

Машины

Работы

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

Машины

Работы

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

2

3

4

5

1

16

9

14

17

0

Канди-

2

7

19

8

14

0

даты

3

15

6

9

10

0

4

19

17

11

4

Затем программа продолжит выполнение, запрашивая, хотите ли Вы ввести стоимости назначений.

После нажатия <Y> на экране появится отформатированная таблица для ввода стоимостей назначений. Заполненная таблица исходных данных показана ниже.

Если Вы хотите использовать более содержательные имена для работников (отличные от Candid1, Candid2 и т.д.), переместите казатель в колонку A таблицы и выполните ссответствующие изменения. Вы можете также поместить казатель в первую строку и изменить названия должностей. После завершения процесса ввода нажмите <F10> для запоминания данных и выхода из табличного редактора.

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

Теперь все готово для решения задачи. Установите казатель на опцию SOLVE и выберите под-опцию "Display output". Через несколько секунд программа выдаст оптимальное назначение, как показано ниже.

Полученное оптимальное назначение (минимальной стоимости) предписывает назначить работника 1 на должность 2, работника 2 на должность 1, работника 3 на должность 3 и работника 4 на должность 4. Общая стоимость этого назначения $29.

ПРИМЕР 2 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ (НЕСБАЛАНСИРОВАННАЯ)

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

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

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

Нажмите <ENTER> для внесения изменений в таблицу стоимостей назначения. Заметим, что новая таблица содержит дополнительного кандидата, стоимости назначения которого равны нулю. становите указатель на последнюю строку (Candid 5) и введите стоимости назначения в стобцы B - E. Заполненная таблица показана ниже.

После завершения ввода данных для нового кандидата нажмите <F10>, чтобы сохранить исходные данные и выйти из табличного редактора.

Теперь все готово для решения задачи. Установите казатель на опцию SOLVE и выберите подопцию "Display output". Через несколько секунд программа выдаст сообщение о несбалансированности задачи и о добавлении дополнительного фиктивного столбца.

Нажмите <ENTER>, чтобы продолжить процесс решения. Оптимальное решение будет выглядеть следующим образом.

Полученное оптимальное назначение такое же, как в примере 1 и имеет такую же стоимость $29. Отличие состоит только в том, что новый работник должен быть назначен на фиктивную должность 5. Это означает, что новому работнику не предоставляется ни одна из существующих четырех должностей.

ПРИМЕР 3 - ЗАДАЧА НАЗНАЧЕНИЯ РАБОТНИКОВ НА ДОЛЖНОСТИ: НОВЫЕ ОГРАНИЧЕНИЯ

Теперь предположим, что по некоторым причинам дополнительный (пятый) работник должен быть назначен на реальную, не на фиктивную должность. Как решить эту задачу? Одно из возможных решений - точно так же ввести фиктивную должность и определить стоимость назначения пятого работника самыми большими. Стоимости назначения остальных четырех работников на эту должность полагаются равными нулю.

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

Нажмите <Y> для ввода стоимостей назначения. Заметим, что добавлена новая фиктивная должность (номер 5) со стоимостями назначения, равными нулю. становите казатель на ячейку F6, представляющую стоимость назначения работника 5 на фиктивную должность и измените значение на 1. Эта большая стоимость назначения предотвратит назначение кандидата 5 на фиктивную должность. Заполненная таблица показана ниже.

Нажмите <F10>, чтобы сохранить исходные данные и выйти из табличного редактора. Теперь все готово для решения задачи назначений с ограничениями. становите казатель на опцию SOLVE и выберите подoпцию "Display output" для того, чтобы решить задачу и получить результаты, которые приведены ниже.

Это решение отличается от решения, полученного в примере 2. Работник (или кандидат 1) назначен на фиктивную должность. Кандидат 2 назначен на должность 1, кандидат 3 - на должность 3, кандидат 4 - на должность 4 и работник 5 - на должность 2. Суммарная стоимость этого нового решения $31, что несколько больше стоимости, полученной ранее ($29).

ЗАДАНИЯ К ЛАБОРАТОРНОМУ ПРАКТИКУМУ

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

2. Назначить пятерых рабочих на пять должностей на основе матрицы стоимостей, приведенной ниже.

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

4. Назначить четыре вида работ пяти машинам, чтобы минимизировать стоимость.

5. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль.

6. Назначить четыре вида работы пяти машинам, чтобы максимизировать прибыль.

7. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы минимизировать стоимость.

8. Корпорации RMC требуется назначить пять должностей пятерым работникам, причем должность 1 должна быть назначена второму работнику. Найдите оптимальное решение на основе матрицы стоимостей, приведенной ниже.

9. Назначить пятерых рабочих на пять рабочих мест на основе матрицы стоимостей, приведенной ниже так, чтобы рабочий 2 не был назначен на рабочее место 4 или 5.

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

11. Назначить четыре из пяти должностей пятерым работникам таким образом, чтобы максимизировать прибыль, причем должность 4 должна быть обязательно назначена.

12. К матрице прибыли, приведенной ниже, добавить дополнительного работника, который может выполнять виды работ 1,3 и 5 с прибылью 50,20 и 100 соответственно. Этот работник, однако, не способен выполнять виды работ 2 или 4. Найти оптимальное решение.

13. Найти минимальное и максимальное решение для задачи назначений, приведенной ниже.

14. 6 претендентов на 5 должностей проходят собеседование. "Оценка" каждого претендента и его ежемесячная зарплата при выполнении различных видов работ показаны ниже в двух отдельных матрицах. Определите назначение на работу на основе "оценки" и отдельно на основе зарплаты. Какова разница в стоимости наилучшего назначения, если вместо минимизации зарплаты максимизировать "оценку?" Содержимое ячеек матрицы не обязательно выражается в долларах или каких-либо денежных единицах.

"Оценка" претендента за месяц

Ежемесячная зарплата претендента

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

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

17. Некий продавец собирается продать 4 автомобиля. Потенциальными покупателями являетесь Вы и Ваши партнеры. Предложенные Вами и Вашими партнерами цены приведены ниже. Решите эту задачу так, чтобы минимизировать Ваши расходы и расходы Ваших партнеров.

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