Автоматика и телемеханика, № 1, 2020

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

ПРОГРАММНЫЕ УПРАВЛЕНИЯ ДВУХСТАДИЙНЫМИ

СТОХАСТИЧЕСКИМИ ПРОИЗВОДСТВЕННЫМИ СИСТЕМАМИ¹

Рассматривается проблема программного управления некоторым клас-

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

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

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

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

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

тематической модели.

Ключевые слова: стохастические производственные системы, двухстадий-

ные системы, программное управление, квазиоптимальное решение.

DOI: 10.31857/S0005231020010067

1. Введение

Рассматривается проблема программного управления некоторым классом

производственных систем, функционирующих в условиях неопределенности.

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

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

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

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

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

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

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

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

вероятности получения того или иного полуфабриката. Известны затраты на

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

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

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

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

(но только один) может быть изготовлен из этого полуфабриката. При этом

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

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

систем можно разбить на две стадии. Первая — от применения технологи-

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

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

¹ Работа выполнена при финансовой поддержке Федеральной целевой программы «Ис-

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

кого комплекса России на 2014-2020 гг.» в рамках соглашения № 14.578.21.0246 (уникаль-

ный идентификатор RFMEFI57817X0246).

производства продукта. Эта стадия носит детерминированный характер. За-

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

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

вторую — переработку полуфабрикатов в продукты производства.

Работа является продолжением статей [1, 2], в которых решаются зада-

чи оптимального планирования и оптимального управления. Задача опти-

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

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

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

гические режимы в процессе функционирования системы нужно применять

для наилучшего выполнения заданного плана. При этом задача оптималь-

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

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

были изготовлены. Так как использование того или иного технологического

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

ресурсами, то для эффективного функционирования рассматриваемых про-

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

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

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

терминах теории управляемых систем [3, 4] носит название задачи поиска

программных управлений.

В [1, 2] дается литературный обзор результатов в рассматриваемой обла-

сти [5-11] и приводятся примеры двухстадийных производственных систем,

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

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

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

ства стали в мартеновских печах [12-17]. Для решения задач программного

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

следуются рассматриваемые задачи.

2. Постановка задачи поиска оптимального

программного управления двухстадийными

стохастическими производственными системами

Как и в [1, 2], пусть I — множество технологических режимов; J —

множество полуфабрикатов; K — множество выпускаемых продуктов; T =

= {0, 1, . . . , T₀} — множество тактов функционирования системы; P = ∥p_ij ∥ —

матрица вероятностей, где p_ij — вероятность того, что, применив технологи-_∑

ческий режим i, будет получен полуфабрикат j,_j∈J p_ij = 1, i ∈ I, p_ij ≥ 0,

i ∈ I, j ∈ J; K(j) — множество продуктов, любой из которых может быть

изготовлен из полуфабриката j, K(j) ⊆ K, j ∈ J; π — |K|-мерный вектор с

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

дуктов в планируемом периоде, где π_k — количество k-х продуктов, которые

должны быть выпущены в планируемом периоде, k ∈ K; c_i — затраты про-

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

режима, i ∈ I; g_k — доход, который получит система от производства одного

запланированного k-го продукта, k ∈ K.

Множество состояний системы разобьем на два подмножества — основ-

ные и вспомогательные состояния. Основные состояния образуют множество

S = {s | s_k ≥ 0 - целые, s_k ≤ T₀, k ∈ K}, где s_k определяет количество про-

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

являются всевозможные пары (s, j), где s ∈ S, j - параметр вспомогательного

состояния, j ∈ J. Управлениями в основных состояниях являются элементы

множества I - выбор технологического режима. Допустимыми управлениями

во вспомогательном состоянии (s, j) являются элементы множества K(j) —

изготовление из полуфабриката продукта производства. Функционирование

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

тактом понимается переход системы из основного состояния в основное — от

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

В основном состоянии s, s ∈ S к системе применяется управление i, i ∈ I

