close

Вход

Забыли?

вход по аккаунту

?

Оптимизация ритмичности производства с двумя типами сырья.

код для вставкиСкачать
Математическое моделирование. Оптимальное управление
Вестник Нижегородского университета
им. Н.И.В.П.Савельев
Лобачевского, 2013, № 4 (1), с. 216–218
А.А.Боровков,
216
УДК 519.6
ОПТИМИЗАЦИЯ РИТМИЧНОСТИ ПРОИЗВОДСТВА
С ДВУМЯ ТИПАМИ СЫРЬЯ
 2013 г.
А.А. Боровков, В.П. Савельев
Нижегородский госуниверситет им. Н.И. Лобачевского
vpsavelyev@rambler.ru
Поступила в редакцию 09.11.2012
Решены две задачи, связанные с планированием ритмичной работы предприятия, перерабатывающего два типа сырья. При этом решение первой задачи (оптимизация общей ритмичности производства), формулируемой в виде задачи выпуклого программирования, существенно облегчает решение
второй (оптимизация ритмичности переработки каждого типа сырья).
Ключевые слова: выпуклое программирование, условия оптимальности.
Введение
Решение задачи планирования
суммарной ритмичной переработки сырья
В работе решается задача планирования
ритмичной переработки сырья двух типов. Решение задачи разбивается на два этапа. На первом этапе решается задача планирования суммарной ритмичной переработки сырья, которую
при известных на период I  1,2,..., n поставках сырья и ограниченном объеме складов (резервуаров) для хранения можно сформулировать [1] как задачу нахождения пары допустимых
векторов X = (x1, x2, …, xn) и Y = (y1, y2, …, yn),
принадлежащих соответственно множествам
n
j
i 1 i
j
j
n
i 1 i
n
i j
n
j
j
i
i 1
j
j
n
i 1
i
n
и доставляющих минимальное значение функn

xj + yj < xj+1+ yj+1, при этом
B)
i j

i 1
xj + yj > xj+1+ yj+1, при этом
C)
f ( xi  yi ). Функция f(z)
ции F(X,Y) =
i 1
предполагается строго выпуклой и дважды
дифференцируемой, то есть f // (z) > 0. Получены необходимые и достаточные условия оптимальности суммарного плана. Показано, что
процесс решения сводится к разбиению исходной задачи на подзадачи такого же типа, но
меньшей размерности, причем решение каждой
подзадачи обладает свойством xi  yi  const .
Поскольку последнее условие оставляет свободу выбора для компонент xi и yi , то на втором
этапе решается задача ритмичной переработки
сырья каждого типа при условии xi  yi  const.
i j

i 1
i j

x = Bj,
i 1 i
y i = Dj ;
i j
 x ≤B ,A <B ,
j = 1, n  1 ;  x  B },
G ={Y  R : C ≤  y ≤ D , C < D ,
j = 1, n  1 ;  y  D }
D ={X  R : Aj ≤
Теорема 1. Для того чтобы пара допустимых
векторов (X,Y) доставляла минимум функции
F(X,Y), необходимо и достаточно, чтобы для
любых двух соседних компонент этих векторов
выполнялось одно из следующих трех условий:
A) xj + yj = xj+1+ yj+1 ;
i j

x = Aj,
i 1 i
yi = Cj .
Доказательство необходимости условий A),
B), C) проведем методом от противного. Пусть
пара допустимых векторов (X,Y) доставляет минимум функции F(X,Y), но нашлась пара соседних компонент, для которых не выполнено ни
одно из этих условий. Это значит, что либо x j +
+ yj < xj+1+ yj+1, но при этом выполнено по
i j

крайней мере одно из неравенств
i j

i 1
x < Bj,
i 1 i
yi < Dj , либо xj + yj > xj+1+ yj+1, но при этом
выполнено по крайней мере одно из неравенств
i j

x
i 1 i
> Aj,
i j

i 1
yi > Cj. Рассмотрим
первый случай (второй случай рассматривается
аналогично) в предположении, что выполнено неравенство
i j

x < Bj. Построим пару вспомога-
i 1 i
тельных допустимых векторов (X1,Y), X1 = (x1,
x2,…, xj+δ, xj+1–δ,…, xn), Y= (y1, y2,…, yn), где δ выбрано следующим образом: 0 < δ < Bj –
1
i j

