资源描述：
《线性规划与单纯形方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章线性规划与单纯形法本章重点内容线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的应用——建模1第一节线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例2一、实例例1生产计划问题(书P8)Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2。Step2:确定约束条件产品III资源限量设备128台时原料A4016公斤原料B0412公
2、斤利润23问应如何安排生产使该厂获利最多？3说明：OBJ表示Objective;s.t.表示SubjecttoStep3:给出目标函数Step4:整理数学模型4例2现要做100套钢架，每套需2.9米、2.1米和1.5米的元钢各一根。已知原料长7.4米，问如何下料，使余料最少？解：设I,II,III,IV,V分别代表五种不同的原料用量方案,x1,x2,x3,x4,x5分别代表采用各方案下料的元钢的根数。方案根数2.9米2.1米1.5米合计余料Ix11037.40IIx22017.30.1IIIx30227
3、.20.2IVx41207.10.3Vx50136.60.856LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。7目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。每一个问题变量都用一组决策变量
4、（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（LP问题）的共同特征8Max(Min)Z=c1x1+c2x2+…+cnxn(1)a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2s.t.……(2)am1x1+am2x
5、2+…+amnxn≤(=,≥)bmxj≥0,j=1,2,…，n(3)(1)—目标函数；(2)约束条件；(3)决策变量非负n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量线性规划模型的一般形式为：9线性规划模型的紧缩形式n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量10练习题：是否为线性规划模型？111.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优
6、点2.图解法步骤三、两变量线性规划问题的图解法124x1=164x2=12x1+2x2=8x1x248Q14Q430例1（书P8）：Q2(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q313目标函数z=ax1+bx2的值递增的方向与系数a、b有关a>0,b>0a<0,b>0X1X2a<0,b<0a>0,b<0z=ax1+bx2目标函数等值线：ax1+bx2=k移项x2=-a/bx1+k/b目标函
7、数等值线在纵轴上的截距为k/b14例4Z=3615例用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当Z值由小变大时，将与Q2Q3重合Q2Q3上任意一点都是最优解有无穷多最优解（多重解）Q3(2,3)16例用图解法求解线性规划问题可行域无界—无界解（“无有限最优解”或“最优解无界”）约束条件过分宽松注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。x2x1x
8、1-x2=1B(2,1)A(1,0)-x1+2x2=0017例用图解法求解线性规划问题可行域无界—唯一最优解X*=(1,0)，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0018例用图解法求解线性规划问题可行域无界—无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0019例3（书P11）：无可行解（可行域为空）x14x1=164x2=12x1
