Автоматика и телемеханика, № 2, 2019

Управление в социально-экономических

системах

(Институт математики им. С.Л. Соболева СО РАН,

Новосибирский государственный университет,

Забайкальский государственный университет),

А.А. ПАНИН, канд. физ.-мат. наук (aapanin1988@gmail.com),

А.В. ПЛЯСУНОВ, канд. физ.-мат. наук (apljas@math.nsc.ru)

(Институт математики им. С.Л. Соболева СО РАН,

Новосибирский государственный университет)

МОДЕЛИ ШТАКЕЛЬБЕРГА В ТЕРРИТОРИАЛЬНОМ

ПЛАНИРОВАНИИ¹

Предложена новая модель формирования механизма государственно-

частного партнерства, формулируемая в виде задачи двухуровневого бу-

∑P

лева программирования. Показано, что данная задача является

-труд-

ной как в оптимистической, так и в пессимистической форме. Разработан

стохастический итерационный алгоритм решения данной задачи. Прове-

дены вычислительные эксперименты на реальной информации, демон-

стрирующие возможности предлагаемого подхода.

Ключевые слова: стохастический локальный поиск, игра Штакельбер-

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

лительная сложность.

DOI: 10.1134/S0005231019020077

1. Введение

Поиск эффективных механизмов государственно-частного партнерства

(ГЧП) — актуальная проблема для минерально-сырьевого комплекса России.

За последние годы в этой сфере был запущен ряд проектов Инвестиционного

фонда РФ, в которых государство на малоосвоенной территории оказывало

помощь инвестору в создании инфраструктуры и реализации природоохран-

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

прежде всего, потому, что все попытки Правительства РФ стимулировать ис-

пользование партнерских отношений с частным бизнесом не сопровождались

принятием экономически выверенных управленческих решений [1, 2].

Параллельно с запуском механизмов ГЧП государство создало законода-

тельную основу для серьезных налоговых льгот крупным сырьевым проек-

там. Это открывает возможность совместного применения механизма ГЧП и

¹ Работа выполнена при финансовой поддержке Комплексной программы фундамен-

тальных научных исследований СО РАН № II.1.

111

налоговых льгот. Практических примеров такого рода крупных проектов в

России пока еще нет, но предшествующий негативный опыт делает актуаль-

ной задачу изучения свойств совокупного механизма взаимодействия, воз-

можность применения которого открывают законы о ГЧП и льготах.

Эта проблема находится в центре внимания настоящей работы. Основная

цель — разработка экономико-математических моделей формирования эф-

фективного механизма партнерства, основанного на теоретико-игровой мо-

дели Штакельберга и использующего полный спектр возможностей, предо-

ставляемых законодательством. Такой подход продиктован особенностями

иерархии взаимодействия государства и частного инвестора в минерально-

сырьевом секторе, позволяет найти компромисс интересов и обеспечивает

эффективность в долгосрочном плане не только частным инвесторам, но и

государству.

Настоящая работа — расширенная версия [3], продолжающая исследова-

ния авторов, начатые в [4, 5], где рассматривалась модель ГЧП, в которой по-

мощь государства ограничивалась инвестициями на развитие инфраструкту-

ры и природоохранные мероприятия. Здесь формулируется обобщенный ва-

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

Модели такого вида востребованы практикой территориального планирова-

ния и могут быть использованы для решения стратегических задач управле-

ния ресурсным регионом.

Во втором разделе приводится постановка модели, в третьем разделе опи-

сывается сложностной статус двухуровневой постановки задачи планирова-

ния и излагается приближенный алгоритм ее решения. Четвертый раздел

посвящен численным экспериментам с моделью, а в пятом обсуждаются ре-

зультаты и дальнейшие направления исследований.

2. Математическая модель

Формальное описание модели формирования механизма ГЧП может быть

представлено следующим образом. Введем обозначения:

I — набор инвестиционных проектов;

J — набор инфраструктурных проектов;

K — набор экологических проектов;

M — набор уровней налоговых льгот;

T = {1,...,T} — плановый период (горизонт планирования — T).

Инвестиционный проект i в год t:

CFP^ti — поток наличности (кэшфло²); EPP^ti — экологический ущерб от

реализации проекта; DBP^ti — бюджетные доходы государства от реализации

проекта; ZP P^ti — доходы населения (зарплата); T P^tim — налоговая льгота

уровня m по проекту.

Инфраструктурный проект j в год t:

² Равен разности полученных доходов и расходов всех видов.

112

ZI^tj — затраты на реализацию проекта; EPI^tj — экологический ущерб от

