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

Рассматривается следующая экстремальная задача: найти минимум mnm

L (x) = 52 52 Vij (xij ' ■ 52''i(xi)

i=1 j=1

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

52xij = Xi, i = 1, 2,...,m,   ^Xij = bj, j = 1, 2,...,n,(2)

j=1

xij > 0, i = 1, 2 ,...,m,   j = 1, 2 ,...,n, где x = |xijImn ; vij(xij) (i = 1, 2,...,m, j = 1, 2, ...,n) — выпуклая непрерывная возрастаю щая функция xij Е [0 ,bj ] (j = 1, 2, ...,n); ^i (xi) (i = 1, 2, ...,m) — выпуклая непрерывная на

(0,t 1 b j ]:

всей числовой оси функция, имеющая разрыв в нуле, x _i ∈

• 7 / x \ ^ i ( x i ) + T i , x i >  0 ,     .

^i(xi )=   0            x. =0 i = 1, 2 ,...,m bj ,Ti — известные постоянные.

Предполагается, что nm E bj = Exi. j=1       i=1

Экономическая постановка задачи (1), (2) аналогична приведенной в [1, 2].

Исследованию задачи (1), (2) посвящены работы [3–6], в которых рассматривались различные случаи.

Вследствие нелинейности ф ,, ( x ,, ) ( i = 1 , 2 , ...,m, j = 1 , 2 , ...,n ) и разрывности функции ^ i ( x , ) ( i = 1 , 2 ,..., m ) в нуле рассматриваемая задача имеет большое количество экстремумов, поэтому для ее решения требуется применение специальных методов и алгоритмов.

Для решения задачи (1), (2) используем метод последовательных расчетов [6]. Введем совокупность множеств ш С I = {i = 1 , 2 , ...,m} , для каждого подмножества ш Е I построим функционал

n f (ш ) = £ 5>j (x,,) + ^*i (Xi) + £ t,.(3)

i£w j=1               i£wi

Наименьшее значение функционала f ( ш ) при условиях

n

Xij = bj, j = 1, 2,...,n, ^Xij = Xi, i Е ш, Xij > 0, i Е ш, j = 1, 2,...,n(4)

i£wj обозначим через p (ш).

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

s(ш 1 ,ш2) = p(ш 1) + p(ш2) - p(a) -p(в) < 0,(5)

где ш 1 ,ш ₂ — произвольные подмножества множества I , такие что a = ш 1 U ш ₂ , в = ш 1 П ш ₂ .

Исходную задачу можно заменить следующей эквивалентной задачей: среди всех множеств ш С I требуется найти множество ш * , такое что p ( ш * ) < p ( ш ) для всех ш С I , т. е. требуется определить функцию

p ( ш * ) = min {p ( ш ) } .

ω ⊂ I

Если в качестве метода решения использовать простой перебор, то число возможных вариантов ш С I будет равно 2 ^m , поэтому при больших значениях m этот метод практически неприменим вследствие большого количества подмножеств ω.

Метод последовательных расчетов заключается в замене полного перебора вариантов направленным частичным перебором, позволяющим отбрасывать большие группы вариантов, заведомо не дающих оптимума [6]. В основе метода последовательных расчетов лежит следующая

Теорема. Пусть функция p ( ш ) удовлетворяет условию (5), ш * — множество, на котором эта функция достигает глобального минимума. Тогда для любой конечной последовательности { ш , } , содержащей ш * , такой что ш , С ш , ₊₁ , функция p ( ш ) монотонно убывает до множества ω ^∗ и монотонно возрастает после множества ω ^∗ .

Использование данной теоремы позволяет исключить из рассмотрения целые массивы вариантов. Действительно, пусть для некоторых ω ₁ и ω ₂ , таких что ω ₁ ⊂ ω ₂ ⊂ I, найдены значения p ( ш 1 ) и p ( ш 2 ) . Тогда при p ( ш 1 ) < p ( ш 2 ) из рассмотрения можно исключить 2 m V ^{х 2} I вариантов ш D ш 2 . Если p ( ш 1 ) > p ( ш 2 ) , то можно отбросить 2 ^{| ш 1} | вариантов ш С ш 1 . Обычно порядок перебора в методе последовательных расчетов не превышает m ³ , что существенно меньше объема полного перебора 2 m [6].

Докажем применимость метода последовательных расчетов при решении поставленной задачи. Из определения множеств а = ш 1 иш 2 , в = ш 1 Пш 2 следует, что имеет место равенство

Е т . + ^T i = ^T i + £ T i .

i ∈ ω 1 i ∈ ω 2 i ∈ α i ∈ β

Учитывая (6), неравенство (5) можно записать в виде s (ш 1 ,ш 2) = min ЕЕVij (xij) + 52 * (xi) + mm EEvij (xij) + 52* (xi) -i∈ω1 j=1              i∈ω1                      i∈ω2 j=1              i∈ω2

• ^- ™ⁱⁿ) 52 52 v j ⁽ x ij ) + 52 * ⁽ x i ) r ^{- m}jⁿi 52 52 v j ⁽ x j ) + 52 * ⁽ x i ) f ^{— 0} • ⁽⁷⁾ i ∈ α j =1 i ∈ α i ∈ β j =1 i ∈ β

