Г.Б. БРОНФЕЛЬД

 

 

              АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ        ПЛАНА  ПРОИЗВОДСТВА                   

 

 

     При современных масштабах народного хозяйства особенно важно применение для решения экономических задач оптимальных методов, чему положено начало Л.В.Канторовичем [1].

     Рассмотрим одну из задач, поставленных Л.В.Канторовичем[1, 2],  с которой началось рассмотрение задач линейного программирования.

      Имеется множество предприятий (участков, станков)  I = {i:i = 1, 2, …, m},

на которых необходимо выпускать множество видов изделий  J = {j:j = 1, 2, …, n} в заданном ассортименте. Ассортиментный набор изделий задан вектор-столбцом {b _j0 }. Известна матрица производительности  i – го предприятия по выпуску  j -  го изделия 

[ a^/_ij ].  Пусть  x _ij – время работы  i – го предприятия по выпуску j – го изделия.

      Примем за единицу времени  время, на которое рассчитана вся программа  работы. Требуется так распределить производство изделий между предприятиями, т.е. найти вектор [ x*_ij ] ,  чтобы в единицу времени выпускалось максимальное количество полных ассортиментных наборов изделий μ  .

      Для  автомобильной промышленности эта задача может быть интерпретирована как задача распределения заданий по выпуску комплектующих изделий по заводам с  целью максимизации количества выпускаемых автомобилей на сборочном заводе.

       Итак, требуется найти вектор оптимального решения  [ х*_ij ],  максимизирующий линейную форму  L  при условиях

 

                                                        L  =    μ ,                                                            (1)

                                                   m

                                                  ∑ a^/_ij x_ij  ≥   b_j0 μ ,                                                      (2)

                                                  i=1

 

                                                                                         n

                                                     ∑  x_ij  =  1  ,                                                            (3)

                                                      j=1

                                                         x_ij   ≥   0,                                                             (4)

    

                                               a^/_ij  ≥   0,   b_j0 > 0 .                                                        (5)

 

          Преобразуем (2) – (5) к следующему виду

 

                                                   m

                                                  ∑ a_ij x_ij  ≥      μ ,                                                         (6)

                                                  i=1

 

                                                                                      n

                                                   ∑  x_ij  =  1  ,                                                              (7)

                                                    j=1

        

                                               x_ij  ≥   0,   a_ij  ≥   0  .                                                      (8)

 

      Для решения данной задачи малой и средней размерности известны эффективные методы решения [2, 3], однако возникают трудности при решении задач большой размерности. Кроме того, существует проблема вырожденности матриц условий, а также нечувствительности  известных методов к особенностям условий задачи, например, к слабозаполненности матриц.

      Далее предлагается итеративный метод, позволяющий находить оптимальное решение с точностью до   ε  за конечное число итераций, использующий идеи метода максимального элемента  [4] и метода ветвей и границ [5].

       Предлагаемый метод ориентирован на решение рассматриваемой задачи малой, средней и большой размерности; отсутствует проблема вырожденности. Эффективность метода повышается при решении задач со слабозаполненной матрицей  [a_ij ],  большой разницей в величинах  a_ij , при использовании   условия целочисленности решения  [ x_ij ].

       К преимуществам предлагаемого алгоритма можно отнести то, что решается задача меньшей размерности, чем требуется для методов линейного программирования. Так, при приведении данной задачи (6) – (8) к стандартному виду задачи линейного программирования [3]  ее размерность увеличивается с  (m+1) x (n+m+1)  до  [n(m+1)+1] x (n+m+1),  что усложняет ее решение.

      Обозначим  t -  номер итерации поиска максимального количества ассортиментных наборов    μ *    для   t   ε  T  = {t: t = 1, 2, … , R}  ,  где  t = R  при

 

                             ‌  μ^t  -   μ^t-1  ‌     ≤     ε  ,                                                               (9)

    

       μ^t  -  количество ассортиментных наборов на  t – й итерации поиска.

       В  [2, 3]  показано, что задача (1), (6) - (8)  имеет  μ^* , которому соответствует вполне определенное значение вектора  [ x*_ij ].

       Для поиска   μ^R = μ^*     c  точностью до  ε   введем итеративную процедуру

 

                                                      μ^t+1  =     μ^t  + α   ,                                              (10)

 

где  α - переменный шаг изменения   μ^t .  Процедура (10) с условием окончания поиска (9) сходится за конечное число итераций  R  к   μ^R ,  принимаемому за  μ^*    [6].

     Теперь покажем, каким образом на каждой итерации  ищется  допустимое решение