реализации проекта; V DI^tj — доходы государства от развития экономики тер-

ритории при реализации проекта; ZP I^tj - доходы населения (зарплата).

Экологический проект k в году t:

ZE^tk — затраты на реализацию проекта; EDE^tk — экологический доход

при реализации проекта; ZP E^tk — доходы населения (зарплата). Матрицы

μ и ν задают взаимосвязь проектов, где μ_ij — индикатор связности инфра-

структурных и производственных проектов, i ∈ I, j ∈ J, а ν_ij — индикатор

связности экологических и производственных проектов, i ∈ I, k ∈ K:

⎧

⎨ 1, если для реализации производственного проекта i

μ_ij =

требуется реализация инфраструктурного проекта j,

^⎩ 0 в противном случае;

⎧

⎨ 1, если для реализации производственного проекта i

ν_ik =

требуется реализация экологического проекта k,

^⎩ 0 в противном случае.

Дисконты государства и инвестора: DG — дисконт государства; DI — дисконт

инвестора. Бюджетные ограничения: b^Gt — бюджет государства в год t; b^Ot —

бюджет инвестора в год t.

Для описания выбора государства будем использовать следующие пере-

менные:

⎧

⎨ 1, если государство запускает инфраструктурный проект

x_j =

с номером j,

^⎩ 0 в противном случае;

⎧

⎨ 1, если государство готово реализовать k-й экологический проект

(государство включило проект в бюджетные расходы),

yk =_⎩

в противном случае;

⎧

⎨ 1, если государство готово предоставить инвестору налоговую

льготу уровня m для i-го производственного проекта,

ϕim =_⎩

в противном случае.

Для описания выбора инвестора будем использовать следующие переменные:

⎧

⎨ 1, если государство запускает экологический проект с номером k

y_k =

по согласованию с инвестором,

^⎩ 0

в противном случае;

^{ 1, если инвестор запускает i-й производственный проект,

z_i =

в противном случае;

^{ 1, если инвестор запускает k-й экологический проект,

u_k =

в противном случае;

113

⎧

⎨ 1, если государство предоставляет инвестору налоговую

льготу уровня m для i-го производственного проекта,

ϕim =

^⎩ 0 в противном случае.

Задача государства PS:

∑

(∑(

)

∑

DBP^ti + ZPP^ti - EPP^ti

z_i -

TP^timϕ_im +

t∈T i∈I

i∈I m∈M

∑(

)

∑

(

)

V DI^tj + ZPI^tj - EPI^tj - ZI^tj

x_j +

EDE^tk + ZPE^tk - ZE^tk

y_k +

j∈J

k∈K

)

∑

(

)

(1)

EDE^tk + ZPE^tk

u_k

/(1 + DG)^t → max

x,y,ϕ,ϕ,y,z,u

k∈K

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

∑

(2)

ZI^tjx_j +

ZE^tk y_k ≤b^Gt

;

t∈T;

j∈J

k∈K

∑

(3)

ϕim

≤ 1; i ∈ I;

m∈M

(4)

(y, z, u, ϕ) ∈ F^∗O

(x, y,

ϕ);

(5)

ϕim, xj , yk,∈ {0,1}; i ∈ I, j ∈ J, k ∈ K, m ∈ M.

Целевая функция государства (1) представляет собой чистый дисконтиро-

ванный доход пары государство — население и состоит из трех частей. Первая

часть складывается из доходов государства и населения от производственных

проектов с учетом экологических потерь, связанных с их реализацией, и на-

логовых льгот всех уровней. Остальные части доходов и расходов связаны с

реализацией инфраструктурных и экологических проектов. Ограничения (2)

гарантируют, что затраты государства на инфраструктуру и экологию не

выйдут за рамки бюджета. Ограничения (3) запрещают государству предо-

ставлять сразу несколько налоговых льгот одному проекту. В ограничении (4)

через F^∗O(x, y,

ϕ) обозначено множество всех оптимальных решений парамет-

рической задачи инвестора. Таким образом, данное ограничение гарантирует,

что государство учитывает только оптимальную реакцию инвестора.

Задача инвестора PI(x, y,

ϕ):

)

∑

(∑

∑

(6)

(CF P^ti z_i +

TP^timϕ_im)-

ZE^tku_k

/(1 + DI)^t → max

z,u,y,ϕ

t∈T i∈I

m∈M

k∈K

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

(

)

∑

(7)

ZE^tku_k -

CFP^tiz_i -

TP^t

≤b^Ot

;

t∈T;

ϕim

k∈K

i∈I

m∈M

114

⎛

∑

∑(

)

∑(

)

⎝

ZPP^ti -EPP^ti

z_i +

ZPI^tj -EPI^tj

x_j +

t∈T i∈I

j∈J

)

∑

(

)

(8)

EDE^tk + ZPE^tk

(y_k + u_k)

/(1 + DI)^t

≥ 0;

k∈K

)