и система с вероятностью p_ij переходит во вспомогательное состояние (s, j),

при этом система несет потери c_i ≥ 0 — затраты на использование техно-

логического режима. Во вспомогательном состоянии (s, j) к системе приме-

няется управление k, k ∈ K(j), под воздействием которого система перехо-

дит в новое основное состояние, отличающееся от состояния s лишь в ком-

поненте k, k-я компонента увеличивается на 1 (больше на 1 стало продук-

та k). При этом переходе система приобретает доход, определяемый функ-

{

g_k, если s_k < π_k,

цией q(s, k, π) =

Здесь g_k ≥ 0 — доход, который

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

получит система от выпуска запланированного продукта k, k ∈ K(j).

Множество всех управлений обозначим через U = V × W . В общем слу-

чае управление u ∈ U есть пара функций v(s, t) и w(s, j, t), определенных

соответственно на множествах S × T и S × J × T со значениями из множеств

соответственно I и K(j). Содержательно функция v(s, t) определяет, какие

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

а функция w(s, j, t) определяет, какие продукты нужно выпускать во вспо-

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

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

система может оказаться в зависимости от тактов функционирования.

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

ний (управлений без обратных связей) функция v(s, t) определяется цело-

численным набором x, i-я компонента которого x_i задает количество техно-

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

x ∈ R^|I|, а функция w(s,j,t) зависит только от параметра вспомогательного

состояния j и рандомизированная, т.е. задается распределением вероятно-

стей, определяемым матрицей Y = ∥y_jk∥, j ∈ J, k ∈ K. Здесь y_jk — вероят-

ность изготовления продукта k из полуфабриката j, j ∈ J, k ∈ K. Опреде-

ленные таким образом вероятности не зависят от состояний и тактов функ-_∑

ционирования,_k∈K y_jk = 1, y_jk ≥ 0, j ∈ J, k ∈ K.

Рассмотрим целочисленную случайную величину σ_k = σ_k(x, Y ), прини-

мающую значения из множества {0, 1, . . . , T₀} — сколько продуктов k будет

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

режимы из набора x: x₁ раз первые технологические режимы, x₂ раз вторые

технологические режимы, . . . , x_|I| раз |I|-е технологические режимы, а во

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

ностью y_jk будет выпускаться продукт k, j ∈ J, k ∈ K.

Обозначим через F (π, T₀, x, Y ) математическое ожидание полного дохо-

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

количество тактов функционирования системы T₀ и к системе будут при-

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

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

матрицей Y , задающей распределение вероятностей изготовления тех или_∑∑

иных продуктов. Тогда F (π, T₀, x, Y ) =_k∈K g_kE min(π_k, σ_k) -_i∈I c_ix_i, где

E min(π_k,σ_k) — математическое ожидание целочисленной случайной величи-

ны min(π_k, σ_k). Действительно, если в результате применения программной

стратегии, определяемой набором x и матрицей Y , будет выпущено продук-

та k не больше запланированного, то каждый продукт k принесет доход g_k;

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

сут только выпущенные первые π_k продукты. Отсюда задача нахождения оп-

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

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

тематического программирования.

∑

Задача 1. F(π,T₀,x,Y ) =

g_kE min(π_k,σ_k) -

c_ix_i → max

k∈K

i∈I

при условиях:

∑

x_i = T₀,

i∈I

∑

y_jk = 1, j ∈ J,

k∈K

y_jk = 0, если k ∈ K(j), j ∈ J,

x_i ≥ 0 - целые, i ∈ I,

y_jk ≥ 0, j ∈ J, k ∈ K.

3. Нахождение квазиоптимального программного управления

Из-за существенной сложности функционала F (π, T₀, x, Y ), связанной с

операцией E min(π_k, σ_k), задачу 1 даже при небольших значениях параметров

решить не удается. Принципиальные трудности возникают даже при подсчете

значения функционала при заданных значениях неизвестных.

Пусть (x⁰, Y⁰) — оптимальное решение исходной задачи 1. Под квазиоп-

тимальным решением задачи 1 будем понимать такое ее допустимое решение

(x^∗, Y^∗), что

F (π, T₀, x⁰, Y⁰) - F (π, T₀, x^∗, Y^∗)

lim

= 0.

T₀→∞

F (π, T₀, x⁰, Y⁰)

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

ния, в которой в отличие от исходной задачи знак математического ожидания

внесен под операцию поиска минимума.

∑

Задача 2. H(π,T₀,x,Y ) =

g_k min(π_k,Eσ_k) -

c_ix_i → max

k∈K

i∈I

при сохраненных условиях задачи 1.

∑

Нетрудно показать, что Eσ_k =_i∈I x_ij∈J p_ij y_jk, k ∈ K. Действительно,

∑

p_ijy_jk - вероятность того, что, используя технологический режим i, из-

j∈J

готовим продукт k, а x_i - количество i-х технологических режимов, которые

будут применяться в планируемом периоде, i ∈ I, k ∈ K.

Преобразуем функционал задачи 2. Учитывая, что

min(π_k,Eσ_k) = - max(-π_k,-Eσ_k) = π_k - π_k - max(-π_k,-Eσ_k) =

= π_k - max(0,π_k - Eσ_k) = π_k - (π_k ⊗ Eσ_k),

где ⊗ — знак усеченной разности, получим

⎛

⎞

∑

∑ ∑

∑

H(π, T₀, x, Y ) =

g_kπ_k -

g_k ⎝π_k ⊗ x_i p_ijy_ij⎠ - c_ix_i.

k∈K

i∈I

j∈J

i∈I

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

задачу 3 минимизации функционала

⎛

⎞

∑

∑ ∑

∑

Φ(π, T₀, x, Y ) =

g_k ⎝π_k ⊗ x_i p_ijy_ij⎠ + c_ix_i

k∈K

i∈I

j∈J

i∈I

при сохраненных условиях задачи 1.

Рассмотрим следующую з а д а ч у 4 математического программирования:

⎛

⎞

∑

Φ(π, T₀, x, Y ) =

g_k ⎝π_k ⊗ z_jk⎠ + c_ix_i → min — при условиях:

k∈K

j∈J

i∈I

∑

x_i = T₀,

i∈I

∑

z_jk -

x_ip_ij = 0, j ∈ J,

k∈K

i∈I

z_jk = 0, если k ∈ K(j), k ∈ K, j ∈ J,

x_i ≥ 0 - целые, i ∈ I,

z_jk ≥ 0, j ∈ J, k ∈ K.

Покажем, как по решению задачи 4 получить решение задачи 3, а тем

самым и задачи 2. Пусть x^′i, z^′jk, i ∈ I, j ∈ J, k ∈ K — решение задачи 4.

Тогда решением задачи 3 будут следующие наборы:

x0i = x^′i, i ∈ I,

z^′

∑

y0jk =

∑

если

x^′ip_ij > 0,

(1)

x^′ip

i∈I

∑

y0jk = 0, если

x^′ip_ij = 0, j ∈ J, k ∈ K.

i∈I

Действительно, x0i, y0jk, i ∈ I, j ∈ J, k ∈ K удовлетворяют ограничениям за-

дачи 3. Пусть существуют такие x^∗i, y^∗jk, i ∈ I, j ∈ J, k ∈ K, которые удовле-

творяют условиям задачи 3, и выполняется Φ(π, T₀, x^∗, Y^∗) < Φ(π, T₀, x⁰, Y⁰),

∑

тогда x^∗i, z^∗jk = y^∗

x^∗ip_ij, i ∈ I, j ∈ J, k ∈ K, удовлетворяют условиям

i∈I

задачи 4 и на них значение функционала меньше значения функционала за-

дачи на x^′i, z^′jk, i ∈ I, j ∈ J, k ∈ K, что противоречит условиям оптимальности

наборов x^′i, z^′jk, i ∈ I, j ∈ J, k ∈ K.

Избавимся в функционале задачи 4 от нелинейности, определяемой усечен-

ной разностью. Рассмотрим з а д а ч у 5 частично-целочисленного линейного

программирования.

∑

Q(x, v, w, Z) =

g_kv_k +

c_ix_i → min — при условиях:

k∈K

i∈I

∑

x_i = T₀,

i∈I

∑

z_jk -

x_ip_ij = 0, j ∈ J,

k∈K

i∈I

∑

z_jk + v_k - w_k = π_k, k ∈ K,

j∈J

z_jk = 0, если k ∈ K(j), k ∈ K, j ∈ J,

x_i ≥ 0 — целые, i ∈ I,

z_jk ≥ 0, v_k ≥ 0, w_k ≥ 0, j ∈ J, k ∈ K.

Покажем, что решение задачи 5 определяет решение задачи 4, а тем самым_∑

и решение задачи 2. Для этого достаточно показать, что π_k ⊗_j∈J z_jk = v_k,

∑

если π_k >_j∈J z_jk, и π_k ⊗_j∈J z_jk = 0, если π_k ≤_j∈J z_jk.

Пусть z0jk, v0k, w0k, j ∈ J, k ∈ K оптимальное решение задачи 5. Тогда для

любого k, k ∈ K, либо v0k = 0, либо w0k = 0. Пусть это не так и существует

другое оптимальное решение задачи 5 z^∗jk, v^∗k, w^∗k, j ∈ J, k ∈ K, для которого

найдется такое k, что v^∗k > 0 и w^∗k > 0. Тогда если v^∗k > w^∗k > 0, то при замене

v^′k = v0k - w0k и w^′k = 0 ограничения задачи 5 будут выполнены, а значение

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

шения задачи 5. Если w^∗k ≥ v^∗k > 0, то v^′k = 0, w^′k = w0k - v0k удовлетворяют

ограничениям задачи 5 и уменьшают значение функционала.

Таким образом, для решения вспомогательной задачи 2 достаточно решить

частично-целочисленную задачу линейного программирования 5, а затем по

соотношениям (1) найти оптимальное решение задачи 2.

4. Обоснование квазиоптимальности программного управления

Теорема. Пусть (x ⁰,Y ⁰) — оптимальное решение исходной задачи 1, а

(x^∗, Y^∗) — оптимальное решение вспомогательной задачи 2.

F (π, T₀, x⁰, Y⁰) - F (π, T₀, x^∗, Y^∗)

Тогда lim

= 0.

T₀→∞

F (π, T₀, x⁰, Y⁰)

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

ния (x⁰, Y⁰), получающегося при решении исходной задачи 1, на программное

управление (x^∗, Y^∗), получающееся при решении вспомогательной задачи 2,

математическое ожидание полного дохода уменьшится, однако с ростом T₀

эти потери по отношению к математическому ожиданию полного дохода при

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

Доказательство теоремы основано на лемме.

Лемма. Для произвольной целочисленной случайной величины σ, σ ∈

∈ {0, 1, . . . , n}, и произвольного целого числа π

min(π,Eσ) - E min(π,σ) =

(E |π - σ| - |Eσ - π|).

Доказательство леммы и теоремы см. в Приложении.

5. Заключение

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

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

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

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

ката готовой продукции. Решение этой задачи позволяет до начала планируе-

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

ны в процессе функционирования производственной системы, и тем самым

обеспечить эти режимы необходимыми ресурсами. Предлагается процедура

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

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

задачи.

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

ренных в постоянную эксплуатацию при планировании и оперативном управ-

лении процессом производства изделий микроэлектроники ФГУП “ФНПЦ

НИИИС им. Ю.Е. Седакова” [12-14], и апробированы при решении задач

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

зации конденсата ООО Сургутгазпром [15-17].

ПРИЛОЖЕНИЕ

Доказательство леммы.

∑

min(π,Eσ) - E min(π,σ) = min(π,Eσ) - min(π,i)p(σ = i) =

i=0

∑

= min(π,Eσ) - ip(σ = i) - π

p(σ = i) =

i=0

i=π+1

(

)

∑

= min π, ip(σ = i)

- ip(σ = i) - π

p(σ = i) =

i=0

i=π+1

(

)

∑

= min

π - ip(σ = i),

ip(σ = i)

-π

p(σ = i) =

i=0

i=π+1

(

)

∑

= min π - π

p(σ = i) - ip(σ = i),

(i - π)p(σ = i)

i=π+1

i=0

i=π+1

(

)

∑

= min

(π - i)p(σ = i),

(i - π)p(σ = i)

i=0

i=π+1

Обозначим:

∑

α(π) = (π - i)p(σ = i) и β(π) =

(i - π)p(σ = i).

i=0

i=π+1

Тогда

∑

α(π) + β(π) =

|π - i| p(σ = i) +

|π - i| p(σ = i) =

i=0

i=π+1

∑

|π - i| p(σ = i) = E |π - σ| .

i=0

С другой стороны

∑

α(π) = (π - i)p(σ = i) = π -

(π - i)p(σ = i) =

i=0

i=π+1

∑

=π-Eσ+Eσ-

(π - i)p(σ = i) =

i=π+1

∑

= π - Eσ + ip(σ = i) -

(π - i)p(σ = i) =

i=0

i=π+1

∑

= π - Eσ + ip(σ = i) - π

p(σ = i) -

ip(σ = i) =

i=0

i=π+1

∑

=π-Eσ+

(i - π)p(σ = i) = π - Eσ + β(π).

i=π+1

Таким образом, α(π) + β(π) = E |π - σ| и α(π) - β(π) = π - Eσ. Отсюда

α(π) =

(E |π - σ| - (Eσ - π)), β(π) =

(E |π - σ| - (π - Eσ)).

Тогда

min(π,Eσ) - E min(π,σ) = min(α(π),β(π)) =

min(E |π - σ| - (Eσ - π),E |π - σ| - (π - Eσ)) =

(E |π - σ| - min(Eσ - π, π - Eσ)) =

(E |π - σ| - |Eσ - π|).

Лемма доказана.

Доказательство теоремы. Из леммы следует, что

H(π, T₀, x, Y ) - F (π, T₀, x, Y ) =

∑

= g_k min(π_k,Eσ_k) - c_ix_i -

g_kE min(π_k,σ_k) +

c_ix_i =

k∈K

i∈I

k∈K

i∈I

∑

= g_k(min(π_k,Eσ_k) - E(min(π_k,σ_k)) =

k∈K

(

)

∑

g_k(E |π_k - σ_k| - |Eσ_k - π_k|)

k∈K

Здесь последнее равенство основано на лемме.

Полученное равенство дает оценку для значения функционала

F (π, T₀, x, Y ), если известно значение функционала H(π, T₀, x, Y ). При этом

√

нужно учитывать, что F (π, T₀, x, Y ) ≤ H(π, T₀, x, Y ) и E |π - σ| ≤

D(π, σ),

где D(π, σ)

— средний квадрат отклонения (дисперсия) целочисленной

случайной величины σ относительно данного целого числа π.

Определим дисперсию и математическое ожидание для данного случая.

⎛

⎞₂

∑ ∑

∑

∑ ∑

D(π_k, σ_k) =

x_i

p_ijy_jk(1 -

p_ijy_jk) +^⎝

x_i

p_ijy_jk - π_k⎠

;

i∈I

j∈J

i∈I

j∈J

∑ ∑

Eσ_k = x_i p_ijy_jk.

i∈I

j∈J

Тогда

H(π, T₀, x, Y ) - δ(π, T₀, x, Y ) ≤ F (π, T₀, x, Y ) ≤ H(π, T₀, x, Y ),

где

∑

(√

)

δ(π, T₀, x, Y ) =

g_k

D(π_k, σk) - |Eσ_k - π_k|

k∈K

Обозначим:

F (π, T₀, x⁰, Y⁰) - F (π, T₀, x^∗, Y^∗)

Δ(F⁰, F^∗) =

F (π, T₀, x⁰, Y⁰)

Здесь (x⁰, Y⁰) — оптимальное решение исходной задачи 1, а (x^∗, Y^∗) — опти-

мальное решение задачи 2. Из того, что F (π, T₀, x⁰, Y⁰) ≤ H(π, T₀, x⁰, Y⁰) ≤

≤ H(π,T₀,x ^∗,Y ^∗) и

-F(π,T₀,x^∗,Y^∗) ≤ -H(π,T₀,x^∗,Y^∗) + δ(π,T₀,x^∗,Y^∗),

получаем F (π, T₀, x⁰, Y⁰) - F (π, T₀, x^∗, Y^∗) ≤ δ(π, T₀, x^∗, Y^∗). Учитывая,

что

F (π, T₀, x⁰, Y⁰) ≥ F (π, T₀, x^∗, Y^∗) ≥ H(π, T₀, x^∗, Y^∗) - δ(π, T₀, x^∗, Y^∗),

получим

F (π, T₀, x⁰, Y⁰) - F (π, T₀, x^∗, Y^∗)

Δ(F⁰, F^∗) =

≤

F (π, T₀, x⁰, Y⁰)

δ(π, T₀, x^∗, Y^∗)

≤

H(π, T₀, x^∗, Y∗0) - δ(π, T₀, x^∗, Y^∗)

Оценим числитель и знаменатель полученного выражения.

δ(π, T₀, x^∗, Y^∗) =

⎛/

⎛

⎞ ⎛

⎞

∑

0∑

∑

⎜

g_k⎝√ x∗

p_ijy^∗jk⎝1-pijy∗jk

⎠₊⎝

x^∗

p_ijy^∗jk -π_k⎠ -

k∈K

i∈I

j∈J

i∈I

j∈J



⎞

⎛

⎞



∑

∑



0∑

∑



⎠≤1∑

⎠_≤

x^∗

p_ijy^∗jk - π_k

g_i√ x∗

p_ijy^∗jk

⎝1-pijy^∗jk



_i∈I

j∈J



i∈I

j∈J

∑

√∑

√

|K|

≤

g_i

x_i ≤

T₀.

i∈I

При доказательстве этого неравенства использовалось:

√

a+b≤

√a +√b, если a ≥ 0 и b ≥ 0;

⎛

⎞

∑

p_ijy_jk ⎝1 -

p_ijy_jk⎠ ≤1;

j∈J

g = maxgi;

i∈I

∑

x_i = T₀;

i∈I

|K| - мощность множества K.

Таким образом, показано, что δ(π, T₀, x^∗, Y^∗) ≤|K|4 g√T0 = α(T0). Это нера-

венство справедливо для любых x, Y, π, T₀. Можно показать, что

⎛

⎞

(

)

∑

H(π, T₀, x^∗, Y^∗) ≥ β(T₀) = g^′T0 ⎝minmax

p_ij⎠ min

k∈K

i∈I

|I|

j|k∈K(j)

Здесь g^′ = min

таких,

g_i. Это неравенство справедливо для любых x,Y,π,T₀

i∈I

∑

что_k∈K π_k ≥ T₀. Очевидно, что начиная с некоторого T₀ β(T₀) > α(T₀).

Тогда

α(T₀)

Δ(F⁰, F^∗) ≤

β(T₀) - α(T₀)

|K|

g√T0

(

)

(

)

∑

√

g^′T₀

minmax

p_ij min

-|K|4g

T₀

j|k∈K(j)

|I|

k∈K

i∈I

отсюда

lim Δ(F⁰, F^∗) = 0.

T₀→∞

Теорема доказана.

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

Прилуцкий М.Х. Оптимальное планирование двухстадийных стохастических

производственных систем // АиТ. 2014. № 8. С. 37-47.

Prilutskii M.Kh. Optimal Planning for Two-Stage Stochastic Industrial Systems //

Autom. Remote Control. 2014. V. 75. No. 8. P. 1384-1392.

Прилуцкий М.Х. Оптимальное управление двухстадийными стохастическими

производственными системами // АиТ. 2018. № 5. С. 69-82.

Prilutskii M.Kh. Optimal Management of Two-Stage Stochastic Production

Systems // Autom. Remote Control. 2018. V. 79. No. 5. P. 830-840.

Моисеев Н.Н. Численные методы в теории оптимальных систем. М.: Наука, 1971.

Красовский Н.Н. Теория управления движением. М.: Наука, 1968.

Kempf K., Keskinocak P., Uzsoy R. (ed.) Planning Production and Inventories in

the Extended Enterprise // Int. Ser. Oper. Res. & Management Sci. V. 152. N.Y.:

Springer, 2010.

Pinedo M.L. Planning and Scheduling in Manufacturing and Services. N.Y.: Springer-

Verlag, 2005.

Weglarz J. (ed.) Project Scheduling: Recent Models, Algorithms and Applications.

N.Y.: Springer, 1999.

Sprecher A. Resource-constrained project scheduling: Exact methods for the multi-

mode Case / Ser. Lect. Notes Econom. Math. Syst. V. 409. Berlin, 1994.

Hapke M., Jaszkiewicz A., Slowinski R. Fuzzy Multi-Mode Resource-Constrained

Project Scheduling with multiple Objectives // Weglarz J. (ed.) Project Scheduling.

Int. Ser. Oper. Res. & Management Sci. V. 14. Boston: Springer, 1999.

10.

Armbruster D., Fonteijn J., Wienke M. Modeling Production Planning and Transient

Clearing Functions // Logist. Res. 2012. V. 5. No. 3-4. P. 133-139.

11.

Bügler M., Borrmann A. Using Swap-Based Search Trees to obtain Solutions for

Resource Constrained Project Scheduling Problems // Proc. 85 Annual Meeting Int.

Associat. Appl. Math. Mechan. (GAMM). 2014. V. 14. No. 1. P. 809-810.

12.

Прилуцкий М.Х., Власов В.С. Оптимизационные задачи распределения ресур-

сов при планировании производства микроэлектронных изделий // Системы

управления и информационные технологии. 2009. № 1. С. 38-43.

13. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объёмно-кален-

дарного планирования // Изв. Акад. наук. Теория и системы управления. 2007.

№ 1. C. 78-82.

14. Прилуцкий М.Х., Власов В.С., Кривошеев О.В. Задачи оптимального планиро-

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

Информационные технологии. 2017. Т. 23. № 9. С. 650-657.

15. Прилуцкий М.Х., Костюков В.Е. Оптимизационные задачи добычи газа и пере-

работки газового конденсата // Автоматизация в промышленности. 2008. № 6.

C. 20-23.

16. Прилуцкий М.Х., Костюков В.Е. Потоковые модели для предприятий с непре-

рывным циклом изготовления продукции // Информационные технологии. 2007.

№ 10. C. 47-52.

17. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи оптимального пла-

нирования производства // АиТ. 2010. № 10. С. 148-155.

Afraimovich L.G., Prilutskii M.Kh. Multiindex Optimal Production Planning

Problems // Autom. Remote Control. 2010. V. 71. No. 10. P. 2145-2151.

Статья представлена к публикации членом редколлегии Е.Я. Рубиновичем.

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

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

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