1、 一、建立问题的数学模型一、建立问题的数学模型 二、求问题的解二、求问题的解 三、问题的灵敏度分析三、问题的灵敏度分析运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线性规划模型的应用线性规划模型的应用Linear ProgrammingLinear Programming第第3 3章章 某厂生产甲、乙两种产品，要消耗某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每生产单位产品甲需要三种资源，已知每生产单位产品甲需要A、B、C资源分别是资源分别是3、2、0，生产单位产品乙需，生产单位产品乙需要要A、B、C资源分别是资源分别是2、1、3，资源资源A、B、C的现有数量分
2、别是的现有数量分别是65、40、75，甲、乙两种，甲、乙两种产品的单位利润分别是产品的单位利润分别是1500、2500，问如何，问如何安排生产计划，使得既能充分利用现有资源又安排生产计划，使得既能充分利用现有资源又使总利润最大使总利润最大？产品甲产品甲产品乙产品乙资源的限制资源的限制资源资源A3265资源资源B2140资源资源C0375单位利润单位利润15002500 x2x1解：解：1确定决策变量：确定决策变量：设x1表示生产甲产品的数量；x2表示生产乙产品的数量2确定目标函数：确定目标函数：工厂的目标是总利润最大 z=1500 x1+2500 x23确定约束条件：确定约束条件：3x1+2x
3、265（A资源的限制）2x1+x2 40（B资源的限制）3x2 75（C资源的限制）4变量取值限制：变量取值限制：一般情况，决策变量只取大于等于0的值（非负值）x1 0,x2 0 3x2 75 753.1、市场营销问题、市场营销问题3.2、财务管理问题（投资问题）、财务管理问题（投资问题）3.3、营运管理问题、营运管理问题生产计划问题、外购自制生产问题、套裁下料问题生产计划问题、外购自制生产问题、套裁下料问题3.4、产品配方问题、产品配方问题3.5、人力资源管理问题、人力资源管理问题【例3.1】某房地产开发公司正在建造一个湖边小区，公司准备投入3万元进行广告媒体宣传,希望能够吸引周围的中高收入
4、家庭前来购房。目前有5种媒体可供选择，相关信息如表3.1所示。对于这次活动，公司有下列要求：（对于这次活动，公司有下列要求：（1）至少进行）至少进行10次电次电视广告播放；（视广告播放；（2）至少有）至少有5万名潜在顾客被告知；（万名潜在顾客被告知；（3）电视广告投入不超过电视广告投入不超过18000元。如何进行媒体组合，才能元。如何进行媒体组合，才能使广告质量最高使广告质量最高?(1)确定决策变量确定决策变量:设x，x，x，x，x，分别表示日间电视、夜间电视、日报、周末新闻杂志、电台广播五种媒体的使用次数。（2）确定约束条件）确定约束条件预算资金约束：预算资金约束：总共花费的广告费用不能超过
5、公司的总共花费的广告费用不能超过公司的3万元资金预算，即：万元资金预算，即：1500 x+3000 x+400 x+1000 x+100 x 30000电视广告播放次数的限制：电视广告播放次数的限制：至少进行至少进行10次电视广告播放，即：次电视广告播放，即：x+x 10潜在顾客被告知度的限制：潜在顾客被告知度的限制：至少有至少有50000名潜在顾客被告知，即：名潜在顾客被告知，即：1000 x+2000 x+1500 x+2500 x+300 x 50000电视广告投入资金的限制电视广告投入资金的限制：电视广告投入不超过电视广告投入不超过l 8000元，即元，即:1500 x+3000 x
6、18000媒体最高使用次数约束：媒体最高使用次数约束：x 15x 10 x 25x 4x 30非负约束非负约束：x，x，x，x，x 0(3)确定目标确定目标函数函数。此次活动的目标是实现广告播放中产品的宣传质量最高，即：Max Z=65 x+90 x+40 x+60 x+20 x(4)变量取值限制：变量取值限制：x,x,x,x,x 0综上所述，该问题的线性规划模型为：Max Z=65 x+90 x+40 x+60 x+20 x 1500 x+3000 x+400 x+1000 x+100 x 30000 x+x 10 1000 x+2000 x+1500 x+2500 x+300 x 5000
7、0 1500 x+3000 x 18000s.t x 15 x 10 x 25 x 4 x 30 x，x，x，x，x 0例例1、某公司在今后四年内考虑以下四个投资项目选择问题：某公司在今后四年内考虑以下四个投资项目选择问题：项目甲：第二年初需投资，到第四年年末收回本利项目甲：第二年初需投资，到第四年年末收回本利180%；项目乙：从第一年到第三年，每年年初需投资，并于次年年项目乙：从第一年到第三年，每年年初需投资，并于次年年 末收回本利末收回本利120%；项目丙：从第一年开始每年年初可购买公债，于当年年末归项目丙：从第一年开始每年年初可购买公债，于当年年末归 还，并加息还，并加息10%；项目丁：
8、第一年初需投资，到第二年年末收回本利项目丁：第一年初需投资，到第二年年末收回本利135%；第三年初又投资，到第四年年末收回本利第三年初又投资，到第四年年末收回本利130%此外，为了使每年项目之间保持平衡性，要求每年年末回收的资此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初金全部投资到第二年年初,另外项目甲每年的最大投资额将另外项目甲每年的最大投资额将不超过不超过8万元，该部门现有投资资金万元，该部门现有投资资金30万元。应如何确定这万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达
9、到最大？试建立该问题的线性规划模型。本利总额达到最大？试建立该问题的线性规划模型。解：解：根据题意，可假设如下决策变量：根据题意，可假设如下决策变量：第一年第一年 第二年第二年 第三年第三年 第四年第四年 项目甲：项目甲：x12项目乙：项目乙：x21 x22 x23 项目丙：项目丙：x31 x32 x33 x34 项目丁：项目丁：x41 x43maxZ=180%x12+120%x23+110%x34+130%x43.x21+x31+x41 =30 x12+x22+x32 =110%x31s.t.x23+x33+x43 =120%x21+110%x32+135%x41 x34=120%x22+1
10、10%x33 x128 x12,x21,x22,x23,x31,x32,x33,x34,x41,x43 0 例、例、永久机械厂生产甲、乙、丙三种产品，每种产品永久机械厂生产甲、乙、丙三种产品，每种产品均要经过均要经过A、B两道加工工序。设该厂有两种规格的设两道加工工序。设该厂有两种规格的设备能完成工序备能完成工序A，它们以，它们以A1、A2表示；有三种规格的表示；有三种规格的设备能完成工序设备能完成工序B，它们以，它们以B1、B2、B3表示。产品甲表示。产品甲可在工序可在工序A和和B的任何规格的设备上加工；产品乙可在的任何规格的设备上加工；产品乙可在工序工序A的任何一种规格的设备上加工，但完成
11、工序的任何一种规格的设备上加工，但完成工序B时，时，只能在设备只能在设备B1上加工；产品丙只能在设备上加工；产品丙只能在设备A2与与B2上上加工。已知在各种设备上加工的单件工时、各种设备加工。已知在各种设备上加工的单件工时、各种设备的有效台时如表所示。另外已知产品甲、乙、丙的原的有效台时如表所示。另外已知产品甲、乙、丙的原料单价分别为料单价分别为0.25元元/件、件、0.35元元/件和件和0.5元元/件，销售件，销售单价分别为单价分别为1.25元元/件、件、2元元/件和件和2.8元元/件，要求制定件，要求制定最优的产品加工方案，使该厂利润最大。最优的产品加工方案，使该厂利润最大。设备设备产品单
12、件工时（小时产品单件工时（小时/件）件）设备的有设备的有效台时效台时（小时）（小时）甲甲乙乙丙丙AA15106000A2791210000BB1684000B24117000B374000原料费原料费(元元/件件)0.250.350.5单价单价(元元/件件)1.2522.8解：解：根据题意，生产三种产品分别有如下几种方案：根据题意，生产三种产品分别有如下几种方案：甲甲：（：（A1,B1),(A1,B2),(A1,B3),(A2,B1),(A2,B2),(A2,B3)六种方案六种方案 乙：（乙：（A1，B1），（），（A2，B1）两种方案）两种方案丙：（丙：（A2，B2）一种方案）一种方案 令令
13、xi表示采用第表示采用第i种方案进行加工的某种产品的数量种方案进行加工的某种产品的数量(i=1,2,9)x1 x2 x3 x4 x5 x6 x7 x8 x9Maxz=(1.25-0.25)(x1+x2+x3+x4+x5+x6)+(2-0.35)(x7+x8)+(2.8-0.5)x9 5(x1+x2+x3)+10 x76000 7(x4+x5+x6)+9x8+12x9 10000s.t.6(x1+x4)+8x7+8x8 4000 4(x2+x5)+11x97000 7(x3+x6)4000 xi0 (i=1,2,9)整理得：整理得：Maxz=x1+x2+x3+x4+x5+x6+1.35x7+1.
14、65x8+2.3x9 5x1+5x2+5x3 +10 x7 6000 7x4+7x5+7x6 +9x8+12x9 10000s.t.6x1 +6x4 +8x7+8x8 4000 4x2 +4x5 +11x97000 7x3 +7x6 4000 xi0 (i=1,2,9)例、例、永久机械厂生产甲、乙、丙三种产品，每种产品均要经过永久机械厂生产甲、乙、丙三种产品，每种产品均要经过A、B两道加工工序。设该厂有两种规格的设备能完成工序两道加工工序。设该厂有两种规格的设备能完成工序A，它们，它们以以A1、A2表示；有三种规格的设备能完成工序表示；有三种规格的设备能完成工序B，它们以，它们以B1、B2、B
15、3表示。产品甲可在工序表示。产品甲可在工序A和和B的任何规格的设备上加工；的任何规格的设备上加工；产品乙可在工序产品乙可在工序A的任何一种规格的设备上加工，但完成工序的任何一种规格的设备上加工，但完成工序B时，只能在设备时，只能在设备B1上加工；产品丙只能在设备上加工；产品丙只能在设备A2与与B2上加工。上加工。已知在各种设备上加工的单件工时、各种设备的有效台时以及已知在各种设备上加工的单件工时、各种设备的有效台时以及满负荷操作时的设备费用满负荷操作时的设备费用如表所示。另外已知产品甲、乙、丙如表所示。另外已知产品甲、乙、丙的原料单价分别为的原料单价分别为0.25元元/件、件、0.35元元/件
16、和件和0.5元元/件，销售单价件，销售单价分别为分别为1.25元元/件、件、2元元/件和件和2.8元元/件，要求制定最优的产品加件，要求制定最优的产品加工方案，使该厂利润最大。工方案，使该厂利润最大。设备设备产品单件工时（小时产品单件工时（小时/件）件）设备的有设备的有效台时效台时（小时）（小时）满负荷时满负荷时的设备费的设备费用（元）用（元）甲甲乙乙丙丙AA15106000300A2791210000321BB1684000250B24117000783B374000200原料费原料费(元元/件件)0.250.350.5单价单价(元元/件件)1.2522.8解：根据题意，生产三种产品分别有如
17、下几种方案：甲甲：（：（A1,B1),(A1,B2),(A1,B3),(A2,B1),(A2,B2),(A2,B3)六种方案六种方案 乙：（乙：（A1,B1），（），（A2，B1）两种方案）两种方案丙：（丙：（A2,B2）一种方案）一种方案 xi表示采用第表示采用第i种方案进行加工的某种产品的数量种方案进行加工的某种产品的数量(i=1,2,9)x1 x2 x3 x4 x5 x6x7 x8 x9Maxz=x1+x2+x3+x4+x5+x6+1.35x7+1.65x8+2.3x9 -300/6000(5x1+5x2+5x3+10 x7)-321/10000(7x4+7x5+7x6+9x8+12x9
18、)-250/4000(6x1+6x4+8x7)-783/7000(4x2+4x5+11x9)-200/4000(7x3+7x6)约束条件不变约束条件不变设备设备产品单件工时（小时产品单件工时（小时/件）件）设备的有设备的有效台时效台时（小时）（小时）设备加工设备加工费（元费（元/小小时）时）甲甲乙乙丙丙AA151060000.05A27912100000.03BB16840000.06B241170000.10B3740000.05原料费原料费(元元/件件)0.250.350.5单价单价(元元/件件)1.2522.8思考思考！决策变量的另一种表示方法：决策变量的另一种表示方法：根据题意，生产三
19、种产品分别有如下几种方案：根据题意，生产三种产品分别有如下几种方案：甲甲：（：（A1，B1),(A1,B2),(A1,B3),(A2,B1),(A2,B2),(A2,B3)六种方案六种方案乙：（乙：（A1，B1），（），（A2，B1）两种方案）两种方案丙：（丙：（A2，B2）一种方案）一种方案设设i=1,2,3分别表示甲、乙、丙三种产品；分别表示甲、乙、丙三种产品；j=1,2,.分别表示第分别表示第j个方案；个方案；xij表示第表示第i种产品采用第种产品采用第j个方案进行加工的产品的数量个方案进行加工的产品的数量x11 x12 x13 x14 x15 x16x21 x22x31 例、例、某公司
20、面临一个是外包协作还是自行生产某公司面临一个是外包协作还是自行生产的问题。该公司有甲、乙、丙三种产品，这三的问题。该公司有甲、乙、丙三种产品，这三种产品都要经过铸造、机械加工和装配三道工种产品都要经过铸造、机械加工和装配三道工序，甲、乙两种产品的铸件可以外包协作，亦序，甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须由本厂铸造才能可以自行生产，但产品丙必须由本厂铸造才能保证质量，有关情况如表所示，公司中可利用保证质量，有关情况如表所示，公司中可利用的总工时为：铸造的总工时为：铸造8000小时，机械加工小时，机械加工12000小时和装配小时和装配10000小时。为了获得最大利润，小
21、时。为了获得最大利润，甲乙丙三种产品各应生产多少件？甲、乙两种甲乙丙三种产品各应生产多少件？甲、乙两种产品的铸件有多少由本公司铸造？有多少为外产品的铸件有多少由本公司铸造？有多少为外包协作？包协作？工时与成本工时与成本甲甲乙乙丙丙限制工时限制工时每件铸造工时每件铸造工时（小时）（小时）51078000每件机械加工工时每件机械加工工时（小时）（小时）64812000每件装配工时每件装配工时（小时）（小时）32210000自行生产铸件每件自行生产铸件每件成本（元）成本（元）354外包协作铸件每件外包协作铸件每件成本（元）成本（元）56-机械加工每件成本机械加工每件成本（元）（元）213装配每件成本
22、（元）装配每件成本（元）322每件产品售价（元）每件产品售价（元）231816 解：解：设设x1,x2,x3分别表示三道工序都由本公司加工的甲、分别表示三道工序都由本公司加工的甲、乙、丙三种产品的件数乙、丙三种产品的件数,x4,x5分别为由外包协作铸造再分别为由外包协作铸造再由本公司进行机械加工和装配的甲、乙两种产品的件由本公司进行机械加工和装配的甲、乙两种产品的件数，则根据题意，得到原问题的数学模型为数，则根据题意，得到原问题的数学模型为:Maxz=23(x1+x4)+18(x2+x5)+16x3-3x1-5x2-4x3-5x4-6x5 -2(x1+x4)-(x2+x5)-3x3-3(x1+
23、x4)-2(x2+x5)-2x3 5X1+10 x2+7x38000 s.t.6(x1+x4)+4(x2+x5)+8x3 12000 3(x1+x4)+2(x2+X5)+2x3 10000 X1,x2,x3,x4,x50Maxz=15x1+10 x2+7x3+13x4+9x5 5X1+10 x2+7x38000 s.t.6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3X4+2x5 10000 X1,x2,x3,x4,x50整理得：整理得：例、例、某工厂要做某工厂要做100套钢架，每套钢架需套钢架，每套钢架需要长度分别为要长度分别为2.9m，2.1m和和1.5m的圆
24、钢的圆钢各一根。已知原料每根长各一根。已知原料每根长7.4m，问应该，问应该如何下料，可使所用原料最省？如何下料，可使所用原料最省？解：做法一：解：做法一：截取法。截取法。每根原材料中各截取一根组成一套，每根原材料中各截取一根组成一套，2.9+2.1+1.5=6.5 每根料头每根料头0.9m,100根根90m料头，浪费料头，浪费 做法二：做法二：套裁法。套裁法。2.92.11.5合计合计(m)料头料头(m)x1 x2 x3 x4 x5设设xi(i=1,2,5)表示按照方案表示按照方案i下料的下料的原材料的根数，则该问题的数学模型原材料的根数，则该问题的数学模型如下：如下：方案11037.40方
25、案22017.30.1方案30227.20.2方案41207.10.3方案50136.60.8Minz=x1+x2+x3+x4+x5 x1+2x2+x4100 s.t.2x3+2x4+x5100 3x1+x2+2x3+3x5100 x1,x2,x3,x4,x5 0 1、约束条件用等于号如何？、约束条件用等于号如何？2、如果问如何下料，可使料头最少？、如果问如何下料，可使料头最少？例、例、某化工厂根据一项合同要为用户生产某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特一种用甲、乙两种原料混合配制而成的特殊产品殊产品.甲、乙两种原料都含有甲、乙两种原料都含有A、B、C三三种化学
26、成分，其含量（种化学成分，其含量（%）和单位成本以）和单位成本以及按合同规定产品中三种化学成分的最低及按合同规定产品中三种化学成分的最低含量（含量（%）限制如表所示）限制如表所示.问厂方应如何配问厂方应如何配制该产品，使得总成本达到最小？制该产品，使得总成本达到最小？3.4、产品配方问题、产品配方问题 原料化学成分甲乙产品成分最低含量A1234B232C3155单位成本32解：解：(1)确定决策变量：确定决策变量：设每单位该产品用设每单位该产品用x1单位甲原料和单位甲原料和x2单位乙原单位乙原料配制而成料配制而成.(2)所满足的约束条件所满足的约束条件 对化学成分对化学成分A的要求：的要求：1
27、2 x1+3 x2 4 对化学成分对化学成分B的要求：的要求：2 x1+3 x2 2 对化学成分对化学成分C的要求：的要求：3 x1+15 x2 5 配料平衡条件：配料平衡条件：x1+x2=1 (3)明确目标函数明确目标函数：成本最小，即求：成本最小，即求 z=3x1+2x2的最小值的最小值 (4)变量取值限制：变量取值限制：x1，x2 0记为记为 min z=3x1+2x2 s.t.12x1+3x2 4 2x1+3x2 2 3x1+15x2 5 x1+x2 =1 x1，x2 0 例、例、某工厂要用三种原料某工厂要用三种原料1、2、3混合调配出三种混合调配出三种不同规格的产品甲、乙、丙，产品的
28、规格要求、不同规格的产品甲、乙、丙，产品的规格要求、产品的单价、每天能供应的原材料数量及原材产品的单价、每天能供应的原材料数量及原材料单价如表所示，该厂应如何安排生产，才能料单价如表所示，该厂应如何安排生产，才能使利润最大？使利润最大？原料1原料2原料3单价(元/kg)产品甲50%25%不限制50产品乙25%50%不限制35产品丙不限制不限制不限制25每天最多供应量(kg)10010060单价(元/kg)652535解：解：xij设表示第设表示第i种产品中原材料种产品中原材料j的含量的含量(i,j=1,2,3),则三种产品的数量和原材料的数量则三种产品的数量和原材料的数量分别是：分别是：甲：甲
29、：x11+x12+x13乙：乙：x21+x22+x23丙：丙：x31+x32+x33材料材料1：x11+x21+x31材料材料2：x12+x22+x32材料材料3：x13+x23+x33根据题意，得到原问题的数学模型根据题意，得到原问题的数学模型:Max z=50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)x1150%(x11+x12+x13)x12 25%(x11+x12+x13)x2125%(x21+x22+x23)s.t.x22 50%(x21+x
30、22+x23)x11+x21+x31100 x12+x22+x32 100 x13+x23+x33 60 xij0 (i,j=1,2,3)例、例、某昼夜服务的公交线路每天各某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数时间段内所需司机和乘务人员人数如表所示，设司机和乘务人员分别如表所示，设司机和乘务人员分别在各时间段开始时上班，并在各时间段开始时上班，并连续工连续工作八小时作八小时，问该公交线路应怎样安，问该公交线路应怎样安排司机和乘务人员，既能满足工作排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的需要，又使配备司机和乘务人员的人数最少？人数最少？班次时间所需人数班次时
31、间所需人数16:00-10:0060418:00-22:0050210:00-14:0070522:00-2:0020314:00-18:006062:00-6:0030.解：解：设设x i表示在第表示在第i个时期初开始工作的司个时期初开始工作的司机和乘务人员人数机和乘务人员人数(i=1,2,6)，z表示所需表示所需的总人数，则根据题意，得到原问题的数的总人数，则根据题意，得到原问题的数学模型为学模型为:123456161223344556m in.607060502030(1,2.3.4.5.6)0izxxxxxxstxxxxxxxxxxxxxi 例、例、一家中型的百货商场对售货员的需求经过
32、一家中型的百货商场对售货员的需求经过统计分析如表所示，为了保证售货员充分休息，统计分析如表所示，为了保证售货员充分休息，要求售货员要求售货员每周工作五天每周工作五天，休息两天，并要求，休息两天，并要求休息的两天是连续的休息的两天是连续的，问应该如何安排售货员，问应该如何安排售货员的休息日期，既满足工作需要，又使配备的售的休息日期，既满足工作需要，又使配备的售货员的人数最少？货员的人数最少？时间时间所需售货员人数所需售货员人数时间时间所需售货员人数所需售货员人数星期一星期一15星期五星期五31星期二星期二24星期六星期六28星期三星期三25星期日星期日28星期四星期四19 解：解：设设x i表示在星期表示在星期i开始休息的人数开始休息的人数(i=1,2,7)，z表示所需的总人数，则根表示所需的总人数，则根据题意，得到原问题的数学模型为据题意，得到原问题的数学模型为:7654321minxxxxxxxz X1+x2+x3+x4+x528 x2+x3+x4+x5+X615 x3+x4+x5+X6+x724s.t.x4+x5+X6+x7+x125 x5+X6+x7+X1+x219 X6+x7+X1+x2+x331 x7+X1+x2+x3+x428 X1,x2,x3,x4,x5,x6,x70