∑

(∑

∑

(9)

CFP^tiz_i +

TP^timϕ_im -

ZE^t

u_k

/(1 + DI)^t

≥ 0;

t∈T i∈I

m∈M

k∈K

∑

(10)

ϕim

≤ 1; i ∈ I;

m∈M

(11)

x_j ≥ μ_ij z_i

;

i∈I, j ∈J;

(12)

y_k + u_k

≤ 1; k ∈ K;

(13)

y_k + u_k ≥ ν_ik z_i

;

i∈I, k∈K;

∑

(14)

y_k + u_k ≤ ν_ik z_i

;

k∈K;

i∈I

(15)

y_k ≤ y_k

;

k∈K;

(16)

ϕim ≤ zi

;

i∈I;

(17)

ϕim ≤

ϕim

;

i∈I; m∈M;

(18)

y_k,z_i,u_k,ϕ_im

∈ {0, 1}; i ∈ I, k ∈ K, m ∈ M.

Доход частного инвестора определяется целевой функцией (6). Из (7) сле-

дует, что затраты инвестора в каждый год не превышают бюджет с учетом

доходов от реализации инвестиционных проектов и налоговых льгот. Выпол-

нение ограничения (8) говорит о достижении компромисса между интересами

населения, государства и частного инвестора. Получение нормальной прибы-

ли инвестором обеспечивает ограничение (9). Из ограничения (10) следует,

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

лее одной налоговой льготы. Ограничения (11)-(13) обеспечивают техноло-

гическую связность проектов и невозможность реализации одних и тех же

экологических проектов одновременно инвестором и государством. Ограни-

чение (14) блокирует запуск автономного экологического проекта без запус-

ка какого-либо из связанных с ним производственных проектов. Ограниче-

ние (15) гарантирует реализацию государством только включенных в бюджет

экологических проектов. Выполнение ограничений (16) означает, что государ-

ство предоставляет инвестору налоговую льготу производственному проекту

только при условии, что инвестор запускает данный проект. Ограничение (17)

гарантирует, что государство предоставляет инвестору налоговую льготу, ес-

ли та была запланирована.

Под допустимым решением задачи (1)-(5) понимается любой вектор

(x, y, ϕ, y, z, u, ϕ), который удовлетворяет условиям (2)-(5). Традиционно в

задачах двухуровневого программирования используются два определения

понятия “наилучшего” решения: оптимальные (оптимистические) решения и

наилучшие гарантированные (пессимистические) решения. Иногда также го-

ворят, соответственно, кооперативные и некооперативные решения, особенно

115

в ситуациях, когда необходимо подчеркнуть игровую составляющую моде-

лируемой ситуации, т.е. кооперируются уровни или нет в процессе принятия

решения. Необходимость в фиксации такого рода отличий не возникает, если,

например, задача нижнего уровня имеет единственное оптимальное решение.

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

собой. Как видно из постановки (1)-(5), в работе рассматривается ситуация,

когда нижний уровень кооперируется с верхним уровнем. В данной ситуа-

ции это естественное соглашение, так как только государство берет на себя

выполнение затратных инфраструктурных проектов, требующих большого

времени для окупаемости. Поэтому для инвестора нет причин конкуриро-

вать с государством или стремиться нанести ему какой-либо ущерб. Таким

образом, постановка (1)-(5) имеет дело с оптимистическими допустимыми

решениями и, как следствие, с оптимистическими оптимальными решения-

ми. Далее будем использовать следующее обозначение F (x, y,

ϕ,y,z,u,ϕ) для

целевой функции государства. Если в модели (1)-(5) заменить множество

F^∗O(x, y,

ϕ) на подмножество F^∗P (x, y,ϕ), которое состоит из оптимальных ре-

шений (y^′, z^′, u^′, ϕ^′) задачи инвестора PI(x, y,

ϕ), удовлетворяющих свойству

(y^′, z^′, u^′, ϕ^′) ∈ F^∗P (x, y,

ϕ) тогда и только тогда, когда F(x, y,

ϕ,y^′,z^′,u^′,ϕ^′) =

= min(y,z,u,ϕ)∈F∗

(x,y,

ϕ) F (x, y,ϕ,y,z,u,ϕ), то получим двухуровневую поста-

новку в пессимистической форме. В дальнейшем предполагается, что все ис-

ходные данные рациональны.

3. Вычислительная сложность и алгоритм решения

Введем далее необходимые определения и обозначения из теории слож-

ности. Свяжем с произвольной оптимизационной задачей L задачу распо-

знавания D(L), в которой входом являются вход задачи L и произвольное

рациональное число θ. Если задача L является задачей на максимум, то в за-

даче D(L) надо установить существование допустимого решения со значением

целевой функции большим или равным θ. Тогда D(L) — стандартная задача

распознавания, соответствующая оптимизационной задаче L. Задача распо-

знавания L принадлежит классу ΣP2 , если существует недетерминированная

оракульная машина Тьюринга, которая распознает за полиномиальное вре-

мя задачу L, используя в качестве оракула некоторый язык из класса NP .

Класс ΣP2 относится ко второму уровню полиномиальной иерархии [6].

Оптимизационная задача принадлежит классу NP O, если его стандартная

задача распознавания принадлежит классу NP [6]. По аналогии, класс ΣP2 O

содержит оптимизационные задачи, у которых соответствующая стандартная

задача распознавания принадлежит классу ΣP2 [7]. Класс NP O относится к

первому уровню аппроксимационной иерархии, а класс ΣP2 O, соответственно,

ко второму уровню данной иерархии.

Теорема 1. Задача государства является NPO-трудной, а задача ин-

вестора является NP O-полной относительно AP -сводимости³.

Доказательства теоремы 1 и всех последующих результатов приведены в

Приложении.

³ Определение AP-сводимости можно найти в [8].

116

В [3, 6] было показано, что задача P S принадлежит классу ΣP2 O. Таким

образом, получена верхняя оценка на положение задачи государства в ап-

проксимационной иерархии. Теперь покажем, что задача государства явля-

ется ΣP2 -трудной. Это свойство следует из сведения ΣP2 -полной задачи Subset-

Sum-Interval к исследуемой задаче [3, 9].

Теорема 2. Задача государства является ΣP2-трудной.

Следствие 1. Стандартная задача распознавания для задачи государ-

ства является ΣP2 -полной задачей.

Следствие 2. Задача государства без льгот и инфраструктурных про-

ектов сохраняет ΣP2 -трудность даже в случае трехлетнего горизонта пла-

нирования, а соответствующая стандартная задача распознавания сохра-

няет ΣP2 -полноту.

Следствие 3. Утверждения теоремы 2 и следствий 1 и 2 выполняют-

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

Описанное выше отношение исследуемой двухуровневой задачи к ап-

проксимационной и полиномиальной иерархиям свидетельствует о том, что

она является значительно более сложной, чем широко известный класс

NP-полных задач. Таким образом, для задачи государственно-частного

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

мов на основе эвристических подходов. Для решения задачи планирования

государственно-частного партнерства применяется стохастический прибли-

женный гибридный алгоритм, использующий оригинальную процедуру по-

строения начального решения двухуровневой задачи, стохастический локаль-

ный подъем и пакет CPLEX⁴. Пакет CPLEX используется для решения одно-

уровневой постановки, когда за инвестора принимает решение государство,

а также для решения задачи инвестора. Локальным подъемом подбирается

хорошее приближенное решение для государства.

При описании алгоритма решения задачи государства будем использовать

понятие полудопустимых решений. Вектор (x, y, ϕ, y, z, u, ϕ) называется полу-

допустимым решением задачи (1)-(5), если он удовлетворяет ограничениям

(2), (3), (5), (7)-(18) [10].

Параметры алгоритма:

mIter — максимальное число итераций алгоритма поиска начального ре-

шения (шаг 2),

cfBound — коэффициент ослабления ограничения на значение целевой

функции (1) при решении вспомогательной задачи на шаге 2.3.

Алгоритм 1 (Стохастический приближенный гибридный алгоритм).

Шаг 1. Вычислить верхнюю границу Bound, решив релаксированную задачу

государства с ограничениями нижнего уровня (т.е. задачу с целевой функ-

цией (1) и ограничениями (2), (3), (5), (7)-(18)).

Шаг 2. Найти вектор (x⁰,y⁰,ϕ⁰), который является частью некоторого по-

лудопустимого решения (который далее будет использоваться как начальное

решение алгоритма локального поиска):

⁴ Данный алгоритм является модификацией метода, описанного в [4, 5].

117

Шаг 2.1. iter := 1.

Шаг 2.2. Если iter ≤ mIter, тогда решить задачу инвестора с переменными

и ограничениями государства (т.е. задачу с целевой функцией (6) и огра-

ничениями (2), (3), (5), (7)-(18)), а также с дополнительным ограничением,

что целевая функция государства (1) не меньше величины (Bound - 1)/iter.

Иначе перейдем на шаг 3.

Шаг 2.3. Если задача на предыдущем шаге разрешима, а (x,y,ϕ,y,z,u,ϕ) —

оптимальное решение, тогда вычислим значение F целевой функции (1), ре-

шив задачу P I(x, y, ϕ). Если F < (Bound - 1)/(iter ∗ cfBound) или задача на

предыдущем шаге была неразрешима, то положим iter := iter + 1 и перейдем

на шаг 2.2, иначе положим x⁰ := x, y⁰ := y, ϕ⁰ := ϕ, F⁰ := F и перейдем на

шаг 3.

Шаг 3. Если на шаге 2 не удалось найти вектор (x⁰,y⁰,ϕ⁰), то в качестве него

будем использовать нулевое решение, т.е. положим x⁰ := 0, y⁰ := 0, ϕ⁰ := 0

и вычислим значение F⁰ целевой функции (1), решив задачу P I(x⁰, y⁰, ϕ⁰).

Далее применим алгоритм локального поиска:

Шаг 3.1. Положить в качестве стартового решения (x,y,ϕ) := (x⁰,y⁰,ϕ⁰), а

рекорд F := F⁰.

Шаг 3.2. Найти наилучшего соседа (x^∗,y^∗,ϕ^∗) в окрестности решения

(x, y, ϕ).

Шаг 3.3. Вычислим значение F^∗ целевой функции (1), решив задачу

PI(x,y,ϕ). Если значение целевой функции F^∗ > F, тогда положим x := x^∗,

y := y^∗, ϕ := ϕ^∗, F := F^∗ и перейдем на шаг 3.2, иначе стоп.

В качестве окрестности вектора (x, y, ϕ) в алгоритме локального поиска

используется рандомизированная окрестность, которая имеет ровно одного

соседа (x^′, y^′, ϕ^′), полученного следующим образом. Каждая компонента век-

тора x^′ является случайной величиной, которая с вероятностью 1 - 1/|J| рав-

на соответствующей компоненте вектора x, а с вероятностью 1/|J| — вектора

1 - x. Аналогично и для вектора y^′ , только вероятности соответственно рав-

ны 1 - 1/|K| и 1/|K| . Для льгот ϕ^′ вероятности соответственно следующие:

1 - 1/(|I||M|) и 1/(|I||M|).

В процессе работы алгоритма локального поиска с рандомизированной

окрестностью в качестве критерия остановки бралось ограничение на число

итераций. Время работы локального спуска ограничивалось 5000 итерация-

ми, а параметры mIter и cfBound равнялись 30 и 3 соответственно. Значения

этих параметров, как и выбор окрестности в алгоритме локального поиска,

подобраны эмпирически на основе предыдущих работ [4, 5].

4. Численный эксперимент

Для отработки методики использования описанного инструментария в ра-

боте строится специальный модельный полигон, прообразом которого являет-

ся набор из 50 месторождений полиметаллических руд Забайкальского края.

Для него строится набор из 10 инфраструктурных проектов, часть из кото-

рых уже реализуется (железная дорога, ЛЭП), а другие восполняют отсут-

ствующую на сегодня, но необходимую с учетом проектов освоения место-

118

рождений инфраструктуру (ЛЭП, автомобильные дороги). Для каждого из

месторождений предусмотрено пять уровней льгот.

Большая часть необходимых данных для модели может быть получена из

ТЭО (технико-экономическое обоснование) проектов. Данные, выходящие за

рамки обычного перечня информации, используемой в хозяйственной практи-

ке (стоимостные оценки экологического ущерба, экологического дохода, пото-

ка наличности, проектных и внепроектных доходов бюджета), генерируются

в специальных моделях прогнозирования, включенных в состав модельного

полигона [2, 4, 5].

Таким способом разработанный модельный полигон позволяет учесть спе-

цифику моделируемого объекта и создает информационную базу для изу-

чения свойств равновесия по Штакельбергу. Методика такого исследования

основана на анализе чувствительности решений соответствующей двухуров-

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

модели.

На рисунке приведены некоторые результаты расчетов, в которых анали-

зировалась чувствительность решения задачи к изменению ключевых пара-

метров модели — дисконтов инвестора и государства. Здесь представлены

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

налоговых льгот (а) и в полной постановке модели, использующей рычаг на-

логовых преференций (в), для которой число и уровень льгот изображены

на (б ) и (г) соответственно. Расчеты показывают, что государство сложным

образом использует все три рычага помощи инвестору на всем диапазоне дис-

контов партнеров. Использование механизма льгот расширяет программу по-

мощи в природоохранном строительстве, при этом число льгот и их уровень

растут с увеличением дисконта инвестора. Это приводит к тому, что ввод ме-

ханизма льготирования позволяет убрать впадину на поверхности модели (а),

обеспечив большую устойчивость результатов партнерства в модели (в) при

росте дисконта инвестора. Расчеты проводились на персональной ЭВМ с про-

цессором i7 3612QM и оперативной памятью 4 гигабайта. Для каждой модели

и каждой пары значений дисконтов для построения приближенного решения

требовалось в среднем не более 30 минут.

5. Обсуждение полученных результатов

Государство, создав законодательную основу серьезных налоговых префе-

ренций для крупных сырьевых проектов, открывает возможность совмест-

ного применения механизма ГЧП и налоговых льгот. Результаты модели-

рования позволяют говорить о практической значимости описанных выше

моделей и построить иерархию факторов, влияющих на эффективность та-

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

комплекса месторождений на малоосвоенных территориях.

На такой модельной основе уже можно подойти и к решению центральной

проблемы сырьевых регионов — разработке комплексного сценария освоения

минерально-сырьевой базы, включающего планы развития производствен-

ной инфраструктуры и формирование пакетов инвестиционных предложе-

ний, содержащих правила предоставления налоговых льгот. И здесь необхо-

120

димо соблюсти интересы не только частного бизнеса, но и общества в целом.

Поиск вариантов согласования этих интересов — непростая задача, на реше-

ние которой и нацелен инструментарий, предложенный в настоящей работе.

Дальнейшее направление исследований — переход к стохастической по-

становке задачи на основе подхода, предложенного в [11-13]. Сегодняшняя

детерминированная форма оперирует прогнозным горизонтом 20-30 лет и ис-

пользует методологию сценарного прогнозирования для внешних параметров

модели — таких, например, как цены сырьевых рынков. Технически это за-

ставляет эксперта строить достаточно представительное множество сценари-

ев внешних условий, решать большое количество трудоемких задач двухуров-

невого программирования и уже на этой основе формулировать результаты.

Практический опыт показывает чрезмерную трудоемкость такой процедуры

для эксперта. И здесь перспективным представляются методы [11-13], позво-

ляющие эффективно учесть исходную стохастическую природу проблемной

области и перенести центр тяжести анализа непосредственно в модель. Дру-

гое интересное направление развивается в [14].

ПРИЛОЖЕНИЕ

Доказательство теоремы 1. Данное утверждение следует из соот-

ветствующего утверждения для задач государственно-частного партнерства

без льгот [4, 5]. Теорема 1 доказана.

Доказательство теоремы 2. В задаче Subset-Sum-Interval заданы

положительные целые числа q₁, . . . , q_l, R и r, где r не превосходит l. Тре-

буется определить, существует ли такое S, R ≤ S < R + 2^r, что для любого_∑

I ⊆ {1,...,l} выполнено_i∈I q_i = S. Сведем данную задачу к задаче государ-

ства. Для этого построим вход задачи (1)-(18), в котором отсутствуют льго-

ты, т.е. величины T P^tim равны нулю. Таким образом, без ограничения общно-

сти можно считать, что в оптимальном решении задачи ϕ_im = 0, i ∈ I, m ∈ M,

и, следовательно, ϕ_im = 0, i ∈ I, m ∈ M. Как результат, ограничения (3), (10)

и (16), (17) становятся тривиальными.

Пусть имеется l + 2 производственных проектов и r + 1 экологических

проектов. Предположим, что никакие инфраструктурные проекты не тре-

буются для реализации производственных проектов, т.е. μ_ij = 0, i ∈ I, j ∈ J,

V DI^tj = ZPI^tj = EPI^tj = ZI^tj = 0, t ∈ T, i ∈ I, j ∈ J. Тогда коэффициенты при

переменных x_j в целевой функции (1) и в ограничении (8) равны нулю и, сле-

довательно, в оптимальном решении задачи можно положить x_j = 0, j ∈ J.

Таким образом, ограничение (11) превращается в тождество.

Предположим, что горизонт планирования — три года. Для первых l про-

изводственных проектов CF P1i = -q_i, CF P2i = 0 и CF P3i = 2q_i. Для осталь-

ных: CF P1l+1 = -1/2, CF P2l+1 = 0, CF P3l+1 = 1 и DBP3l+1 = Δ, CF P3l+2 = Δ,

DBP3l+2 = 2Δ, где Δ = 2(R + 2^r) — достаточно большое положительное чис-

ло. Все остальные параметры производственных проектов положим рав-

ными нулю. Всем производственным проектам, за исключением (l + 2)-го,

не требуется реализация экологических проектов: ν_ik = 0, i ∈ I \ {l + 2},

k ∈ K, а проекту (l + 2) требуется реализация всех экологических проек-

тов: νl+2k = 1, k ∈ K. Определим затраты на реализацию экологических

121

проектов в первый и второй год как ZE¹¹ = ZE²¹ = R, ZE¹² = ZE²² = 2^r/2,

ZE¹³ = ZE²³ = 2^r/4,··· ,ZE1r = ZE2r = 2, ZE1r+1 = ZE2r+1 = 1. Все остальные

параметры экологических проектов равны нулю. Величины затрат выбра-

ны так, что с их помощью можно выразить любое число S из интервала

R ≤ S < R + 2^r. Бюджет государства в любой год равен R + 2^r - 1. Бюджет

инвестора в первый год равен R + 2^r - 1, во второй — 2^r - 1, в третий год

равен нулю. Отметим, что при таких исходных данных ограничения (3), (8),

(10) являются тривиальными и не требуют проверки, а ограничения (11)-(13)

сводятся к неравенствам y_k + u_k ≤ 1, y_k + u_k ≥ zl+2, y_k ≤ y_k, k ∈ K. Целевые

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

)