[ x^t_ij]*.

     Введем оценки

 

                                                           s^vt_ij =  a_ij d^vt_ij,                                                    (11)

 

где  d^vt_ij -  ресурс переменных  x^vt_ij ,  определяемый на  v – м шаге и t – й итерации. Здесь

v = 1, 2, …, W – номер шага поиска подходящего закрепления оценок на t – й итерации.

      В начале каждой итерации

 

                                                      ì   1,  если a_ij  >   0,   

                               d^1t_ij        =    í

            î   0, если  a_ij  =   0 .

 

 Матрицу производительности  [ a _ij ]  при переменных   x^vt_ij   преобразуем в матрицу оценок  [ s^vt_ij ].  В соответствии со структурой матрицы  [ s^vt_ij ]  введем классы оценок  s^vt_ij .

      Определение 1.  Оценкой А - класса называем оценку   s^vt_il,  ℓ  Î J, которая единственная имеет s^vt_il >0  в  ℓ  – м столбце матрицы [s^vt_ij ].

      Определение 2. Оценкой  В - класса называем оценку  s^vt_kj  ,  k Î I  которая единственная имеет    s^vt_kj   >0  в  k – й строке  матрицы  [s^vt_ij].    

        Определение 3. Оценкой С - класса называем оценку  s^vt_kl , k  ÎI, ℓ  Î J которая имеет величину  s^vt_kl  соответствующую условиям:              

 

                                            s^vt_kl     ≥     s^vt_il,     j =  ℓ,  k  ¹   i                                    (12)

 

                                             s^vt_kj      ≤   s^vt_ij                                                                 (13)

 

         Какое-то из неравенств (12), (13) должно быть строгое.

         Определение 4. Оценкой D - класса  называем оценку  s^vt_ij ,  которая имеет величину  s^vt_ij > 0 и которая не подходит под предыдущую классификацию и закрепляется по

 

                            max   s^vt_ij          для    "  i  ε  I и   "    j ε  J.                               (14)

 

 Под закреплением оценки  s^vt_ij  понимается определение для данного номера  (i, j)

  d^vt_ij ,  s^vt_kl   при   k ¹  i, ℓ ¹ j   и вводимых величинах  b^vt_j  для оценки   μ^t   в j-х строках неравенств (6).  Оценки   s^vt_ij   в процессе работы алгоритма могут переходить из  одного класса в другой.

        Введение оценок  С- и D - классов основано на применении идеи максимального элемента для поиска допустимого решения  [4].

 

                                         ОПИСАНИЕ  АЛГОРИТМА

 

       1. Оценки  s^vt_ij  матрицы   [s^vt_ij]  объединим в подмножества

 

                                I^vt_j = {  s^vt_ij  : s^vt_ij   >  0,   i  ε  I   }.        

 

Внутри  I^vt_j   оценки  s^vt_ij  пронумеруем в порядке убывания их величины. Подмножества  I^vt_j  будут соответствовать сжатым и упорядоченным  j – м столбцам матрицы   [s^vt_ij]  . Подмножества  I^vt_j  образуют множество   J^vt_M  = { I^vt_j : j  ε  J}.

        Введем множества

            

                               X^vt_j = { d^vt_ij : d^vt_ij =  x^vt_ij ,  i  ε  I}

 

для элементов  d^vt_ij,  зафиксированных в них, как значения переменных   x^vt_ij  .

        2. Определим, есть ли в подмножествах  I^vt_j оценки  А - класса. Введем величины 

b^vt_j  для оценки  μ^t   в  j – х строках неравенств (6)

 

                                                          b^vt_j  ≤   μ^t.

 

В начале каждой итерации b^vt_j = μ^t.  Пусть  s^vt_kl  - оценка  А - класса для некоторого номера

 

                                    ( k, ℓ) ε N = { (k, ℓ): k ε I,  ℓ ε J} .

 

Тогда определяем

 

                                              ì   s^vt_kl / a_kl  ,  если    s^vt_kl < b^vt_l  ,   

                               d^vt_kl   =   í                                                                            (15) 

                                              î  b^vt_l / a_kl,  если   s^vt_kl  ≥   b^vt_l  .

 

   Далее находим остаток  s^vt_kj   в подмножествах  I^vt_j

 

                                              ì   0 ,  если    s^vt_kl  ≤  b^vt_l  

                                 s^vt_{kj     =}     í

                                              î ((s^vt_kl - b^vt_l )/ a_kl ) a_kj , если   s^vt_kl  >  b^vt_l  ,  j ¹ ℓ

 

                     

