管理运筹学第2章线性规划课件

第2章线性规划2/6/20231课件教学目标与要求【教学目标】通过对本章的学习，理解线性规划的含义、解、可行解、可行域、基解、基可行解、最优解的定义；掌握图解法、单纯形法（包括大M法）；会建立线性规划数学模型；至少掌握一种软件求解LP【知识结构】2/6/20232课件导入案例——最优生产计划2/6/20233课件2.1.1线性规划问题的提出产品甲产品乙生产能力设备A设备B2111108单位利润32承导入案例设两种产品产量为x1,x2,则有:总利润表达式最大化设备A台时占用设备B台时占用生产能力,不允许超过产量非负决策变量

（decisionvariable）目标函数

（objectivefunction）约束条件

（subjectto）三要素当目标函数与约束条件均为决策变量的线性函数，且变量取连续值时，称为线性规划LP；变量取整称为整数线性规划ILP；变量取二进制为0-1规划BLP。2/6/20235课件2.1.2线性规划的数学模型【例2.1】（合理配料问题）由下表建立一个LP模型求解满足动物成长需要又使成本最低的饲料配方。饲料营养甲(g/kg)营养乙(g/kg)营养丙(g/kg)成本(g/kg)10.50.10.082220.060.76330.040.35541.50.150.25450.80.20.023解设xi为第i种饲料的用量，有：满足营养甲需求满足营养乙需求满足营养丙需求变量非负限制目标是总成本最低2/6/20236课件2.1.2线性规划的数学模型线性规划的一般形式：线性规划的集合形式：线性规划的向量形式：线性规划的矩阵形式：2/6/20237课件2.1.3线性规划的标准模型【例2.2】将LP模型转化为标准式解（1）决策变量变为非负（2）目标函数最大化（3）右端项变为非负（4）约束一、三添加松弛变量；约束二减剩余变量。2/6/20239课件2.2.1线性规划几何解的有关概念2/6/202310课件可行域2.2.2图解法基本步骤建立直角坐标系；图示约束条件，确定右行域；图示目标函数一根基线，按目标要求平行移动，与可行域相切，切点即为最优解；求出切点坐标，并代入目标函数求得最优值。【例2.3】用图解法求LP最优解ox1x22x1+x2=10x1+x2=8令3x1+2x2=121058864(2,6)z=3×2+2×6=18最优解：x1=2,x2=6最优值：z=182/6/202311课件2.3.1线性规划解的有关概念及性质承导入案例LP模型：ACXbCNCBXNXBNBb基基变量非基非基变量B-1b基解;若满足XB≥0,称基可行解.2/6/202313课件2.3.2单纯形法一般而言，B为A中任一m×m阶使XB非负、XN为0的可逆矩阵，由：约束条件两端左乘B-1得基变量的非基变量表达：代入目标函数，得：常数考察该项可见目标函数为非基变量的线性函数。当σN所有元素非正时，目标函数值达到最大，得到了最优解。因为任何一个非基变量入基后，不会使目标函数值增大。若σN某元素（假设第k个元素）>0，则该非基变量入基，会使目标函数值增大。σN中若有多个元素>0，选择其中最大的（假设第k个元素）非基变量xk入基，会使目标函数值增加的更快，于是确定xk为入基变量，σN称为检验数。2/6/202314课件2.3.2单纯形法由于基变量为m个，有一个入基，必然有一个出基，哪个出基呢？在确定初始基时，选择B为单位矩阵，则下式可简化为：即：xk入基,其余仍为0，故有当xk的值由0增加到θ时，原来的基变量xl取值首先变成零，选择其为出基变量。称θ的表达式为最小比值原则。如果所有aik≤0,xk的值可以由0增加到无穷，表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时不存在有限最优解。下面对以上讨论进行总结.2/6/202315课件2.3.2单纯形法2/6/202317课件2.3.2单纯形法例：承导入案例x1x2x3x4基cj3200bx3x40021111001108cj-zjB标准化基可行解3210/2=58/1=8[]2/6/202318课件2.3.2单纯形法x1x2x3x4基cj3200bθx3x400[2]111100110858cj-zj320x1x2x3x4基cj3200bθx1x430101/2[1/2]1/2-1/20153106cj-zj1/2-3/215将入基变量替换出基变量，列出新的单纯形表，并通过初等变换将新基变成单元阵：x1x2x3x4基cj3200bθx1x23210011-1-1226cj-zj-1-118最优解最优值2/6/202319课件2.4工人变量法【例2.4】求解LP问题标准化添加人工变量X1X2X3X4基cj320-MB-1b比值X4X3-M0[2]111011010858σj=cj-zj32*M21X1X2X3X4基cj320-MB-1b比值X1X2321001-111-126σj=cj-zj-1-118*M-1X1X2X3X4基cj320-MB-1b比值X1X330101/2[1/2]011/2-1/25358σj=cj-zj1/2-3/2*M-12/6/202321课件2.5应用举例2/6/202322课件案例2-1广告媒体选择≥2400000≥10≥2≤300000≤180000max目标函数可达消费者人数总费用限制电视广告费限制2/6/202323课件案例2-2公司投资计划2/6/202325课件案例2-3自制/外购计划设x1,x2,x3自制甲,乙,丙数量;