(∑

f^G(x,y,y,z,u) = Δzl+1 + 2Δzl+2 -

(ZE1k + ZE2k + ZE³)yk

(

)

∑

f^I(y,z,u) =

q_iz_i + zl+/2 + Δzl+2 -

(ZE1k + ZE2k + ZE³)uk

Последующие рассуждения также основываются на структуре бюджетных

ограничений государства:

∑

ZE^tky_k ≤ R + 2^r - 1, t = 1,2,3,

и инвестора:

∑

ZE1ku_k + q_iz_i + zl+1/2 ≤ R + 2^r - 1,

ZE2ku_k ≤ 2^r - 1.

i=1

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

деления экологических проектов следует, что в оптимальном решении двух-

уровневой задачи и в оптимальном решении задачи инвестора реализуется

производственный проект (l + 2). Так как тогда zl+2 = 1, то ограничения (11),

(12) эквивалентны равенствам y_k + u_k = 1. Таким образом, государство и ин-

вестор должны выполнить все экологические проекты, поделив их между

собой. В силу своих бюджетных ограничений государство не может реализо-

вать экологические проекты с суммарными затратами S ≥ R + 2^r. С другой

стороны, из-за ограниченных возможностей инвестора во второй год госу-

дарство не может реализовать экологические проекты на сумму S, строго

меньшую, чем R.

Действительно, общая стоимость экологических проектов равна

R + 2^r - 1. Тогда инвестору в этой ситуации надо оплатить выполнение

экологических проектов на сумму R + 2^r - 1 - S > 2^r - 1, т.е. бюджетное

ограничение нарушено. Таким образом, государство должно реализовать

экологические проекты с суммарными затратами в первый и второй год,

равными S, где R ≤ S < R + 2^r, а инвестор реализует оставшиеся экологи-

ческие проекты с суммарными затратами R + 2^r - 1 - S в первый и второй

год. После чего у инвестора в первый год остается от бюджета ровно S, что

122

он может потратить на первые l + 1 проектов. Как следует из бюджетного

ограничения инвестора на первый год, если есть такое I ⊆ {1, . . . , k}, при ко-_∑

тором выполнено_i∈I q_i = S, то инвестор не сможет реализовывать проект

l + 1 (так как доход от реализации любого из производственных проектов

с номером, не превосходящим l, строго больше, чем доход от реализации

проекта l + 1). Заметим, что l + 1-й проект очень выгоден государству. Зна-

чит, государство будет так подбирать S (R ≤ S < R + 2^r), чтобы для любого_∑

I ⊆ {1,...,k} выполнялось_i∈I q_i = S, если это возможно. Таким образом,

в задаче распознавания Subset-Sum-Interval ответ «да» тогда и только тогда,

когда в задаче государства существует оптимальное решение со значением

целевой функции, строго большим 2Δ. Все величины, фигурирующие в

двухуровневой задаче, могут быть получены за полиномиальное время от

длины входа задачи Subset-Sum-Interval. Теорема 2 доказана.

Доказательство следствия 1. Ранее [3] было показано, что стан-

дартная задача распознавания для задачи государства принадлежит клас-

∑_P

су

. Из доказательства теоремы 2 следует полиномиальная сводимость

задачи распознавания Subset-Sum-Interval к задаче D(P S). Таким образом,

∑_P

задача D(P S) является полной в классе

и, следовательно, является самой

сложной задачей данного класса.

Доказательство следствия

2. Прямо следует из доказательства

теоремы 2.

Доказательство следствия 3. В пессимистической постановке за-

дачи государства инвестор среди своих решений выбирает свое наименее ин-

тересное для государства оптимальное решение. Однако сводимость теоре-

мы 2 устроена так, что у инвестора нет возможности повлиять на оптимум

государства, перебирая свои оптимальные решения.

СПИСОК ЛИТЕРАТУРЫ

1. Ерешко Ф.И. Моделирование рефлексивных стратегий в управляемых системах.

М.: ВЦ РАН, 2001.

2. Лавлинский С.М. Государственно-частное партнерство на сырьевой террито-

рии — экологические проблемы, модели и перспективы // Проблемы прогно-

зирования. 2010. № 1. С. 99-111.

3. Кочетов Ю.А., Лавлинский С.М., Панин А.А., Плясунов А.В. Вычислительная

сложность моделей планирования государственно-частного партнерства // Тр.

12-й Междунар. Азиат. шк.-семинара “Проблемы оптимизации сложных систем”.

2016. С. 290-297.

4. Лавлинский С.М., Панин А.А., Плясунов А.В. Двухуровневая модель планиро-

вания государственно-частного партнерства // АиТ. 2015. № 11. С. 89-103.

Lavlinskii S.M., Panin A.A., Plyasunov A.V. A Bilevel Planning Model for Public-

private Partnership // Autom. Remote Control. 2015. V. 76. No. 11. P. 1976-1987.

5. Лавлинский С.М., Панин А.А., Плясунов А.В. Сравнение моделей планирова-

ния государственно-частного партнерства // Дискрет. анализ и исслед. опера-

ций. 2016. Т. 23. № 3. С. 35-60.

Lavlinskii S.M., Panin A.A., Plyasunov A.V. Comparison of Models of Planning the

Public-Private Partnership // J. Appl. Ind. Math. 2016. V. 10. No. 3. P. 356-369.

123

Ausiello G., Crescenzi P., Gambosi G., et al. Complexity and approximation:

combinatorial optimization problems and their aproximability properties. Berlin:

Springer-Verlag, 1999.

Панин А.А., Пащенко М.Г., Плясунов А.В. Двухуровневые модели конкурент-

ного размещения производства и ценообразования // АиТ. 2014. № 4. P. 153-169.

Panin A.A., Pashchenko M.G., Plyasunov A.V. Bilevel Competitive Facility

Location and Pricing Problems // Autom. Remote Control. 2014. V. 75. No. 4.

P. 715-727.

Панин А.А., Плясунов А.В. О сложности двухуровневых задач размещения и це-

нообразования // Дискрет. анализ и исслед. операций. 2014. Т. 21. № 5. С. 54-66.

Panin A.A., Plyasunov A.V. On complexity of bilevel problems of location and

pricing // J. Appl. Ind. Math. 2014. V. 8. No. 4. P. 574-581.

Eggermont C.E.J., Woeginger G.J. Motion planning with pulley, rope, and baskets //

Theory Comput. Syst. 2013. V. 53. No. 4. P. 569-582.

10.

Ben-Ayed O. Bilevel linear programming // Comput. Oper. Res. 1993. V. 20. No. 5.

P. 485-501.

11.

Иванов С.В. Двухуровневые задачи стохастического линейного программирова-

ния с квантильным критерием // АиТ. 2014. № 1. С. 130-144.

Ivanov S.V. Bilevel Stochastic Linear Programming Problems with Quantile

Criterion // Autom. Remote Control. 2014. V. 75. No. 1. P. 107-118.

12.

Иванов С.В., Морозова М.В. Стохастическая задача конкурентного размещения

предприятий с квантильным критерием // АиТ. 2016. № 3. С. 109-122.

Ivanov S.V., Morozova M. V. Stochastic Problem of Competitive Location of

Facilities with Quantile Criterion // Autom. Remote Control. 2016. V. 77. No. 3.

P. 451-461.

13.

Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероят-

ностными критериями. М.: Физматлит, 2009.

14.

Alekseeva E., Kochetov Y., Talbi El-G. A matheuristicfor the discrete bilevel problem

with multiple objectives at the lower level // Int. Trans. Oper. Res. 2017. V. 24. No. 5.

P. 959-981.

Статья представлена к публикации членом редколлегии А.А. Лазаревым.

Поступила в редакцию 10.12.2017

После доработки 27.06.2018

Принята к публикации 08.11.2018

124