线性规划在工商管理中的应用17课件.ppt

第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用•§1 §1 人力资源分配的问题•§2 §2 生产计划的问题•§3 §3 套裁下料问题•§4 §4 配料问题•§5 §5 投资问题1 例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?2 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 03最优解为：X1＝50X2＝20X3＝50X4＝0X5＝20X6＝10最优值为Z＝1504 例例2 2．一家中型的百货商场，它对售货员的需．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。

为了保证售货人员充求经过统计分析如下表所示为了保证售货人员充分休息，售货人员每周工作分休息，售货人员每周工作5 5天，休息两天，并要天，休息两天，并要求休息的两天是连续的问应该如何安排售货人员求休息的两天是连续的问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的的作息，既满足工作需要，又使配备的售货人员的人数最少？人数最少？5 解：设解：设 x xi i ( i = 1,2,…,7) ( i = 1,2,…,7)表示星期一至日开始表示星期一至日开始休息的人数休息的人数, ,这样我们建立如下的数学模型这样我们建立如下的数学模型目标函数：目标函数：Min Min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 + + x x7 7 约束条件：约束条件：s.t. s.t. x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 ≥ 28 ≥ 28 x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 ≥ 15 ≥ 15 x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 + + x x7 7 ≥ 24 ≥ 24 x x4 4 + + x x5 5 + + x x6 6 + + x x7 7 + + x x1 1 ≥ 25 ≥ 25 x x5 5 + + x x6 6 + + x x7 7 + + x x1 1 + + x x2 2 ≥ 19 ≥ 19 x x6 6 + + x x7 7 + + x x1 1 + + x x2 2 + + x x3 3 ≥ 31 ≥ 31 x x7 7 + + x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 ≥ 28 ≥ 28 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 6, ,x x7 7 ≥ 0 ≥ 06最优解为：最优解为：X1X1＝＝1212X2X2＝＝0 0X3X3＝＝1111X4X4＝＝5 5X5X5＝＝0 0X6X6＝＝8 8X7X7＝＝0 0最优值为最优值为Z Z＝＝36367 例例3 3．某公司面临一个是外包协作还是自行生产的问题。

该．某公司面临一个是外包协作还是自行生产的问题该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间甲、乙两种产品的铸件可以外包协作，亦可以自配三个车间甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量数据如表问：行生产，但产品丙必须本厂铸造才能保证质量数据如表问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？少件？8 解：设解：设 x x1 1,x,x2 2,x,x3 3 分别为三道工序都由本公司加工的甲、乙、分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，丙三种产品的件数，x x4 4,x,x5 5 分别为由外协铸造再由本公司加工和分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数装配的甲、乙两种产品的件数 求求 x xi i 的利润：利润的利润：利润 = = 售价售价 - - 各成本之和各成本之和 产品甲全部自制的利润产品甲全部自制的利润 =23-(3+2+3)=15 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 =23-(5+2+3)=13 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1+2)=10 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 =18-(6+1+2)=9 产品丙的利润产品丙的利润 =16-(4+3+2)=7 =16-(4+3+2)=7 可得可得x xi i （（i = 1,2,3,4,5i = 1,2,3,4,5）的利润分别为）的利润分别为1515、、1010、、7 7、、1313、、9 9元。

元9通过以上分析,可建立如下的数学模型:目标函数：Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件：5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 010最优解为：最优解为：X1X1＝＝16001600X2X2＝＝0 0X3X3＝＝0 0X4X4＝＝0 0X5X5＝＝600600最优值为最优值为Z Z＝＝2940029400（元）（元）11 例例4 4．永久机械厂生产．永久机械厂生产ⅠⅠ、、ⅡⅡ、、ⅢⅢ三种产品，均要经过三种产品，均要经过A A、、B B两两 道工序加工设有两种规格的设备道工序加工设有两种规格的设备A A1 1、、A A2 2能完成能完成 A A 工序；有三种工序；有三种规格的设备规格的设备B B1 1、、B B2 2、、B B3 3能完成能完成 B B 工序ⅠⅠ可在可在A A、、B B的任何规格的的任何规格的设备上加工；设备上加工；Ⅱ Ⅱ 可在任意规格的可在任意规格的A A设备上加工，但对设备上加工，但对B B工序，只工序，只能在能在B B1 1设备上加工；设备上加工；ⅢⅢ只能在只能在A A2 2与与B B2 2设备上加工。