Обозначим оптимальный план задачи (3), (4) на множестве α через xiαj , а на множестве β — через xiβj . Тогда для доказательства выполнения условия (7) достаточно показать, что n   n   nn s (ш 1 ,ш 2) = £ £vj (xj) + E v>2 (x^j) - E E*« (xaj) - E E*« (xe)+ i∈ω1 j=1               i∈ω2 j=1               i∈α j=1               i∈β j=1

+ E * ( x " ¹ ) + E * ( x " ² ) - E * ( x a ) - E » i ( x e ) - о . (8)

i∈ω1               i∈ω2               i∈αi

Здесь xiωj1 , xiωj2 — некоторые допустимые планы задачи (3), (4) на множествах ω1 и ω2, nn   nn

α          α β          β      ω1          ω1      ω2

xi           xij, xi           xij, xi            xij , xi j=1              j=1               j=1

Отметим, что, поскольку функции * i ( x i ) являются выпуклыми вниз и возрастающими, для каждой из них справедливо следующее неравенство:

*i(x 1 - А)+ *i(x2 + А) — *.(x 1) + *i(x2) при x 1 > x2, i = 1, 2, •••,m,(9)

где 0 — А — |x 1 - x 2 1.

Аналогично для функции v ij ( x ij ) , i = 1 , 2 ,...,m, j = 1 , 2 ,...,n имеет место неравенство (9).

Предположим, что для задачи (3), (4) на множествах ω1 и ω2 существуют допустимые планы xiωj1 , xiωj2 , удовлетворяющие условиям xt = x^, i e а\ш 2, j = 1, 2 ,...,n, x^ = Xaj, i E a\w 1, j = 1, 2,...,n,                            (10)

x j + x j = x a + 4, i ^e 3, j = 1 , ² ,... ^,n ;

x a < x t ¹ , x t ² < х в , i e в.                               (11)

Тогда, используя условия (10), из (8) получаем равенства n   n   nn s (. 1,ш 2) = E Exj (xs)+E E x, (xs) - E Ex., (xa,) - E E x, (^j)+

• - е в j =1               - е в j =1               - е в j =1               - е в j =1

+e ф- (x"1) + E * (xt2) - E * (xa) - E x- (xв) ■ (12) i∈β              i∈β              i∈βi

Из (12), используя свойства выпуклости функций ф-,(x-j) и ф-(x-) (9), находим n   nnn s 1 (ш 1 ,ш 2) = Е Е x-j (x^j)+Е Е х., (xt*) - Е Е x-j (xaj) - Е Е х., (x-j) < о,

• -ев j=1              -ев j=1              -ев j=1              -евj

s 2 ⁽ ш 1 ,ш 2 ) = e ^ф - ^{( x t 1} ) + E ^ф - ^{( x t 2} ) ^- E ^ф - ⁽ x ^a ) ^- E ^ф - ⁽ x ) < ⁰ .

i∈β              i∈β              i∈βi

Таким образом, достаточное условие (5) применимости метода последовательных расчетов доказано в предположении о существовании допустимых планов x _i ^ω _j ¹ , x _i ^ω _j ² , удовлетворяющих условиям (10), (11).

Остается доказать существование таких допустимых планов для рассматриваемой задачи. Доказательство существования допустимых планов x _i ^ω _j ¹ и x _i ^ω _j ² , удовлетворяющих соотношениям (10), (11) для рассматриваемой задачи, аналогично доказательству, приведенному в работе [7].