Задачи распределения ресурсов в системах

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

Задача планирования производства. Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: а_ij – количество i -го ресурса, необходимого для производства единичного количества j -й продукции; а_ij ³0 (i =1,…, m; j =1,…, n); b_i – запас i -го ресурса на предприятии, b_i >0; c_j – цена единичного количества j -й продукции, c_j >0. Предполагается, что затраты ресурсов растут пропорционально объему производства. Пусть x_j – планируемый объем производства j -й продукции. Тогда допустимым является только такой набор производимой продукции x =(x ₁, x ₂,…, x_n), при котором суммарные затраты каждого вида i -го ресурса не превосходят его запаса:

. (3.2.1)

Кроме того, имеем следующее естественное ограничение:

. (3.2.2)

Стоимость набора продукции x выражается величиной. Задача планирования состоит в том, чтобы среди всех векторов x, удовлетворяющих ограничениям (3.2.1), (3.2.2), найти такой, при котором стоимость набора продукции принимает наибольшее значение

. (3.2.3)

Реальные задачи планирования редко представимы в столь идеальном виде, обычно приходится действовать в условиях риска или неопределенности. Для формализации задачи требуется затратить немало усилий, точнее, как говорил известный персонаж Эркюль Пуаро, понадобится «включить серые мозговые клеточки». В частности, определение параметров a_ij, b_i, c_j связано с используемой технологией, а последняя, в свою очередь, зависит от стратегии фирмы. На установление цены влияют цель и стратегия фирмы, ее положение на рынке и другие факторы. Появляются вмененные издержки (так называемые теневые цены), связанные с ослаблением или ужесточением ресурсных ограничений задачи. Эти издержки могут быть определены решением двойственной задачи линейного программирования. В реальных условиях невозможно получить точное оптимальное решение и определить истинное значение вмененных издержек.

Транспортная задача. Некоторая продукция хранится на m складах и потребляется в n пунктах. Известны следующие величины: а_i – запас продукции на i -м складе, а_i >0 (i =1,…, m); b_j – потребность в продукте на j -м пункте, b_j >0 (j =1,…, n); с_ij – стоимость перевозки единичного количества продукции с i -го склада в j -й пункт, с_ij >0. При этом предполагается, что суммарные запасы равны суммарным потребностям:

. (.3.2.4)

Транспортная задача сводится к задаче линейного программирования следующего вида:

, (3.2.5)

при условиях,,

где x_ij – количество продукции, перевозимой с i -го склада в j -й пункт.

Таким образом, надо организовать перевозки продукции со складов в пункты потребления, чтобы при полном удовлетворении потребностей минимизировать суммарные транспортные потери. При этом условие (3.2.4) является необходимым и достаточным для существования, по крайней мере, одной матрицы перевозок { x_ij }, удовлетворяющей ограничениям задачи (3.2.5). Сказанное выше о задаче планирования в равной мере относится к транспортной задаче. Здесь неформальными параметрами являются c_ij. Определение стоимости перевозки c_ij зависит от ряда факторов, в частности от парка автомобилей, положения автотранспортного предприятия на рынке услуг, стратегии предприятия, государственных субсидий и т.п. На нее влияет также наличие приоритетов потребностей на разных пунктах, выбор маршрутов и т.д. Кроме того, условие (3.2.4) является скорее гипотетическим, чем реально выполняемым на практике, так как запасы и потребности определяются разными системами (разными ЛПР). Здесь также имеют место вмененные издержки, связанные с работой в условиях риска.

Задача планирования и транспортная задача решаются методами линейного программирования, например симплекс-методом. К этому же классу относится так называемая задача о рационе. Мы рассмотрим ее в более общей постановке.

Задача обеспечения потребностей. Для функционирования системы необходимы m ресурсов, получаемых из n типов сырья. Известны следующие величины: a_ij – количество i -го ресурса, которое может быть получено из единичного количества j -го типа сырья, a_ij >0 (i =1,…, m; j =1,…, n); b_i – минимальное количество i -го ресурса, необходимое для работы системы в течение определенного времени, b_i >0; c_j – цена единичного количества j -го типа сырья, c_j >0. Задача состоит в том, чтобы минимизировать затраты на сырье, требуемое для нормальной работы системы:

, (3.2.6)

при условиях

где x_j – искомое количество j -го типа сырья, необходимое для обеспечения нормальной работы системы в течение определенного времени при минимальных затратах на сырье.

Сказанное выше о задаче планирования относится и к этой задаче, так как величины a_ij, b_i, c_j зависят от технологий, стратегии обеспечения, приоритетов потребностей и т.п. Могут появляться также вмененные издержки, связанные с отклонением спроса от предложения и неопределенностью информационной среды задачи.

Задача составления расписаний. Такая задача возникает при планировании работ, составлении проектов сложных технических или экономических систем. Задача заключается в следующем: найти такое распределение ресурсов и такое назначение очередности работ, при которых совокупность работ, составляющих проект, будет выполнена за минимальное время. При этом предполагаются известными: а) перечень работ p ₁, p ₂,…, p_n; б) ресурс (люди, оборудование, сырье, деньги и т. п.), необходимый для выполнения работы p_i (i =1,…, n).

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

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

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

Таблица 3