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