Software & Systems

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

При решении данной задачи необходимо учитывать соответствие подаваемых заявок следующим требованиям: выполнение проектов в установленные сроки, непревышение границ бюджета, оценка рисков по гарантиям успешного выполнения проекта – не менее заданного значения вероятности. Следует отметить, что некоторые проекты являются комплекс­ными и включают в себя другие проекты в качестве составных частей, реализация которых обеспечит создание комплексных технических систем. В этом случае вероятность завершения проекта определяется вероятностями успешного завершения всех проектов по созданию его составных частей [1].

При выборе исполнителей необходимо принимать во внимание возможное требование обеспечения некоторых предприятий минимальным объе- мом заказов и вместе с тем учитывать возможности предприятий по освоению выделяемых ассигнований.

Формализация задачи

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

В формализованном виде задачу оптимального назначения на выполнение проектов можно представить следующим образом: задано множество выставленных на конкурс проектов Q={Q1, Q2, ..., Qj, ..., Qm}. Имеется множество возможных претендентов на выполнение отдельных проектов I = {I1, I2, ..., Ii, ..., In}. Требуется распределить множество проектов Q между исполнителями I:

=Æ

при i≠j, так, чтобы выполнялось

                                            (1)

при ,                                                                (2)

      ,                                    (3)

,                                                            (4)

где P(Qj) – вероятность успешного завершения проекта Qj; C(Qi) – стоимость выполнения проектов, назначенных i-му исполнителю; T(Qj) – время завершения проекта Qj.

Заявленная стоимость i-го исполнителя выполнения j-го проекта не должна превышать заданную (Сij ≤ С0), а время до завершения проекта τij превышать директивное.

По предоставленным данным формируются признаки претендентов на каждый проект:

Необходимо определить матрицу назначений

где

Успешное завершение j-го проекта i-м исполнителем оценивается вероятностью P(Ii, Qj). Если проект Qj является комплексным, то есть

то                                                   (5)

где P(Ii, Qje) – вероятность успешного завершения составной части проекта Qj исполнителем Ii.

Таким образом, математическая формулировка задачи на основании условий (1)–(4) выглядит следующим образом:

минимизировать    (6)

при ограничениях

                                                        (7)

,                                                                (8)

,                                                (9)

,                                         (10)

.                                                          (11)

Переменная πij не допускает распределение проектов исполнителям, не претендующим в конкурсе на этот проект.

Ограничения (7) и (8) означают, что все m проектов распределены в результате конкурса и один проект распределяется, соответственно, только одному исполнителю, а ограничение (9) обеспечивает выполнение проектов в заданные директивные сроки.

Ограничения (10) обусловлены необходимостью минимального обеспечения предприятия-исполнителя заказами (Cmin) для его функционирования, а также призваны учитывать его возможности по освоению выделяемых ассигнований (Cmax).

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

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

Подходы к решению

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

Обобщенная задача о назначениях в наиболее общей форме формулируется следующим образом: имеется некоторое число работ A = {a1, …, ai, …, am} и некоторое число исполнителей B = {b1, …, bj, …, bn}, при этом множество исполнителей имеют размер, необязательно равный размеру множества работ. Исполнитель может быть назначен на выполнение любых (необязательно одной) работ, но с неодинаковыми затратами, то есть эффективность пары ai и bj – это c(ai, bj); xij = 1, если ai размещено на позиции bj, и 0 в противном случае, xijÎ{0, 1}. Для каждой задачи был назначен один исполнитель, то есть  В этой формулировке решение может и не быть целым, но всегда существует оптимальное решение с целыми значениями. Это утверждение следует из абсолютной унимодулярности матрицы [2]. Каждый исполнитель имеет определенный бюджет, так что сумма всех затрат не должна его превышать:

,

где Rk – ресурс агента k. Требуется распределить работы так, чтобы выполнить их с минимальными затратами: .

Обобщенная задача может быть решена несколькими методами. Вот некоторые из них:

–      метод полного перебора;

–      метод ветвей и границ;

–      эвристические алгоритмы (алгоритм жадности, метод поиска ближайшего соседа);

–      метод восхождения;

–      генетические алгоритмы (эволюционные вычисления);

–      мета-эвристики (локальная оптимизация, гибридные схемы) и др.

