线性规划中最优整解的一种求解方法

1、72.线性规划中最优整解的一种求解方法（陕西省小学教师培训中心王凯成 710600）正如文1 所说，“在线性规划问题中，最令学生、教师头疼的莫过于如何寻找最优整解. 通常作法是用网格法，即把可行域中的整点标出，再通过代点检验来完成最优整解寻找；不 过这种方法要经过大量繁复的运算才能保证结果的正确性.”笔者经过研究，找到了一种快 速求解线性规划中最优整解的方法，这种方法不需要作出可行域，简化了作图这一步骤，而 且计算量小，更容易掌握.例1 （文1例2）某人有楼房一幢，室内面积共180m2，拟分割成两类房间作为旅游 客房，大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每

2、 间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000 元，装修小房间每间需600元.如果他只能筹款8000元用于装修，且游客能住满客房，他应 隔出大房间和小房间各多少间，能获得最大收益？（人教社编高中数学第二册p65习题7.4 第4题）解 设隔出大房间x间，小房间y间，收益为z元，z = 200 x+150y = 50 （4x+3y）= 50z，Z = 4x+3y，使z尽可能地大，x、y满足约束条件：8x+15y 1801000 x+600y 8000 x N、y N4x+3y=z，的通解为：尸，一河 N）y = - z + 4t （t Z）18x+15y 1

3、80f z + 2t 60 1000 x+600y 80002z- 3t 40 x3 + x 2 有：7 z 260 n z 371 n Z 37.7由及知:奖-也 t （t Z）32当z = 37时，由知：11上 t 111，但t 乙无解.322当z = 36时，由知：10 t 12，但t 乙所以t=11或t=12.当z = 36且t = 11时，由4x+3y = z的通解知：x = 3， y = 8.当 z = 36 且 t = 12 时，由 4x+3y = z的通解知：x = 0， y = 12.注意到x30，y30.所以，z的最大值为36，z的最大值为50X36=1800.答：应隔出大

4、房间3间，小房间8间；或者隔出小房间12间.这都能获得最大效益.例2 某工厂生产甲、乙两种产品.已知生产甲种产品1t需耗A种矿石10t、B种矿石 5t、煤4t；生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是 600元，每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿 石不超过300t、B种矿石不超过200t、煤不超过360t.甲、乙两种产品应各生产多少（精确 到0.1t），能使利润总额达到最大？（人教社编高中数学第二册p61例3）解设甲种产品生产x个0.1t，乙种产品生产y个0.1t，利润总额为z元则z = 60 x +100y =

5、20 （3x + 5y） = 20z， z = 3x + 5y，应使z尽可能地大.x、y满足约束条件：x + 0.4y 3000.5x + 0.4y 2000.4x + 0.9y 360 x e N,y e N3 x + 5 y = z的通解为:x = 2Z-5t(Z e N) y = -z，+ 3t(t e Z)x + 0.4y 300 0.5x + 0.4y 200 n 0.4x + 0.9y 36010 x + 4y 3000 5x + 4y 20004x + 9y 360016z- 38t v 6z- 13t 2000-z+ 7t 3600 x 7 + x 13有：29Z 60800

6、n Z 2096(Z e N).由、知：166二3000 t 迎土 (t e Z) TOC o 1-5 h z 387且竺* t 迎土 (t e Z您13775z的最大可能值为2096.当z= 2096时，由知：813 t 813，但是t e Z,无解；13714z的最大可能值为2095.当z = 2095时，由知：813 t 813，但是t e Z，无解；137z的最大可能值为2094.当z = 2094时，由知：812 t 8133，但是t e Z，只有t=813.137注意到t=813也满足.所以当z=2094且t=813时，由3x+5y=z的通解知：x=123，y=345.注意到x 3

7、0，y 30.故知z的最大值为2094，z的最大值为20X2094 =41880.答：应生产甲产品约12.3t，乙产品约34.5t，能使利润总额达到最大.(注：例2解法说明中学数学教材给出的解法是不妥的)例3 本公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告，广告 总费用不超过9万元，甲、乙电视台的广告收费标准分别为500元/分钟和200元/分钟，规 定甲、乙两个电视台为该公司所做的每分钟广告，能给公司带来的收益分别为0.3万元和0.2 万元。问该公司如何分配在甲、乙两个电视台的广告时间，才能使公司的收益最大，最大收 益是多少万元？ (2007年山东省高考数学文科第19题)

8、解：设公司在甲电视台和乙电视台做广告的时间分别为x分钟和y分钟，总收益为z元. 由题意得目标函数为 z = 3000 x + 2000y = 1000 (3x + 2y) = 1000 z，z = 3x + 2y，应使x + y 300z尽可能地大.整数x、y满足约束条件：v 500 x + 200y 0, y 03x + 2y = z的通解为 = z-2了 e N).y = - z3t (t e N)x + y 300 x + y 300v 500 x + 200y 90000n 5x + 2y x 0, y 0 x 0, y 0t 3003 z - 4t 900故 3z 4t + 900

9、4 x 300 + 900 = 2100，所以 z 700.当 z取最大值 700 时，t 取最大 值 300，此时 x = 100，y = 200. z 的最大值为 1000 x 700 = 700000.答：该公司在甲电视台做100分钟广告，在乙电视台做200分钟广告，公司的收益最大， 最大收益是70万元.例4 某公司招收男职员x名，女职员y名，x和y须满足约束条件 TOC o 1-5 h z 5 x - 1 Ay- 2 22x + 3y，9则z = x H0的最大值是2x -222x + 3y 92x -225z-16t-22 9x=矿 t, y=t_ 92x 112 Z - 2t 11

10、 II + （ -8）x 有：-11z，3 - 110 n z，W 10 .由及有：z-11 t 22 + 55 （t e Z）216当 z，= 10 时，由知：4.5W t W 4.5 （tZ），无解.当 z，= 9 时，由知：3.5W t W 4.1875 （tZ）， n t = 4 .当z，= 9及t = 4时也满足，由知：x = 5， y = 4.注意到x = 5，y = 4及xN、yN，故知2，的最大值为9, z的最大值为9X10 = 90 . 选择C.根据以上例题可见，快速准确地寻找线性规划问题的整点最优解的一般步骤为：（1）设线性目标函数z = Ax + By = d （ax+b

11、y） = d z，其中d是A与B的最大公约 数，z，= ax+by， （a， b） =1.x=x z，-bt。（t e Z）.y=y z，+at（3）将x=x0z，-bt，y=y0z，+at （t e Z ）代入线性约束条件化简，并消去参数t， 得到z，Wc （或z，3c），c是整数.（4）由约束条件得到不等式g （z，）WtWh （z，）.（5）依次将 z，=c、c-1、c-2、（或依次将 z，=c、c+1、c+2、）代入 g （z，）W t W h （ z，），将第一次得到满足所有约束条件的整数t及相应的z，的值代入 x=x z-bt =0z，+at（t e Z）中就可以得到该整数规划问题的最优解.I 0参考文献1贾耕、张弢，线性规划中最优整解的一种寻找方法J，数学通报，2005, 12.2王凯成，充分利用目标函数解整数规划问题J，数学教学，2004，9.3全日制普通高级中学教科书（必修）数学第二册（上），人民教育出版社，2004年6 月第1版.4安培录，如何寻找线性规划问题的整点最优解J，数学通报，2000，3.5 文吉华，对“如何寻找线性规划问题的整点最优解”一文具体操作中的补充和 完善J，数学通报，200