Решение задач целочисленного программирования средствами Excel

К задачам целочисленного (дискретного) программированием относятся задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Это продиктовано физической неделимостью многих элементов расчета (например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д.). В таких задачах переменные могут принимать только два значения – единица и нуль.

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

Пятерым следователям нужно поручить расследование пяти уголовных дел . В силу разной квалификации на завершение расследования им потребуется различное время. Время выполнения (в сутках) приведено в таблице. Как следует распределить следователей прокуратуры по заданиям, чтобы минимизировать время выполнения?

Люди	Задания

Методические указания к решению:

Пусть – время участия i человека в выполнении j -го задания. Все величины – неотрицательны, и, поскольку каждый человек должен быть полностью задействован, а каждое задание полностью выполнено, величины должны удовлетворять следующим ограничениям:

При этих ограничениях минимизируется полное время

Таким образом получилась задача линейного программирования транспортного типа. Все суммы по строкам и по столбцам равны 1. Поскольку задача транспортная, в ее оптимальном решении (целочисленном) пять из величин будут равны 1, а остальные – 0. Далее задача решается стандартными средствами Excel.