Реферат: Метод назначений

--PAGE_BREAK--
Таблица 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 и нажмите клавишу <ENTER>. Программа приступит к вводу данных, запрашивая ввод заголовка задачи. Выберите заголовок, который Вы считаете подходящим, м введите его в поле заголовка задачи. Нажмите <ENTER>, чтобы ввести следующий параметр.

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

Для продолжения ввода данных нажмите клавишу «Стрелка вправо» и напечатайте «4» для количества кандидатов. Нажмите <ENTER>, чтобы ввести количество должностей. Нажмите клавишу «Стрелка вправо», напечатайте «4» и нажмите <ENTER>. Максимальная размерность задачи — 30 на 30, стоимости назначений должны быть в диапазоне от 0 до 9999. Заполненный экран исходных данных показан ниже.






          Problem title:   JOB  CONTRACT

          Objective type (MIN/MAX):  MIN

          Number of candidates (rows):  4

          Number of jobs (columns): 4



<img width=«445» height=«90» src=«ref-1_1915573709-532.coolpic» v:shapes="_x0000_s1026">

Enter 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  (Y/N)  Y





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













B1

Job1











A

B

C

D

    E

1



Job1

Job2

Job3

   Job4

2

Candid1

16

9

14

    17

3

Candid2

7

19

8

    14

4

Candid3

15

6

9

    10

5

Candid4

19

17

11

    4















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

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

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





Problem Title:  JOB CONTRACT

Optimal 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 (MIN/MAX):  MIN

          Number of candidates (rows):  5

          Number of jobs (columns):  4

<img width=«349» height=«62» src=«ref-1_1915574241-393.coolpic» v:shapes="_x0000_s1027">



Continue with assignment costs (Y/N)  Y







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



E6

16











A

B

C

D

  E

1



Job1

Job2

Job3

Job4

2

Candid1

16

9

14

 17

3

Candid2

7

19

8

 14

4

Candid3

15

6

9

 10

5

Candid4

19

17

11

  4

6

Candid5

14

11

18

 16



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

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



<img width=«455» height=«71» src=«ref-1_1915574634-475.coolpic» v:shapes="_x0000_s1029">

Since there are fewer columns than rows, additional dummy

columns will be added with zero value in each cell





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





Problem Title:  EXAMPLE 2

Optimal 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 (MIN/MAX):  MIN

          Number of candidates (rows):  5

          Number of jobs (columns):  5

<img width=«349» height=«62» src=«ref-1_1915574241-393.coolpic» v:shapes="_x0000_s1028">



Continue with assignment costs (Y/N)  Y





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



 F6

1000













A

B

C

D

E

    F

1



Job1

Job2

Job3

Job4

Dummy5

2

Candid1

16

9

14

17

    0

3

Candid2

7

19

8

14

    0

4

Candid3

15

6

9

10

    0

5

Candid4

19

17

11

4

    0

6

Candid5

14

11

18

16

1000



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





Problem Title:  EXAMPLE 2

Optimal 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).


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



Должности





1

2

3

4

5



1

115

158

174

75

96

Канди-

2

160

148

165

127

142

даты

3

90

139

95

118

198



4

127

85

170

185

135



5

146

90

119

140

112



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



Должности





1

2

3

4

5



1

14

15

19

18

17

Рабо-

2

16

14

18

13

15

чие

3

17

13

20

18

16



4

15

12

15

16

18



5

12

17

13

14

19



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



Виды работ





1

2

3

4

5



1

75

55

50

65

76

Отделы

2

35

30

95

110

100



3

30

15

25

65

125



4

55

60

65

95

85



5

45

95

75

85

110


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



Виды работ





1

2

3

4



1

19

18

25

42



2

13

11

35

14

Маши-

3

41

32

16

19

ны

4

14

39

19

26



5

33

21

40

32



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



Должности





1

2

3

4

5



1

1

9

8

19

21

Канди-

2

17

4

17

11

26

даты

3

16

19

7

10

4



4

8

22

12

23

17




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



Виды работ





1

2

3

4



1

19

18

25

42

Маши-

2

13

11

35

14

ны

3

41

32

16

19



4

14

39

19

26



5

33

21

40

32



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



Должности





1

2

3

4

5

Канди-

1

1

9

8

19

21

даты

2

17

4

17

11

26



3

16

19

7

10

4



4

8

22

12

23

17



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



Должности





1

2

3

4

5



1

115

158

174

75

96

Канди-

2

160

148

165

127

142

даты

3

90

139

95

118

198



4

127

85

170

185

135



5

146

90

119

140

112



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



Виды работ





1

2

3

4

5



1

14

15

19

18

17

Рабо-

2

16

14

18

13

15

чие

3

17

13

20

18

16



4

15

12

15

16

18



5

12

17

13

14

19


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



Виды работ





1

2

3

4

5



1

75

55

50

65

76



2

35

30

95

110

100

Отделы

3

30

15

25

65

125



4

55

60

65

95

85



5

45

95

75

85

110



6

20

60

30

300

40


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



Должности





1

2

3

4

5



1

1

9

8

19

21

Работ-

2

17

4

17

11

26

ники

3

16

19

7

10

4



4

8

22

12

23

17



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



Виды работ





1

2

3

4

5



1

1

9

8

19

21

Работ-

2

17

4

17

11

26

ники

3

16

19

7

10

4



4

8

22

12

23

17



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



Виды работ





1

2

3

4

5



A

9

2

9

8

1

Работ-

B

8

9

1

5

4

ники

C

3

4

7

4

9



D

4

7

6

6

8



E

2

5

7

2

5



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

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



Должности





1

2

3

4

5



1

13

18

19

21

18

Претен-

2

14

15

17

18

19

денты

3

12

17

25

24

20



4

19

21

16

17

25



5

24

25

21

19

14



6

16

17

24

23

19



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



Должности





1

2

3

4

5



1

800

850

775

750

700

Претен-

2

1100

1000

1050

950

1000

денты

3

600

550

700

750

650



4

900

950

1100

850

1000



5

600

700

600

800

900



6

850

900

750

800

750



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



Станки





1

2

3

4

5



A

65

50

60

55

80

Рабо-

B

30

75

125

50

40

чие

C

75

35

85

95

45



D

60

40

115

130

110



E

90

85

40

80

95



F

145

60

55

45

85



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






Chevy

Ford

Dodge

Pontiac

Carol

5,000

4,000

3,200

4,900

John

3,500

3,500

3,100

5,000

Harry

4,200

3,700

2,950

4,750

Paul

3,800

4,100

3,000

4,600


    продолжение
--PAGE_BREAK--