и новые значения

 

                                  ì b^vt_l - s^vt_kl ,  если    s^vt_kl  <  b^vt_l  ,

                     b^vt_l   =    í    

                                  î0 ,  если    s^vt_kl  ≥   b^vt_l  .

               

      3. Определяем, есть ли в подмножествах  I^vt_j   оценки В - класса.

      Пусть  s^vt_kl  - оценка  В - класса  для некоторого номера   (k, ℓ) ε N .

Тогда

                                                    d^vt_kl   =  s^vt_kl  / a_kl   ,

                                             

                                           ì     0 ,  если    s^vt_kl  ≥   b^vt_{j  ,}

                                                    s^vt_il =  í                                                                                  (16)

                                           î    s^vt_il ,  если    s^vt_kl  <  b^vt_j  , k ¹  i,  ℓ  ¹  j,

                             

 

                                           ì b^vt_l - s^vt_kl ,  если    s^vt_kl  <  b^vt_l  ,

                              b^vt_l   =    í    

                                           î0 ,  если    s^vt_kl  ≥   b^vt_l  .

 

  4. Проверяем, не пустые ли подмножества  I^vt_j  и множество  J^vt_M .

     Может получиться, что  I^vt_j =  Æ,  а  b^vt_j  > 0,  т.е. не выполнено ограничение (6). Это означает, что решение не найдено при данном варианте закрепления оценок.  Для поиска решения осуществляем перебор возможных закреплений оценок  С- ,  D - классов в подмножествах  I^vt_j  рекурсивно по методу ветвей и границ, начиная с последнего шага  [5].  Для ускорения обнаружения ветвей закрепления оценок  s^vt_ij, не обеспечивающих выполнения ограничений (6), используем оценки  P^vt и  Q^vt_j, которые точно определяют «удачность» или «неудачность» ветви

 

                        m                             n

            P^vt =    ∑    max   s^vt_ij     -   ∑  b^vt_j  ,   для   s^vt_ij   ε  I^vt_j,                                  (17)

                        i=1    j εJ                   j=1

 

 

                        m

           Q^vt_j    =  ∑   s^vt_ij - b^vt_j ,  для    s^vt_ij   ε I^vt_j .                                                     (18)

                        i=1

 

       Оценка    P^vt  ≥ 0  является необходимой, но не достаточной оценкой выполнения ограничений (6).

        Оценка  Q^vt_j  ≥ 0  является достаточным условием выполнения (6).

        Если

                            P^vt ≥  0 ,   Q^vt_j  ≥ 0 ,                                                                      (19)

 

то поиск  допустимого решения на данной итерации продолжается.

Если

 

                  P^vt  <  0,          Q^vt_j  ≥ 0      или                                                                (20)

                   P^vt  ≥  0 ,        Q^vt_j <  0,                                                                           (21)

 

то ограничения (6) не выполняются, и начинается рекурсивный перебор возможных закреплений оценок D-  и  С - классов по методу ветвей и границ на данной  t – й итерации. Если перебор закреплений оценок  s^vt_ij не дает результатов,  переходим к пункту 8.

        5. Поиск оценок А- и В- классов.

        Если они есть, переходят к пункту 2.

        6. В оставшихся подмножествах  I^vt_j   ищем оценки  С – класса.

      Пусть  s^vt_kl - оценка С - класса по (12), (13) с номером   (k, ℓ) ε N  .

Определяем

 

                                              ì   s^vt_kl / a_kl  ,  если    s^vt_kl < b^vt_l  ,   

                                d^vt_kl   =   í                                                                            (22) 

                                              î  b^vt_l / a_kl,  если   s^vt_kl  ≥   b^vt_l  .

 

 

                                           ì     0 ,  если    s^vt_kl  ≥   b^vt_{l  ,}

                                                    s^vt_il =  í                                                                                  (23)

                                           î    s^vt_il ,  если    s^vt_kl  <  b^vt_l  ,  i  ¹ k,

 

                                          ì   0 ,  если    s^vt_kl  ≤  b^vt_l  

                             s^vt_{kj     =}     í                                                                                 (24)

                                          î ((s^vt_kl - b^vt_l )/ a_kl ) a_kj , если   s^vt_kl  >  b^vt_l  ,  j ¹ ℓ

 

 

                                           ì b^vt_l - s^vt_kl ,  если    s^vt_kl  <  b^vt_l  ,

                              b^vt_l   =    í                                                                                                                                       (25)

                                           î0 ,  если    s^vt_kl  ≥   b^vt_l  .

 

    Затем выполняем пункт 2. Если оценок  С - класса нет, переходим к пункту 7.

     7. В оставшихся подмножествах   I^vt_j  ищем оценки  D – класса  по (14).

