1、线性规划的应用线性规划的应用1.生产生产2#岩石铵梯炸药和岩石铵梯炸药和3#露天铵梯炸药，配比如下：露天铵梯炸药，配比如下：品种品种 配比（配比（%）原料原料硝酸铵硝酸铵梯恩梯梯恩梯 木粉木粉售价（元售价（元/吨）吨）2#岩石铵梯炸药岩石铵梯炸药8511412003#露天铵梯炸药露天铵梯炸药8839800原料可用量原料可用量(吨吨)4004436该厂应如何规划下个月的生产，才能使产值最高。该厂应如何规划下个月的生产，才能使产值最高。品种品种 配比（配比（%）原料原料硝酸铵硝酸铵梯恩梯梯恩梯 木粉木粉售价（元售价（元/吨）吨）2#岩石铵梯炸药岩石铵梯炸药8511412003#露天铵梯炸药露天铵梯
2、炸药8839800原料可用量原料可用量(吨吨)400443603609004044030110400880850321212121xxxxxxxxx,.218001200 xxZmax设下月生产两种产品分别为设下月生产两种产品分别为x1,x2吨，所获产值为吨，所获产值为Z,2.现要做现要做100套钢架，每套用长为套钢架，每套用长为2.9m,2.1m和和1.5m的元钢各一的元钢各一根。已知原料长根。已知原料长7.4m，问如何下料，使用的原材料最省？，问如何下料，使用的原材料最省？可能的方案可能的方案:2.9m 2.1m 1.5m 用料长用料长m 余料余料(m)设按方案设按方案1、2、3、4、5各
3、截取各截取x1,x2,x3，x4，x5根原料，则根原料，则（1）1 0 3 7.4 0（2）2 0 1 7.3 0.1 （3）0 2 2 7.2 0.2 （4）1 2 0 7.1 0.3(5)0 1 3 6.6 0.80,1003 23100 22 100 2 543215321543421xxxxxxxxxxxxxxx543218.03.02.01.00 xxxxxZMin3.产品产品原料原料甲甲乙乙丙丙原料成本原料成本（元（元/千克千克)每月限制每月限制用量用量(千克千克)A60%15%2.002000B1.502500C20%60%50%1.001200加工费加工费0.500.400.3
4、0售价售价3.402.852.25每月应生产这三种型号的糖果各多少千克，使该厂获利最大？每月应生产这三种型号的糖果各多少千克，使该厂获利最大？设每月生产三种糖果分别为设每月生产三种糖果分别为x1,x2,x3 千克，所获利润为千克，所获利润为321321951452902300252400852500403x.x.x.x.x.x.Z利润利润=收入收入-成本成本 产品产品原料原料甲甲乙乙丙丙原料成本原料成本（元（元/千克千克)每月限制每月限制用量用量(千克千克)A60%15%2.002000B1.502500C20%60%50%1.001200加工费加工费0.500.400.30售价售价3.402
5、.852.25原料约束：？原料约束：？决策变量应重新设定。决策变量应重新设定。设在产品甲中，原料设在产品甲中，原料A、B、C的用量分别为的用量分别为x1,x2,x3,则则x1+x2+x3为甲产品的产量为甲产品的产量，其中，其中，A原料的含量原料的含量60%，可表示为，可表示为603211.xxxx0606040321 xxx.同理。有甲产品中同理。有甲产品中C原料的用量原料的用量203213.xxxx0202080321xxx.即即设乙产品中设乙产品中A、B、C原料的用量分别为原料的用量分别为x4,x5,x6，则有，则有1506544.xxxx606546.xxxx设乙产品中设乙产品中A、B、
6、C原料的用量分别为原料的用量分别为x7,x8,x9，则有，则有509879.xxxx原料用量约束（原料用量约束（A）2000741xxx原料用量约束（原料用量约束（B）2500852xxx原料用量约束（原料用量约束（C）1200963xxx利润利润=收入收入-成本成本原料用量约束（原料用量约束（A）2000741xxx原料用量约束（原料用量约束（B）2500852xxx原料用量约束（原料用量约束（C）1200963xxx原料成本（元原料成本（元/千克千克)2.001.501.00Z=(3.4-0.5)(x1+x2+x3)+(2.85-0.40)(x4+x5+x6)+(2.25-0.30)(x7
7、+x8+x9)1501002963852741xxx.xxx.xxx*-4.连续加工问题连续加工问题 某工厂在第某工厂在第1车间用车间用1单位原料单位原料M加工成加工成3单位产品单位产品A及及2单单位产品位产品B.A可以按单位售价可以按单位售价8元出售，也可以在第元出售，也可以在第2车间继续车间继续加工，单位生产费用要增加加工，单位生产费用要增加6元，加工后单位售价为元，加工后单位售价为16元。元。B可以按单位售价可以按单位售价7元出售，也可以在第元出售，也可以在第3车间继续加工，单车间继续加工，单位生产费用要增加位生产费用要增加4元，加工后单位售价为元，加工后单位售价为12元。原料的单元。原
8、料的单位购入价为位购入价为2元，上述生产费用均不包括工资在内。元，上述生产费用均不包括工资在内。3个车间每月最多有个车间每月最多有20万工时，每小时工资为万工时，每小时工资为0.5元。每元。每加工加工1单位单位M需需1.5工时，如工时，如A继续加工，每单位需继续加工，每单位需3工时，工时，如如B继续加工，每单位需继续加工，每单位需1工时。每月最多能够得到原料工时。每月最多能够得到原料M10万单位，问如何安排生产，使工厂获利最大？万单位，问如何安排生产，使工厂获利最大？M第一车间加第一车间加工，购入费工，购入费用用=2，工资，工资=0.75，工，工时时=1.5A=3MB=2M出售出售A,单价单价
9、=8第二车间加工费用第二车间加工费用=6，工资工资=1.5，工时，工时=3出售出售,单价单价=16出售出售B,单价单价=7第三车间加工费用第三车间加工费用=4，工资工资=0.5，工时，工时=1出售出售,单价单价=12设设 x1=A出售的数量；出售的数量；x2=A在第在第2车间加工后的出售数量；车间加工后的出售数量；x3=B的出售数的出售数量量；x4=B在第在第3车间加工后的出售数量；车间加工后的出售数量；x5=第第1车间所用原料数量车间所用原料数量Max Z=8 X1+8.5 X2+7 X3+7.5 X4-2.75 X5原料供应限制原料供应限制 X5 100000工时限制工时限制 3X2+X4
10、+1.5X5 200000A产品数量的限制产品数量的限制 X1+X2-3X5=0B产品数量的限制产品数量的限制 X3+X4-2X5=05.连续投资问题连续投资问题某部门有现金某部门有现金10万元，在今后五年内考虑给下面项目投资，已知：万元，在今后五年内考虑给下面项目投资，已知：项目项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利，从第一年到第四年每年年初需要投资，并于次年末回收本利115%项目项目D，五年内每年初可购买公债，于当年末归还，并加利息，五年内每年初可购买公债，于当年末归还，并加利息6%项目项目C，第二年初需要投资，到第五年末回收本利，第二年初需要投资，到第五年末回收本利
11、140%，但最大投资额不，但最大投资额不超过超过3万元万元项目项目B，第三年初需要投资，到第五年末回收本利，第三年初需要投资，到第五年末回收本利125%，但最大投资额不，但最大投资额不 超过超过4万元万元12345ABCDX1AX1DX2AX2CX2DX3AX3BX3DX4AX4DX5D解解 设各年用于项目的资金为设各年用于项目的资金为xiji=1,2,5.j=A,B,C,DX1A+X1D=100000X2A+X2C+X2D=1.06 X1DX3A+X3B+X3D=1.15 X1A+1.06 X2DX4A+X4D=1.15 X2A+1.06 X3DX5D=1.15 X3A+1.06 X4DX3
12、B 40000X2C 30000Max Z=1.15X4A+1.40X2C+1.25 X3B+1.06 X5D6.工厂选址问题工厂选址问题 有有A、B、C三个原料产地，其原料要在工厂加工，制成成三个原料产地，其原料要在工厂加工，制成成品，再在销售地出售。品，再在销售地出售。A、B两地又是销售地。已知有关数据两地又是销售地。已知有关数据如下表。如下表。4t原料制成原料制成1t成品。成品。AB间距离间距离150km，BC间距离间距离200km，CA间距离间距离100km。原料运费为。原料运费为300元元/万万tkm，成品运，成品运费为费为250元元/万万tkm。如在。如在B地设厂，每年生产成品不能
13、超过地设厂，每年生产成品不能超过5万万t,在在A、C设厂，生产规模不受限制。设厂，生产规模不受限制。在哪里设厂，生产能力多大，使总费用（生产费、原料费在哪里设厂，生产能力多大，使总费用（生产费、原料费和运输费）最少和运输费）最少?地点 年原料产量(万t)年成品销量(万t)每万t成品加工费(千元)ABC30262471305.543 某公司生产甲、乙、丙三种产品，都需要经过铸造、机加工某公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件既可以外包协作，也可和装配三个车间。甲、乙两种产品的铸件既可以外包协作，也可以自行生产，但产品丙必须本厂铸造才能保证质量。有关
14、的数据以自行生产，但产品丙必须本厂铸造才能保证质量。有关的数据如表。问公司为了获得最大利润，甲、乙、丙三种产品各生产多如表。问公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？少件？7.生产问题生产问题甲乙丙工时限制单件铸造工时/h51078000单件机加工工时/h64812000单件装配工时/（元/件）32210000自产铸件成本/（元/件）454外协铸件成本/（元/件）56-机加工成本/（元/件）213装配成本/（元/件）322产品售价/（元/件）231816X1：三道工序都由本公司加工的甲产品数；：三道工序都由本公司加工的甲产品数；c1=23-（3+2+3）X2：三道工序都由本公司加
15、工的乙产品数；：三道工序都由本公司加工的乙产品数；c2=18-（5+1+2）X3：三道工序都由本公司加工的丙产品数；：三道工序都由本公司加工的丙产品数；c3=16-（4+3+2）X4：由外协铸造再由本公司机加工和装配的甲产品数；：由外协铸造再由本公司机加工和装配的甲产品数；c4=23-（5+2+3）X5：由外协铸造再由本公司机加工和装配的乙产品数；：由外协铸造再由本公司机加工和装配的乙产品数；c5=18-（6+1+2）某工厂有某工厂有3个车间生产同一种产品。每件产品由个车间生产同一种产品。每件产品由4个零件个零件1和和3个零件个零件2组成。这两种零件需耗用两种原材料。已知这两种原组成。这两种零
16、件需耗用两种原材料。已知这两种原材料的供应量分别为材料的供应量分别为300公斤和公斤和500公斤。由于公斤。由于3个车间拥有的个车间拥有的设备及工艺条件不同，每个工班原材料用量和零件产量也不同，设备及工艺条件不同，每个工班原材料用量和零件产量也不同，具体情况如下表。建立产量最多的线性规划模型。具体情况如下表。建立产量最多的线性规划模型。8.非线性规划问题非线性规划问题 用料及产量数车间每班用料数(公斤)每班产量(件数)A材料B材料零件1零件2一车间二车间三车间853698768594设设x1,x2,x3分别为三个车间所开的工班数分别为三个车间所开的工班数8x1+5x2+3x3=3006x1+9
17、x2+8x3=500)3342915,4382617min(xxxxxxz产品的产量产品的产量yxxxyxxx33429154382617yz max目标函数目标函数)3342915,4382617min(xxxxxxy令令9.城市间汽车运输问题城市间汽车运输问题某汽车运输公司经营某汽车运输公司经营A、B、C三个城市之间的货物运三个城市之间的货物运输业务，任两个城市间都有公路连通，货运量及每年输业务，任两个城市间都有公路连通，货运量及每年利润如下表。公司有汽车利润如下表。公司有汽车250辆，每周每辆车最多在两辆，每周每辆车最多在两个城市间单程运行个城市间单程运行4次，由于技术原因，全部汽车每周
18、次，由于技术原因，全部汽车每周末必须停留在末必须停留在A城。汽车回空没有利润，也不记成本，城。汽车回空没有利润，也不记成本，建立最大利润的线性规划模型。建立最大利润的线性规划模型。ABCABC100500150100250200货运量货运量ABCABC50100150150200300利润利润第二章第二章 对偶理论和灵敏度分析对偶理论和灵敏度分析 1 单纯形法的矩阵描述单纯形法的矩阵描述 本节重点：本节重点：单纯形表各部分的数量关系单纯形表各部分的数量关系 方方程程组组中中，非非基基变变量量为为 0 0，基基变变量量系系数数矩矩阵阵为为单单位位矩矩阵阵，故故 XB=B-1b jjjBjjBjj
19、BPBPPCcPBCcbBCz111 可可知知，XS的的系系数数总总对对应应1 B；已已知知1 B，就就能能求求出出整整个个表表。基变量基变量非基变量非基变量 XBXNXSI0B-1 NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b单纯形表的矩阵形式单纯形表的矩阵形式cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 8 16 12 1 4 0 2 0 4 1 0 0 0 1 0 0 0 1-z 0 2 3 0 0 0 cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x4 x2 2
20、8 3 1 0 0 0 0 1 1-4 0 0 1 0-1/21/2 2 1/4-z-13 0 0-2 0 1/41/4 如例如例1 的初始表和第三张表的初始表和第三张表 3821216841 0 02 1 42 0 111-bB 10040241 0 02 1 42 0 1211-PB 20413 0 203133 PBCcB 注意：注意：B 的列顺序的列顺序和和 XB的下标顺序的下标顺序相同。相同。CBB-1称为单称为单纯形乘子向量。纯形乘子向量。cj 2 3 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x4 x2 2 8 3 1 0 0 0 0 1 1-4 0 0 1 0-1 1/2 2 2 1/4-z-13 0 0-2 0 1 1/4 4 第三张表：41 0 02 1 42 0 1 4 0 00 1 42 0 11-BB-1，
