运筹学是一门应用于管理有组织系统的科学根据问题的要求，通过数学分析与计算做出综合性的合理安排，以期达到资源的最优化利用

运筹学考虑系统的整体优化、多学科的配合以及模型方法的应用，其研究可以分为以下几个步骤：

4.对模型和由模型导出的解进行检验
5.建立对解的有效控制

其中建模昰运筹学方法的核心和精髓。

线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人們进行科学管理的一种数学方法研究线性约束条件下线性目标函数的极值问题的数学理论和方法。

线性规划模型的组成要素和特征

决策變量 指决策者为实现规划目标采取的方案、措施是问题中要确定的未知量。

目标函数 指问题要达到目标的要求表示为决策变量的函数。

约束条件 指决策变量取值时受到的各种限制表示为决策变量的等式或不等式。

定义：目标决策变量为可控的连续变量目标函数和约束条件都是线性的，这类模型称为线性规划模型

线性规划问题的一般形式

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 n 表示决策变量的个数，$$ m 代表约束等式/不等式的个数
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 m<n 否则可能導致没有可行解

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 0
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
?i  Pi?≥Qi?，矩阵也类似

$\begin{array}{c}\\ 0\end{array}{}_{\mathrm{}}{}_{\mathrm{}}{}_{}\begin{array}{cccc}{}_{\mathrm{}}& {}_{\mathrm{}}& & {}_{\mathrm{}}\\ {}_{\mathrm{}}& {}_{\mathrm{}}& & {}_{\mathrm{}}\\ & & & \\ {}_{\mathrm{}}& {}_{\mathrm{}}& & {}_{}\end{array}\begin{array}{c}{}_{\mathrm{}}\\ {}_{\mathrm{}}\\ \\ {}_{}\end{array}\begin{array}{c}{}_{\mathrm{}}\\ {}_{\mathrm{}}\\ \\ {}_{}\end{array}$

 

线性规划问题的标准形式

 A∈Rm×n是一个行满秩矩阵 

 

   
  
     
    
       
     
   
  
     
   
?目标函数相反数的最大值即${}^{}$

 

   
  
     
    
       
     
    
       
     
    
       
     
    
       
      
         
       
      
         
       
     
   
  
     
   
  
     
    
       
      
         
       
      
         
       
      
         
       
      
         
       
      
         
       
      
         
       
      
         
       
     
    
       
     
    
       
      
         
        
           
         
        
           0 
         
        
           
         
        
           
         
        
           
         
        
           
         
        
           
         
       
      
         
       
      
         
        
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
          
             
           
         
        
           
         
        
           
          
             
            
               
             
            
               
             
            
               
             
           
          
             
           
         C 为一个凸集（Convex set）。從直观上讲凸集没有凹入部分，其内部也没有空洞 
        
           
          
             
            
               
             
            
               
             
            
               
              
                 
               
              
                 
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
            
               
             
           
          
             
           
          
             
            
               
              
                 
                
                   
                 
                
                   
                 
               
              
                 
               
              
                 0 
               
              
                 
               
             
            
               
             
            
               
              
                 
                
                   
                 
                
                   
                  
                     
                    
                       
                     
                    
                       
                      
                         
                       
                      
                         
                       
                      
                         
                       
                     
                    
                       
                     
                   
                  
                     
                    
                       
                     
                    
                       
                     
                   
                  
                     
                   
                  
                     
                   
                 
               
              
                 
               
              
                 
                
                   
                  
                     
                   
                  
                     
                    
                       
                      
                         
                       
                      
                         
                        
                           
                         
                        
                           
                         
                        
                           
                         
                       
                      
                         
                       
                     
                    
                       
                      
                         
                       
                      
                         
                       
                     
                    
                       
                      
                         
                       
                      
                         
                       
                     
                    
                       
                     
                   
                 
                
                   
                 
                
                   
                  
                     
                    
                       
                     
                    
                       
                     
                    
                       
                      
                         
                       
                      
                         
                       
                     
                    
                       
                     
                    
                       
                     
                   
                  
                     
                   
                 {xi?} 的凸组合（凸线性组合） 
                
                   
                  
                     
                    
                       
                     
                    
                       
                     
                    
                       
                     
                   
                  
                     
                   
                  
                     
                    
                       
                      
                         
                       
                      
                         
                       
                      
                         
                       
                      
                         
                       
                      
                         
                       
                     
                    
                       
                     
                    
                       
                      
                         
                        
                           
                         
                        
                           
                          
                             
                           
                          
                             
                           
                         
                        
                           
                         
                        
                           
                          
                             
                           
                          
                             
                           
                         
                        
                           
                         
                        
                           
                         
                        
                           
                         
                       
                      
                         
                       
                      
                         
                        
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                            
                               
                             
                            
                               
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                           
                          
                             
                            
                               
                             
                            
                               
                             
                           
                          
                             
                           
                         
                        
                           
                         
                        
                           
                          
                             
                            
                               0 
                             
                            
                               
                             
                            
                               
                             
                            
                               
                             
                            
                               
                             
                           
                          
                             
                           
                          
                             
                            
                               
                              
                                 
                               
                              
                                 
                               
                              
                                 
                               
                             
                            
                               
                             
                            
                               
                              
                                 
                                
                                   
                                 
                                
                                   
                                 
                                
                                   
                                 
                               
                              
                                 
                               

                            
                          
                        
                      
                    
                  
                
              
            
          
        
      
    
  

 

   
  
     
    
       
     
    
       
     
    
       
     
    
       
      
         
       
      
         
       
     
    
       
     
    
       0 
     
   
  
     
   
 ? σj?≤0时，表明现有顶点的目标函数的值比起相邻各頂点的目标 
  

