Минимизация затрат

Далее предлагается задача о назначениях. Имеются четыре вида работ и четверо рабочих. Затраты каждого рабочего на каждую работу в условных единицах приведены в таблице. Каждый рабочий может выполнять только одну работу, и каждая работа выполняется только один раз. Требуется минимизировать общие затраты.

Рис.

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

1) Значения в ячейках должны принимать только два целочисленные значения 0 или 1,

2) Суммы строк и столбцов должны принимать значение равное 1.

В качестве целевой функции для перемножения и суммирования элементов массивов удобно использовать функцию суммы произведений, в качестве аргументов которой использовать два диапазона: таблицу затрат и таблицу загрузки. Например,

СУММПРОИЗВ(В3:Е6;В9:Е12).

Для ограничений на 0 и 1 вячейках таблицы загрузки удобно использовать двоичные значения.

В результате решения получим ответ на то, какой рабочий какую работу выполняет и минимальные суммарные затраты равные 20 условным единицам.

Дата добавления: 2015-07-02