II. Распределительные задачи

Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным способом. Поэтому целью решения задачи является отыскание такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.

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

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

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

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