Составить математическую модель линейной производственной задачи

            1/4x1+ x2 + x3 + 1/4x7   = 162/4

Приравняв к нулю свободные переменные х2, х3, х4, х7, получаем базисное неотрицательное решение, совпадающее с (10), причем первые четыре компоненты его определяют новую производственную программу

                       x1=38, x2=0, x3=0, x4=0         (12)

Исследуем, является ли эта программа наилучшей, т.е. обеспечивает ли она наибольшую прибыль. Для этого выразим функцию прибыли (1) через новые свободные переменные х2, х3, х4, х7.

Из последнего уравнения системы (11) выражаем базисную переменную х1 через свободные и подставляем в (1). Получаем: 

   z = 48*(38-5/6x2 - 1/6x3 -1/6x7) +30x2+29x3+10х4 =

= 1824 - 40x2 -8x3 -8x7 +30x2 +29x3 +10x4 = 1824-10 x2+21 x3+10 x4-8 x7      (13)

Видим, что программа (12) не является наилучшей, так как прибыль будет расти, если мы начнем производить или третью, или четвертую продукцию, но наиболее быстро функция z растет при возрастании х3. Поэтому принимаем х3 в системе (11) за разрешающую неизвестную, находим разрешающее уравнение

min (24,30,228) = 24       -    разрешающее ур-ние 1

Важно обратить внимание на то, что эти преобразования можно выполнить очень просто. Представим соотношение (1) в виде уравнения

       -48x1-30x2-29x3-10х4 =0- z    (14)

и припишем его к системе (4). Получается вспомогательная система уравнений

              3x1 + 2x2 + 4x3 + 3x4  + x5   = 198

                        2x1 + 3x2 +  x3   + 2x4 + x6   = 96            (15)

                6x1 + 5x2 +  x3           + x7     = 228

     -48x1-30x2-29x3-10х4 =0- z   

Теперь, если посмотреть на систему уравнений (15), то достаточно умножить третье уравнение системы (15) на 8 и прибавить к четвертому, получим

48 x1+40 x2+8 x3+8 x7=1824

10 x2-21 x3-10 x4+8 x7=1824 - z       (16)

Таким образом, приписав к системе (11) уравнение (16), получаем:

              -0,5x2 + 3,5x3  + 3x4 + x5 - 0,5 x7  = 84

               4/3x2 +2/3 x3  +2x4  + x6 - 1/3x7 = 20                 (17)   

               x1+ 5/6x2 + 1/6x3 +1/6x7   = 38

       10 x2-21 x3-10 x4+8 x7=1824 - z      

Очевидно, если имеется хотя бы один отрицательный коэффициент j при какой-нибудь переменной xj в последнем уравнении системы (17), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (13) мы выяснили, что следует начинать производить продукцию третьего вида, т.е. фактически мы нашли в последнем уравнении системы (17) наименьший отрицательный коэффициент

min(j<0) = min(-21,-10) = -21 = 3                           

и решили перевести свободную переменную х3  в число базисных, для чего, определили разрешающее уравнение и указали разрешающий элемент а13=4.

Учитывая сказанное выше, теперь мы будем преобразовывать не систему (11), а всю вспомогательную систему (17), по правилу прямоугольника:

аij = аrj/ аrs         ,  r = i

2

а11= 0

а12 = -1/7

а13 =1

а14 =6/7

а15 =2/7

а16 = 0

а17 =  -1/7

2

аij = аij – аis/ аrs * аrj   ,    i≠r

2

а21= 0

а22 =30/21

а23 =0

а24 =10/7

а25 = -4/7

а26 =1

а27 =  -5/21

2

2

а31 =1         

а32 = 6/7

а33=0   

а34 = -1/7

а35 = -1/21

а36 =0

а37 =  4/21

2

2

а41 = 0         

а42 =7   

а43=0    

а44 =8

а45 =6

а46 =0

а47 =  5

2

bi = br/ аrs      ,   r = i

b1= 24

bi = bi - аis/ аrs* br           ,  i≠r

b2 = 4

b3 = 34

b4 = 2328-z

       -1/7x2 + x3  + 6/7x4 +2/7 x5 – 1/7 x7  = 24

        30/21x2 +10/7 x4  - 4/21x5  + x6 - 5/21x7 = 4                 (18)   

         x1+ 6/7x2 – 1/7x4- 1/21x5  +4/21x7  = 34

         7 x2+8 x4+6x5 +5 x7=2328 - z      

x1=34, x2=0, x3=24, x4=0, x5=0, x6=4, x7=0         (19)

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

x1=34, x2=0, x3=24, x4= 0             (20)

и остатки ресурсов:

первого вида              х5=0

второго вида              х6=4                                                                                                  (21)

третьего вида              х7=0

В последнем уравнении системы (18) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные

              Z = 2328 -7 x2-8 x4-6x5 -5 x7           (22)

то становится совершенно очевидным (в силу того, что все xj0), что прибыль будет наибольшей тогда, когда x2=0,  x4=0, x5=0, x7=0                      (23)

Это означает, что производственная программа (20) является наилучшей и обеспечивает предприятию наибольшую прибыль   zmax = 2328                                              (24)

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

Процесс решения обычно записывается в виде симплексной таблицы, где представлены расширенные матрицы вспомогательных систем уравнений     (15)    (17)    (18):

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

Воспользуемся тем, что в оптимальной производственной программе х2=0, х4=0. Предположим, что вторую и четвертую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

X (x1, x3) - ?

Z = 48x1 + 29x3  max

            3x1 + 4x3     198                       x3  198/4-3/4 x1    I

                    2x1 +  x3      96                          x3   96 - 2x1          II                                     

            6x1 +  x3     228                        x3    228 - 6x1      III

                      x1  0, x2  0

     x2

     96

    198/4

                                                          A

                                                           38       48            66                                                     x1

                                                               III      II                 I

Точка A находится на пересечении I и III линий.

     x3 = 198/4-3/4 x1                          x1    =34                            

     x3  = 228 - 6x1                      x3  =24

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

Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:

24                        198                            2/7    0   -1/7                 

Н =      4                  В=    96              Q-1 =  -4/21    1    -5/21

            34                         228                        -1/21    0    4/21

24             2/7    0   -1/7               198                                         

             4     =  -4/21    1    -5/21      *      96

            34          -1/21    0    4/21              228

Обращенный базис сходится.

14