Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 47 стр.

2. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                  I (u ) = c, u ® min (max), u Î R n ,
                                   a1 , u £ b1 ,L, am , u £ b m ,
                                   am+1 , u ³ b m+1 ,L, ak , u ³ b k ,
                                   ak +1 , u = bk +1 ,L, a s , u = b s ,
                                  u% ³ 0.

     Или по-другому. Обозначим

                 æ a11 L a1n ö÷        æam+11 L am+1n ö÷    æ ak +11 L ak +1n ö÷
                 çç              ÷÷    çç                ÷÷ çç                 ÷
            A = çç L L L ÷÷ , A = çç L L L ÷÷ , A = çç L L L ÷÷÷ ,
              *                     **
                  çç              ÷     çç                ÷  çç                ÷
                   çèam1 L amn ÷÷ø       çè ak 1 L akn ÷÷ø    çè a s1 L a sn ø÷÷

                                        æ b1 ö÷         æb m +1 ö÷    æb k +1 ö÷
                                        çç ÷            çç       ÷    çç       ÷÷
                                               ÷                 ÷
                                 b* = ççç L÷÷ , b** = ççç L ÷÷ , b = ççç L ÷÷ .
                                         çç m ÷÷         çç k ÷÷÷      çç s ÷÷÷
                                          çèb ø÷          çè b ø÷       çè b ø÷

      Тогда

                                  I (u ) = c, u ® min (max), u Î R n ,

                                 A*u £ b* , A**u ³ b* , Au = b , u% ³ 0.

                    æ A* ÷ö
                    çç ÷
      Матрица A = ççç A** ÷÷÷÷ размера s ´ n называется матрицей коэффициентов, а
                     çç ÷
                      çè A ÷ø

               æ b * ÷ö
               çç ÷
                      ÷
вектор   b = çççb** ÷÷ -вектором правых частей ограничений задачи линейного
                çç ÷÷÷
                 çè b ÷ø

программирования. В дальнейшем строки матриц A* , A** , A будем нумеровать
теми же номерами, какие они имеют как строки матрицы A , а элементы
столбцов b* , b** , b - как элементы столбца b .

      В линейном программировании принята следующая терминология.
Линейная      форма     I (u )      называется              целевой        функцией,   вектор   u Î Rn ,

удовлетворяющий всем ограничениям задачи, - допустимым вектором,
множество U всех допустимых векторов - допустимым множеством. Задача
линейного программирования называется допустимой, если U ¹ Æ . В случае,


                                                       47