Задача о назначениях в Excel

1. Постановка экономической задачи (исходные данные варианта)
Мастер должен назначить на 5 типовых операций 7 рабочих. Время, которое затрачивают рабочие на выполнение каждой операции, приведено в таблице.
Рабочие Операции
О1 О2 О3 О4 О5
Р1 25 22 30 24 31
Р2 32 14 34 30
Р3 35 32 31 28
Р4 36 27 14 24 30
Р5 35 25 30 22
Р6 34 33 26 14 19
Р7 34 27 30 37 37

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

2. Экономико-математическая модель задачи
Данная задача является задачей о назначениях и реализуется как частный случай транспортной задачи. Видно, что число рабочих (7) превышает количество операций, которое они должны выполнить (5). Следовательно, задача является открытой, и решать ее целесообразно путем приведения к закрытой задаче, для чего вводятся две фиктивные операции — О6 и О7. Время на выполнение фиктивных операций равно нулю, так как они фактически не выполняются.
Представим исходные данные закрытой задачи в виде таблицы:

Рабочие Операции
О1 О2 О3 О4 О5 О6 О7
Р1 25 22 30 24 31 0 0
Р2 32 1000 14 34 30 0 0
Р3 35 1000 32 31 28 0 0
Р4 36 27 14 24 30 0 0
Р5 35 25 30 22 1000 0 0
Р6 34 33 26 14 19 0 0
Р7 34 27 30 37 37 0 0

В ячейках с заливкой находятся затраты времениcij на выполнениеi–м рабочим (i=1, …, 7) j–й операции (j=1, …, 7). В ячейки, в которых был знак «–», вместо него помещены числа, существенно превышающие другие затраты времени (1000), чтобы при решении задачи соответствующие значения переменных оказались заведомо равными нулю.
Обозначим черезxij факт назначенияi–го рабочего на выполнениеj–й операции(1 — если рабочий назначен, 0 — если не назначен). Математическая модель задачи имеет вид:
Найти такие значения xij, чтобы суммарное время на выполнение всех работ было наименьшим:

;
и при этом:

  • каждый рабочий должен быть назначен только на одну операцию:
    ;
  • на каждую операцию должен быть назначен только один рабочий:
    ;
  • переменные задачи являются двоичными:
    .

3. Компьютерная технология получения оптимального решения
Данную задачу решаем с помощью калькулятора и надстройки Поиск решения табличного процессора MS Excel. В ячейки рабочего листа программного средства вводятся исходные данные и формулы:

  • В ячейки B5:H11 вводятся затраты времени, необходимого рабочим на выполнение операций;
  • В ячейках B15:H21 находятся значения переменных xij. Первоначально в них помещаются произвольные числа, например, единицы.
  • В ячейки I15:I21 вводятся формулы для расчета сумм значений переменных в соответствующих строках. Например, в ячейке I15 формула имеет вид: =СУММ(B15:H15).
  • В ячейки B22:H22 вводятся формулы для расчета сумм значений переменных в соответствующих столбцах. Например, в ячейке B22 формула имеет вид: =СУММ(B15:B21).
  • В ячейку B24 вводится выражение целевой функции задачи с использованием встроенной функцииEXCEL «СУММПРОИЗВ». Аргументами этой функции являются блоки ячеек, содержащие затраты времени и значения переменных: =СУММПРОИЗВ(B5:H11;B15:H21).

Лист исходных данных, таким образом, имеет вид:

После ввода исходных данных запускается надстройка «Поиск решения» (меню «Сервис» ® «Поиск решения…») и заполняются необходимые поля в панели надстройки:

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

4. Решение задачи на ЭВМ
После запуска надстройки «Поиск решения» на выполнение было получено сообщение об успешном решении задачи оптимизации:

В окне «Тип отчета» выбираем пункт «Результаты».

Рабочий лист MS Excel, содержащий результаты решения имеет вид:

5. Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению
Таким образом, чтобы суммарные затраты времени на выполнение операций были наименьшими, следует назначить:

  • рабочего 1 на выполнение операции 1;
  • рабочего 2 на выполнение операции 3;
  • рабочего 3 на выполнение операции 5;
  • рабочего 4 на выполнение фиктивной операции 6;
  • рабочего 5 на выполнение операции 2;
  • рабочего 6 на выполнение операции 4;
  • рабочего 7 на выполнение фиктивной операции 7.
  • Рабочие 4 и 7, назначенные на выполнение фиктивных операций, фактически не работают.

Суммарное время на выполнение всех операций составит 106 ч.
загрузка...