Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Задача о назначениях - файл 1.doc


Задача о назначениях
скачать (74.5 kb.)

Доступные файлы (1):

1.doc75kb.26.11.2011 10:30скачать

1.doc

Задача о назначениях.

В данной задаче продемонстрируем, как средство Поиск решения позволяет решать задачу о назначениях.

В нашем конкретном случае задача о назначении формулируется так. Имеются четыре рабочих и четыре вида работ. Стоимости Cij выполнения i-м рабочим j-й работы приведены в таблице, где под строкой понимается рабочий, а под столбцом- работа.

Стоимость выполнения работ.

1

4

6

3

9

10

7

9

4

5

11

7

8

7

8

5



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

Данная задача является сбалансированной, т.е. число работ совпадает с числом рабочих. Если задача несбалансированна, то перед началом решения ее необходимо сбалансировать, введя недостающее число фиктивных строчек или столбцов с достаточно большими штрафными стоимостями работ.


Для решения данной задачи сначала построим ее математическую модель. Обозначим символом Xij переменную, имеющую только два допустимых значения: 0 или 1. Такие переменные называются двоичными. Причем, будем считать, что:

- Xij=1 , если i-м рабочим выполняется j-я работа.

- Xij=0, если i-м рабочим не выполняется j-я работа.

Тогда математическую модель задачи о назначении можно сформулировать следующим образом:

- минимизировать

4 4

Z=∑ ∑ CijXij,

I=1 j=1

- при ограничениях

4

∑Xij=1, j[1,4]

i=1

4

∑Xij=1, i[1,4],

j=1

Xij{0,1}, i[1,4], j[1,4]
Для решения этой задачи с помощью средства Поиск решения необходимо выполнить некоторые предварительные действия:

  1. В ячейки диапазона А2:D5 введите стоимости работ.

  2. Отведите ячейки диапазона F2:I5 под неизвестные.

  3. Введите в ячейку J1 функцию цели, вычисляющую стоимость работ

= СУММПРОИЗВ(A2:D5;F2:I5)

  1. В ячейки диапазонов J2:J5 и F6:I6 введите следующие формулы, задающие левые части ограничений.

Ячейка

Формула

Ячейка

Формула

J2

J3

J4

J5

=СУММ(F2:I2)

=СУММ(F3:I3)

=СУММ(F4:I4)

=СУММ(F5:I5)

F6

G6

H6

I6

=СУММ(F2:F5)

=СУММ(G2:G5)

=СУММ(H2:H5)

=СУММ(I2:I5)



Рис. 5.15 Исходные данные задачи о назначении и заполненное диалоговое окно Поиск решения.
Рис.5.16. Оптимальное решение задачи о назначении.
Теперь все готово для поиска первого решения при помощи средства Поиск решения.

  1. В
    ыберите команду Сервис /Поиск решения и заполните диалоговое окно Поиск решения, как показано на рис. 5.15.

  2. Нажмите кнопку Выполнить, Средство Поиск решения найдет оптимальный план назначений на работы.(рис 5.16.)









Скачать файл (74.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации