Назначение механизмов на работы

Имеются три механизма М₁, М₂, М₃, каждый из которых может быть использован на трех видах работ Р₁, Р₂, Р₃ с производительностью (в условных единицах), заданной в виде таблицы:

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

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

x₁₁+2× x₁₂+3× x₁₃+2× x₂₁+4× x₂₂+x₂₃+3× x₃₁+x₃₂+5× x_33® max,

Ограничения имеют вид:

x₁₁+x₁₂+x₁₃=1,

x₂₁+x₂₂+x₂₃=1,

x₃₁+x₃₂+x₃₃=1,

x₁₁+x₂₁+x₃₁=1,

x₁₂+x₂₂+x₃₂=1,

x₁₃+x₂₃+x₃₃=1.

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 37. Значения переменных x_ij располагаются в блоке ячеек B4:D6 (см. рис. 37). Коэффициенты целевой функции, отражающие производительность механизмов, находятся по адресам B11:D13.

Рис. 37

Формулы целевой функции и ограничений находятся соответственно в ячейке E8 и ячейках E4:E6 (каждый механизм может быть назначен только на одну работу), B8:D8 (каждая работа выполняется только на одном механизме) (см. рис. 37 и 38). Вид электронной таблицы в режиме отображения формул представлен на рис. 38.

Рис. 38

Рис. 39

Данная задача является задачей линейного булева программирования и в ней переменные x_ij должны принимать значения либо 0 либо 1. В поиске решения такое ограничение задается тремя ограничениями, по которым изменяемые ячейки в блоке (x_ij) одновременно больше либо равны 0, меньше либо равны 1 и являются целыми. Первые три записи в группе Ограничения (см. рис. 39) отражают этот факт.

Результаты поиска решения приведены на рис. 37.