Пусть  s^vt_kl  - оценка  D – класса  для номера   (k, ℓ) ε N . Определение  d^vt_kl ,  s^vt_il ,  s^vt_kj ,  b^vt_l   соответствует пункту 6 по формулам (22) – (25).  Затем выполняем пункт 2.

      8. В соответствии с (10) формируется новое значение  μ^t+1  до выполнения условия (9) и нахождения  μ^R  .

      Покажем возможный способ формирования переменного шага  α . Принцип формирования    α  основан на нахождении некоторого начального  μ⁰ и равномерного приближения   к   снизу,   а  при   μ^t >  μ^*, что определяется по (20), (21), применяется способ дихотомии.

      Из  (7) найдем условное среднее значение   x_ijcp

 

                                                 x_ijcp     =  m / (n + m)   .                                      (26)

 

      Из граничного значения 

 

                                                    P^vt    = 0,                                                          (27)

 

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

 

                                                       μ_гр =  b^vt_jгр                                                (28)

 

Из (17) и (27) находим

 

                             m                              n

               P^vt       =  ∑    max   s^vt_ij     -   ∑  b^vt_jгр  = 0

                             i=1      j ε  J                   j=1  

 

Или с учетом (28), (11) получаем

 

                      m            

                      ∑  max  a_ij x_ijcp  - n  μ_гр  = 0                                                              (29)

                      i=1  j ε  J                  

 

Теперь из (26) и (29) находим

 

                                                                   m            

                                   μ_гр  =   m / n (n+m)  ∑  max  a_ij  .

                                                                    i=1  j ε  J                  

     Определим исходное  μ⁰,  используемое в процедуре (10), следующим образом

 

                                               μ⁰  =   μ_гр  / 10 .

 

       Переменный шаг изменения  μ^t находим в виде

 

                                           ì 0,1 μ^t  / 10^k  при оценках        (19)                       (30)

                              α     =    í                                                                                                                 

                                           î  - ‌  μ^t  -   μ^t-1  ‌  / 2  при оценках (20), (21)            (31) 

                    

 где   k -  количество нахождений  α  по формуле  (31).

         При нахождении   μ^R   решением является

 

                                      [ x*_ij ]   =   [ d ^WR_ij ] .

 

       Приведем численный пример,  взятый из практического опыта решения задачи, описанной в  [7].

        Задан план выпуска на участке  {b_j0} ассортиментного набора 16 изделий на 20 агрегатах. Задана производительность  работы   i – х  агрегатов по  j – м изделиям  [ a^/_ij ] , а также ресурс времени работы  i -  х  агрегатов (правая часть равенств (3)).  Требуется так распределить выпуск изделий по агрегатам, чтобы за заданный ресурс времени работы агрегатов выпустить максимальное количество продукции пропорционально плановому заданию, т.е. найти [ x*_ij ]     при максимизации   μ .

       Условия задачи записываются в виде  (1), (2), (4) и несколько измененном виде (3) (см.табл.1 и 2).

 

                                                                                                                        Табл.1.

 

1,52х0701

+1,52х0801

51μ

1,52х0102

+1,52х0202

+1,52х1902

216 μ

1,52х0803

69μ

1,52х0704

33μ

1,52х0705

72μ

1,52х1806

+1,52х2006

51μ

1,52х0307

+1,52х0407

+1,52х1807

+1,52х2007

60μ

1,52х0308

+1,52х0408

+1,52х1808

42μ

1,52х1709

60μ

1,44х0310

+1,44х0410

+1,44х1310

+1,44х1410

+1,44х1810

114μ

1,52х0311

+1,52х0411

+1,52х0511

+1,52х1811

30μ

1,52х0312

+1,52х0412

+1,52х0512

+1,52х1812

90μ

1,52х0313

+1,52х0413

+1,52х0513

1,52х1713

33μ

1,52х0314

+1,52х0414

+1,52х0614

+1,52х0914

+1,52х1014

+1,52х1514

+1,52х1614

318μ

1,52х1115

+1,52х1215

+1,52х1815

24μ

1,52х1116

+1,52х1216

+1,52х1816

