《管理定量分析》第三部分最优化

第三章最优化方法第一节线性规划概述第二节线性规划问题的解法第三节线性规划问题的对偶问题第四节整数规划（运输、分配问题）第五节动态规划案例：河流污水处理费用优化A城市排2万立方米/天污水，到城市B前20%自然净化问题：要求污水含量不大于0.2%，如何处理污水费用最少？支流200万立方米/天主河流500万立方米/天B城市排1.4万立方米/天污水处理成本：A市1000元/万立方米；B市800元/万立方米一、线性规划问题的提出——利用有限资源某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表1-1。该工厂每生产一件产品Ⅰ可获利润2元，每生产一件产品Ⅱ可获利润3元，问应如何安排生产计划使该工厂获得的利润最大？第一节线性规划概述生产计划问题产品资源ⅠⅡ资源限量设备(台时)128原材料A(g)4016000原材料B(g)0412000如何制定生产计划，使两种产品总利润最大？利用有限资源：某鸡厂共饲养1万只鸡，用大豆和谷物混合喂养，已知鸡消耗饲料1kg/天，鸡至少需要蛋白质、钙分别为0.22、0.06kg/天，每公斤大豆含蛋白质、钙为50％、0.2％，每公斤谷物含蛋白质、钙为10％、0.1％，大豆和谷物售价0.4、0.2元/kg。0,1241648232max21212121xxxxxxxxZ饲料成分大豆谷物营养/天.鸡蛋白质.kg50％10％≥0.22钙.kg0.2％0.1％≥0.06售价.元0.40.2设：每只鸡需要大豆x1公斤，谷物x2公斤，0,106.0001.0002.022.01.05.02.04.0min2121212121xxxxxxxxxxZ设：养鸡场每天需要大豆x1公斤，谷物x2公斤0,100001000006.0001.0002.01000022.01.05.02.04.0min2121212121xxxxxxxxxxZ二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj(j=1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LP）。2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数；对决策变量有非负要求。3．LP的数学描述(数学模型)：（1）一般形式njxbxaxaxabxaxaxabxaxaxaxcxcxcZjmnmnmmnnnnnn,,2,1,0),(),(),(max(min)221122222121112121112211（2）紧缩形式njxmibxatsxcZjnjijijnjjj,,2,10,,2,1),(..max(min)11（3）矩阵形式其中:0),(..max(min)XbAXtsCXZ),,,(21ncccCTnxxxX),,,(21Tmbbbb),,,(21mnmmmnnaaaaaaaaaaaaA32122322211131211（4）向量—矩阵形式：0)(..)(1XbxPtsCXZMinMaxnjjj或其中：),,,(,,2,1),,,(2121nTmjjjjPPPAnjaaaP三、LP的标准型：1、LP标准型的概念（1）什麽是LP的标准型？（2）LP标准型的特点目标函数约定是极大化Max（或Min）;约束条件均用等式表示;决策变量限于取非负值;右端常数b均为非负值;（3）数学表达式:有几种形式?为什麽?如何书写?2、LP问题的标准化（1）目标函数的标准化CXZCXZZZ'maxmin'y3y=f(x)1025x-1y’=-f(x)-3目标函数标准化示意图●●◆◆（2）约束条件的标准化&约束条件是≤类型——左边加非负松弛变量&约束条件是≥类型——左边减非负剩余变量&变量符号不限——引入新变量21kkkxxx四、在管理中一些典型的线性规划应用1、合理利用线材问题：如何在保证生产的条件下，下料最少2、配料问题：在原料供应量的限制下如何获取最大利润3、投资问题：从投资项目中选取方案，使投资回报最大4、产品生产计划：合理利用人力、物力、财力等，使获利最大5、劳动力安排：用最少的劳动力来满足工作的需要6、运输问题：如何制定调运方案，使总运费最小线性规划总结：（一）线性规划的组成：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素（二）建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件（三）线性规划模型的一般形式目标函数：约束条件：njxbxaxaxabxaxaxabxaxaxaxcxcxcZjmnmnmmnnnnnn,,2,1,0),(),(),(max(min)221122222121112121112211例题分析1：生产计划问题例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元问：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？例题分析1：生产计划问题解：工厂应分别生产Ⅰ、Ⅱ产品x1、x2单位，则所求的线性规划模型为：0,2504002300..10050max212212121xxxxxxxtsxxZ例题分析2：食谱问题例1已知某人每周所需的营养成分、所食用的食品及单位食品所含营养如下表所示：营养成分大米白菜鸡蛋猪肉营养成分的需要量（周）蛋白质某维生素某矿物质a11a12a13a14a21a22a23a24a31a32a33a34b1b2b3单价（元）c1c2c3c4—问这个人每周应食用大米、白菜、鸡蛋和猪肉各多少，能使生活费用最省？例题分析2：食谱问题解：设这个人每周应食用大米、白菜、鸡蛋、猪肉各为x1、x2、x3、x4，则所求的线性规划模型为：0,,,..min432134143332321312424323222121141431321211144332211xxxxbxaxaxaxabxaxaxaxabxaxaxaxatsxcxcxcxcZ例题分析3：人力资源分配问题例2．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030例题分析3：人力资源分配问题解：设xi表示从第i班次开始上班的司机和乘务人员数(i=1,2,3,4,5,6),这样我们建立如下的数学模型。0,,,,,302050607060..min654321655443322116654321xxxxxxxxxxxxxxxxxxtsxxxxxxZ例题分析4：合理下料问题例4假定现有一批某种型号的圆钢长8米，需要裁取长2.5米的毛坯100根、长1.3米的毛坯200根，问应该怎样选择下料方式才能既满足需要，又使总的用料最省？解：各种可能的裁剪方案如下表所示：型号方案1方案2方案3方案4需要根数2.5米1.3米32100246100200余料(米)0.50.40.30.2—例题分析4：合理下料问题设x1,x2,x3,x4分别为上面4种方案下料的原材料根数。这样我们建立如下的数学模型。0,,,20064210023..min43214323214321xxxxxxxxxxtsxxxxZ例题分析5：投资问题例5某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。问应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？例题分析4：投资问题解：设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：12345Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24例题分析5：投资问题)4,3,2,1;5,4,3,2,1(0100080)4,3,2,1(3025.11.125.11.125.11.11.1200..55.14.125.11.1max2433232415122314241122133323111242221121124334251jixxxixxxxxxxxxxxxxxxxxxxtsxxxxZiji投资问题（作业）某部门现有资金100万元，今后五年内考虑给以下的项目投资。已知：项目A：五年内每年初均可投资，且金额不限，投资期限1年，年回报率7%；项目B：五年内每年初均可投资，且金额不限，投资期限2年，年回报率10%（不计复利）；项目C：五年内每年初均可投资，且金额不限，投资期限3年，年回报率12%（不计复利）；项目D：只在第一年初有一次投资机会，最大投资额50万元，投资期限4年，年回报率20%（不计复利）；项目E：在第二年和第四年初有一次投资机会，最大投资额30万元，投资期限1年，年回报率30%；项目F：在第四年初有一次投资机会，金额不限，投资期限2年，年回报率25%；假设当年投资金额及其收益均可用于下一年投资，问公司如何投资才能使得第五年末收回的本利金额最大？合理下料问题（作业）新华造纸厂接到三份订购卷纸的订单，其长和宽的要求如下表所示：该厂生产1米和2米两种标准宽度的卷纸。假定卷纸的长度无限制，即可以连接起来达到所需的长度，问如何切割才能使切割损失的面积最小？订单号码宽（米）长（米）10.5100020.7300030.92000产品配套问题（作业）假定一个工厂的甲、乙、丙三个车间生产同一产品，每件产品包含4个A零件和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别是100千克和200千克。第个生产班的原材料需要量和零件产量如下表所示：问：这三个车间各应开多少班次才能使这种产品的配套数达到最大？车间第班进料数（千克）每班产量（个数）第一种原料第二种原料A零件B零件甲8675乙5969丙3884计划生产问题（作业）某化工厂要用三种原料混合配置三种不同规格的产品，各产品的规格单价如下表所示：