Из перечисленных методов наиболее затратным по машинному времени является метод полного перебора, наиболее выгодными – метод ветвей и границ и генетические алгоритмы. Наиболее эффективное решение получается при использовании генетических алгоритмов.  Однако стоит отметить, что в общем случае генетические алгоритмы не гарантируют нахождение оптимального решения [3]. Это является существенным недостатком для контекста данной задачи: различия между решением с хорошим результатом и оптимальным решением, составляющие небольшую разницу между стоимостными характеристиками C(Xij), на деле могут привести к значительным экономическим потерям.

В представленной задаче о назначениях присутствует ряд дополнительных условий – ограничений и зависимостей, что также предъявляет опреде- ленные требования к используемым алгоритмам. Во-первых, это наличие не только верхнего ограничения по ресурсам для исполнителей, но и нижнего значения: . Во-вторых, в случае комплексного проекта Qj возникает элемент нелинейности в ограничении по вероятности его успешного выполнения: .

Для решения оптимизационных задач часто используются алгоритмы нелинейной оптимизации, представленные в вычислительных пакетах, однако они, как и все численные итеративные методы, обладают рядом недостатков, что существенно затрудняет их применение: при поиске условного экстремума данные методы осуществляют поиск локального экстремума, а также обладают вероятностью зацикливания. Кроме этого, они требуют приближенного начального решения – определения некоторого допустимого распределения и в случае неудачных начальных значений не позволяют решить задачу [4].

Таким образом, для решения задач этого типа разрабатываются специфические алгоритмы, основанные на комбинаторике, графах и т.д. [5].

Алгоритм поиска оптимальных назначений

Исходя из того, что данная задача является задачей целочисленного (булевого) программирования и переменные матрицы назначений Xij могут принимать всего лишь два значения – 0 и 1, для оперирования предоставляемыми входными данными и ограничениями при реализации алгоритмов решения наиболее эффективно представление множества заявок на исполнение в форме графа.

Вершинами графа являются объекты заявок исполнителей на тот или иной проект XijÎX, ребрами – все возможные варианты назначений исполнителей I на проекты Q.

Образованный граф G является многодольным или m-дольным, так как множество X его вершин Xij можно разбить на m (по количеству проектов) непересекающихся подмножеств таким образом, что в графе G нет ни одного ребра, у которого оба конца лежали бы в одной доле [6]. Действительно, в соответствии с условием (8) каждый проект или часть комплексного проекта выполняется единственным исполнителем и, учитывая требование (7), все проекты {Q1, Q2, ..., Qj, ..., Qm} должны быть выполнены.

Заявку Xij претендента Ii на проект Qj характеризуют следующие параметры:

–      стоимостная характеристика C(Xij) – заявленная стоимость, за которую исполнитель готов реализовать проект;

–      временная характеристика τ(Xij) – время, необходимое исполнителю на реализацию проекта;

–      вероятностная характеристика P(Xij) – гарантируемая вероятность выполнения проекта на требуемых условиях и в заданные сроки.

Множество проектов Q представляется в форме списка, где каждый проект Qj характеризуют параметры:

–      заданная стоимость Сj – максимальная стоимость выполнения проекта;

–      временная характеристика Tдир(Qj) – директивное время выполнения проекта;

–      вероятностная характеристика P(Qj) – нижняя граница требуемой вероятности успешного завершения проекта.

Аналогично представляется множество исполнителей I, где каждый исполнитель Ii характеризуется

–      минимальным бюджетом Cmin – бюджет минимального обеспечения исполнителя заказами;

–      максимальным объемом средств Cmax – максимальный объем выделяемых исполнителю ассигнований.

Структура данных в форме m-дольного графа, множества исполнителей и проектов в общем виде представлена на рисунке 1.

Используемая на начальном этапе подготовки данных методика последовательного развития, анализа и отсева вариантов состоит в способе построения операторов их анализа таким образом, чтобы они позволяли отсеивать бесперспективные начальные части вариантов до их рассмотрения. Поскольку при отсеивании бесперспективных начальных частей вариантов отсеивается и все множество их продолжений, происходит значительная экономия вычислительных затрат [7].

Таким образом, на первом этапе алгоритма определяется множество допустимых решений. При отсеве недопустимых вариантов назначений осуществляется просмотр всех поданных заявок исполнителей по перечню проектов. В соответствии с представленными требованиями ограничений отсеиваются заявки:

–      не проходящие по стоимостным критериям, C(Xij) ≤ Сj;

–      не укладывающиеся в сроки исполнения, τ(Xij) ≤ Tдир(Qj);

