资源描述：
《运筹学 02 线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性规划LinearProgramming线性规划及其数学模型LPandItsMathematicalModel线性规划的图解法GraphicMethodofLP线性规划解的概念与性质ConceptsandPropertiesofLPSolution线性规划的单纯形法SimplexMethodofLP线性规划的软件包解法PackageMethodofLP线性规划的应用举例ApplicationsofLP1线性规划及其数学模型线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划模型的共同特征线性规划模型的一般形式线性规划模型的标准形式问题的提出例1：生产计划问题。工厂要安排生产两种
2、产品：产品Ⅰ和产品Ⅱ，各需要设备、原材料A和原材料B，有关数据见表。问：如何安排生产使利润最大？产品Ⅰ产品Ⅱ资源限量设备128台时原材料A4016kg原材料B0412kg单台产品利润23产品I产品Ⅱ如何安排生产使利润最大?基本概念决策变量(Decisionvariables)目标函数(Objectivefunction)约束条件(Constraintconditions)可行域(Feasibleregion)最优解(Optimalsolution)问题要确定的未知量，表明规划中用数量表示的方案、措施，可由决策者决定和控制。是决策变量的函数。决策变量取值时受到的各种资源条件的限制，通常表达为
3、含决策变量的等式或不等式。满足约束条件的决策变量的取值范围。可行域中使目标函数达到最优(最大或者最小)的决策变量的值。数学模型第1步-确定决策变量第2步-定义目标函数第3步-表示约束条件第4步-形成数学模型第1步-确定决策变量设x1——产品Ⅰ的产量x2——产品Ⅱ的产量第2步-定义目标函数Maxz=2x1+3x2决策变量决策变量目标函数最大化第3步-表示约束条件x1+2x2≤84x1≤164x2≤12x1,x2≥0对我们有何限制?资源约束非负约束第4步-形成数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1,x2≥0x1x2线性规划模型的共同特征一组
4、决策变量X表示一个方案，一般X大于等于零。约束条件是关于X的线性等式或不等式。目标函数是线性的，求目标函数最大化或最小化线性规划模型的一般形式线性规划模型的标准形式目标函数最大右边常数非负约束条件等式决策变量非负简写用向量表示用矩阵表示C—价值向量b—资源向量A—约束条件系数矩阵X—决策变量向量0—零向量线性规划问题的标准化目标函数求最大值minZ=CX等价于maxZ’=-CX约束条件右边常量为非负负数常量两边乘以-1，如x1≤-5等价于-x1≥5约束条件为等式“≤”约束：加上非负松驰变量“≥”约束：减去非负松弛变量决策变量为非负x≤0：令x’=-x，则x’≥0x变量为无符号要求：令x’-
5、x’’=x，其中x’,x’’≥0线性规划问题的标准化-例1+x3=+x4=+x5=maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥0maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥0结果线性规划问题的标准化-例2minz=-x1+2x2-3x3x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=7x1,x2≥0,x3无约束令x3=x4-x5，其中x4,x5≥0。加上x6,x7，非负约束条件为：x1,x2,x4,x5,x6,x7≥0max–z=x1-2x2+3(x4
6、-x5)+0x6+0x7x1+x2+(x4-x5)+x6=7x1-x2+(x4-x5)-x7=2–3x1+x2+2(x4-x5)=7maxf=-z=x1-2x2+3(x4-x5)+0x6+0x7x1+x2+(x4-x5)+x6=7x1-x2+(x4-x5)-x7=2-3x1+x2+2(x4-x5)=7x1,x2,x4,x5,x6,x7≥0结果课堂练习：建立LP数学模型例2：有两个煤厂A、B，每月产量分别为60吨、100吨；三个居民区X、Y、Z从这些煤厂获得一定量煤，每月需要量分别为45吨、75吨、40吨；单位运价见表。求运费最少的运输方案。居民区AB需求量X10445Y5875Z61540
7、供应量601002线性规划的图解法图解法图解法求解步骤线性规划问题求解的几种可能结果由图解法得到的启示图解法9—8—7—6—5—4—3—2—1—0
8、
9、
10、
11、
12、
13、
14、
15、
16、123456789x1x2x1+2x2=8目标函数MaxZ=2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1,x2≥04x1=164x2=122x1+3x2=6最优解(4,2)；最大值14图解法求解步骤由全部约束条件作图求出可行域；作目标函数
