运筹学第二章-线性规划

2020/5/121CHAPTER2线性规划及单纯形法(LINEARPROGRAMMING)LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法LP模型的应用本章主要内容：2020/5/122线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）2020/5/123线性规划问题的数学模型例1.1如图所示，如何截取x使铁皮所围成的容积最大？xaxxav220dxdv0)2()2()2(22xaxxa6ax2020/5/124线性规划问题的数学模型例1.2某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润项目ⅠⅡ每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：maxz=2x1+x23.约束条件：5x2≤156x1+2x2≤24x1+x2≤5x1，x2≥02020/5/125线性规划问题的数学模型例1.3已知资料如下表所示，问如何安排生产才能使利润最大？设备产品ABCD利润（元）Ⅰ21402Ⅱ22043有效台时1281612解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总利润为z，则有：maxz=2x1+3x23.约束条件：x1≥0,x2≥02x1+2x2≤12x1+2x2≤84x1≤164x2≤122020/5/126线性规划问题的数学模型例1.4某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用量分别为：x1、x2、x3、x42.目标函数：设总成本为zminz=5x1+6x2+7x3+8x43.约束条件：x1+2x2+x3+x4≥1602x1+4x3+2x4＝2003x1＋x2+x3+2x4≤180x1、x2、x3、x4≥02020/5/127例1.5某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？线性规划问题的数学模型2020/5/128解：设：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2＝20040x3+20x4＝400xj≥0（j=1,2,3,4）线性规划问题的数学模型2020/5/129线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？2020/5/1210线性规划问题的数学模型3.建模条件(1)优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；(2)限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；(3)选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。2020/5/1211线性规划问题的数学模型4.建模步骤(1)确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量；(2)找出所有限定条件：即决策变量受到的所有的约束；(3)写出目标函数：即问题所要达到的目标，并明确是max还是min。2020/5/1212线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：约束条件：5.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为：2020/5/1213线性规划问题的数学模型向量形式：)(21ncccCnxxX1mjjjaaP1mbbB10)((min)maxXBxpCXzjj其中：2020/5/1214线性规划问题的数学模型矩阵形式：mnmnaaaaA11110)((min)maxXBAXCXZ其中：)(21ncccCnxxX1mbbB12020/5/1215线性规划问题的数学模型6.线性规划问题的标准形式11max,1,2,,.0,1,2,,njjjnijjijjZcxaxbimstxjn特点：(1)目标函数求最大值；(2)约束条件为等式方程，且右端常数项bi都大于或等于零；(3)决策变量xj为非负。2020/5/1216线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。jjxczmin也就是：令，可得到上式。zzjjxczzmax即若存在取值无约束的变量，可令其中：jxjjjxxx0,jjxx变量的变换2020/5/1217线性规划问题的数学模型约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量ijijbxa0iniinjijxbxxa称为剩余变量常量bi＜0的变换:约束方程两边乘以（－1）2020/5/1218线性规划问题的数学模型例1.6将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以33xx3x0,33xx2020/5/1219线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;2020/5/1220线性规划问题的数学模型12334512334123351233123345max23()005()7()252()5,,,,,0Zxxxxxxxxxxxxxxxxxxxxxxxxxx标准形式如下：2020/5/1221例1.7将下列线性规划问题化为标准形式12312312312123min5262352100,0,Zxxxxxxxxxxxxxx为无约束（无非负限制）线性规划问题的数学模型2020/5/1222解:标准形式如下：123345123341233512123345max5()2()00()()62()3()52()10,,,,,0Zxxxxxxxxxxxxxxxxxxxxxxxx线性规划问题的数学模型2020/5/122312121212minZ2385340,xxxxxxxx1341345134613456maxZ2()38()53()4,,,,0xxxxxxxxxxxxxxxx例1.8将线性规划问题化为标准型解：线性规划问题的数学模型无约束2020/5/1224线性规划问题的数学模型7.线性规划问题的解)3(,,2,1,0)2(),,2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。2020/5/1225线性规划问题的数学模型可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件②的m×n阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基矩阵，简称基。设：)(11111mmmmmppaaaaB称B中每个列向量Pj(j=12……m)为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。2020/5/1226线性规划问题的数学模型基解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。mnC非可行解可行解基解基可行解2020/5/1227线性规划问题的数学模型例1.10求线性规划问题的所有基矩阵。5,,1,0226103524max53214321321jxxxxxxxxxxxxZj解:约束方程的系数矩阵为2×5矩阵10261001115Ar(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即100116010211120101015061111005261161015987654321BBBBBBBBB2020/5/1228图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。2020/5/1229解题步骤4.确定目标函数值增大（或减小）方向；1.作出平面直角平面坐标系；2.根据约束条件找出可行域；3.作出目标函数线；图解法5.让目标函数线沿着增大（或减小）方向平行移动，与可行域相交且有最大（或最小）目标函数值的顶点，即为最优值。2020/5/1230图解法maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例1.1