线性规划

运筹学讲稿（第一讲）主讲人：罗和治浙江工业大学经贸管理学院§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming目录绪论第2章线性规划第3章对偶理论第4章运输问题第5章整数规划第6章图与网络第7章存储论第8章对策论第八章目标规划§2.1线性规划问题及其模型MathematicalModelofLPLinearProgrammingChapter2线性规划LinearProgramming第一节线性规划问题及其数学模型第二节图解法第三节单纯形法原理第四节单纯形法基本计算步骤第五节单纯形法的进一步讨论第六节数据包络分析第七节其他应用例子§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming线性规划（LinearProgramming缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟。借助计算机，可使计算更简便，应用领域更广泛和深入。线性规划通常解决下列两类问题（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming【例2.1】美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。问：该公司应制造两种家电各多少件，使获取的利润最大？项目III每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润(元)21§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming解：设该公司每天生产I、II两种家电各x1，x2台，所获得利润为z.≥≤+≤+≤+=−052426155..2max212121221xxxxxxtsxxz§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming【例2.2】河流1：每天流量500万m3；河流2：每天流量200万m3,水质要求：污水含量≤0.2%污水从工厂1流向工厂2有20%可以自然净化；处理污水成本：工厂11000元/万m3，工厂2800元/万m3问两个工厂每天各处理多少污水总成本最少？500万m32万m31.4万m3河流1河流2工厂1工厂2§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming1%2.0500211≥⇒≤xx－6.18.0%2.0200500)4.1(28.02121≥+⇒≤+−+xxxx）－（工厂2：工厂1：解：设x1、x2分别为工厂1、2每天处理的污水量(万m3)§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming≥≤≤≥+≥+=0,4.126.18.01..8001000min212121121xxxxxxxtsxxZ整理后，数学模型如下：§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming线性规划数学模型的特征1、有决策变量、约束条件和目标函数等三要素；2、目标函数是决策变量的线性函数，约束条件是决策变量的线性等式或不等式。同时满足以上特征的这类优化问题，称为线性规划问题。§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming线性规划数学模型的一般表达式假设：线性规划中含有n个决策变量，用表示，jxnxxx,,,21在目标函数中，决策变量的系数用表示，即目标函数为：jcnnxcxcxcZ+++=2211max(min)我们通常把称为价值系数。jc§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming假设决策变量的取值受到项资源的限制，，表示第种资源的拥有量，表示决策变量取值为1个单位时所消耗的第种资源的数量；我们通常把称为工艺系数。jxmibmi,,2,1=iijajxiija=≥≥=≤+++≥=≤+++≥=≤+++njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn,,2,1,0),(),(),(..22112222212111212111或或或即线性规划问题的约束条件为：§2.1线性规划问题及其模型MathematicalModelofLPLinearProgrammingnnxcxcxcZ+++=2211max(min)=≥≥=≤+++≥=≤+++≥=≤+++njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn,,2,1,0),(),(),(..22112222212111212111或或或则线性规划数学模型的一般表达式可写成：§2.1线性规划问题及其模型MathematicalModelofLPLinearProgramming∑==njjjxcZ1max(min)minjxbxatsjnjijij,,2,1,,2,1,0),(..1==≥≥=≤∑=或在实际中一般xj≥0,但有时xj≤0或xj无符号限制。§2.2线性规划应用举例LinearProgramming•§1人力资源分配的问题•§2生产的组织与计划问题•§3合理套裁下料问题•§4合理配料问题•§5投资项目的合理选择问题•§6运输问题§2.2线性规划应用举例LinearProgramming§1人力资源分配的问题例2.3某昼夜服务的公交线路每天各时间段内所需司乘人员数如下：设司乘人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司乘人员，既能满足工作需要，又配备最少司乘人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030§2.2线性规划应用举例LinearProgramming解：设表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。Min654321xxxxxxz+++++=≥≥+≥+≥+≥+≥+≥+−030,2050,6070,60..61655443322116xxxxxxxxxxxxxtsix§2.2线性规划应用举例LinearProgramming例2.4一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28§2.2线性规划应用举例LinearProgramming解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。§2.2线性规划应用举例LinearProgramming例2.5某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816§2生产计划的问题§2.2线性规划应用举例LinearProgramming解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15产品甲铸造外协，其余自制的利润=23-(5+2+3)=13产品乙全部自制的利润=18-(5+1+2)=10产品乙铸造外协，其余自制的利润=18-(6+1+2)=9产品丙的利润=16-(4+3+2)=7可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。§2.2线性规划应用举例LinearProgramming通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0§2.2线性规划应用举例LinearProgramming例2.6永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时设备ⅠⅡⅢ设备的有效台时设备加工费(元/h)A151060000.05A27912100000.03B16840000.06B241170000.11B3740000.05原料（元/件）0.250.350.50售价（元/件）1.252.002.80§2.2线性规划应用举例LinearProgramming§3套裁下料问题例2.7某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？§2.2线性规划应用举例LinearProgramming方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.47.37.27.16.6剩余料头00.10.20.30.8解：共可设计下列5种下料方案，见下表：§2.2线性规划应用举例LinearProgramming设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。54321minxxxxxz++++=≥≥+++≥++≥++−0100323100221002..515321543421xxxxxxxxxxxts§2.2线性规划应用举例LinearProgramming•可以得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套钢架。•注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。§2.2线性规划应用举例LinearProgramming§4配料问题例2.8某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006