线性规划在管理中的应用.ppt

13452线性规划在管理中的应用线性规划在管理中的应用线性规划问题的建模过程•1. 理解要解决的问题，了解解题的目标和条件；•2. 定义决策变量（x1 ，x2 ，… ，xn），每一组值表示一个方案；•3. 用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；•4. 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件人力资源分配的问题（1）•例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?人力资源分配的问题（1）解：设 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 ≥ 0 最优解：x1 = 50，x2 = 20，x3 = 50，x4 = 0，x5 = 20，x6 = 10，共 150 人。

人力资源分配的问题（2）•例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？人力资源分配的问题（2）解：设 xi ( i = 1, 2, …, 7) 表示星期一至日开始休息的人数，这样我们建立如下的数学模型 目标函数： min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件： s.t. x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x4 + x5 + x6 + x7 + x1 ≥ 25 x5 + x6 + x7 + x1 + x2 ≥ 19 x6 + x7 + x1 + x2 + x3 ≥ 31 x7 + x1 + x2 + x3 + x4 ≥ 28 x1, x2, x3, x4, x5, x6, x7 ≥ 0最优解：x1 = 12，x2 = 0，x3 = 11，x4 = 5，x5 = 0， x6 = 8， x7 = 0，共 36 人。

生产计划的问题（1）•例3．某公司面临一个是外包协作还是自行生产的问题该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量数据如表问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题（1）解：设 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 元生产计划的问题（1）通过以上分析,可建立如下的线性规划模型:目标函数： 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 ≥ 0最优解： x1 = 1600， x2 = x3 = x4 = 0，x5 = 600生产计划的问题（2）•例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。

设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序Ⅰ可在A、B的任何规格的设备上加工；Ⅱ 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工数据如表问：为使该厂获得最大利润，应如何制定产品加工方案？生产计划的问题（2）解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量约束条件为： s.t. 5x111 + 10x211 ≤ 6000 （ 设备 A1 ） 7x112 + 9x212 + 12x312 ≤ 10000 （ 设备 A2 ） 6x121 + 8x221 ≤ 4000 （ 设备 B1 ） 4x122 + 11x322 ≤ 7000 （ 设备 B2 ）7x123 ≤ 4000 （ 设备 B3 ）x111+ x112 = x121 + x122 + x123 （Ⅰ产品在A、B工序加工的数量相等）x211+ x212 = x221 （Ⅱ产品在A、B工序加工的数量相等） x312 = x322 （Ⅲ产品在A、B工序加工的数量相等） xijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3生产计划的问题（2）目标函数为计算利润最大化，利润的计算公式为： 利润 = [（销售单价 - 原料单价）* 产品件数]之和 -（每台时的 设备费用 * 设备实际使用的总台时数）之和。

这样得到目标函数：max (1.25 – 0.25)(x111+x112) + (2 – 0.35)x221 + (2.8 – 0.5)x312 – 300/6000(5x111+10x211) – 321/10000(7x112+9x212+12x312) – 250/4000(6x121+8x221) – 783/7000(4x122+11x322) – 200/4000(7x123)经整理可得： max 0.75x111 + 0.7753x112 + 1.15x211 + 1.3611x212 + 1.9148x312 – 0.375x121 – 0.5x221 – 0.4475x122 – 1.2304x322 – 0.35x123解得：x111 = 1200，x112 = 230.049，x211 = 0，x212 = 500，x312 = 324.138，x121 = 0， x221 = 500， x122 = 858.6206，x322 = 324.138， x123 = 571.4286生产计划的问题（2）•另解：设 yijk 表示在第 j 种设备上完成工序A、在第 k 种设备上完成工序B的第 i 种产品的数量。

•目标函数为： max (1.25 – 0.25) (y111 + y112 + y113 + y121 + y122 + y123) + (2 – 0.35) (y211 + y221) + (2.8 – 0.5) y322 – 300/6000 [5(y111 + y112 + y113) + 10 y211] – 321/10000 [7(y121 + y122 + y123) + 9 y221 +12 y322] – 250/4000 [6(y111 + y121) + 8(y211 + y221)] – 783/7000 [4(y112 + y122) + 11 y322] – 200/4000 [7(y113 + y123)]•约束条件为：s.t. 5(y111 + y112 + y113) + 10 y211 ≤ 6000 （ 设备 A1 ） 7(y121 + y122 + y123) + 9 y221 +12 y322 ≤ 10000 （ 设备 A2 ） 6(y111 + y121) + 8(y211 + y221) ≤ 4000 （ 设备 B1 ） 4(y112 + y122) + 11 y322 ≤ 7000 （ 设备 B2 ） 7(y113 + y123) ≤ 4000 （ 设备 B3 ） yijk ≥ 0 , i = 1,2,3; j = 1,2; k = 1,2,3套裁下料问题•例5．某工厂要做100套钢架，每套用长为 2.9m，2.1m，1.5m 的圆钢各一根。

已知原料每根长 7.4m，问：应如何下料，可使所用原料最省？解： 共可设计下列 5 种下料方案，见下表设 x1, x2, x3, x4, x5 分别为上面 5 种方案下料的原材料根数 套裁下料问题•最优解：x1=30，x2=10，x3=0，x4=50，x5=0•约束条件中，用“=”还是“≥”？目标函数： min 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 ≥ 0配料问题（1）•例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。