–      не предоставляющие необходимых гарантий исполнения, P(Xij) ≥ P(Qj).

Для комплексных проектов отсев претендентов по вероятности не осуществляется, так как в данном случае учитывается только совместная вероятность успешного выполнения.

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

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

На втором этапе алгоритма происходит сортировка списка вершин-заявок в каждой доле m-доль­ного графа, то есть для каждого проекта. Вершина содержит следующий набор данных: наименование проекта Ii, наименование исполнителя Qj, заявленная стоимость C(Xij), временная характеристика τ(Xij), вероятностная характеристика P(Xij).

Сортировка производится по возрастанию заявленной стоимости.

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

На третьем этапе осуществляется поиск в графе допустимых маршрутов – распределений за- явок способами, удовлетворяющими всем требованиям ограничений.

Поиск осуществляется методом обхода графа по стратегии DFS – поиска в глубину [8]. Данный алгоритм позволяет увеличить скорость поиска, просматривая сначала заявки на каждый проект с минимальными стоимостями и только потом переходя к рассмотрению помещенных в конец отсортированного списка.

Для реализации алгоритма используются вспомогательные структуры:

–      стек для запоминания еще не обработанных вершин графа (заявок);

–      список допустимых решений – выборок заявок;

–      текущий формируемый список заявок.

Поиск выполняется следующим образом.

I. Задается множество стартовых вершин – заявок на выполнение первого проекта в списке проектов Q.

II. Организуется цикл по условию опустошения стека, и внутри цикла выполняются следующие шаги:

1. извлечь из стека очередную вершину (заявку);

2. обработать вершину (заявку);

3. заменить в формируемом списке заявку на анализируемый проект из списка Q на извлеченную из стека;

4. удалить из формируемого списка все заявки на проекты, следующие за анализируемым;

5. определить исполнителя, подавшего извлеченную из стека заявку;

6. проверить превышение бюджета для формируемого списка заявок () по определенному исполнителю из списка I: если бюджет превышен, извлечь из стека очередную вершину (заявку), иначе перейти к шагу 7;

7. для комплексного проекта проверить значение гарантированной вероятности успешного исполнения проекта: если значение меньше заданного, извлечь из стека очередную вершину (заявку), иначе перейти к шагу 8;

8. если заявка извлечена, перейти на последний проект из списка Q, иначе перейти к шагу 9;

8.1. проверить обеспечение минимального финансирования, , ля формируемого списка заявок по всем исполнителям списка I:

8.1.1. если финансирование не обеспечивается, извлечь из стека очередную вершину (заявку),

8.1.2. иначе добавить формируемый список к списку допустимых решений;

9. включить в стек все вершины (заявки) на следующий проект из списка Q, то есть смежные с текущей.

Основные принципы работы алгоритма пока- заны на рисунке 2.

По окончании работы поискового подалгорит­ма найдены все возможные варианты, обеспечивающие назначение исполнителей по всем заданным проектам в рамках ограничений (10) и в случае (5) (комплексного проекта) ограничения (11).

На четвертом этапе осуществляется определение оптимального пути – варианта назначений – из составленного списка допустимых решений, в котором суммарная стоимость исполнения всех проектов будет минимальной. Для этого достаточно просуммировать заявочные стоимости проектов и остановиться на варианте с минимальным значением: min.

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

В методах неявного перебора делается попытка так организовать перебор, используя свойства рассматриваемой задачи, чтобы отбросить часть допустимых решений. Наибольшее распространение среди схем неявного перебора получил метод ветвей и границ, в основе которого лежит идея последовательного разбиения множества допустимых решений. На каждом шаге метода элементы подмножества подвергаются анализу: содержит ли данное подмножество оптимальное решение [9].

При поиске в графе путем его обхода метод неявного перебора применяется на шагах 6 и 7. На шаге 6 дальнейший поиск при превышении максимального объема финансирования (10), выделяемого организации, прекращается. Благодаря данному анализу отсекается подмножество вершин графа, образующее дерево с корневой вершиной, содержащей заявку, рассматриваемую в текущий момент работы алгоритма. Исследуемый путь в графе переходит на соседнюю или возвращается на предыдущую вершину, и поиск продолжается. Аналогичная ситуация возникает на шаге 7, когда множество вершин, изначально предполагаемых к рассмотрению, исключаются по причине уменьшения вероятности успешного завершения комплексного проекта до неприемлемых значений (11).