x .
i 1 i
Подсчитаем и оценим разность F(X ,Y) – F(X,Y):
217
Оптимизация ритмичности производства с двумя типами сырья
F(X1,Y) – F(X,Y)= f(xj+δ+yj) – f(xj +yj) +
+f(xj+1– δ+yj+1) – f(xj+1+yj+1) = f /(θ1)δ – f /(θ2)δ =
= δ(f /(θ1) – f /(θ2)),
где
θ1 ⋴ (xj +yj, xj+δ+yj),
θ2 ⋴ ( xj+1– δ+yj+1, xj+1+yj+1).
При достаточно малом положительном δ
будем иметь xj+yj+δ < xj+1+ yj+1 – δ, то есть
θ1 < θ2, f /(θ1) < f /(θ2) и F(X1,Y) – F(X,Y) < 0, что
противоречит оптимальности пары (X,Y).
Доказательство достаточности условий A), B),
C) проведем также методом от противного. Пусть
для любых двух соседних компонент допустимых векторов (X,Y) выполняется одно из указанных трех условий A), B), C), но минимум функции F(X,Y) доставляет другая пара допустимых
векторов (U,V). Докажем, что для всех
i {1,2,…,n} будет выполняться соотношение xi +
+ yi = ui + vi, то есть F(X,Y) = F(U,V). Предположим, что xi + yi = ui + vi для i {1,2,…,k} (k < n –
– 1), но xk+1 + yk+1 > uk+1 + vk+1 (случай xk+1 + yk+1 <
< uk+1 + vk+1 рассматривается аналогично). Так
как
i n

i 1
i n

( xi  yi ) =
i 1
(ui  vi ) =Bn + Dn , то
найдется такой номер m (m < n), что xi + yi ≥ ui+ +
vi для i {1,2,…,m}, и выполняется неравенство
im

i 1
i m

( xi  yi ) >
i 1
(u i  v i ),
im
 ( x  y ) =A + C , и, следовательно,  (u  v ) < A + C , что протиi
i 1
m
i
m
im
i
i 1
m
i
m
воречит допустимости пары векторов (U,V).
Если же выполнено противоположное неравенство um+1 + vm+1 > um + vm , то оно означает в
силу условия B), что
следовательно,
im

i 1
im

i 1
i  jk

i 1
( xi  y i ) = M j k , 0 <
i n

i 1
( f ( xi )  f ( yi )).
Решение задачи ритмичной переработки
каждого типа сырья
Теорема 2. Для того чтобы пара допустимых
векторов (X,Y) доставляла минимум функции
Ф(X,Y) в задаче 2, необходимо и достаточно, чтобы для любых двух соседних компонент вектора
X выполнялось одно из следующих трех условий:
a) xj = xj+1;
b) xj < xj+1; при этом выполнено хотя бы
одно из следующих равенств:
i j
тиворечит допустимости пары векторов (X,Y).
Итак, предположение, что начиная с некоторого
номера мы имеем xi + yi ≠ ui + vi, приводит к
противоречию с допустимостью либо пары векторов (U,V), либо пары векторов (X,Y).
Следствие. Необходимые и достаточные условия теоремы 1 позволяют разбить исходную
задачу на р+1 подзадачу такого же типа, определяемую наличием p (0 ≤ p ≤ n–1) активных
[2] ограничений вида
ции Ф(X,Y) =

(ui  vi ) =Bm + Dm, и,
( xi  yi ) >Bm+Dm, что про-
M jk  M jk 1
, k  1, p  1,
(2)
jk  jk 1
где введены обозначения j0=0, M0=0, jp+1=n,
Mn=Bn.
Таким образом, в каждой из указанных выше
подзадач для всех номеров i ⋴{jk+1, jk+2,…,jk+1}
имеем условие xi + yi = z k = const. При этом
дополнительном условии можно поставить вторую задачу – задачу оптимизации ритмичности
переработки каждого из двух видов сырья. Для
простоты формулировки этой задачи будем
считать, что в первой задаче число p активных
ограничений равно нулю, то есть xi + yi = z1 =
Bn  Dn
=
для всех i ⋴ {1,2,…,n} . Тогда втоn
рая задача будет состоять в нахождении такой
пары векторов X=(x1,x2,…,xn) ∈ D, Y = (y1,y2,
…,yn) ∈ G (при дополнительном условии xi + yi =
Bn  Dn
=
= const для всех i ⋴ {1,2,…,n}), коn
торая доставляет минимальное значение функ-
(1)
но xm+1 + ym+1 < um+1 + vm+1. Если при этом
um+1 + vm+1 ≤ um + vm , то получим неравенство
xm + ym > xm+1 + ym+1, а это означает в силу условия C), что
zk 
i j

x = Bj,
i 1 i
i 1
yi =C j,
c) xj > xj+1; при этом выполнено хотя бы одно из следующих равенств:
i j
i j


x = Aj,
i 1 i
i 1
yi =D j.
Доказательство необходимости условий a),
b), c) проведем методом от противного. Пусть
пара допустимых векторов (X,Y) доставляет минимум функции Ф(X,Y), но нашлась пара соседних компонент вектора X, для которых не выполнено ни одно из этих условий. Это значит,
что либо xj < xj+1, но при этом выполняются неравенства
i j

x < Bj,
i 1 i
i j

i 1
yi > Cj, либо xj >
< j1 < j2 <…< j p < n, где M jk равно А jk + С jk
> xj+1, но при этом выполняются неравенства
или В jk + D jk . Оптимальный вектор Z = X + Y
имеет р+1 постоянное значение (режим работы) z k :

