Общая характеристика распределительной задачи

1. Общая  характеристика  распределительной  задачи.

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

Типичная  распределительная   задача.

Таблица №1

Рекомендуем посмотреть лекцию "Введение".

Большинство  распределительных  задач  можно  представить  в  виде  матриц, приведённых  в  таблице №1. Элементы  С_i,j, стоящие в клетках  матрицы,  соответствуют  затратам  или  доходу, отвечающим  выделению, одной  единицы  ресурса  R_i   на работу J_j .  Величины  С_i,j  могут  быть  независимыми   или  зависимыми. Так, например, затраты, обусловленные  назначением  одной  автомашины  на  некоторый  маршрут  доставки  грузов, не  зависят  от  того  какие  машины  назначены  на  обслуживание  других  маршрутов. В  то  же  время  при  распределение  средств  между  подразделениями  фирмы  доход  от  затрат   определённого  количества  денег  одним  её  подразделением (скажем  производством)  обычно  зависит  от  того, какие  средства  будут  затрачены  другими  подразделениями  (скажем  отделом  сбыта). В  теории  распределения  рассматриваются  преимущественно  задачи  с  независимыми  затратами  и  доходами. Это  объясняется  не  тем, что  такие  задачи  более  важны,  а  лишь  тем,  что  для  них  значительно  легче  строить  модели    и  получать  решения.

Если  затраты  (или  доход), определяемые  объёмом  X_i,j   ресурса  i, выделенного  на  выполнение  работы  J_j, ровны  X_{i,j *} C_i,j , то  имеем линейную  распределительную  задачу. Распределительные  задачи  с независимыми  линейными  функциями  затрат (или  дохода) стали  объектом, наиболее  интенсивных  исследований, в  виду  того  что  для  их  решения  были  развиты  эффективные, итеративные  методы  линейного  программирования. Однако  имеются  также  методы  решения  некоторых  нелинейных  распределительных  задач, в  том  числе  методы  основанные  на  линейной  аппроксимации.

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

Основные методы решения  распределительных  задач, в  частности  линейного  программирования, построены  на  допущении, что  объёмы, имеющихся  в  наличии ресурсов (b_i), требуемые  объёмы (a_j )  и  затраты  (C_i,j ) точно  известны.

Если общий объём наличных ресурсов Sb_i (i=1...m) равен общей  потребности в них Sa_j (j=1...n), то имеет место сбалансированная  (зак-рытая) распределительная задача. Если  же  Sa_j ¹ Sb_i , то задача называется несбалансированной (открытой). Если ресурсы можно разделить между работами, то некоторые работы можно выполнять с помощью различных комбинаций ресурсов. Если работы и ресурсы измеряются  в  единицах  одной и той же шкалы, то такие задачи обычно  называют  транспортными  или задачами разложения. Если же работы  и ресурсы выражаются в различных единицах измерениях, то задача  называется общей распределительной задачей.  Таким образом транспортная задача является частным случаем общей распределительной  задачи.