数据如表问：设备上加工数据如表问：为使该厂获得最大利润，应如何制定产品加工方案？为使该厂获得最大利润，应如何制定产品加工方案？12解：设解：设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序上的第种工序上的第 k k 种设备种设备上加工的数量建立如下的数学模型上加工的数量建立如下的数学模型: : s.t. 5 s.t. 5x x111111 + 10 + 10x x211 211 ≤ 6000 ≤ 6000 （（ 设备设备 A A1 1 ）） 7 7x x112112 + 9 + 9x x212212 + 12 + 12x x312312 ≤ 10000 ≤ 10000 （（ 设备设备 A A2 2 ）） 6 6x x121121 + 8 + 8x x221221 ≤ 4000 ≤ 4000 （（ 设备设备 B B1 1 ）） 4 4x x122122 + 11 + 11x x322322 ≤ 7000 ≤ 7000 （（ 设备设备 B B2 2 ）） 7 7x x123123 ≤ 4000 ≤ 4000 （（ 设备设备 B B3 3 ））x x111111+ + x x112112- - x x121121- - x x122122- - x x123123 = 0 = 0 （（ⅠⅠ产品在产品在A A、、B B工序数量相等）工序数量相等） x x211211+ + x x212212- - x x221221 = 0 = 0 （（ⅡⅡ产品在产品在A A、、B B工序加工的数量相等）工序加工的数量相等） x x312 312 - - x x322322 = 0 = 0 （（ⅢⅢ产品在产品在A A、、B B工序加工的数量相等）工序加工的数量相等） x xijkijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3 ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,313 目标函数为计算利润最大化，利润的计算公式为：目标函数为计算利润最大化，利润的计算公式为： 利润利润 = [ = [（销售单价（销售单价 －－ 原料单价）原料单价）××产品件数产品件数] ] －－（每台时的设备费用（每台时的设备费用* *设备实际使用的总台时数）设备实际使用的总台时数）目标函数：目标函数： MaxZ=(1.25-0.25)(xMaxZ=(1.25-0.25)(x111111+x+x112112) )＋＋(2-0.35)x(2-0.35)x221221＋＋(2.80-0.5)x(2.80-0.5)x312312 －－ 300/6000(5x300/6000(5x111111+10x+10x211211)321/10000(7x)321/10000(7x112112+9x+9x212212+12x+12x312312) )－－250/4000(6x250/4000(6x121121+8x+8x221221) )－－783/7000(4x783/7000(4x122122+11x+11x322322) )－－200/4000(7x200/4000(7x123123) ) 整理可得：整理可得：MaxZ=0.75MaxZ=0.75x x111111+0.7753+0.7753x x112112+1.15+1.15x x211211+1.3611+1.3611x x212212+1.9148+1.9148x x312312-0.375-0.375x x121121-0.5-0.5x x221221-0.4475-0.4475x x122122- -1.23041.2304x x322322-0.35-0.35x x12312314最优解为最优解为X111X111＝＝12001200X112X112＝＝230.0492230.0492X211X211＝＝0 0X212X212＝＝500500X312X312＝＝324.138324.138X121X121＝＝0 0X221X221＝＝500500X122X122＝＝858.6206858.6206X322X322＝＝324.138324.138X123X123＝＝571.4286571.4286最优值为最优值为Z Z＝＝1146.60051146.6005（元）（元）15 例5．某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。

已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表16设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数这样我们建立如下的数学模型目标函数：MinZ= x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 017•软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根 即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套钢架•注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。

如果用等于号，这一方案就不是可行解了18§4§4　　配料问题 例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表问：该厂应如何安排生产，使利润收入为最大？19解：设解：设 x xijij 表示第表示第 i i 种（甲、乙、丙）产品中原料种（甲、乙、丙）产品中原料 j j 的含量的含量这样我们建立数学模型时，要考虑：这样我们建立数学模型时，要考虑： 对于甲：对于甲： x x1111，，x x1212，，x x1313；； 对于乙：对于乙： x x2121，，x x2222，，x x2323；； 对于丙：对于丙： x x3131，，x x3232，，x x3333；； 对于原料对于原料1 1：： x x1111，，x x2121，，x x3131；； 对于原料对于原料2 2：： x x1212，，x x2222，，x x3232；； 对于原料对于原料3 3：： x x1313，，x x2323，，x x3333；； 目标函数：目标函数： 利润最大，利润利润最大，利润 = = 收入收入 - - 原料支出原料支出 约束条件：约束条件： 规格要求规格要求 4 4 个；个； 供应量限制供应量限制 3 3 个。