问：该厂应如何安排生产，使利润收入为最大？解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量目标函数： 利润最大，利润 = 收入 – 原料支出 约束条件： 规格要求 4 个；供应量限制 3 个配料问题（1）目标函数：max 50 (x11+x12+x13 ) + 35 (x21+x22+x23) + 25 (x31+x32+x33) – 65 (x11+x21+x31) – 25 (x12+x22+x32) – 35(x13+x23+x33)= – 15x11 + 25x12 + 15x13 – 30x21 + 10x22 – 40x31 – 10x33 约束条件： 从第 1个表中有： x11 ≥ 0.5(x11 + x12 + x13) x12 ≤ 0.25(x11 + x12 + x13) x21 ≥ 0.25(x21 + x22 + x23) x22 ≤ 0.5(x21 + x22 + x23)从第 2 个表中有： x11 + x21 + x31 ≤ 100 x12 + x22 + x32 ≤ 100 x13 + x23 + x33 ≤ 60配料问题（1）•线性规划模型为：目标函数：max z = – 15x11+25x12+15x13 – 30x21+10x22 – 40x31 – 10x33 约束条件： s.t. 0.5 x11 – 0.5 x12 – 0.5 x13 ≥ 0 （原材料1不少于50%） – 0.25x11+0.75x12 – 0.25x13 ≤ 0 （原材料2不超过25%） 0.75x21 – 0.25x22 – 0.25x23 ≥ 0 （原材料1不少于25%） – 0.5 x21+0.5 x22 – 0.5 x23 ≤ 0 （原材料2不超过50%） x11 + x21 + x31 ≤ 100 (供应量限制） x12 + x22 + x32 ≤ 100 (供应量限制） x13 + x23 + x33 ≤ 60 (供应量限制） xij ≥ 0，i = 1,2,3；j = 1,2,3解得： x11 = 100，x21 = 50，x31 = 50配料问题（2）•例7. 汽油混合问题。

一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于下表中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求也列于下表中问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？标准汽油辛烷数蒸汽压力(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不少于250000配料问题（2）•解：设xij为飞机汽油 i 中所用标准汽油 j 的数量(L)•目标函数为飞机汽油1的总产量：x11+ x12+ x13+ x14•库存量约束为：x11+ x21 ≤ 380000x12+ x22 ≤ 265200x13+ x23 ≤ 408100x14+ x24 ≤ 130100•产量约束为飞机汽油2的产量： x21+ x22+ x23+ x24 ≥ 250000配料问题（2）•物理上的分压定律：•得到有关蒸汽压力的约束条件：即同理有：•同理，得到有关辛烷数的约束条件：配料问题（2）•线性规划模型：投资问题（1）•例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资：–项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；–项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；–项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；–项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。

•据测定每万元每次投资的风险指数如下表：•问：–（1）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？–（2）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？投资问题（1）•注意两个问题：–连续投资–闲置资金•决策变量：设 xij ( i = 1～5，j = 1～4)表示第 i 年初投资于A (j=1)、B (j=2)、C (j=3)、D (j=4)项目的金额这样我们建立如下的决策变量：Ax11x21x31x41x51Bx12x22x32x42Cx33 Dx24投资问题（1）•约束条件：–第一年：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–非负条件： xij ≥0 ( i = 1～5，j = 1～4)•目标函数：max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24投资问题（2）•决策变量：同上•目标函数： min f = x11+x21+x31+x41+x51 + 3(x12+x22+x32+x42) + 4x33 + 5.5x24 •约束条件：–问题（1）中的条件–“第五年末拥有资金本利在330万元”的条件： 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 ≥ 330投资问题（2）•决策变量：–设 xij ( i = 1～5，j = 1～4)表示第 i 年初投资于A (j=1)、B (j=2)、C (j=3)、D (j=4)项目的金额。

–设si ( i = 1～5)表示第 i 年的闲置资金Ax11x21x31x41x51Bx12x22x32x42Cx33 Dx24闲置 s1 s2 s3 s4 s5投资问题（2）•约束条件：–第一年：投资额与闲置资金之和为总资金，于是 x11+ x12 + s1 = 200；–第二年：B次年末才可收回投资，故第二年年初有资金 1.1 x11 + s1 ，于是 x21 + x22+ x24 + s2 = 1.1x11 + s1 ；–第三年：年初有资金 1.1x21+ 1.25x12 + s2 ，于是 x31 + x32+ x33 + s3 = 1.1x21+ 1.25x12 + s2 ；–第四年：年初有资金 1.1x31+ 1.25x22 + s3 ，于是 x41 + x42 + s4 = 1.1x31+ 1.25x22 + s3 ；–第五年：年初有资金 1.1x41+ 1.25x32 + s4 ，于是 x51 + s5 = 1.1x41+ 1.25x32 + s4 ；–B、C、D的投资限制： xi2 ≤ 30 ( i =1、2、3、4 )，x33 ≤ 80，x24 ≤ 100–第五年末拥有资金本利在330万元： 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 + s5 ≥ 330–非负条件： xij ≥0 ( i = 1～5，j = 1～4)， si ≥0 ( i = 1～5)•目标函数：min f = x11+x21+x31+x41+x51 + 3(x12+x22+x32+x42) + 4x33 + 5.5x24 作业•2. (1) (3)•3. (1)•4. (1)•5•7•9。