运筹学线性规划.ppt

《运筹学线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、Chapter1线性规划(LinearProgramming)LP的数学模型图解法单纯形法单纯形法的进一步讨论－人工变量法LP模型的应用本章主要内容：线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（

2、如产品量最多、利润最大.）线性规划问题的数学模型例1.1某工厂生产甲、乙两种产品。这些产品分别要在A、B、C三种不同的设备上加工。按工艺资料规定，每吨产品在不同设备上加工所需要的台时，三种加工设备在计划期内能提供的有限台时数如表1.1.1所示，企业决策者应如何安排生产计划，使企业总的利润最大？线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，Z为总利润，则数学模型为：maxZ=32x1+30x2x1≥0,x2≥0s.t.3x1+4x2≤365x1+4x2≤409x1+8x2≤76目标函数约

3、束条件例２：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元，厂方希望总成本达到最小，问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分定义x1，x2分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本Z=3x1+2x2极小化

4、约束：配料平衡条件，x1+x2=1产品中A、B、C三种化学成分的最低含量12x1+3x2≥42x1+3x2≥23x1+15x2≥5非负性条件x1≥0,x2≥0原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分数学模型：s.t.这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1和x2的值使目标函数取得最小值。原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙

5、A1234B232C3155单位成本（元）３２化学成分例３，某铁器加工厂要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短

6、。设xj表示用第j种下料方案下料的原料根数，j=1,2…8,目标：使料头总长度Z=0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8极小化约束：三种规格圆钢根数x1+2x2+x4+x6=1002x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非负取整条件xj≥0(j=1,2…8)且取整数圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4数

7、学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最小值。圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.11.4且为整数线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特

8、征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式；（3）在一般情况下，变量的取值是非负的。怎样辨别一个模型是线性规划模型？线性规划问题的数学模型目标函数：约束条件：3.线性规划数学模型的一般形式简写为：线性规划问题的数学模型向量形式：其中：线性规划问题的数学模型矩阵形式：其中：线性规划问题的数学模型3.线性规划问题的标准形式特点：(1)目标函数