А.В. Катаев Т.М. Катаева
Управление проектами на базе динамической сети партнеров. Монография.
| Предыдущая |
3.3. Модели назначения минимального количества исполнителей работ при ограниченном бюджете проекта
Проектный менеджер, действуя в рамках ограниченного бюджета, в ряде случаев стремится к минимизации количества исполнителей работ по проекту. Причем поиск единственного исполнителя, готового выполнить все работы, на практике, как правило, не оканчивается успешно либо ввиду отсутствия у претендентов перечня всех необходимых компетенций, либо из-за превышения существующих финансовых лимитов.
Основные причины, связанные с минимизацией команды проекта в рамках партнерской сети:
- желание упростить контроль и управление выполнением проекта;
- возможность получить скидки от партнеров за объем передаваемых им работ;
- стремление сократить транзакционные издержки, связанные с заключением контрактов, трудовых договоров и дальнейшим контролем их исполнения.
В этой связи актуальным является применение методов оптимизации, позволяющих подобрать минимальную по численности команду проекта. Далее рассмотрим одну из базовых задач и возможные методы ее решения.
Постановка задачи. Имеется m работ в проекте. На выполнение каждой работы претендуют n различных исполнителей (субподрядчиков), готовых в полном объеме выполнить определенные работы за согласованную с каждым исполнителем стоимость . На каждую работу требуется выбрать только по одному исполнителю, но исполнитель может быть назначен на несколько работ одновременно. Требуется произвести назначение потенциальных исполнителей на основные проектные работы таким образом, чтобы количество задействованных в реализации проекта было минимальным, а общая стоимость их услуг не превышала выделенный бюджет.
Из постановки задачи следует, что целевой функцией является именно количество задействованных в проекте исполнителей. В качестве ограничений выступает выделенный на выполнение работ бюджет и условие выполнения одной работы одним исполнителем. Неизвестные – булевы переменные, показывающие факт назначения i-го исполнителя на j-ю работу (1 – назначается, 0 – нет). Оптимальное же решение задачи представляет собой удовлетворяющий всем ограничениям план распределения работ по партнерам, при котором значение целевой функции будет минимально.
Очевидно, что без ограничения на бюджет оптимальным решением задачи является выполнение всех работ только одним (любым) исполнителем. Следовательно, лучшим значением целевой функции является 1 (нижняя граница), когда задействован только один исполнитель на всех работах, а худшим – n (верхняя граница), если потребовалось привлечь всех исполнителей для выполнения работ с выделенным общим объемом финансирования. Причем в случаях, когда n > m, верхней границей будет m – по условию задачи нельзя задействовать больше исполнителей, чем работ в проекте. Таким образом, значение целевой функции дискретно и лежит в интервале .
Задача может не иметь решения в том случае, если не существует удовлетворяющего ограничению по бюджету варианта расстановки исполнителей по работам. Условие наличия решения можно выразить следующим выражением:
- i – порядковый номер исполнителя,
- j – порядковый номер проектной работы,
- m – количество работ, а n – количество исполнителей;
- – стоимость выполнения j-й работы i-м исполнителем;
- S – выделенный бюджет проекта.
В случае же моделирования частной задачи о покрытии множества, S = 0, а устанавливаются в следующих значениях: 0 – i-й исполнитель может выполнить j-ю работу, 1 – не может выполнить.
В приведенной модели целевая функция (3.32) нелинейная, что не позволяет найти оптимальное решение точными методами линейного программирования, включая симплекс-метод.
При решении же задачи методом полного перебора количество вариантов состава проектных групп будет
К примеру, если количество исполнителей n равно 10, то количество вариантов групп будет 1023. Количество же комбинаций при расстановке исполнителей по задачам составит . Если же n и m равняются 10, тогда число вариантов расстановки составит 10 млрд. Очевидно, что в этом случае полный перебор всех вариантов и выбор из них лучшего занимает неприемлемо длительное время.
В отдельных случаях возможно сокращение размерности исходной задачи путем исключению из рассмотрения заведомо недопустимых элементов (назначений) и нахождения единственного допустимого назначения исполнителя на работу. Для иллюстрации приведем следующий пример:
|
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
Р6 |
И1 |
4 |
5 |
7 |
5 |
6 |
4 |
И2 |
2 |
1 |
5 |
2 |
5 |
1 |
И3 |
1 |
1 |
1 |
1 |
3 |
8 |
И4 |
3 |
2 |
2 |
6 |
4 |
8 |
Мин |
1 |
1 |
1 |
1 |
3 |
1 |
Бюджет (S) = 9.
В примере серым цветом залиты элементы, выбор которых не даст допустимого решения. Видно, что строка И1 не имеет ни одного допустимого элемента, а столбец Р6 имеет всего один допустимый элемент (назначение И2 на Р6). Следовательно, в любом допустимом решении не будет исполнителя И1, всегда будет И2 с назначением на работу Р6 и назначения будут произведены только среди элементом, залитых белым цветом. Логика нахождения недопустимых элементов по каждому столбцу следующая: если на все остальные работы будут выбраны исполнители, предлагающие выполнить каждую из них с минимальными затратами, что останется из бюджета на выполнение рассматриваемой работы? То есть все элементы, большие этого «остатка», являются недопустимыми.
Перебор можно вести не по элементам, а по вариантам проектных команд (составу групп). В этом случае также возможно увеличение скорости поиска точного оптимального решения путем отсечения заведомо недопустимых и, соответственно, неоптимальных решений. К примеру, если n = 4, то количество всех вариантов решений составит 15 (рис.3.2). Предположим, что для группы из трех участников под номерами 2, 3 и 4 («234») нет допустимого варианта расстановки исполнителей по задачам, тогда для всех групп меньшей размерности, состоящих только из участников группы «234», отсутствует допустимый вариант расстановки. Следовательно, данные группы можно исключить из рассмотрения на предмет оптимальной расстановки исполнителей по задачам.
Рис. 3.2.Пример дерева вариантов групп
Для установления факта отсутствия допустимых в соответствии с условиями (3.33) – (3.35) вариантов назначения потенциальных исполнителей на реализацию выделенных работ по проекту необходимо и достаточно выполнение следующего условия:
(3.36)
Условие (3.36) отражает, что в случае, если сумма минимальных по стоимости вариантов выполнения всех работ будет больше бюджета S, тогда не существует ни одной группы (подгруппы) с допустимым распределением задач по исполнителям.
Движение по дереву вариантов групп может осуществляться следующими способами:
1. Веточный способ – перебор ведется по веткам вниз, т.е. сначала проверяется наличие допустимого решения для группы «1234», затем для «234», «34», «3» и так далее.
2. Уровневый способ – перебор ведется с верхнего уровня поочередно, т.е. проверяются все группы 4-го уровня, затем все 3-го и так далее. В этом случае, если на определенном уровне не находится ни одного допустимого решения, тогда оптимальным решением является любая допустимая группа вышестоящего уровня.
При уровневом способе для ускорения нахождения решения возможно применение алгоритма бинарного поиска (метода деления «пополам»). По этому алгоритму перебор ведется не с верхнего, а с «центрального» уровня, который делит количество всех уровней на две части: верхнюю и нижнюю. В случае, если на «центральном» уровне нет ни одной группы, отвечающей необходимым требованиям, поиск осуществляется в верхней части, которая в свою очередь таким же способом делится на две части и так далее, до нахождения искомого решения. Если на центральном уровне нашлась хотя бы одна допустимая группа, тогда оптимальное решение находится на данном уровне либо ниже. При использовании данного алгоритма количество проверяемых уровней сократится до . Например, при n, равном 128, максимальное количество проверяемых уровней составит 8.
Модель (3.32) – (3.35) можно свести к задаче целочисленного линейного программирования[1] путем введения булевых неизвестных :
В итоге получаем модель целочисленного линейного программирования: (3.38), (3.39), (3.37), (3.33) – (3.35). Точное решение задачи в данной постановке можно получить с помощью симплекс-метода и методов решения задач целочисленного программирования, которые реализованы в широком спектре программных средств, включая LPSolve (sourceforge.net/projects/lpsolve/), MS Excel с надстройкой Solver («Поиск решения») или OpenSolver (opensolver.org), CPLEX Optimizer и др.
Для быстрого решения задач большой размерности целесообразно использовать приближенные алгоритмы. Ниже подробно описаны два таких метода: алгоритм максимального количества минимальных элементов[2](МКМЭ) и алгоритм максимального количества допустимых элементов[3] (МКДЭ).
Метод максимального количества минимальных элементов (МКМЭ)
В основе предложенного эвристического алгоритма лежит идея пошагового поиска и добавления строк (в терминах решаемой задачи – исполнителей), имеющих максимальное количество минимальных элементов (МКМЭ) по столбцам (т.е. работам). Метод МКМЭ можно использовать как для программной реализации, так и для ручных расчетов (при небольших размерностях). Основные принципы, заложенные в описываемом ниже алгоритме:
1. Поиск решения начинается с лучших значений целевой функции по пути «вписывания» в бюджет (принцип последовательной уступки). Другими словами, если ни один исполнитель не может выполнить все работы с установленным бюджетом, то следует выбрать одного из них и закрепить за ним некоторые работы, а на оставшиеся работы искать партнеров, предлагающим выполнить их с меньшими затратами.
2. При выборе исполнителя следует отдавать предпочтение тем исполнителям, которые могут выполнить большее количество работ с минимальными для каждой работы затратами (принцип максимального количества минимальных элементов).
3. При наличии нескольких вариантов назначений, подходящих под имеющийся (оставшийся) бюджет, следует отдавать предпочтение назначению, не увеличивающему количество задействованных исполнителей. Если такого назначения нет, тогда отдается предпочтение наименьшему по затратам варианту (принцип экономии бюджета).
Для алгоритма целесообразным является представление исходных данных решаемой нами задачи в виде матрицы затрат С размерностью n на m, где столбцы – основные проектные работы, строки – возможные исполнители, – затраты на выполнение j-й работы i-м исполнителем.
Пошаговый эвристический алгоритм нахождения оптимального решения:
Шаг 1. Основные действия:
1.1. Находим сумму всех по каждой строке – Di.
1.2. Если имеются , тогда решение найдено и на выполнение всех работ назначается исполнитель с минимальным значением . В противном случае переходим к действию 1.3.
1.3. Находим значения минимальных элементов по каждому столбцу и обозначим их как Mj. Помечаем в каждом столбце все элементы, равные Mj.
1.4. Считаем количество помеченных элементов в каждой строке (Ki) и сумму этих элементов (Zi).
1.5. Выбираем строку с максимальным Ki. Если таких строк несколько, то выбираем из них любую с максимальным Zi. Фиксируем назначение выбранного i-го сотрудника на работы с помеченными в строке i элементами, строку помечаем.
1.6. Вычеркиваем столбцы, соответствующие зафиксированным назначениям. Уменьшаем бюджет на Zi. Переходим к следующему шагу.
Шаг 2. На данном шаге аналогично предыдущему производятся те же действия, только с оставшимися столбцами и уменьшенным бюджетом. Действие 3 можно опустить – его результат получен на первом шаге и не изменится в дальнейшем.
Шаг 3. Аналогичен второму шагу. Основное отличие состоит в том, что при выполнении действия 2 предпочтение отдается Di в уже помеченных строках. Другими словами, сначала ищутся минимальные значения Di, меньшие либо равные остаточному бюджету, среди уже назначенных ранее исполнителей, а в случае неудачного поиска – среди остальных.
Шаг 4 и далее. Аналогично шагу 3 до нахождения подходящего по бюджету значения. Максимальное количество шагов составляет (m-1).
Численный пример задачи и ее решение методом МКМЭ
Согласно приведенной выше постановке задачи имеется четыре исполнителя и пять работ, матрица затрат С приведена в табл. 3.1, затраты на оплату работ по проекту определены в тысячах рублей. Ограничение на бюджет S составляет 14 тыс. руб. Требуется найти минимальное количество исполнителей, задействовав которых можно выполнить все работы и уложиться в бюджет.
Таблица 3.1
Затраты на выполнение основных работ проекта возможными исполнителями
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
|
И1 |
5 |
7 |
9 |
2 |
2 |
И2 |
2 |
3 |
3 |
8 |
3 |
И3 |
2 |
6 |
5 |
5 |
1 |
И4 |
4 |
1 |
4 |
6 |
3 |
Ниже представлено решение в табличной форме по предложенному выше алгоритму.
Шаг №1
Результаты, полученные на первом шаге алгоритма, приведены в табл. 3.2.
Таблица 3.2
Вспомогательная таблица для проведения расчетов
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
||||
И1 |
5 |
7 |
9 |
2 |
2 |
25 |
1 |
2 |
И2 |
2 |
3 |
3 |
8 |
3 |
19 |
2 |
5 |
И3 |
2 |
6 |
5 |
5 |
1 |
19 |
2 |
3 |
И4 |
4 |
1 |
4 |
6 |
3 |
18 |
1 |
1 |
M, тыс. руб. |
2 |
1 |
3 |
2 |
1 |
|
|
|
В табл. 3.2, кроме непосредственно значений стоимости выполнения работ исполнителем, добавлены следующие столбцы:
- суммы элементов по каждой строке (столбец D);
- найденные минимальные значения элементов по каждому столбцу исходной матрицы (строка M), а соответствующие этим значениям элементы выделены жирным и подчеркнуты;
- количество отмеченных подчеркиванием элементов по каждой строке (столбец K) и сумма значений этих элементов (столбец Z).
Как видно, все Di > S, однако, большее количество минимальных по величине значений (К = 2) имеют строки И2 и И3, при этом Z2>Z3, в связи с чем целесообразным является для дальнейшего нахождения решения выбрать строку И2, назначив на выполнение работ Р1 и Р3 исполнителя И2.
Для большей наглядности полученных на данном шаге промежуточных результатов выделим интересующую нас строку в табл. 3.2 серым цветом. Выделим также ячейки с минимальными значениями элементов в указанной строке, а столбцы, где они расположены, отметим серым цветом. Переходя к следующему шагу поиска решения, выделенные столбцы исключаются из рассмотрения (вычеркиваются), а бюджет уменьшается на величину Z2, соответствующую сумме значений в выделенных ячейках.
Шаг №2
На данном шаге аналогично предыдущему производятся те же действия только с новой матрицей, полученной путем исключения столбцов Р1 и Р3, и с бюджетом, уменьшенным на сумму выбранных назначений (S2 = 14 – 5 = 9 тыс. руб.). Результат представлен в табл. 3.3.
Таблица 3.3
Вспомогательная таблица для проведения расчетов в рамках второго шага
Возможные исполнители |
Выбор |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
||
Р2 |
Р4 |
Р5 |
|||||
И1 |
|
7 |
2 |
2 |
11 |
1 |
2 |
И2 |
* |
3 |
8 |
3 |
14 |
0 |
0 |
И3 |
|
6 |
5 |
1 |
12 |
1 |
1 |
И4 |
|
1 |
6 |
3 |
10 |
1 |
1 |
M, тыс. руб. |
|
1 |
2 |
1 |
|
|
|
Знаком «*» отмечены выбранные ранее исполнители, которые уже задействованы в выполнении работ проекта.
В результате проведенных действий нами было закреплено выполнение работы Р4 за исполнителем И1. При этом сумма оставшегося после предыдущего назначения бюджета уменьшилась на величину, равную стоимости указанной работы, т.е. на 2 тыс. руб.
Шаг №3
Повторяем аналогичные шагу №2 действия с учетом оставшегося бюджета (S3) в 7 тыс. руб. Результаты представлены в табл. 3.4.
Таблица 3.4
Вспомогательная таблица для проведения расчетов в рамках третьего шага
Возможные исполнители |
Выбор |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
|
Р2 |
Р5 |
|||||
И1 |
* |
7 |
2 |
9 |
0 |
0 |
И2 |
* |
3 |
3 |
6 |
0 |
0 |
И3 |
|
6 |
1 |
7 |
1 |
1 |
И4 |
|
1 |
3 |
4 |
1 |
1 |
M, тыс. руб. |
|
1 |
1 |
|
|
|
Несмотря на то, что большее количество минимальных по величине значений (К=1) имеют строки И3 и И4, имеет смысл назначить на выполнение работы Р2 и Р5 исполнителя И2, так как данное назначение позволяет нам не выйти за рамки оставшейся части выделенного бюджета (S3=7 тыс. руб.) и не увеличить количество членов команды проекта.
Таким образом, в результате проведенных действий мы получили план распределения задач по партнерам (табл. 3.5) с двумя исполнителями, суммарными затраты на выполнение в размере 13 тыс. руб. и экономией бюджета (1 тыс. руб.). Следует заметить, что полученное решение можно улучшить по критерию минимизации затрат, перераспределив выбранных партнеров по задачам – на Р5 назначить И1, уменьшив тем самым затраты на 1 тыс. руб.
Таблица 3.5
План распределения основных работ по проекту между возможными исполнителями
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
|
И1 |
5 |
7 |
9 |
2 |
2 |
И2 |
2 |
3 |
3 |
8 |
3 |
И3 |
2 |
6 |
5 |
5 |
1 |
И4 |
4 |
1 |
4 |
6 |
3 |
В соответствии с ней разработана оптимизационная модель целочисленного математического программирования, а также пошаговый эвристический алгоритм поиска оптимального решения, который позволяет на практике за приемлемое время найти близкое к оптимальному решение без применения специализированного программного обеспечения.
Метод максимального количества допустимых элементов (МКДЭ)
В отличие от МКМЭ метод МКДЭ реализует идею пошагового выбора строк с максимальным количеством допустимых элементов (МКДЭ).
Допустимыми считаются элементы, выбор которых в соответствии с условиями (3.34) – (3.35) не нарушит условие (3.33), т.е. не будет превышения имеющегося бюджета.
Ниже представлен пошаговый эвристический алгоритм нахождения оптимального решения при условии, что исходная задача имеет решение, т.е. соблюдается условие (3.31).
Пошаговый алгоритм МКДЭ:
Шаг 1. Основные действия:
1.1. Находим сумму всех по каждой строке – Di.
1.2. Если имеются , тогда решение найдено и на выполнение всех работ назначается i-й исполнитель. В противном случае переходим к действию 1.3.
1.3. Находим значения по каждому столбцу.
1.4. Определяем коэффициент допуска d по формуле (3.40). Этот коэффициент одинаков для всех столбцов на определенном шаге алгоритма. Помечаем в каждом столбце все элементы меньшие либо равные .
1.5. Считаем количество помеченных элементов в каждой строке (Ki) и сумму этих элементов (Zi).
1.6. Выбираем строку с максимальным Ki. Фиксируем назначение выбранного i-го исполнителя на работы с помеченными в i-й же строке элементами, строку помечаем.
1.7. Вычеркиваем столбцы, соответствующие зафиксированным назначениям. Уменьшаем бюджет на Zi. Переходим к следующему шагу.
Шаг 2 и далее.
На данном шаге аналогично предыдущему производятся те же действия, только с матрицей, полученной путем вычеркивания столбцов на предыдущем шаге, и остатком бюджета. Основное отличие состоит в том, что предпочтение отдается выбору в ранее помеченных строках, т.е. сначала ищутся допустимые назначения среди уже задействованных исполнителей, а в случае неудачного поиска – среди остальных.
На последнем шаге получаем решение с количеством задействованных исполнителей L. Максимальное количество шагов составляет (m-1).
Численный пример задачи и ее решение методом МКДЭ
Согласно приведенной выше постановке задачи имеется пять исполнителей и шесть работ, матрица затрат С приведена в табл. 3.6, затраты на оплату работ по проекту определены в тысячах рублей. Ограничение на бюджет S составляет 16 тыс. руб. Требуется найти минимальное количество исполнителей, задействовав которых можно выполнить все работы и уложиться в бюджет.
Таблица 3.6
Затраты на выполнение основных работ проекта возможными исполнителями
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
|||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
Р6 |
|
И1 |
1 |
1 |
8 |
8 |
8 |
8 |
И2 |
8 |
8 |
1 |
8 |
2 |
8 |
И3 |
3 |
8 |
8 |
1 |
3 |
3 |
И4 |
8 |
3 |
3 |
3 |
8 |
8 |
И5 |
8 |
8 |
8 |
2 |
8 |
2 |
Ниже представлено решение в табличной форме по предложенному выше алгоритму.
Шаг №1
Результаты, полученные на первом шаге алгоритма, приведены в таблице 3.7.
Табл. 3.7 аналогична по структуре табл. 3.2 примера для алгоритма МКМЭ. Основное отличие в том, что выделены и подчеркнуты допустимые элементы, а не только минимальные. В табл. 3.7 так же представлены следующие данные и результаты расчетов:
- стоимость выполнения работ;
- суммы элементов по каждой строке (столбец D);
- найденные минимальные значения элементов по каждому столбцу исходной матрицы (строка M);
- количество отмеченных подчеркиванием элементов по каждой строке (столбец K) и сумма значений этих элементов (столбец Z).
Таблица 3.7
Вспомогательная таблица для проведения расчетов
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
|||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
Р6 |
||||
И1 |
1 |
1 |
8 |
8 |
8 |
8 |
32 |
2 |
2 |
И2 |
8 |
8 |
1 |
8 |
2 |
8 |
33 |
2 |
3 |
И3 |
3 |
8 |
8 |
1 |
3 |
3 |
26 |
3 |
7 |
И4 |
8 |
3 |
3 |
3 |
8 |
8 |
33 |
0 |
0 |
И5 |
8 |
8 |
8 |
2 |
8 |
2 |
36 |
2 |
4 |
M, тыс. руб. |
1 |
1 |
1 |
1 |
2 |
2 |
|
|
|
Как видно, все Di > S1, следовательно, проект не может быть выполнен целиком одним партнером и требуется на этом шаге алгоритма выбрать строку с максимальным количеством допустимых элементов, т.е. строку И3. Соответственно, на выполнения работ Р4 – Р6 назначается исполнитель И3.
Для большей наглядности полученных на данном шаге промежуточных результатов выбранная строка в табл. 3.7 выделена серым цветом. Выделены также ячейки с допустимыми элементами в указанной строке, а столбцы, где они расположены, отмечены серым цветом. Переходя к следующему шагу поиска решения, отмеченные столбцы исключаются из рассмотрения (вычеркиваются), а бюджет уменьшается на величину Z3, соответствующую сумме значений в выделенных ячейках:
Таблица 3.8
Вспомогательная таблица для проведения расчетов
второго шага
Возможные исполнители |
Выбор |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
||
Р1 |
Р2 |
Р3 |
|||||
И1 |
|
1 |
1 |
8 |
10 |
2 |
2 |
И2 |
|
8 |
8 |
1 |
17 |
1 |
1 |
И3 |
* |
3 |
8 |
8 |
19 |
1 |
3 |
И4 |
|
8 |
3 |
3 |
14 |
2 |
6 |
И5 |
|
8 |
8 |
8 |
24 |
0 |
0 |
M, тыс. руб. |
|
1 |
1 |
1 |
|
|
|
Знаком «*» отмечены выбранные ранее исполнители, которые уже задействованы в выполнении работ проекта.
На данном шаге новые строки не добавлялись, а произведено назначение ранее выбранного исполнителя И3 на работу Р1. Следовательно, бюджет уменьшается на стоимость выполнения работы Р1 исполнителем И3:
В выбранных на предыдущих шагах алгоритма строках допустимых элементов нет, следовательно, требуется добавлять еще одного исполнителя. Выбран исполнитель И4 на выполнения всех оставшихся работ по той причине, что D4 не превышает остаток бюджета S3.
Таблица 3.9
Вспомогательная таблица для проведения расчетов
второго шага
Возможные исполнители |
Выбор |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
D, тыс. руб. |
K, ед. |
Z, тыс. руб. |
|
Р2 |
Р3 |
|||||
И1 |
|
1 |
8 |
9 |
1 |
1 |
И2 |
|
8 |
1 |
9 |
1 |
1 |
И3 |
* |
8 |
8 |
16 |
0 |
0 |
И4 |
|
3 |
3 |
6 |
2 |
6 |
И5 |
|
8 |
8 |
16 |
0 |
0 |
M, тыс. руб. |
|
1 |
1 |
|
|
|
Таким образом, в результате проведенных действий мы получили план распределения задач по партнерам (табл. 3.10) с двумя исполнителями и суммарными затратами на выполнение проекта в размере 16 тыс. рублей.
Таблица 3.10
План распределения основных работ по проекту между возможными исполнителями
Возможные исполнители |
Стоимость выполнения основных работ по проекту (Pi), тыс. руб. |
|||||
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
Р6 |
|
И1 |
1 |
1 |
8 |
8 |
8 |
8 |
И2 |
8 |
8 |
1 |
8 |
2 |
8 |
И3 |
3 |
8 |
8 |
1 |
3 |
3 |
И4 |
8 |
3 |
3 |
3 |
8 |
8 |
И5 |
8 |
8 |
8 |
2 |
8 |
2 |
Поиск точного решения
Представленные выше пошаговые эвристические алгоритмы позволяют на практике за приемлемое время найти близкое к оптимальному решение. Далее возможна проверка полученного решения на оптимальность путем полного перебора групп размерностью L-1. Если допустимого решения среди групп L-1 нет, следовательно, решение, соответствующее целевой функции со значением L, оптимально, в противном же случае не оптимально и возможно нахождением оптимального решения путем перебора оставшихся вариантов групп (L-2 и менее).
[1] Катаев А.В. Задача оптимизации количества участников проекта как задача целочисленного линейного программирования // Теория и практика современной науки. 2016. №8 (14). С. 181-186.
[2] Катаев А.В., Катаева Т.М. Задача минимизации количества исполнителей работ в проекте: математическая модель и алгоритм решения // Экономика и социум. 2016. №6-3 (25). С. 77-84.
[3] Катаев А.В., Катаева Т.М., Коженко Я.В. Оптимизация численного состава команды проекта: экономико-математический инструментарий // Конкурентоспособность в глобальном мире: экономика, наука, технологии. 2016. № 8-3 (22). С. 101-104.
| Предыдущая |