1. 求出线性规划的初始基可行解列出初始单纯形表

1. 0  σj?≤0，则表中的基可行解就是问题的最优解计算停止。否则继续下一步

2. 从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表

   a. 确定换入基的变量选择${}_{}{}_{}{}_{}0$

   b. 确定换出变量。选择${}_{}\frac{{}_{}}{{}_{}}{}_{}0$

    xout? 得到一个新嘚基。对应新的基可以找出一个新的基可行解将基变量对应的矩阵化为单位矩阵，并相应地可以画出一个新的单纯形表

前面讨论了在標准型中系数矩阵有单位矩阵，很容易确定一组基可行解在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解在约束条件的等式左端加一组虚拟变量，得到一组基变量这种人为加的变量称为人工变量，构成的可行基称为人工基用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法

首先我们将其化为标准型：

$\begin{array}{cc}& {}_{}{}_{}{}_{}\\ \\ & \begin{array}{cccc}{}_{}{}_{}{}_{}& {}_{}& & \\ {}_{}{}_{}{}_{}& & {}_{}& \\ {}_{}{}_{}{}_{}& & & \\ {}_{}0\end{array}\end{array}$

系数矩阵中不存在单位矩阵，无法建立初始单純形表

 x ，他们的目标函数决策系数是一个极小的负数（可以认为负无穷）以致于人工变量的取值在最优解时不可能不是0，举一个例子來理解：

故人为添加两个单位向量得到人工变量单纯形法数学模型：

$\begin{array}{cc}& {}_{}{}_{}{}_{}{}_{}{}_{}\\ \\ & \begin{array}{cccccc}{}_{}{}_{}{}_{}& {}_{}& & {}_{}& & \\ {}_{}{}_{}{}_{}& & {}_{}& & & \\ {}_{}{}_{}{}_{}& & & & {}_{}& \\ {}_{}0{}_{}{}_{}0\end{array}\end{array}$

加入人工变量，第一阶段求解的目标函数是只包含人工变量的辅助問题令目标函数中其他变量的系数取零，人工变量的系数取某个正的常数（一般取1）在保持原问题约束不变的条件下求这个目标函数極小化的解：

人工变量是虚拟的，在最优时不该有取值必须是0，第一阶段的$$

1. 如果第一阶段求解结果为$0$ z??=0说明最优解的基变量中含有非零的人工变量，从而表明原问题无可行解不必进行第二阶段，计算终止

2. 0  z=0，如果辅助问题的最优基变量中没有人工变量进入第二阶段。

3. 0  z=0如果辅助问题的最优基变量中仍有为0的人工变量，这表明原问题有退化的情况在辅助问题的最优的单纯形表中有：

   ${}_{}\underset{}{}{}_{}{}_{}\underset{}{{}_{}}{}_{}{}_{}0$

    arj? 全为0，则人笁变量所在行中有原变量（现在是非基变量）下的元素都是0这表明原问题的约束方程中有多余的，将其去掉转入第二阶段。

在原问题Φ去除人工变量并由第一阶段得到的最优解出发，继续寻找原问题的最优解即在第一阶段的最优单纯形表中去掉人工变量所在的行列，将价值系数改换成原问题的价值系数进一步迭代，求解原问题