个20•利润=总收入－总成本＝甲乙丙三种产品的销售单价×产品数量－甲乙丙使用的原料单价×原料数量，故有目标函数目标函数Max 50Max 50（（x x1111+ +x x1212+ +x x1313））+35+35（（x x2121+ +x x2222+ +x x2323））+25+25（（x x3131+ +x x3232+ +x x3333））-65-65（（x x1111+ +x x2121+ +x x3131））-25-25（（x x1212+ +x x2222+ +x x3232））-35-35（（x x1313+ +x x2323+ +x x3333））= -15= -15x x1111+25+25x x1212+15+15x x1313-30-30x x2121+10+10x x2222-40-40x x3131-10-10x x3333 约束条件：约束条件： 从第从第1个表中有：个表中有： x x1111≥0.5(≥0.5(x x1111+ +x x1212+ +x x1313) ) x x1212≤0.25(≤0.25(x x1111+ +x x1212+ +x x1313) ) x x2121≥0.25(≥0.25(x x2121+ +x x2222+ +x x2323) ) x x2222≤0.5(≤0.5(x x2121+ +x x2222+ +x x2323) )21 从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有 (x11+x21+x31)≤100 (x12+x22+x32)≤100 (x13+x23+x33)≤60 通过整理，得到以下模型：22目标函数：Max Z= -15Max Z= -15x x1111+25+25x x1212+15+15x x1313-30-30x x2121+10+10x x2222-40-40x x3131-10-10x x3333 约束条件： s.t. 0.5 s.t. 0.5 x x1111-0.5 -0.5 x x12 12 -0.5 -0.5 x x1313 ≥ 0 ≥ 0 （原材料（原材料1 1不少于不少于50%50%）） -0.25 -0.25x x1111+0.75+0.75x x1212 -0.25 -0.25x x1313 ≤ 0 ≤ 0 （原材料（原材料2 2不超过不超过25%25%）） 0.75 0.75x x2121-0.25-0.25x x2222 -0.25 -0.25x x2323 ≥ 0 ≥ 0 （原材料（原材料1 1不少于不少于25%25%）） -0.5 -0.5 x x2121+0.5 +0.5 x x2222 -0.5 -0.5 x x2323 ≤ 0 ≤ 0 （原材料（原材料2 2不超过不超过50%50%）） x x1111+ + x x2121 + + x x3131 ≤ 100 ( ≤ 100 (供应量限制）供应量限制） x x1212+ + x x2222 + + x x3232 ≤ 100 ( ≤ 100 (供应量限制）供应量限制） x x1313+ + x x2323 + + x x3333 ≤ 60 ( ≤ 60 (供应量限制）供应量限制） x xijij ≥ 0 , i = 1,2,3; j = 1,2,3 ≥ 0 , i = 1,2,3; j = 1,2,323最优解为：最优解为：X11X11＝＝100100X12X12＝＝5050X13X13＝＝5050其它的其它的X Xijij＝＝0 0最优值为最优值为Z Z＝＝500(500(元元) )24§4§4　　配料问题 例7.汽油混合问题。

一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？25标准汽油标准汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)库存量库存量(L)1107.57.11×10-2380000293.011.38 ×10-2265200387.05.69×10-24081004108.028.45 ×10-2130100飞机飞机汽油汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)产量需求产量需求1不小于不小于91不大于不大于9.96 ×10-2越多越好越多越好2不小于不小于100不大于不大于9.96 ×10-2不少于不少于25000026 解：设xij为飞机汽油i中所用标准汽油j的数量(L) 目标函数为飞机汽油1的总产量：库存量约束为：27产量约束为飞机汽油2的产量：由物理中的分压定律， 可得有关蒸汽压力的约束条件：同样可得有关辛烷数的约束条件为：28 综上所述，得该问题的数学模型为：29 由运筹学软件求解得：30§5§5　　投资问题 例例8 8．某部门现有资金．某部门现有资金200200万元，今后五年内考虑给以下的项目万元，今后五年内考虑给以下的项目投资。

已知：项目投资已知：项目A A：从第一年到第五年每年年初都可投资，：从第一年到第五年每年年初都可投资，当年末能收回本利当年末能收回本利110%110%；项目；项目B B：从第一年到第四年每年年：从第一年到第四年每年年初都可投资，次年末能收回本利初都可投资，次年末能收回本利125%125%，但规定每年最大投资，但规定每年最大投资额不能超过额不能超过3030万元；项目万元；项目C C：需在第三年年初投资，第五年：需在第三年年初投资，第五年末能收回本利末能收回本利140%140%，但规定最大投资额不能超过，但规定最大投资额不能超过8080万元；项万元；项目目D D：需在第二年年初投资，第五年末能收回本利：需在第二年年初投资，第五年末能收回本利155%155%，但，但规定最大投资额不能超过规定最大投资额不能超过100100万元 据测定每万元每次投资的风险指数如右表：据测定每万元每次投资的风险指数如右表：31问：（问：（a a）应如何确定这些项目的每年投资额，使得第）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？五年年末拥有资金的本利金额为最大？（（b b）应如何确定这些项目的每年投资额，使得第五年）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在年末拥有资金的本利在330330万元的基础上使得其投资总万元的基础上使得其投资总的风险系数为最小？的风险系数为最小？解：（解：（1 1）确定决策变量：连续投资问题）确定决策变量：连续投资问题 设设 x xijij ( i = 1 ( i = 1～～5 5，，j = 1j = 1～～4)4)表示第表示第 i i 年初投年初投资于资于A(j=1)A(j=1)、、B(j=2)B(j=2)、、C(j=3)C(j=3)、、D(j=4)D(j=4)项目的金额。

项目的金额这样我们建立如下的决策变量：这样我们建立如下的决策变量： A A x x11 11 x x21 21 x x3131 x x4141 x x5151 B x B x12 12 x x22 22 x x3232 x x4242 C C x x3333 D D x x242432（（2 2）约束条件：）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200；第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，有 x21 + x22+ x24 = 1.1x11；第三年：年初有资金 1.1x21+ 1.25x12，有 x31 + x32+ x33 = 1.1x21+ 1.25x12；第四年：年初有资金 1.1x31+ 1.25x22，有 x41 + x42 = 1.1x31+ 1.25x22；第五年：年初有资金 1.1x41+ 1.25x32，有 x51 = 1.1x41+ 1.25x32； B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100 333 3）目标函数及模型：）目标函数及模型：（（a) Max z a) Max z ＝＝ 1.1 1.1x x5151+ 1.25+ 1.25x x4242+ 1.4+ 1.4x x33 33 + 1.55+ 1.55x x24 24 s.t. s.t. x x1111+ + x x12 12 ＝＝ 200 200 x x21 21 + + x x2222+ + x x2424 ＝＝ 1.1 1.1x x1111；； x x31 31 + + x x3232+ + x x3333 ＝＝ 1.1 1.1x x2121+ 1.25+ 1.25x x1212；； x x41 41 + + x x4242 ＝＝ 1.1 1.1x x3131+ 1.25+ 1.25x x2222；； x x51 51 ＝＝ 1.1 1.1x x4141+ 1.25+ 1.25x x3232；； x xi2 i2 ≤ 30 ( i =1≤ 30 ( i =1、、2 2、、3 3、、4 )4 )，，x x3333 ≤ 80 ≤ 80，， x x2424 ≤ 100 ≤ 100 x xijij ≥ 0 ( i = 1 ≥ 0 ( i = 1、、2 2、、3 3、、4 4、、5 5；；j = 1j = 1、、2 2、、3 3、、4 4））34最优解为：最优解为：X11X11＝＝170170，，X12X12＝＝3030X21X21＝＝5757，，X22X22＝＝3030，，X24X24＝＝100100X31X31＝＝0 0，， X32 X32＝＝20.220.2，， X33 X33＝＝80 80 X41X41＝＝7.57.5，， X42 X42＝＝30 30 X51X51＝＝33.5 33.5 最优值为最优值为Z Z＝＝341.35341.35（万元）（万元）35（（b)b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，于是模型如下：36Minf = Minf = ( (x x1111+ +x x2121+ +x x3131+ +x x4141+ +x x5151)+3()+3(x x1212+ +x x2222+ +x x3232+ +x x4242)+4)+4x x3333+5.5+5.5x x24 24 s.t. s.t. x x1111+ + x x12 12 = 200= 200 x x21 21 + + x x2222+ + x x2424 = 1.1 = 1.1x x1111；； x x31 31 + + x x3232+ + x x3333 = 1.1 = 1.1x x2121+ 1.25+ 1.25x x1212；； x x41 41 + + x x4242 = 1.1 = 1.1x x3131+ 1.25+ 1.25x x2222；； x x51 51 = 1.1= 1.1x x4141+ 1.25+ 1.25x x3232；；x xi2 i2 ≤ 30 ( i =1≤ 30 ( i =1、、2 2、、3 3、、4 )4 )，，x x3333 ≤ 80 ≤ 80，，x x2424 ≤ 100 ≤ 100 1.1 1.1x x51 51 + 1.25+ 1.25x x4242+ 1.4+ 1.4x x3333+ 1.55+ 1.55x x2424 ≥ 330 ≥ 330 x xijij ≥ 0 ( i = 1 ≥ 0 ( i = 1、、2 2、、3 3、、4 4、、5 5；；j = 1j = 1、、2 2、、3 3、、4 4））37。