111μ

 

 

 

 

                                                                                                                                       Табл.2.

 

Х0102

=16

Х0202

=60

Х0307

+х0308

+х0310

+х0311

+х0312

+х0313

+Х0314

=16

Х0407

+х0408

+х0410

+х0411

+х0412

+х0413

+х0414

=60

Х0511

+х0512

+х0513

=80

Х0614

=80

Х0711

+х0704

+х0705

=80

Х0801

+х0803

=80

Х0914

=37

Х1014

=39

Х1115

+Х1116

=37

Х1215

+х1216

=39

Х1310

=40

Х1410

=18

Х1514

=40

Х1614

=18

Х1709

+Х1713

=80

Х1806

+х1807

+х1808

+Х1810

+х1811

+х1812

+х1815

+х1816

=50

Х1902

=80

Х2006

+х2007

=80

 

       В примере в правой части равенств использованы разные величины ресурсов времени, что не влияет на работу метода (см. табл.2) .

        Решение с помощью описанного метода находится за 6 итераций с 16 шагами закрепления оценок. Для рассматриваемого алгоритма программа на ЭВМ еще не закончена, однако с помощью логарифмической линейки находится значение 39 переменных (10  переменных определяется из исходных условий) за 3 часа.

        Решением является:

 

       μ   =1,08  (с точностью до 0,01);

 

       х₀₈₀₁ = 30,97;  х₀₇₀₁ = 5,39;   х₀₁₀₂ = 16,0;     х₀₂₀₂ = 60,0;      х₁₉₀₂ = 16,0;

       х₀₈₀₃ = 49,03;  х₀₇₀₄ = 23,45;   х₀₇₀₅ = 51,16;   х₁₈₀₆ = 0;          х₂₀₀₆ = 36,24;

       х₀₃₀₇ =  0;         х₀₄₀₇ =  0;       х₁₈₀₇ = 0;           х₂₀₀₇ = 43,76;    х₀₃₀₈ = 0;

       х₀₄₀₈ =  29,84;   х₀₁₀₈ =  0;      х₁₇₀₉ = 42,63;     х₀₃₁₀ = 0;    х₀₄₁₀ = 30,16;

       х₁₃₁₀ =  0;         х₁₄₁₀ =  0;       х₁₈₁₀ = 0;           х₀₃₁₁ = 0;    х₀₄₁₁ = 0;

       х₀₅₁₁ =  21,32;         х₁₈₁₁ =  0;       х₀₃₁₂ = 0;           х₀₄₁₂ =  0;    х₀₅₁₂ = 0;

       х₁₈₁₂ =  5,27;         х₀₃₁₃ =  0;       х₀₄₁₃ = 0;           х₀₅₁₃ =  0;    х₁₇₁₃ = 37,37;

       х₀₃₁₄ =  16,0;         х₀₄₁₄ =  0;       х₀₆₁₄ = 80;           х₀₉₁₄ =  37;    х₁₀₁₄ = 39;

       х₁₅₁₄ =  40;         х₁₆₁₄ =  18;       х₁₁₁₅ = 0;           х₁₂₁₅ =  0;    х₁₈₁₅ = 17,05;

       х₁₁₁₆ =  37;         х₁₂₁₆ =  39;        х₁₈₁₆ = 27,68.

 

         Решение  указанного численного примера на ЭВМ ЕС-1020 с использованием пакета линейного программирования LPS/30 занимает около 2 часов.

         Предлагаемый алгоритм позволяет решать некоторые задачи нелинейного программирования, в частности задачу [7] с невыпуклой областью допустимых  решений.

 

                                               ЛИТЕРАТУРА

 

1.     Канторович Л.В.  Математические методы организации и планирования производства. Л., ЛГУ, 1939.

2.     Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М., АН СССР. 1960.

3.     Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения.М., «Наука», 1969.

4.     Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. М.,   «Советское  радио», 1974.

5.     Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М., «Наука», 1969.

6.     Беленький В.В., Волконский В.А. и др. Итеративные методы теории игр и программирования. М., «Наука», 1974.

7.      Автоматизированная система управления технологическим процессом производства листа из полистирола на Нелидовском заводе пластмасс. Алешин А.Я. и др. – В кн.:«Всесоюзное научно-техническое совещание по автоматизации  технологических процессов химической промышленности» (3-5 сентября 1974 г., Северодонецк). Тезисы докладов. Первая секция «Научно-технические и организационные проблемы разработки АСУТП». М., НИИТЭХИМ, 1974, с.127-145.