Stochastic Local Search for the Strategic Planning Public-Private Partnership Alexander A. Zyryanov1, Yury A. Kochetov1,2, and Sergey M. Lavlinskii1,2,3 1 Sobolev Institute of Mathematics, Novosibirsk, Russia 2 Novosibirsk State University, Novosibirsk, Russia 3 Transbaikalian State University, Chita, Russia alexander.zyryanov44@gmail.com jkochet@math.nsc.ru lavlin@math.nsc.ru Abstract. We present a new bi-level linear integer programming model for the strategic planning of the public-private partnership. This model is an extension of the previously studied models where the ecological, infrastructure, and production projects have known schedules into the planning horizon if they start. A stochastic local search matheuristic is designed for this new problem according to the upper level variables. The optimal solution for the lower level is obtained by CPLEX soft- ware. To reduce the running time, we use randomized Flip and Swap neighborhoods. To evaluate the neighboring solutions, we solve the lower level problem approximately with a small fixed deviation from the optimum. Computational results for real world instances for the Tranbaikalian polymetal fields are discussed. Keywords: Stackelberg game · Bilevel mathematical programming problem · Public-private partnership · Local search Copyright © by the paper’s authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org Локальный поиск для планирования государственно-частного партнерства 447 Стохастический локальный поиск для перспективного планирования государственно-частного партнерства 1 Александр А. Зырянов1, Юрий А. Кочетов1,2, Сергей М. Лавлинский1,2,3 1 Институт математики СО РАН, Новосибирск, Россия 2 Новосибирский государственный университет, Новосибирск, Россия 3 Забайкальский государственный университет, Чита, Россия alexander.zyryanov44@gmail.com jkochet@math.nsc.ru lavlin@math.nsc.ru Аннотация. Представлена новая математическая модель формирования эффективного механизма взаимодействия государства и частного инве- стора. Новая модель является развитием предшествующих моделей, в ко- торых экологические, инфраструктурные и производственные проекты имели заданные графики выполнения, если их реализация оказывалась выгодной. В настоящей работе предполагается, что графики выполнения проектов могут сдвигаться по времени. Для решения задачи разработан стохастический метод локального поиска по переменным верхнего уровня (государства). Оптимальное решение нижнего уровня (инвестора) нахо- дится пакетом CPLEX. Для сокращения трудоемкости применяется ран- домизация окрестностей Flip и Swap. При оценке соседних решений зада- ча инвестора решается приближенно с заданной точностью. Методика ис- пользования такого подхода демонстрируется на примере Забайкалья. Для него строится программа освоения месторождений полиметаллов и исследуются свойства получаемых решений. Ключевые слова: игра Штакельберга, двухуровневая задача математиче- ского программирования, государственно-частное партнерство, локаль- ный поиск Введение Значительная часть проблем, связанных с освоением природных ресурсов на малоосвоенных территориях РФ, концентрируется в области разработки меха- низма согласования долгосрочных интересов государства и частного инвестора. Такой механизм должен обеспечить инвестиционную привлекательность, бюд- 1 Работа1выполнена при частичной финансовой поддержке РФФИ (проект 16-06-00046, 16-07- 00319), РГНФ (проекты 16-02-00049, 16-02-00102). А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 448 жетные поступления и соблюдение экологических ограничений в процессе со- циально-экономического развития территории. Эта проблема лежит в основе стратегического планирования, ядро которого – формирование программы освоения минерально-сырьевой базы. В рамках про- граммы необходимо решить, какая производственная инфраструктура нужна для развития территории и привлечения инвесторов, и можно ли пойти на трату бюджетных средств для оказания помощи инвестору в инфраструктурном и природоохранном строительстве, не нарушая основных принципов устойчивого развития, сохранения природы и получения обществом наибольшей отдачи от природных ресурсов. Государственно-частное партнерство (ГЧП) широко используется в мире и яв- ляется эффективным инструментом достижения компромисса интересов в раз- личных сферах экономики. Мировой опыт демонстрирует успешность исполь- зования механизма ГЧП, прежде всего, для создания новой и поддержания су- ществующей инфраструктуры общественного сектора. В минерально-сырьевом комплексе государственно-частное партнерство позволяет существенно расши- рить источники финансирования проектов, заинтересовать недропользователей в освоении новых месторождений в труднодоступных районах. В России положение дел с развитием ГЧП в минерально-сырьевом комплексе следует признать неудовлетворительным. Так, характерной здесь является ситу- ация, когда инвестор не может реализовать инвестиционный проект, поскольку для этого нет необходимой инфраструктуры, а государство не хочет вкладывать деньги в инфраструктуру, пока нет уверенности в том, что эта инфраструктура будет загружена. Практические примеры решения этой проблемы в российских условиях немногочисленны, не очень успешны и говорят о необходимости со- здания специального экономико-математического инструментария для под- держки процесса разработки эффективной модели ГЧП. Эта проблема находится в центре внимания настоящей работы. Основная цель – разработка экономико-математических моделей формирования эффективного механизма партнерства, основанных на теоретико-игровой модели Штакельбер- га и решении двухуровневых задач булевого программирования. Такой подход позволяет найти компромисс экономических интересов и обеспечивает эффек- тивность в долгосрочном плане не только частным инвесторам, но и государ- ству, ставящему перед собой задачу стратегического управления минерально- сырьевым комплексом. Настоящая работа продолжает исследования авторов [1,2], где рассматривалась стационарные модели формирования ГЧП, в которых помощь государства включала инвестиции на развитие инфраструктуры и финансирование части компенсирующих природоохранных мероприятий, а моменты запуска проектов всех видов были заданы на входе. В настоящей статье формулируется обобщен- ный вариант модели в нестационарной постановке, генерирующий расписание моментов запуска отдельных проектов. Модели такого вида в наибольшей сте- пени востребованы практикой территориального планирования и могут быть использованы для решения стратегических задач управления ресурсным регио- ном. Локальный поиск для планирования государственно-частного партнерства 449 1. Постановка задачи В условиях малоосвоенной ресурсной территории главенствующую роль в партнерстве должно играть государство – именно оно должно сделать первые шаги, создающие достаточные стимулы для прихода недропользователей. Про- блема разработки эффективной модели партнерства в этих условиях сводится к задаче поиска пропорций использования основных рычагов государственной помощи инвестору – прямых государственных инвестиций на развитие инфра- структуры и финансирования части компенсирующих природоохранных меро- приятий. Конкретная комбинация этих инструментов воздействия государства на экономику проекта и фиксированная схема проектного финансирования во многом определяют и уровень рентабельности для инвестора, и эффективность использования природных ресурсов для общества – долю природно-ресурсной ренты, которую получает государство в виде налоговых платежей. Механизм партнерства эффективен, если достигнут компромисс интересов в паре «госу- дарство-инвестор», выражающийся в том, что инвестор в проекте достигает нужного уровня рентабельности, а государство получает возможно большую часть ренты как части стоимости, созданной природой. Такая схема концептуальной модели партнерства в минерально-сырьевом сек- торе России содержательно естественным образом вкладывается в философию двухуровневого программирования. Процедура взаимодействия «лидер- ведомый», положенная в основу модели Штакельберга, в наибольшей степени подходит для условий рыночной экономики и малоосвоенной ресурсной терри- тории, где роль лидера в партнерстве отведена государству, своими действиями создающему дополнительные стимулы для прихода инвесторов. В соответствии с этим и строится задача лидера, в которой государство принимает решение, основываясь на своих бюджетных ограничениях и рациональном ответе частно- го инвестора, стремящегося максимизировать свой доход. При этом необходимо учесть нестационарный характер сырьевых рынков (см. рис. 1) – практика управления минерально-сырьевым комплексом выделяет именно его в качестве ключевого фактора, определяющего результаты освоения месторождения. Волнообразный характер динамики цен и большая амплитуда создают существенные трудности в процессе принятия инвестиционного реше- ния. Выбор момента «запуска» процесса освоения месторождения определяет, на какой фрагмент волны приходится момент выхода рудника на проектную мощность. В идеальном случае разработку месторождения следует начинать таким образом, чтобы «попасть» в среднюю часть подъема ценовой волны и максимальное время продавать продукцию по высоким ценам. Еще больше за- дача усложняется, если мы начинаем конструировать целую программу освое- ния природных богатств, в которой моменты запусков отдельных проектов должны быть гармонизированы не только с рыночной конъюнктурой, но и меж- ду собой. А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 450 450 400 350 300 % 250 200 150 100 50 0 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 свинец; цинк; медь. Рис. 1. Динамика относительных цен на некоторые металлы (мировой рынок, цена 1989 г. - 100 %). Каким образом это обстоятельство может быть учтено в процессе формирова- ния программы освоения минерально-сырьевой базы (МСБ) на основе механиз- ма ГЧП? Нестационарная модель ГЧП развивает подход, предложенный в [1,2] и форму- лируется в виде задачи двухуровневого булевого программирования, решение которой уже учитывает возможность взаимных сдвигов моментов стартов от- дельных проектов и генерирует оптимальный механизм взаимодействия част- ного инвестора и государства. На входе модели задаются: – набор инвестиционных проектов, реализуемых частным инвестором, момен- ты запуска и конкретную конфигурацию которых инвестор выбирает в зависи- мости от того, что предлагает государство в области инфраструктурного строи- тельства; – набор инфраструктурных проектов, реализуемых государством, конкретный перечень которых и моменты запуска государство выбирает, исходя из своих оценок эффективности с точки зрения перспектив долгосрочного развития тер- ритории; – перечень экологических проектов, необходимых для компенсации экологиче- ских потерь, вызванных реализацией инвестиционных проектов; конкретный раздел обязательств по реализации экологических проектов между частным ин- вестором и государством на входе не определен и должен быть получен на вы- ходе модели. Выход модели – расписание старта проектов всех видов и механизм раздела затрат в процессе реализации экологических проектов между государством и инвестором. Введем следующие обозначения. Локальный поиск для планирования государственно-частного партнерства 451 𝑁𝑃, 𝑁𝐼, 𝑁𝐸 – число производственных, инфраструктурных и экологических проектов, 𝑇 – временной горизонт планирования, 𝑖 = 1, … , 𝑁𝑃, 𝑗 = 1, … , 𝑁𝐼, 𝑘 = 1, … , 𝑁𝐸, 𝑡 = 1, … , 𝑇,  = 1, … , 𝑇. Булевы переменные: 𝑧𝑖𝜏 =1, если инвестор в году 𝜏 запускает производственный проект 𝑖, и 𝑧𝑖𝜏 =0 в противном случае; 𝑥𝑗𝜏 =1, если государство в году 𝜏 запускает инфраструктурный проект 𝑗, 𝑥𝑗𝜏 =0 в противном случае; 𝑦𝑘𝜏 =1, если государство в году 𝜏 запускает экологический проект 𝑘, и 𝑦𝑘𝜏 =0 в противном случае; 𝑢𝑘𝜏 =1, если инвестор в году 𝜏 запускает экологический проект 𝑘, 𝑢𝑘𝜏 =0 в противном случае,. Производственные проекты 𝐶𝐹𝑃𝑖𝜏𝑡 – кэшфло производственного проекта 𝑖, стартовавшего в году 𝜏. 𝐸𝑃𝑃𝑖𝜏𝑡 – стоимостная оценка экологических потерь при реализации производ- ственного проекта 𝑖, стартовавшего в году 𝜏. 𝐷𝐵𝑃𝑖𝜏𝑡 – доходы бюджета от реализации производственного проекта 𝑖, старто- вавшего в году 𝜏. 𝑍𝑃𝑃𝑖𝜏𝑡 – зарплата, выплачиваемая в ходе реализации производственного проекта 𝑖, стартовавшего в году 𝜏. Инфраструктурные проекты 𝑡 𝑍𝐼𝑗𝜏 – затраты на реализацию инфраструктурного проекта 𝑗, стартовавшего в году 𝜏. 𝑡 𝐸𝑃𝐼𝑗𝜏 – стоимостная оценка экологических потерь при реализации инфраструк- турного проекта 𝑗, стартовавшего в году 𝜏. 𝑡 𝑉𝐷𝐼𝑗𝜏 – внепроектные доходы бюджета от реализации инфраструктурного про- екта 𝑗, стартовавшего в году 𝜏, связанные с общим развитием экономики терри- тории. 𝑡 𝑍𝑃𝐼𝑗𝜏 – зарплата, выплачиваемая в ходе реализации инфраструктурного проекта 𝑗, стартовавшего в году 𝜏. Экологические проекты 𝑡 𝑍𝐸𝑘𝜏 – график затрат на реализацию экологического проекта 𝑘, стартовавшего в году 𝜏. 𝑡 𝐸𝐷𝐸𝑘𝜏 – стоимостная оценка экологического дохода при реализации экологиче- ского проекта k , стартовавшего в году 𝜏. 𝑡 𝑍𝑃𝐸𝑘𝜏 – зарплата, выплачиваемая в ходе реализации экологического проекта 𝑘, стартовавшего в году 𝜏. Взаимосвязь проектов 𝜇𝑖𝑗 – индикатор технологической связности производственных и инфраструк- турных проектов, равный 1, если для реализации производственного проекта 𝑖 А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 452 необходима реализация инфраструктурного проекта 𝑗, и равный 0 в противопо- ложном случае. 𝜈𝑖𝑘 – индикатор связности производственных и экологических проектов, равный 1, если реализация производственного проекта 𝑖 влечет необходимость реали- зации экологического проекта 𝑘, и равный 0 в противоположном случае. Возможные взаимные сдвиги моментов старта проектов задаются следующими параметрами: 𝜂𝑖𝑗 – матрица взаимного временного лага производственных и инфраструктур- ных проектов, фиксирующая минимальное число лет, разделяющее год старта производственного и год старта задействованного инфраструктурного проекта, 𝑖 = 1, … , 𝑁𝑃, 𝑗 = 1, … , 𝑁𝐼; 𝜓𝑖𝑘 , 𝛾𝑖𝑘 – матрицы взаимного временного лага производственных и экологиче- ских проектов, фиксирующие, на сколько лет раньше (𝜓𝑖𝑘 ), и позже (𝛾𝑖𝑘 ) эко- логического не может быть запущен производственный, 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸. Дисконты и бюджетные ограничения 𝐷𝐺 – дисконт государства, 𝐷𝐼 – дисконт инвестора. 𝑏𝑡𝐺 , 𝑏𝑡𝑂 – бюджетные ограничения государства и инвестора в году 𝑡. Нестационарная постановка модели взаимодействия государства и частного инвестора на основе сформулированных принципов ГЧП может быть представ- лена следующим образом. Задача государства Максимизировать дисконтированный поток наличности пары «государство- население»: 𝑇 𝑁𝑃 𝑇 ∑ (∑ ∑(𝐷𝐵𝑃𝑖𝜏𝑡 + 𝑍𝑃𝑃𝑖𝜏𝑡 − 𝐸𝑃𝑃𝑖𝜏𝑡 )𝑧𝑖𝜏 + 𝑡=1 𝑖=1 𝜏=1 𝑁𝐼 𝑇 𝑡 𝑡 𝑡 𝑡 ∑ ∑(𝑉𝐷𝐼𝑗𝜏 + 𝑍𝑃𝐼𝑗𝜏 − 𝐸𝑃𝐼𝑗𝜏 − 𝑍𝐼𝑗𝜏 )𝑥𝑗𝜏 + 𝑗=1 𝜏=1 𝑁𝐸 𝑇 (1) 𝑡 𝑡 𝑡 )𝑦 ∑ ∑ (𝐸𝐷𝐸𝑘𝜏 + 𝑍𝑃𝐸𝑘𝜏 − 𝑍𝐸𝑘𝜏 𝑘𝜏 + 𝑘=1 𝜏=1 𝑁𝐸 𝑇 𝑡 𝑡 )𝑢 𝑡 ∑ ∑(𝐸𝐷𝐸𝑘𝜏 + 𝑍𝑃𝐸𝑘𝜏 𝑘𝜏 ) /(1 + 𝐷𝐺) ⇒ max 𝑘=1 𝜏=1 при условиях 𝑁𝐼 𝑇 𝑁𝐸 𝑇 𝑡 𝑡 ∑ ∑ 𝑍𝐼𝑗𝜏 𝑥𝑗𝜏 + ∑ ∑ 𝑍𝐸𝑘𝜏 𝑦𝑘𝜏 ≤ 𝑏𝑡𝐺 , 𝑡 = 1, … 𝑇, (2) 𝑗=1 𝜏=1 𝑘=1 𝜏=1 𝑇 ∑ 𝑥𝑗𝜏 ≤ 1, 𝑗 = 1, … , 𝑁𝐼, (3) 𝜏=1 Локальный поиск для планирования государственно-частного партнерства 453 𝑇 ∑ 𝑦𝑘𝜏 ≤ 1, 𝑘 = 1, … , 𝑁𝐸, (4) 𝜏=1 𝑥𝑗𝜏 , 𝑦𝑘𝜏 ∈ {0,1}, 𝑖 = 1, … , 𝑁𝑃, 𝑗 = 1, … , 𝑁𝐼, 𝑘 = 1, … , 𝑁𝐸, 𝜏 = 1, … , 𝑇, (5) (𝑧, 𝑢) ∈ 𝐹 ∗ (𝑥, 𝑦). (6) Задача инвестора Инвестор максимизирует свой суммарный чистый приведенный доход: 𝑇 𝑁𝑃 𝑇 𝑁𝐸 𝑇 ∑ (∑ ∑ 𝐶𝐹𝑃𝑖𝜏𝑡 𝑧𝑖𝜏 − ∑ ∑ 𝑍𝐸𝑘𝜏𝑡 𝑢𝑘𝜏 ) /(1 + 𝐷𝐼)𝑡 ⟹ max (7) 𝑡=1 𝑖=1 𝜏=1 𝑘=1 𝜏=1 при условиях 𝑁𝑃 𝑇 𝑁𝐸 𝑇 − ∑ ∑ 𝐶𝐹𝑃𝑖𝜏𝑡 𝑧𝑖𝜏 + ∑ ∑ 𝑍𝐸𝑘𝜏 𝑡 𝑢𝑘𝜏 ≤ 𝑏𝑡𝑂 , 𝑡 = 1, … , 𝑇, (8) 𝑖=1 𝜏=1 𝑘=1 𝜏=1 𝑇 𝑇 ∑ 𝑥𝑗𝜏 ≥ 𝜇𝑖𝑗 ∑ 𝑧𝑖𝜏 , 𝑖 = 1, … , 𝑁𝑃, 𝑗 = 1, … , 𝑁𝐼, (9) 𝜏=1 𝜏=1 𝑇 𝑇 ∑(𝑦𝑘𝜏 + 𝑢𝑘𝜏 ) ≥ 𝜈𝑖𝑘 ∑ 𝑧𝑖𝜏 , 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, (10) 𝜏=1 𝜏=1 𝑇 ∑(𝑦𝑘𝜏 + 𝑢𝑘𝜏 ) ≤ 1, 𝑘 = 1, … , 𝑁𝐸, (11) 𝜏=1 𝑇 ∑ 𝑢𝑘𝜏 ≤ 1, 𝑘 = 1, … , 𝑁𝐸, (12) 𝜏=1 𝑇 ∑ 𝑧𝑖𝜏 ≤ 1, 𝑖 = 1, … , 𝑁𝑃, (13) 𝜏=1 𝑇 𝑁𝑃 𝑇 ∑(𝑦𝑘𝜏 + 𝑢𝑘𝜏 ) ≤ ∑ 𝜈𝑖𝑘 ∑ 𝑧𝑖𝜏 , 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, (14) 𝜏=1 𝑖=1 𝜏=1 𝑇 𝑥𝑗𝜏 + 𝜇𝑖𝑗 ∑ 𝑧𝑖𝜌 ≤ 1, 𝑖 = 1, … , 𝑁𝑃, 𝑗 = 1, … , 𝑁𝐼, 𝜏 = 1, … , 𝑇, (15) 𝜌=min{𝑇,𝜏+𝜂𝑖𝑗 } 𝑇 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, 𝑦𝑘𝜏 + 𝑢𝑘𝜏 + 𝜈𝑖𝑘 ∑ 𝑧𝑖𝜌 ≤ 1, (16) 𝜏 = 1, … , 𝑇, 𝜌=max{1,𝜏−𝜓𝑖𝑗 } 𝜓𝑖𝑘 𝜈𝑖𝑘 ∑ 𝑧𝑖𝜌 = 0, 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, (17) 𝜌=1 А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 454 𝑇 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, 𝑦𝑘𝜏 + 𝑢𝑘𝜏 + 𝜈𝑖𝑘 ∑ 𝑧𝑖𝜌 ≤ 1, (18) 𝜏 = 1, … , 𝑇, 𝜌=min {𝑇,𝜏+𝛾𝑖𝑘 } 𝑧𝑖𝜏 , 𝑢𝑘𝜏 ∈ {0,1}, 𝑖 = 1, … , 𝑁𝑃, 𝑘 = 1, … , 𝑁𝐸, 𝜏 = 1, … , 𝑇. (19) В сформулированной модели государство максимизирует аналог чистого дис- контированного дохода от реализации всей программы освоения, при этом це- левая функция строится с учетом интересов населения и учитывает экономиче- ский выигрыш от появления новых рабочих мест и сопутствующие этому эко- логические потери. Ограничения (9), (10) гарантируют запуск экологических и инфраструктурных проектов необходимых для старта производственных проек- тов. Ограничения (3),(4),(12),(13) определяют однократность запуска проектов, а (11),(14) гарантируют, что экологический проект не может быть запущен, если он не нужен ни для какого из запущенных производственных. Временная вза- имосвязь проектов различного вида описывается в (15)–(18) с учетом того об- стоятельства, что, в общем случае, производственный проект может быть начат ранее момента завершения инфраструктурного, а экологический – в некотором диапазоне момента завершения производственного. Наряду со стандартными бюджетными ограничениями (2),(8) мы будем рас- сматривать и более «мягкую» их форму, позволяющую переход неизрасходо- ванных в текущем году средств на следующий год. 𝑁𝐼 𝑇 𝑁𝐸 𝑇 𝑡 𝑡 ∑ (∑ ∑ 𝑍𝐼𝑗𝜏 𝑥𝑗𝜏 + ∑ ∑ 𝑍𝐸𝑘𝜏 𝑦𝑘𝜏 ) ≤ ∑ 𝑏𝑡𝐺 , 𝜔 = 1, … , 𝑇, (2a) 1≤𝑡≤𝜔 𝑗=1 𝜏=1 𝑘=1 𝜏=1 1≤𝑡≤𝜔 𝑁𝑃 𝑇 𝑁𝐸 𝑇 ∑ (− ∑ ∑ 𝐶𝐹𝑃𝑖𝜏𝑡 𝑧𝑖𝜏 + ∑ ∑ 𝑍𝐸𝑘𝜏𝑡 𝑢𝑘𝜏 ) ≤ ∑ 𝑏𝑡𝑂 , 𝜔 = 1, … , 𝑇, (8a) 1≤𝑡≤𝜔 𝑖=1 𝜏=1 𝑘=1 𝜏=1 1≤𝑡≤𝜔 Отметим, что задачи двухуровневого программирования такой структуры, когда внутренняя задача является NP-трудной, часто оказываются более сложными с вычислительной точки зрения, чем широко известные NP-полные задачи [5–8]. В связи с этим для их решения применяются метаэвристики, способные быстро находить решения с небольшой погрешностью [9–12]. 2. Стохастический локальный поиск с запретами Для решения задачи (1)–(19) разработан стохастический метод локального по- иска с запретами по переменным 𝑠 = (𝑥𝑗𝜏 , 𝑦𝑘𝜏 ) верхнего уровня (государства). Соответствующее решение нижнего уровня (инвестора) находится методом вет- вей и границ с помощью пакета CPLEX. Такой подход показал свою эффектив- ность при решении многих задач двухуровневого программирования [13–14]. Локальный поиск для планирования государственно-частного партнерства 455 В качестве окрестности 𝑁(𝑠) решения s используются все решения, получаемые из данного применением одной из следующих операций: – открытием нового проекта; – закрытием одного из уже открытых проектов; – сдвигом старта одного из проектов на более раннее или более позднее время. Для диверсификации поиска и сокращения трудоемкости одной итерации при- меняется процедура рандомизации окрестности [10–11]: каждое соседнее реше- ние включается в рандомизированную окрестность 𝑁𝑝 (𝑠) с заданной вероятно- стью p независимо от других решений. Общая схема алгоритма поиска с запре- тами для максимизации целевой функции (1) – дисконтированного потока наличности 𝑓(𝑠) пары «государство–население» – может быть представлена следующим образом. Алгоритм STS 1. Выбрать начальное решение 𝑠 и положить 𝑓 ∗ : = 𝑓(𝑠), 𝑠 ∗ ≔ 𝑠, 𝑇𝑎𝑏𝑢𝑙 (𝑠): = ∅. 2. Повторять, пока не выполнен критерий остановки: 2.1. Сформировать окрестность 𝑁𝑝 (𝑠). 2.2. Если 𝑁𝑝 (𝑠) ≠ ∅, то найти такое решение 𝑠′, что 𝑓(𝑠′) = m𝑎𝑥{𝑓(𝑗) | 𝑗 ∈ 𝑁𝑝 (𝑠)\ 𝑇𝑎𝑏𝑢𝑙 (𝑠)}. 2.3. Если 𝑓 ∗ < 𝑓(𝑠′), то 𝑓 ∗ ∶= 𝑓(𝑠′) и 𝑠 ∗ ≔ 𝑠′. 2.4. Положить 𝑠 ≔ 𝑠′ и обновить список запретов. 3. Предъявить наилучшее найденное решение 𝑠 ∗ . Параметр 𝑝 рандомизации окрестности 𝑁𝑝 (𝑠) и длина списка запретов l для множества 𝑇𝑎𝑏𝑢𝑙 (𝑠) являются управляющими для данного алгоритма. Выбор их значений зависит от размерности задачи и мощности окрестности. В числен- ных экспериментах значение параметра p выбиралось из интервала [0.01–0.05]. Длина списка запретов 𝑙 полагалась равной 10. Список запретов включает в себя номера проектов, открытие, закрытие или сдвиг которых по времени произво- дился на последних 𝑙 итерациях. В качестве стартового решения используется точное решение задачи без учета интересов инвестора [12]. Критерием останов- ки алгоритма выступает общее число итераций, которое в экспериментах не превышало 1000. Если существует несколько оптимальных решений нижнего уровня при заданном решении 𝑠, то принято выделять различать оптимистиче- ские и пессимистические решения исходной задачи (1)–(19) [9, 10, 12]. Ниже будут рассматриваться только оптимистические решения . 3. Численный эксперимент Для демонстрации методики использования описанного инструментария в рабо- те строится специальный модельный полигон, прообразом которого является набор из 50 месторождений полиметаллических руд Забайкальского края. Для него строится набор из 10 инфраструктурных проектов, часть из которых уже А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 456 реализуется (железная дорога, ЛЭП), а другие восполняют отсутствующую на сегодня, но необходимую с учетом проектов освоения месторождений инфра- структуру (ЛЭП, автомобильные дороги). Для каждого из месторождений набор компенсирующих природоохранных мероприятий интегрировался в соответ- ствующий комплексный экологический проект. Таким способом разработанный модельный полигон позволяет учесть специфи- ку моделируемого объекта и создает информационную базу для изучения свойств равновесия по Штакельбергу. Методика такого исследования основана на анализе чувствительности решений соответствующей двухуровневой задачи булевого программирования к изменению основных параметров модели. Этот вопрос принципиально важен, прежде всего, потому, что для многих парамет- ров модели известны лишь рабочие диапазоны значений. Так, в процессе фор- мирования программы освоения недр эксперт располагает лишь данными про- ектов, а значительная часть параметров, таких как дисконты участников парт- нерства, экологические затраты и потери, могут быть оценены им лишь при- ближенно. При некоторых предположениях относительно возможностей государства ис- ходная двухуровневая постановка задачи планирования может быть существен- но упрощена и сведена к одноуровневой задаче математического программиро- вания. Это возможно, если государство полностью информировано о техноло- гических проектах освоения месторождений и бюджетных ограничениях инве- стора. Тогда исходная двухуровневая модель трансформируется в задачу булева программирования с переменными 𝑧𝑖𝜏 , 𝑢𝑘𝜏 , 𝑦𝑘𝜏 , 𝑥𝑗𝜏 ∈ {0,1}, целевой функцией государства (1) и ограничениями (2)–(5), (8)–(19). Такая одноуровневая поста- новка в большей степени описывает экономику с доминирующей ролью госу- дарства в минерально-сырьевом секторе, но оказывается удобной для понима- ния того, что дает переход от одноуровневой к двухуровневой постановке. На последующих рисунках приведены результаты расчетов, в которых анализи- ровалась чувствительность решения задачи к изменению ключевых параметров модели – дисконтов инвестора и государства. В расчетах сравнивались четыре модели – двухуровневая и одноуровневая с бюджетными ограничениями в «жесткой» ((2), (8)) и «мягкой» ((2а), (8а)) форме. Во всех постановках для малых дисконтов партнеров государство реализует полную инфраструктурную программу, открывая инвестору возможность осво- ения всего комплекса месторождений (рис. 2). При росте дисконтов государ- ство, начиная с некоторого уровня, сворачивает инфраструктурную программу со скоростью, зависящей от постановки. Наибольшую устойчивость объему инфраструктурного и производственного строительства обеспечивает одноуровневая постановка с мягкими бюджетными ограничениями (см. рис. 3). В общем случае по числу реализованных проектов освоения месторождений двухуровневые модели уступают одноуровневым, а мягкие бюджетные ограничения создают дополнительные возможности расши- рения фронта работ. Локальный поиск для планирования государственно-частного партнерства 457 Рис. 2. Число реализованных инфраструктурных проектов Рис. 3. Число реализованных производственных проектов А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 458 Различен также и характер помощи государства инвестору в реализации эколо- гических проектов (см. рис. 4). В одноуровневых моделях государство, распола- гая полной информацией об инвесторе, минимизирует свои затраты на приро- доохранные мероприятия для инвестора с малым дисконтом. При росте дискон- та инвестора государство начинает с некоторого уровня наращивать помощь в реализации экологических проектов, доводя его до 80-процентного уровня при- родоохранных затрат. В двухуровневой модели государство начинает помогать рационально действу- ющему инвестору уже с минимального уровня дисконта инвестора. Оно после- довательно наращивает интенсивность помощи до уровня 100 % для макси- мального дисконта инвестора и минимального у государства. Рис. 4. Доля государства в экологических затратах Такая сложная зависимость от дисконтов партнеров объемов помощи инвестору в инфраструктурном и природоохранном строительстве в значительной степени объясняет характер поверхностей, представленных на рисунке 5. Мы видим, что в некотором диапазоне дисконта инвестора целевая функция государства опре- деляется только его дисконтом. Это вполне соответствует виду целевой функ- ции государства, напрямую не зависящей от дисконта инвестора. По мере даль- нейшего роста дисконта инвестора, сокращается инфраструктурная, но растет экологическая помощь государства. Сложным образом взаимодействуя, эти факторы в различных постановках порождают поверхности для значения це- левой функции государства разного уровня регулярности. Как это следует из рисунка 5, одноуровневая постановка обеспечивает наибольшую устойчивость уровня результативности программы освоения к по- Локальный поиск для планирования государственно-частного партнерства 459 ведению «рентоориентированного» инвестора. Здесь и наибольшие значения функционала государства, и минимальный уровень его реакции на рост дис- конта инвестора в области его высоких значений, особенно в постановке с мяг- кими бюджетными ограничениями. Соответствующие модели Штакельберга поверхности на рисунке 5 имеют из- ломы и впадины. Это говорит о том, что двухуровневая постановка даже в вари- анте с мягкими бюджетными ограничениями порождает решение, для которого в некоторых случаях нарушается устойчивость функционала государства к из- менению дисконтов участников партнерства2. В определенной степени это ком- пенсируется функционалом инвестора, для которого не так важна устойчивость, а более приоритетным является Рис. 5. Целевая функция государства. абсолютное значение целевой функции. Здесь для инвестора модель Штакель- берга обеспечивает существенный выигрыш по сравнению с одноуровневыми постановками даже для больших дисконтов (см. рис. 6). 2 А значит, и к изменению внешних условий реализации проектов освоения месторождений. Учи- тывая переходной характер экономики России и нестационарный характер сырьевых рынков, это приводит к тому, что даже малые изменения внешних условий приводят к существенному падению функционала государства и снижению уровня эффективности стратегии освоения минерально- сырьевой базы, построенной на основе решения задачи. А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 460 Рис. 6. Целевая функция инвестора. 4. Обсуждение полученных результатов Результаты численных экспериментов иллюстрируют возможности предлагае- мого подхода к формированию механизма взаимодействия государства и инве- стора на принципах партнерства. Предлагаемый инструментарий стратегиче- ского планирования предназначен для малоосвоенной сырьевой территории и строит программу освоения минерально-сырьевой базы на основе арсенала ры- чагов партнерства, включающего не только помощь инвестору в создании необ- ходимой инфраструктуры, но и реализацию части необходимых природоохран- ных мероприятий. Мы видим, что в рамках построенных моделей формирова- ния механизма взаимодействия в некоторых случаях государство берет на себя не только инфраструктуру, но и фиксированный перечень экологических про- ектов. Такое поведение рационально, но требует выверенного подхода к опре- делению конкретного размера помощи. Результаты моделирования позволяют оценить воздействие дисконтов партне- ров на эффективность программ освоения недр, генерируемых в разных моде- лях. Хотя механизм взаимодействия государства и частного инвестора во всех рассмотренных моделях основан на помощи государства в инфраструктурном и природоохранном строительстве, исходные предположения об уровне инфор- мированности и возможностях государства в существенной степени различны. При прочих равных условиях для государства предпочтительна одноуровневая модель. В ее рамках государство может эффективно работать с инвестором, Локальный поиск для планирования государственно-частного партнерства 461 дисконт которого укладывается в традиционный диапазон, характерный для минерально-сырьевого комплекса, не теряя значения своей целевой функции – ренты, полученной в виде налогов. Более адекватной здесь оказывается и реак- ция на рост дисконтов – сокращение объема инфраструктурного строительства и помощи в реализации экологических проектов и, как следствие, минимально возможный уровень рентабельности инвестора. Двухуровневая постановка модели Штакельберга, напротив, дает определенные преимущества инвестору, обеспечивая ему, как правило, больший, чем в одно- уровневой постановке, функционал. Расчеты показывают, что значение его це- левой функции здесь мало зависит от дисконта государства и определяется в основном дисконтом инвестора. Какая из моделей – двухуровневая или одноуровневая – обеспечивает наилуч- ший компромисс долгосрочных интересов государства и частного инвестора и в большей степени соответствует сегодняшнему положению дел в российском минерально-сырьевом комплексе? Предположение о полной информированности государства о технологиях и возможностях инвестора, лежащее в основе одноуровневой модели, представля- ется не вполне корректным в условиях современной России. Двухуровневая постановка модели более адекватно отражает сегодняшние реалии и особенно- сти процесса нахождения компромисса интересов государства и инвестора. Практические примеры реализации проектов ГЧП в России подтверждают, что такая постановка содержательно близка к реальной процедуре разработки плана освоения минерально-сырьевой базы ресурсного региона. Это говорит о том, что для повышения общественной эффективности сего- дняшнего механизма сотрудничества с рентоориентированным инвестором и справедливого раздела природно-ресурсной ренты необходимо всемерно сни- жать дисконты. Высокие ставки дисконта в современной России — это не спе- цифическая для минерально-сырьевого сектора проблема, они в значительной степени определяются общими макроэкономическими условиями и качеством управления в стране. Поэтому меры, повышающие эффективность производ- ственных процессов на микроэкономическом уровне, могут оказаться малопо- лезными, если эти условия не будут меняться к лучшему. Таким образом, эффективность сотрудничества в процессе разработки комплек- са месторождений на малоосвоенных территориях зависит не только от общих макроэкономических условий, но и от обстоятельств, непосредственно с содер- жанием сотрудничества не связанных, таких, как качество государственного управления в природоохранной сфере. И здесь необходимы шаги, позволяющие существенно улучшить работу государственных институтов и на этой основе снизить дисконты как государства, так и частного инвестора. Сравнительный анализ свойств решений, полученных в разных моделях, поз- воляет сделать ряд практических выводов. Решение одноуровневой модели ин- формированного государства определяет верхнюю грань для значения функци- онала двухуровневой модели, содержательно максимально близко описываю- А. А. Зырянов, Ю. А. Кочетов, С. М. Лавлинский 462 щей сегодняшний стиль управления в минерально-сырьевом комплексе3. Это говорит о том, что государство в процессе принятия решения должно стремить- ся получить более детальное представление об объектах природопользования и проектах освоения. Только так можно эффективно строить отношения с инве- стором на позициях собственника ресурсов, получающего возможно большую часть природно-ресурсной ренты, как стоимости, созданной природой. Для этого государству необходимо провести инвентаризацию основных место- рождений с учетом сегодняшних условий и организовать постоянный монито- ринг их рентной оценки. Это позволит создать не только необходимую для внешнего инвестора инфраструктуру процесса принятия решения, но и базу знаний для государства, стремящегося наиболее рационально распорядиться имеющимися природными ресурсами. На такой основе уже можно подойти и к решению центральной проблемы сы- рьевых регионов – разработке комплексного сценария освоения минерально- сырьевой базы, включающего планы развития производственной инфраструк- туры и формирование пакетов инвестиционных предложений, реализующих различные этапы развития территории. И здесь необходимо соблюсти интере- сы не только частного бизнеса, но и общества в целом. Поиск вариантов согла- сования этих интересов – непростая задача, на решение которой и нацелен ин- струментарий, предложенный в настоящей работе. Список литературы 1. Lavlinskii, S.M., Panin, A.A., Plyasunov, A.V.: Comparison of models of plan- ning public-private partnership. Journal of Applied and Industrial Mathematics. 10(3), 356–369 (2016) 2. Лавлинский С.М., Панин А.А., Плясунов А.В.: Двухуровневая модель пла- нирования государственно-частного партнерства. Автоматика и телемехани- ка. 11, 89–103 (2015) 3. Лавлинский С.М.: Государственно-частное партнерство на сырьевой терри- тории – экологические проблемы, модели и перспективы. Проблемы прогно- зирования. 1, 99–111 (2010) 4. Ерешко Ф.И.: Моделирование рефлексивных стратегий в управляемых си- стемах. М., ВЦ РАН. (2001) 5. Iellamo, S., Alekseeva, E., Chen, L., Coupechoux, M., Kochetov, Yu.: Competi- tive location in cognitive radio networks. 4OR. 13(1), 81–110 (2015) 3 Анализ документации ряда проектов ГЧП в минерально-сырьевом секторе показывает, что основ- ной акцент в экспертизе делается на доказательство рентабельности проекта для инвестора. Вопро- сы о том, какая часть ренты будет получена государством, как правило, даже не ставится. Это вполне соответствует исходным посылам модели Штакельберга, в которой государство решает задачу верхнего уровня, ничего не зная о тонкостях технологии и рыночной конъюнктуры, а ренто- ориентированный инвестор стремится получить максимальную рентабельность в сотрудничестве с государством. При этом интересы общества, как правило, отступают на второй план. Локальный поиск для планирования государственно-частного партнерства 463 6. Davydov, I., Kochetov, Yu., Plyasunov, A.: On the complexity of the (r|p)- centroid problem in the plane. TOP. 22(2), 614–623 (2014) 7. Panin, A.A, Plyasunov, A.V.: On complexity of the bilevel location and pricing problems. Journal of Applied and Industrial Mathematics. 8(4), 574–581 (2014) 8. Plyasunov, A.V.; Panin, A.A.: The pricing problem. II: Computational complexi- ty. Journal of Applied and Industrial Mathematics 7(3), 420–430 (2013) 9. Alekseeva, E., Kochetov, Yu., Plyasunov, A.: An exact method for the discrete (r|p)centroid problem. Journal of Global Optimization 63(3), 445–460 (2015) 10. Alekseeva, E., Kochetov, Yu.: Matheuristics and exact methods for the discrete (r|p)centroid problem In: El-G. Talbi (Ed.) Metaheuristics for Bi-level Optimiza- tion (Studies in Computational Intelligence). vol. 482, pp. 189–219. Springer (2013) 11. Davydov, I.A., Kochetov, Y.A., Carrizosa, E.: A local search heuristic for the (r|p)centroid problem in the plane. Computers & Operations Research 52, 334– 340 (2014) 12. Beresnev, V.L., Melnikov, A.A.: A capacitated competitive facility location prob- lem. Journal of Applied and Industrial Mathematics 10(1), 61–68 (2016) 13. Diakova, Z., Kochetov, Yu.: A double VNS heuristic for the facility location and pricing problem. Electronic Notes in Discrete Mathematics 39, 29–34 (2012) 14. Plyasunov, A.V.; Panin, A.A.: The pricing problem. I: Exact and approximate algorithms. Journal of Applied and Industrial Mathematics 7(2), 241–251 (2013)