运筹学——第2讲线性规划模型.pptVIP

第1章 线性规划 本章要求： 1.掌握并熟练应用线性规划的模型处理实际问题 2.掌握线性规划的图解法 3.掌握软件求解线性规划 4.了解线性规划对偶问题的基本性质 5.理解有关灵敏度分析内容 关于“线性规划” 英文名：Linear Programming,缩写为LP 自1947年丹齐格提出求解一般线性规划的有效方法——单纯形法后，得到迅速发展，成为运筹学应用最广泛的分支。 特点： 1.应用广泛 2.模型简单易建 3.求解方法成熟 例3：生产计划问题 某厂计划安排生产A，B两种产品，已知生产单位产品的利润与所需的劳动力，设备台时及原材料的消耗如图所示。问应该如何安排生产获利最大？ LP模型： 例4：饮料配制计划 大众酒吧自行配制生产甲，乙两种饮料，管理层决定下月总产量至少达到350升。甲饮料每升的制造成本为2元，制造时间需2小时，乙饮料每升的制造成本为3元，制造时间需1小时，下月总生产时间为600小时。此外，下月有一位客户已预定甲饮料125升。试为管理层制定满足客户要求且制作成本最小的生产计划。 线性规划模型？ LP模型： 例6：运输问题 A1，A2两个煤矿给B1，B2，B3三个城市供煤，各煤矿产量和各城市需求量以及各地之间的单位运价如下表所示： 问应该如何调运，才能既满足城市需求，又使总运费最小？线性规划模型？ 用图解法求例3：生产计划问题 用图解法求例4:饮料配制计划 作业 复习：LP的图解方法与标准型。 预习： 单纯形法与对偶理论。 作业：习题 1.1；习题 1.2 引例：LP的应用 例1：大通曼哈顿银行员工工作安排 例2：航空公司机组人员排程 利用LP安排的结果 建立线性规划模型 （1）确定决策变量：通常为非负，决策变量的一组 取值称为线性规划的一组解，表示一个方案。 （2）确定目标函数z：它是决策变量的线性函数，我们要使它取最大值或最小值。 （3）确定约束条件：可用决策变量的一组线性等式或不等式表示。 解 例 将下列线性规划化成标准型 得到 例、将下列线性规划模型化为标准型 s.t. 例、将下列线性规划模型化为标准型 s.t. 令x2=-x4,x3=x5-x6 s.t. 可行解： 满足约束条件(b)、(c)的解X=（x1，?，xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。 最优解：使目标函数(a)达到最大值的可行解称为最优解。 （a） （b） （c） 1.1.2 线性规划问题的基本概念 基：设Am×n (nm)为约束方程组(b)的系数矩阵，其秩为m。Bm×m 是矩阵A 中的一个m×m 阶的满秩子矩阵(|B|不等于0), ，称B 是线性规划问题的一个基。不失一般性，设 B 中的每一个列向量Pj（j=1,2,…,m）称为基向量，与基向量Pj 对应的变量xj 称为基变量。除基变量以外的其它变量称为非基变量。 基B的m个列向量是线性无关的。 标准形式 max z = 3x1+5x2 是一个基，对应的变量x3,x4,x5是基变量，x1,x2是非 基变量。 基解：假设系数矩阵A 的秩为m，不妨设A 中前m 个列向量线性独立，方程可以写为 令所有非基变量xm+1=?=xn=0， 由|B|≠0，根据克莱姆规则，可得m个基变量的唯一解 xb=(x1,x2,…,xm) 加上所有取值为0 的非基变量，得： x=(x1,x2,…,xm,0,…,0) 称x 为线性规划问题的基解。 令x1=x2=0，解得x3=4,x4=12,x5=18,则x=(0,0,4,12,18)T是一个基解。 max z = 3x1+5x2 基可行解： 满足变量非负约束条件(c)的基解称为基可行解。 可行基：对应于基可行解的基称为可行基。 可行解 基 解 基可行解 令x1=x2=0，解得x3=4,x4=12,x5=18,则x=(0,0,4,12,18)T是一个基解。 由于该基解中所有变量取值为非负，故是基可行解，对应的基 是可行基。 可行基往往不只一个。 如（P1,P4,P5）也是可行基。 最多可能有多少个? 例：求下述线性规划的基可行解 A= =( A1 , A2 , A3 , A4 ) 2 1 1 0 -1 1 0 1 B1=( A3 , A4 )= X(1)=( 0 , 0 , 4 , 1 )T 基解 1 0 0 1 B2=( A1 , A4 )= X(2)=( 2 , 0 , 0 , 3 )T 基解 2 0 -1 1 B3=( A1 , A