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

Наряду с рассмотренными типами проблем имеется класс задач, связанных с оптимальным распределением ресурсов в системах, которые изучаются в теории исследования операций. Приведенные ниже традиционные формулировки задач соответствуют полной информационной определенности. Реальные задачи приходится решать в условиях риска, неопределенности и неясности, что изменяет их информационное содержание и результаты (см. главу 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). Неформальный характер задачи составления расписаний обусловлен установлением приоритетов в выполнении работ и расходовании ресурсов на реализацию проекта, что, в свою очередь, зависит от значимости проекта, согласованности целей заказчиков и проектировщиков, эффективности используемых технологий, работы смежных (субподрядных) организаций, объема имеющихся ресурсов по сравнению с требуемыми и т.п. Здесь также имеют место вмененные издержки. В заключение отметим, что более сложные постановки приведенных задач должны учитывать характер взаимосвязей систем в рамках общей системы. В литературе наиболее продвинутым является случай систем с жесткой централизацией [24]. В качестве примера рассмотрим задачу сетевого планирования и распределения ресурсов. В некотором проекте заданы работы, их взаимозависимость (рис. 1) и продолжительность (табл. 3). Нужно найти такую последовательность работ в сети, которая потребует наибольшего времени для своего выполнения, и определить возможность сокращения сроков выполнения проекта.

При решении задачи используется метод критического пути PERT (Program Evaluation Review Technique). При этом рассчитываются:

1. t₀ – самое раннее время, когда работа может быть начата;

2. t₁ – самое раннее время, когда работа может быть завершена , где– продолжительность выполнения работы;

3. t₃ – самое позднее время, к которому работа может быть завершена без угрозы срыва плана. Это время может совпадать с плановой датой завершения всего проекта;

Рис. 1. Сетевой график проекта. Работы S₄ и S₉ называются фиктивными, время их выполнения равно 0. Они показывают, что работы S₅ и S₁₀ могут начаться только после завершения работ S₁, S₃ и S₇, S₈ соответственно.

4. t₂ – самое позднее время, когда работа может быть начата без угрозы нарушения графика завершения проекта: , где– продолжительность выполнения работы;

5. t₄ – суммарное время задержек (запаздывания или отклонения от графика) без угрозы невыполнения проекта в срок .

Суммарные запаздывания в ходе работ можно рассматривать как меру эффективности сетевого графика проекта. Определим те работы, для которых t₄ минимально или равно нулю, т.е. находящиеся на критическом пути. Будем считать, что продолжительность работ может быть сокращена за счет увеличения

Таблица 3