资源描述：
《线性规划与对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二部分线性规划LinearProgramming简记LP北京科技大学经济管理学院1运筹学ABC——线性规划主要内容：学习数学规划的建模，提高分析问题的能力掌握线性规划的标准型、图解法掌握线性规划的单纯形法、对偶理论掌握影子价格的意义了解灵敏度分析的目的/北京科技大学经济管理学院2运筹学ABC——线性规划第一节（LP）模型的建立及标准形式一、由实际问题出发，建立（LP）模型LP主要解决的问题：例如：产品的最优组合生产排序最优投资方案人力资源分配……/稀缺资源在竞争中如何进行最优分配。北京科技大学经济
2、管理学院3运筹学ABC——线性规划模型的四个要点：真实性简明性完整性规范性/北京科技大学经济管理学院4运筹学ABC——线性规划规划论模型包含的三个方面：1、设计方案：利用变量x1,x2,···,xn表示方案，称为设计变量或决策变量。2、目标（方案好坏的评价标准）：一般表示为决策变量的函数f(x1,···,xn)，称为目标函数，用Max(Min)表示最优。3、限制条件（客观条件对方案的限制）：一般表示为决策变量的不等式方程，称为约束方程。/北京科技大学经济管理学院5运筹学ABC——线性规划规划论模型的
3、数学表示：x1,x2,···,xn，Max(Min)Z=f(x1,···,xn)g1(x1,···,xn)≥(≤,=)b1……gm(x1,···,xn)≥(≤,=)bms.tLP只是规划论中的一种。/北京科技大学经济管理学院6运筹学ABC——线性规划规划论中不同规划的主要区别：——函数若目标函数与约束方程中的函数均为线性函数，——线性规划若目标函数与约束方程中的函数有非线性函数，——非线性规划若设计变量要求取整数，——整数规划若设计变量要求只取(0,1)，——0-1规划若函数中引入时间参数,——动态
4、规划另：若目标有多个,——多目标规划/北京科技大学经济管理学院7运筹学ABC——线性规划线性与非线性的区别：线性函数：函数为多元一次。表达式：a1x1+a2x2+······+anxnx1f(x1)2维(一元)x1f(x1,x2)3维(二元)x2不是线性的函数，均称为非线性函数。例如：2x12+3x1x2x1f(x1)2维(一元)x1f(x1,x2)3维(二元)x2北京科技大学经济管理学院8运筹学ABC——线性规划函数不是线性的规划问题例：把半径为R的实心金属球熔化后，铸成一个实心圆柱体，问：圆柱体
5、取什么尺寸，才能使它的表面积最小？/R北京科技大学经济管理学院9运筹学ABC——线性规划解：设计变量：设圆柱体的底面半径为x1，高为x2Rx1x2目标函数：Min(圆柱体表面积)=(两个底面积)+(侧面积)=2πx12+2πx1x2约束方程：V圆柱=V圆球s.tπx12x2=4/3πR3x1，x2≥0北京科技大学经济管理学院10运筹学ABC——线性规划二、（LP）模型的种类（1）(引论中的例1)2x2+4x3+5x4+7x5≥704x1+3x2+2x3+x4≥90s.txi≥0i=1······5M
6、inZ=x1+x2+x3+x4+x5（2）(引论中的例2)s.tx1+140156x2≤120x1+16001380x2≤10x1≤4000x2≤3000x1+x2≤5000x1，x2≥0MaxZ=20x1+30x2北京科技大学经济管理学院11运筹学ABC——线性规划例3(运输最优调配问题)某矿区有四座冶炼厂和三座选矿厂，三座选矿厂选出的精矿分别送到四座冶炼厂冶炼。冶炼厂年处理精矿能力、选矿厂年生产精矿能力以及精矿运费如表：冶炼厂选矿厂运费(元/T)ABCD生产量(T)甲乙丙处理量(T)1.52.0
7、0.33.010007.40.81.42.08001.20.22.02.5500500700800300问：如何调配精矿，使运费最低？/23002300北京科技大学经济管理学院12运筹学ABC——线性规划建模：设计变量：设第i选矿厂向第j冶炼厂调配精矿xij(T)。i=1,2,3(甲,乙,丙)，j=1,2,3,4(A,B,C,D)ABCD甲乙丙x11x12x13x14x21x22x23x24x31x32x33x34目标函数：总运费→最少ABCD甲乙丙1.52.00.33.07.40.81.42.01
8、.20.22.02.5MinZ=1.5x11+2.0x12+0.3x13+3.0x14……1.2x31+0.2x32+2.0x33+2.5x34约束方程：s.tABCD生产量甲乙丙处理量1000800500500700800300x11x12x13x14x21x22x23x24x31x32x33x34产量约束x11+x12+x13+x14=1000x21+x22+x23+x24=800x31+x32+x33+x34=500处理量约束x11+x21+x31=500x12