i j
x > > Aj,
i 1 i
i j

i 1
y i < Dj .
Рассмотрим первый вариант (второй рассматривается аналогично). Поскольку выполня-
218
А.А.Боровков, В.П.Савельев
Bn  Dn
= const для всех
n
i ⋴ {1,2,…,n}, в этом случае имеем также неравенство y j > y j+1. Построим пару вспомогательных допустимых векторов (X1,Y1), X1 = (x1, x2,…,
xj+δ, xj+1–δ,…, xn), Y1 = (y1, y2…, yj – δ, yj+1 +
+ δ,…, yn), где δ выбрано следующим образом:
ется условие xi + yi =
i j

0 < δ < min{Bj –
i 1
xi ,
i j

i 1
1
yi – Cj}. Подсчи-
1
таем и оценим разность F(X ,Y ) – F(X,Y):
F(X1,Y1) – F(X,Y) = f(xj+δ) – f(xj) + f(xj+1 – δ ) –
– f(xj+1) + f(yj–δ) – f(yj) + f(yj+1+ δ) – f(yj+1) =
=f / (θ1)δ – f / (θ2)δ – f / (θ3)δ + f / (θ4)δ = δ(f / (θ1) –
–f / (θ2))+ δ(f / (θ4) – f /(θ3)),
где
θ1 ⋴ (xj , xj+δ), θ2 ⋴ (xj+1– δ, xj+1), θ3 ⋴ ( yj–δ, yj),
θ4 ⋴ (yj+1, yj+1+ δ).
При достаточно малом положительном δ будем иметь xj + δ < xj+1 – δ и yj – δ > yj+1 +δ, то есть
θ1 < θ2 , θ4 < θ3 и F(X1,Y1) – F(X,Y) < 0, что противоречит оптимальности пары (X,Y).
Доказательство достаточности условий a),
b), c) проведем также методом от противного.
Пусть для любых двух соседних компонент
допустимых векторов (X,Y) выполняется одно
из указанных трех условий a), b), c), но минимум функции Ф(X,Y) доставляет другая пара
допустимых векторов (U,V). Докажем, что для
всех i ⋴ {1,2,…n} будет выполняться соотношение xi = ui, то есть (X,Y) = (U,V). Предположим,
что xi = ui для i ⋴ {1,2,…,k} (k < n – 1), но xk+1 >
> uk+1 (случай xk+1 < uk+1 рассматривается аналогично). Так как
i n

x =
i 1 i
i n

i 1
im
i 1
xi >
i m

i 1
тельно,
im

i 1
ui ,
(3)
но xm+1 < um+1. Если при этом um+1 ≤ um , то получим неравенство xm > xm+1, а это означает в
im

i 1
xi = Am, и, следова-
ui < Am, что противоречит допус-
тимости пары векторов (U,V). Если же выполнено противоположное неравенство um+1 > um ,
то оно означает в силу условия b), что
=Bm, и, следовательно,
im

i 1
im

i 1
ui =
xi > Bm, что про-
тиворечит допустимости пары векторов (X,Y).
Итак, предположение, что начиная с некоторого
номера мы имеем xi ≠ ui, приводит к противоречию с допустимостью либо пары векторов
(U,V), либо пары векторов (X,Y). Отметим, что в
доказательстве необходимых и достаточных
условий теоремы 2 практически указан алгоритм последовательных приближений нахождения оптимальных планов переработки каждого
типа сырья.
Заключение
Задача ритмичной переработки сырья двух
типов при неритмичных поставках и ограниченных объемах складов решена в два этапа. На
первом решена задача суммарной ритмичной
переработки сырья. Решение этой задачи позволило решить и вторую задачу – задачу оптимальной ритмичной переработки каждого из
двух типов сырья.
Список литературы
ui = Bn, то най-
дется такой номер m (m < n), что xi ≥ ui для
i ⋴ {1,2,…,m}, и выполняется неравенство

силу условия с), что
1. Савельев В.П. Оптимизация производства в
смысле ритмичности и минимального числа переключений режимов работы // Вестник ННГУ. 2007.
№ 4. С. 115–119.
2. Карманов В.П. Математическое программирование. М.: Наука, 1980. 256 с.
OPTIMIZATION OF SMOOTH PRODUCTION FLOW WITH TWO TYPES OF RAW MATERIALS
A.A. Borovkov, V.P. Savelyev
Two production planning problems (optimization of an overall smooth production flow and optimization of the
smooth production flow of each raw material) have been solved for an enterprise processing two types of raw materials.
The solution of the first problem as a problem of convex programming essentially facilitates the solution of the second
one.
Keywords: convex programming, optimality conditions.
Документ
Категория
Без категории
Просмотров
3
Размер файла
294 Кб
Теги
двумя, ритмичность, оптимизация, типам, производства, сырье
1/--страниц
Пожаловаться на содержимое документа