Триста миллионов долларов остались неиспользованными, а крупный проект, охватывавший двенадцать самых прибыльных процессов, в бюджет не попал. Так работает отбор «по выгоде на рубль». Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует жадный алгоритм и задачу о рюкзаке в трёх нотациях.

Рис. 1. Жадный отбор по убыванию отдачи и страховка в конце
Проекты в бюджет отбирали по очереди: сначала самые выгодные на рубль. Постоянно побеждали «малыши», обещавшие краткосрочный эффект.
В итоге не влез важный крупный проект, охватывавший двенадцать самых прибыльных бизнес-процессов, хотя неиспользованными остались 300 млн долларов. До стратегии очередь так и не доходила: её всякий раз обгоняли быстрые победы.
Короткий ответ: жадный алгоритм берёт самое выгодное одно за другим и считается мгновенно, но может пропустить большое и оставить деньги на столе.
Точный набор даёт таблица решений, где для каждого бюджета записан лучший достижимый эффект. Рисовать отбор руководителю удобнее всего именно этой таблицей.
Как устроен жадный отбор?
Жадный алгоритм – способ решать задачу шаг за шагом, каждый раз выбирая то, что выглядит лучшим прямо сейчас, и не пересматривая прошлые шаги. В отборе проектов это значит: посчитать отдачу на рубль, упорядочить проекты по убыванию и брать, пока хватает бюджета.
По ГОСТ 19.701 это две подготовки и цикл с одним ромбом. Справа на схеме – страховка: в конце сравнить портфель с самым ценным проектом, взятым в одиночку. Она гарантирует не меньше половины лучшего результата, а без неё жадность может проиграть сколько угодно.
Как «Кедр» делит десять миллионов?
Сервисная компания «Кедр» выбирает из пяти проектов на бюджет 10 млн руб. Крупный проект «А» стоит 8 млн и даёт 26 млн эффекта, остальные дешевле и выгоднее на рубль. Отдача у «Б» – 3,67, у «В» – 3,50, у «Г» и «А» – по 3,25.

Рис. 2. Жадный выбор оставил миллион на столе и упустил проект «А»
Жадный отбор берёт «Б», «В» и «Г»: потрачено 9 млн, эффект 31 млн, а на «А» уже не хватает. Лучший набор – «А» и «В»: ровно 10 млн и эффект 33 млн. Страховка здесь не спасает: одиночный «А» даёт 26 млн против 31 у портфеля, и точный ответ находит только таблица.
Что такое задача о рюкзаке?
Задача о рюкзаке – выбор набора предметов с наибольшей суммарной ценностью, общий вес которых не превышает вместимости. Предметы – проекты, вес – цена, ценность – эффект, рюкзак – бюджет. Проект берут целиком или не берут: половину крупного не профинансируешь.
Таблица решений – способ, где строки – проекты, рассмотренные по одному, а столбцы – все бюджеты от нуля до полного. В каждой ячейке записан лучший эффект: больший из двух вариантов – без нового проекта или с ним, если на него хватает денег.

Рис. 3. Оранжевый путь ведёт к ответу: проекты «А» и «В»
Метод называют динамическим программированием, его развивал Ричард Беллман в 1950-х годах. Таблица заполняется слева направо и сверху вниз, а ответ стоит в правом нижнем углу. Путь назад показывает выбор: где число в строке изменилось, там проект взят.
Что делать, если рюкзак мал?
Лимит риска и сумма сделок часто оказывались велики для лимитов собственных принятий решений подчинённых. Приходилось объединяться, чтобы заключать сделки с крупными клиентами, до которых «ещё не доросли». Общий лимит – это один большой рюкзак вместо нескольких маленьких: крупный предмет помещается только в него.
Тот же приём работает с бюджетами отделов. Пока каждый отбирает проекты в узкий лимит, стратегический проект не влезает никуда. Его рассматривают наверху, в общем бюджете, а остаток раздают отделам по прежним правилам.
Сколько стоит точность?
Перебор всех наборов удваивается с каждым новым проектом: для 20 проектов – миллион вариантов, для 40 – больше триллиона. Таблица решений растёт куда медленнее: проекты умножаются на шаги бюджета, и 40 проектов при бюджете в 100 шагов дают 4’000 ячеек.

Рис. 4. Число вычислений для 5, 20 и 40 проектов на логарифмической шкале
Жадный отбор дешевле всех: упорядочить сорок проектов – около двухсот сравнений. Цена этой скорости – точность: ошибка тем больше, чем крупнее проекты относительно бюджета. Для «Кедра» она составила 2 млн эффекта из 33, или 6%.
Когда жадности хватает?
Быстрое решение «по удельной выгоде» сработало при выдаче потребительских кредитов. Утром займы выдавались охотнее, а ближе к концу дня гайки скоринговых систем закручивались, чтобы обеспечить ожидаемый расчётный уровень риска. Первые четыре рабочих часа, или четверть сделок, точный расчёт не пытались делать.
Жадность уместна, когда каждое решение мало по сравнению с общим лимитом и ошибку можно поправить позже. Тысячи небольших сделок – как песок: рюкзак заполняется без пустот. Крупные проекты – как камни: без таблицы остаётся дыра.
Какими нотациями рисовать отбор?
ГОСТ 19.701 хорошо передаёт жадный цикл и страховку, но для рюкзака бесполезен: двойной цикл по проектам и бюджетам превращается в клубок стрелок. Его ценят авторы регламентов отбора: каждый ромб – пункт процедуры.
Таблица решений показывает все бюджеты сразу и делает выбор видимым. Её любят финансовые аналитики: по строке видно, сколько эффекта добавляет каждый проект при любом бюджете, а значит, и цену урезания бюджета на миллион.
Псевдокод укладывает оба алгоритма в девять строк каждый. Им пользуются разработчики систем бюджетирования: текст сразу переносится в код и в таблицу Excel.

Рис. 5. Жадный отбор – один проход, рюкзак – двойной цикл
Какая нотация лучше?
Лучшая нотация для отбора в бюджет – таблица решений: 20 баллов против 19 у псевдокода и 17 у ГОСТ. Руководитель видит не только ответ, но и как он меняется при другом бюджете. Вес вопроса о руководителе удвоен: сборник написан для него.

Рис. 6. Оценка трёх нотаций: 20, 19 и 17 баллов
Псевдокод отстал на балл и лучше для разработчика и ИИ. ГОСТ остаётся для регламента жадного отбора со страховкой.
В следующей статье сборника – венгерский алгоритм: как назначить людей на задачи, чтобы общий результат был наибольшим.
Что сделать руководителю?
Хватит четырёх шагов:
- Посмотрите, какие крупные проекты не прошли отбор и сколько денег осталось неиспользованными.
- Сравните жадный портфель с лучшим набором из таблицы решений.
- Стратегические проекты рассматривайте в общем лимите, а не в лимитах отделов.
- Мелкие однотипные решения отдайте жадному правилу и поправляйте порог по ходу дня.
Что запомнить?
- жадный отбор берёт лучшее на рубль и может упустить крупное
- страховка гарантирует не меньше половины лучшего результата
- таблица решений находит точный набор для любого бюджета
- общий лимит вмещает проекты, которым тесно в лимитах отделов
- отбор в бюджет лучше всего рисовать таблицей решений.