Задача оптимизации количества участников проекта как задача целочисленного линейного программирования

Рассмотрим следующую задачу оптимизации количества участников проекта. Имеется m работ (задач) в проекте. На выполнение каждой работы претендуют n различных исполнителей (партнеров), готовых в полном объеме выполнить определенные работы за согласованную с каждым партнером стоимость c _{i , j} . На каждую работу требуется выбрать только по одному партнеру, но при этом исполнитель может быть назначен на несколько работ одновременно. Требуется найти такое распределение всех задач по партнерам, чтобы задействовать минимальное количество партнеров и уложиться в выделенный бюджет S .

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

Очевидно, что без ограничения на бюджет оптимальным решением является выполнение всех работ только одним (любым) исполнителем. Следовательно, лучшим значением целевой функции является 1 (нижняя граница), когда задействован только один исполнитель на всех работах, а худшим - n (верхняя граница), если потребовалось привлечь всех партнеров для выполнения работ с выделенным общим объемом финансирования.

Задача может не иметь решения в том случае, если не существует удовлетворяющего ограничению по бюджету варианта расстановки исполнителей по работам. Условие наличия допустимого решения следующее: m

Е ^{min с}м ^ ⁵ ,                        ⁽¹⁾

j=1 i где:

• -    i - порядковый номер исполнителя, i = 1, n ;

• -    j - порядковый номер работы, j = 1, m ;

• -    m - количество работ, а n - количество исполнителей;

• -    S - бюджет;

• -    c_t - стоимость выполнения j -ой работы i -ым исполнителем.

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

Математическая   постановка   задачи в виде модели целочисленного нелинейного программирования (2) предложена нами в [1]:

L = L (x) = X max x^ ^ min

(2.1)

(2.4)

факт назначения i -го

i=1 j        , nm

XX C , jj S (2.2) i . 1 n

* X x , j = 1, j = 1, m ⁽²-^{3) 1} = 1

• ^xi , j ^G{ °,1 } , i = 1, n , j = 1, m

где:

• -    x – искомые неизвестные, показывающие ¹ , ^j

исполнителя на j -ю работу (1 – назначается, 0 – нет).

• -    L - количество задействованных партнеров, a L ( x ) - функция определяющая L через x .

Заметим, что при решении частного случая рассматриваемой задачи, когда c интерпретируется как возможность выполнения j -ой работы i -ым исполнителем (0 – может выполнить, 1 – не может), условие (2.2) можно заменить на (3). nm

i = 1 j = 1

В модели (2) целевая функция (2.1) нелинейная, что не позволяет найти оптимальное решение точными методами линейного программирования, включая симплекс-метод.

Задача может быть решена методом полного перебора вариантов и выбора из них оптимального. Однако, насчитывается nm комбинаций, удовлетворяющих условиям (2.3) и (2.4). К примеру, если n и m равняются 10, то число допустимых вариантов составит 10 миллиардов, перебор и расчет которых может занять продолжительное время. На практике же требуется решать задачи большей размерности. В этой связи целесообразно использовать алгоритмы, позволяющие быстро найти близкое к оптимуму решение. Один из таких алгоритмов предложен и подробно описан в [1].

Дальнейшие исследования позволили привести (2) к задаче целочисленного линейного программирования путем введения булевых неизвестных y , принимающие следующие значения:

• 1 - если i -ый исполнитель задействован, т.е. партнер назначается на одну или более работ.

• 0 - если i -ый исполнитель не задействован, т.е. партнер не участвует в выполнении работ проекта.

Целевая функция при этом принимает линейный вид:

n

L = L ( y ) = Z y i ^ min                     ⁽⁴⁾

i = 1

Далее, требуется установить корректную связь y и x . Из самой постановки задачи следует, что если yt = 0, то

m

Е Ч j = 0 .(5)

j = 1

Когда же у, = 1 , тогда

m m >Е x,j >1.

j = 1

Следовательно, связь x и y можно выразить условием следующего вида:

m • y >Exi,j > yi, i=1, n(7)

j = 1

Покажем корректность условия (7) при любом целом значении m >  1 :

• 1.    Корректные значения y и x :

m

• -    если y, = 0 и Z x_t j = 0, то условие 0 >  0 >  0 истинно;

j=1,

m

• -    если у, = 1 и Z x_t j = 1, то условие m >  1 >  1 истинно;

j=1,

m

• -    если yt = 1 и Z xt =r r, то условие m > r > 1 истинно при любом r в j =1

• 2.    Противоречивые значения y_t и x_t .:

интервале [1, m];

m

• -    если y_t = 0 и Z x_t j = 1, то условие 0 >  1 >  0 ложно;

j=1    , m - если yt = 1 и Z xi j = 0, то условие m > 0 > 1 ложно;

j = 1 , m

• -    если y i = 0 и Z x_t . = r , то условие 0 >  r >  1 ложно при любом r ;

j = 1 ,

В итоге получаем модель линейного целочисленного программирования (7).

L(У)=ЁУг ^min i=1

nm

ZZ -v S i .1 j .1

• n                   ____

• Z j 1, j = ¹, m

i , 1

m

• , ^m ' У , > Z ^x i,j , i = 1, n

j - ¹

m

• Z ^x i , j >  Уг , i = 1, n

• j = 1         _

У г e { ^0,1 } , i = 1, n

^ x i , j e { 0,1 } , i = 1, n , j = 1, m

Задача оптимизации количества участников проекта в постановке (7) решается с помощью симплекс-метода и метода отсечений, которые реализованы в широком спектре программных средств, включая LPSolve, MS Excel с надстройкой Solver («Поиск решения»), CPLEX Optimizer и др.

В предложенную модель в случае необходимости могут быть добавлены другие ресурсные ограничения и условия:

• -    ограничения на возможное количество ресурсов, которое может выделить партнер для выполнения всего проекта и отдельных работ [3];

• -    ограничения по срокам начала и окончания отдельных работ и всего проекта в целом, учитывая топологию сетевой модели проекта [2, 4].

• -    «запреты» на выполнение отдельных работ конкретными партнерами, путем присвоения соответствующим c _{i , j} значений больших S [2, 5].

Наряду с названными ограничениями в линейной постановке задачи могут быть учтены и другие условия, выдвигаемые заказчиком, менеджером проекта и самими партнерами.