运筹与决策之2线性规划.ppt

《运筹与决策之2线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1授课内容Question线性规划的概念和建模线性规划的图解法单纯形法基本步骤计算机软件求解LP问题（下料优化）Case2:哈特风险基金（教材P51）灵敏度分析(Case:生产优化问题)21绪论—Introduction2线性规划—LinearProgramming3运输问题—TransportationModels4整数规划—IntegerProgramming5网络模型—NetworkModels6项目计划—PERT&CPM7排队论—QueueingModels8模拟—Simulation9决策分析—Decision

2、Theory10多目标决策—Multi-objectiveDecision《运筹与决策》目录3§2.1线性规划的概念和模型线性规划问题的导出OR在企业管理的具体应用例1、家具厂生产计划问题例3、合理下料问题线性规划概念和模型4线性规划问题的导出产品AB可用资源木工1230油漆工3260搬运工0224利润(￥)4050例1、家具厂生产计划问题A,B各生产多少,可获最大利润?如何建模？5TransformingModelInputsintoOutputUncontrollableInputs(EnvironmentalFac

3、tors)产品消耗系数、利润、可用资源ControllableInputs(DecisionVariables)A,B各生产多少Output(ProjectedResults)最大利润MathematicalModel（见下页）6x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2解:设产品A,B产量分别为变量x1，x27例2营养配餐求：最低成本的原料混合方案原料iABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量如何建模？8解：设每单位

4、添加剂中原料i的用量为xi(i=1,2,3,4)MinZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)9线性规划概念定义：对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。10要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件线性规划模型的要求11WhyUseLinearProgramming?

5、为什么要使用线性规划线性规划很容易而有效率地被求解如果存在最优解，则必能够找到功能强大的敏感性分析（sensitivityanalysis）许多实际问题本质上是线性的12线性规划模型的特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小13一般式max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn(=,)b2………am1X1+am2X2+…

6、+amnXn(=,)bmXj0(j=1,…,n)1415隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值16某钢筋架需要长度1.5m、2.1m和2.9m各100段，每根标准钢筋长度为7.4m，问如何合理下料所需标准钢筋数目最少？ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203合计7.47.37.27.16.6料头00.10.20.30.8例3、合理下料

7、问题17解：设按第i种方案下料的原材料为xi根minZ=0.1x2+0.2x3+0.3x4+0.8x5x1+2x2+x4=1002x3+2x4+x5=1003x1+x2+2x3+3x5=100xi0(i=1,…,5)如何正确建模？18该线性规划模型错误决策变量缺少整数变量约束约束条件为等式用余料作为目标函数下料方式不全（少3种下料方式）19解：设按第i种方案下料的原材料为xi根minZ=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x41002x2+x3+3x5+2x6+x7100x1+x3+3

8、x4+2x6+3x7+4x8100xi0(i=1,…,8)，且为整数如何建模？20例4、运输问题某公司有三个分厂分别供应三个市场，具体生产能力和需求量如下表：如何建模？市场1市场2市场3产量工厂121350工厂222430工厂334210需求40153521设xij为i工厂运到j市场的产品数量(i＝1，2，3，j