第二章线性规划模型和图解法全

Chapter2线性规划模型和图解法(LinearProgramming---LP)LP方法应用的典型情况LP的数学模型LP模型的图解法LP问题的计算机求解本章主要内容：Chapter2线性规划模型和图解法本章教学目的、重点、难点：掌握线性规划问题数学模型建立和线性规划模型的特征；线性规划模型的一般形式及标准形式，解的相关概念；掌握两个变量线性规划问题的几何作图求解方法；掌握两个变量线性规划模型可行域的特点及最优解存在的位置；熟悉计算机QM软件求解线性规划问题的步骤。Page31.规划问题阐述生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）LP方法应用的典型情况Page42在管理中一些典型的线性规划应用LP方法应用的典型情况（1）生产的组织与计划问题：合理利用现有的人力、物力、财力做出最优产品生产计划。（2）运输问题：根据生产单位的产量和销售单位的销量，制订产品调运方案，使得总运费最小。（3）合理下料问题：如何裁截下料，既满足生产需要，又使得所用的材料数量最少。（4）配料问题：在原料供应量限制和保证产品成分含量的前提下，获取最优配料方案Page52在管理中一些典型的线性规划应用LP方法应用的典型情况（5）营销管理问题：要从几种媒体中选择一种组合，使其在广告费用预算条件下广告效益最好。（6）投资组合问题：选择一组股票或证券进行投资，使得有最大的回报率。（7）人力资源管理问题：在不同的时间段需要不同数量的劳动力，如何安排劳动力才能用最少的劳动力来满足工作的需要。Page61数学模型的提出例1.1某塑料制品公司生产各种各样的塑料CD盒，几种产品可以在同一生产线上制造，如果有新产品上就需要对生产线改造。这个成本称为建造成本。有一种CD盒建造成本为3000美元，这个成本就是固定成本(FixCost)，如果生产一个CD盒劳动力和材料成本为2美元。解设生产CD盒的数量为x个，则成本数量模型为：xxc23000)()(xc就是边际成本(MarginalCost)，边际成本是指在产量变化时，总成本的变化率。线性规划问题的数学模型Page7线性规划问题的数学模型易拉罐的设计理念具体下料--模型的建立Page8线性规划问题的数学模型例1.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时12816122线性规划模型的建立Page9线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12Page10线性规划问题的数学模型3.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？模型建立练习：P13Page11线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：约束条件：4.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为：Page12线性规划问题的数学模型向量形式：0)((min)maxXBxpCXzjj)(21ncccCnxxX1mjjjaaP1mbbB1其中：Page13线性规划问题的数学模型矩阵形式：0)((min)maxXBAXCXZmnmnaaaaA1111其中：)(21ncccCnxxX1mbbB1Page14线性规划问题的数学模型5.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,,2,1,,2,1,0.max11特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。Page15线性规划问题的数学模型6如何化标准形式目标函数的转换如果是求极小值即则可将目标函数乘以(-1)，可化为求极大值问题。jjxczmin也就是：令，可得到上式。zzjjxczzmax即若存在取值无约束的变量，可令其中：jxjjjxxx0,jjxx变量的变换Page16线性规划问题的数学模型约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量ijijbxa0iniinjijxbxxa称为剩余变量变量的变换0jx可令，显然jjxx0jxPage17线性规划问题的数学模型例1.3将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以用替换，且;33xx0,33xx3xPage18线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;Page19线性规划问题的数学模型0,,,,,5)(252)(7)(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：Page20学习要点小结：1.线性规划模型在管理中的应用：生产组织，下料问题等2.线性规划模型的构成：目标函数、约束条件；3.将一般形式转化标准形式：目标函数求最大、最小时；约束条件变为不等号时；常数项为负时；决策变量无约束时；小结Page21作业作业：课堂出题练习思考：建立模型后怎样进行求解？Page22线性规划模型的图解法1.基本概念)3(,,2,1,0)2(),,2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。Page23可行解：满足约束条件（2）、(3)的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。最优值：最优解带入目标函数所得的值称为线性规划的最优值。凸集：如果集合C中任何两点连线上所有的点都是集合C中的点，则称该集合为凸集。线性规划模型的图解法Page24线性规划模型的图解法凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。凸集凸集不是凸集顶点Page25线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。线性规划模型的图解法Page26线性规划模型图解法基本步骤：Step1：建立坐标系；Step2：图示约束条件；Step3：图示目标函数；Step4：确定最优解；图解法简单直观，有助于领会线性规划的基本性质及一般求解方法的基本思想。线性规划模型的图解法Page27maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.4用图解法求解线性规划问题线性规划模型的图解法Page28x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxZ=2X1+X2线性规划模型的图解法Page29maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2maxZ34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域线性规划模型的图解法Page30minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2maxZminZ8=5X1+4X243=5X1+4X2（0，2）可行域此点是唯一最优解线性规划模型的图解法Page31006346321212121xxxxxxxx、246x1x2246无界解(无最优解)maxZ=x1+2x2例1.5x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ线性规划模型的图解法x1x2O10203040102030405050无可行解(即无最优解)0,050305.140221212121xxxxxxxxmaxZ=3x1+4x2例1.6Page33线性规划模型的图解法练习：0,12416482st.32max21212121xxxxxxxxz用图解法求解下面线性规划模型：Page34线性规划模型的图解法分析：用图解法求解下面线性规划模型：图1最大化线性规划模型的图解法Page35线性规划模型的图解法分析：用图解法求解下面线性规划模型：多边形区域OABCD中的点就是线性规划问题的可行解（可行点），多边形区域OABCD称为线性规划问题的可行解区域。显然它是一个凸区域。可行域：目标函数：我们将看作参数，则表示坐标平面上的一族平行线，直线上任意一点的坐标对应的目标函数值均为，我们称这样的直线为等值线（或等高线）。z2132xxzzxx2132Page36线性规划模型的图解法分析：用图解法求解下面线性规划模型：可得C点坐标X1=4,X2=2，对应的目标函数值为142342maxZPage37线性规划模型有以下4种情况：•唯一最优解：凸多边形的某个顶点；•无穷多最优解：目标函数直线和可行域边界一条边重合；•无