Модификация алгоритма

Алгоритм, основанный на методе ветвей и границ, который строит дерево решений для перебора вариантов маршрута (циклов обхода) с отсечением, можно модифицировать, уменьшив время его работы. Отсекаются такие частично построенные маршруты, у которых оценка длины маршрута больше или равна длине ранее построенного полного наилучшего маршрута [10]. Применительно к предлагаемому алгоритму данная модификация будет следующей.

Изначально определяется минимально возможная стоимость исполнения каждого проекта без учета финансовых ограничений (10). Для этого достаточно найти минимальную заявленную стоимость на каждый из m проектов из числа допустимых решений, полученных на 1-м этапе.

Если при выборе заявки на j-й проект Qj сумма стоимостей уже отобранных заявок совместно с суммой минимально заявленных из возможных по оставшимся проектам превышает стоимость выполнения всех проектов в наилучшем наборе назначений из ранее найденных и помещенных в список допустимых решений, то дальнейший анализ, начиная с вершины j+1 по текущему варианту маршрута, не имеет смысла:

.

В общем случае при применении алгоритма на множествах проектов Q небольшой размерности (до 10 проектов) данную проверку имеет смысл производить на шагах при j³m/2, то есть со второй половины списка проектов. При работе со списками большой размерности частота проведения проверок увеличивается.

Описание разработанного программного средства

Описанные в статье методы и алгоритмы были реализованы в виде программного комплекса со следующими характеристиками.

Максимально возможное количество проектов и кандидатов на исполнение не ограничивается конкретными пороговыми значениями, однако при обработке больших объемов данных или многовариантных решений возможно существенное увеличение времени работы алгоритма программного комплекса. Во избежание этого множество заявок Х, подаваемых на вход системе, следует делать минимальным, для чего необходимо указывать все возможные ограничивающие критерии [11]. Однако при полном отсутствии ограничивающих критериев (10) алгоритму достаточно одного шага анализа, так как решение задачи сводится к выборке заявки минимальной стоимости из всех заявленных на проект и, благодаря предварительной сортировке данных, в первую очередь будет просмотрен оптимальный вариант.

Графический интерфейс разработанного на основе приведенного алгоритма ПО представлен на рисунке 3.

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

–      задание временных, стоимостных и вероятностных ограничений по каждому проекту;

–      задание финансовых ограничений на бюджет исполнителей;

–      работа в режимах с множеством независи- мых проектов и многозадачным комплексным проектом;

–      определение на основе входных данных всех возможных назначений (заявок), соответствующих требованиям, по видам работ;

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

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

Литература

1.     Кордюков Р.Ю. Метод оптимизации размещения гос- оборонзаказа на предприятиях оборонно-промышленного комплекса // Науч. вестн. ОПК России. 2015. № 2. С. 70–73.

2.     Вагнер Г. Основы исследования операций; [пер. с англ.]. М.: Мир, 1972. Т. 1. 336 с.

3.     Фомина Ю.Н. Исследование алгоритмов оптимизации конфигурирования и распределения заказов при решении задач ТПП в среде виртуального предприятия // Науч.-технич. вестн. 2007. № 38. С. 188–196.

4.     Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. 3-е изд. М.: Высш. школа, 2008. 544 с.

5.     Вавилов В.А., Змеев О.А., Змеева Е.Е. Исследование операций: электр. пособие. URL: http://fmi.asf.ru/library/book/ OperReserch/ (дата обращения: 24.12.2015).

6.     Кузнецов О.П. Дискретная математика для инженера. СПб: Лань, 2009. 400 с.

7.     Сипко Е.Н. Метод последовательного анализа вариантов решения задачи составления расписания занятий // Искусственный интеллект. 2011. № 1. С. 243–250.

8.     Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2005. 1296 с.

9.     Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: учеб. пособие. Новосибирск: Изд-во НГУ, 2005. 78 с.

10.  Костюк Ю.Л. Эффективная реализация алгоритма решения задачи коммивояжера методом ветвей и границ // Прикладная дискретная математика. 2013. № 2. С. 78–90.

11.  Иванова А.В., Абу-Абед Ф.Н. Построение имитационных моделей со случайными событиями и процессами // Проблемы информатики в образовании, управлении, экономике и технике: сб. стат. XV Междунар. науч.-технич. конф.; [под ред. В.И. Горбаченко, В.В. Дрождина]. Пенза, 2015. С. 38–42.