线性规划运筹学课件

运筹帷幄之中决胜千里之外线性规划LinearProgramming运筹学课件第1章线性规划线性规划问题提出可行区域与基本可行解单纯形算法单纯形法进一步讨论1.1线性规划问题提出线性规划例题

生产计划问题线性规划模型

一般形式

规范形式

标准形式

形式转换

概念

图解法

1.1.1线性规划例题某工厂用三种原料生产三种产品，已知的条件如表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354

生产计划问题问题分析模型1.1.2

线性规划模型

一般形式注释

向量形式

矩阵形式

标准形式

变一般形式为标准形式约束转换实例目标转换变量转换不等式变等式松弛变量剩余变量几个概念图解法例解线性规划

注释解可能出现的情况：

可行域是空集可行域无界无最优解

最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解1.2可行区域与基本可行解

可行域的几何结构

基本可行解与基本定理可行域的几何结构基本假设凸集可行域的凸性基本假设凸集与顶点基本可行解与基本定理定义基本定理问题例:基本解不一定是可行解基本定理1.3单纯形算法算法的三个阶段算法步骤单纯形表算例阶段1：确定初始基可行解假设问题引入松弛变量得则，可设则，约束变为则，初始基可行解为则阶段2：由一个基可行解到另一个设初始基可行解又设前m个坐标非0，即因为是基可行解，所以若我们总假定有方法使基矩阵是单位矩阵，则上式展开为因为是基，所以，其余向量可由它线性表示对上式乘以正数上式与相加得从中可找到另一个满足约束的点要使它成为基可行解，需要满足，且至少有一个取等号。又因为，若aij<0，则条件自然满足，所以，只需取即可。阶段3：最优性检验和解的判别把基可行解分别代入目标令（1）当所有的说明：现有顶点的目标函数值比相邻各顶点的目标函数值都大，现有顶点对应的基可行解即为唯一最优解。（2）当所有的又对某个非基变量有则，无穷多最优解。（3）若存在某个又无界解。的所有分量算法步骤单纯形表例子例：解：0x321/50[14/5]1-3/510x18/512/501/5cj－zj010-25x23/2015/14-3/1410x1110-1/72/7cj－zj00-5/14-25/14cj10500cBxBbx1x2x3x40x3934100x48[5]201cj－zj10500单纯形法的矩阵描述考虑问题引入松弛变量得设B是一个可行基，若则对应于B的变量向量则同时将C也分成两块所以,有所以，LP问题写成将（2）移项后得将（3）左乘将（4）代入目标（1）得单纯形法进一步讨论两阶段法大M法退化说明为什么要做进一步讨论两阶段法第一阶段：不考虑原问题是否存在基可行解，给原问题加入人工变量，并构造只含人工变量的目标函数w，并要求实现最小化。若求解得w=0，说明原问题存在基可行解，可进入第二阶段，否，原问题无可行解，停。第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换成原问题的目标函数系数，作为第二阶段的初始表。例算例解:第一阶段

cj0000011cBxBbx1x2x3x4x5x6x70x4111-2110001x63-4120-1101x71-20[1]0001

Cj-zj6-1-30100

cj00000110x4103-20100-11x610[1]00-11-20x31-2010001

Cj-zj0-1001030x412[3]001-22-50x210100-11-20x31-2010001

Cj-zj0000011所以，w=0第二阶段

cj-31100cBxBbx1x2x3x4x50x412[3]001-21x210100-11x31-20100

Cj-zj-10001-3x141001/3-2/31x210100-11x390012/3-4/3

Cj-zj0001/31/3大M法在一个LP问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（－M），这样目标要实现最大化时，必须把人工变量换出基，否则不能最大化。采用大M法，引入人工变量，构造新的线性规划问题（LP）单纯形表如下例：cj-31100MMcBxBbx1x2x3x4x5x6x70x4111-211000Mx63-4120-110Mx71-20[1]0001Cj-zj-3+6M1-M1-3M0M000x4103-20100-1Mx610[1]00-11-21x31-2010001

Cj-zj-11-M00M03M-1

cj-31100MM0x412[3]001-22-51x210100-11-21x31-2010001

Cj-zj-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3

Cj-zj0001/31/3M-1/3M-2/3关于退化的说明单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，如此