簡單線性規(guī)劃doc

1、典型例題一xy20，例 1畫出不等式組 xy40， 表示的平面區(qū)域x3 y30.分析：采用“圖解法” 確定不等式組每一不等式所表示的平面區(qū)域，然后求其公共部分解： 把 x0 ，y0代入xy2 中得0020不等式xy20 表示直線xy20下方的區(qū)域（包括邊界），即位于原點的一側(cè)，同理可畫出其他兩部分，不等式組所表示的區(qū)域如圖所示說明：“圖解法”是判別二元一次不等式所表示的區(qū)域行之有效的一種方法典型例題二例 2 畫出 2x3y3 表示的區(qū)域，并求所有的正整數(shù)解( x , y) y2 x 3,x ， y 還有限制條件，即求分析： 原不等式等價于3.而求正整數(shù)解則意味著yx0, y0,xz, yz,y

2、2x3,y3.解： 依照二元一次不等式表示的平面區(qū)域，知2x 3 y3 表示的區(qū)域如下圖：x0, y0,對于 2x 3y 3xz, yz,的正整數(shù)解，先畫出不等式組2 x所表示的平面區(qū)域，y3,y3.如圖所示容易求得，在其區(qū)域內(nèi)的整數(shù)解為(1,1)、(1,2) 、 (1,3)、 (2,2) 、(2,3)說明：這類題可以將平面直角坐標(biāo)系用網(wǎng)絡(luò)線畫出來， 然后在不等式組所表示的平面區(qū)域內(nèi)找出符合題設(shè)要求的整數(shù)點來典型例題三yx11例 3 求不等式組所表示的平面區(qū)域的面積yx1分析：本題的關(guān)鍵是能夠?qū)⒉坏仁浇M所表示的平面區(qū)域作出來， 判斷其形狀進(jìn)而求出其面積而要將平面區(qū)域作出來的關(guān)鍵又是能夠?qū)Σ坏仁?/p>

3、組中的兩個不等式進(jìn)行化簡和變形，如何變形？需對絕對值加以討論解： 不等式 yx1 1 可化為 yx( x1) 或 yx2( x1) ；不等式 yx1可化為 yx1(x0) 或 y x1(x0) 在平面直角坐標(biāo)系內(nèi)作出四條射線AB： yx( x1) ，AC： yx2( x1)DE ： yx1( x 0)， DF ： yx1( x0)則不等式組所表示的平面區(qū)域如圖由于 AB 與 AC 、 DE 與 DF 互相垂直，所以平面區(qū)域是一個矩形根據(jù)兩條平行線之間的距離公式可得矩形的兩條邊的長度分別為2 和 32 22所以其面積為3 2典型例題四2xy120，例 1若 x 、 y 滿足條件3x2 y100，

4、求 zx2y 的最大值和最小值x4y100.分析： 畫出可行域，平移直線找最優(yōu)解解： 作出約束條件所表示的平面區(qū)域，即可行域，如圖所示作直線 l : x2y z ，即 y1 x1 z ，它表示斜率為1，縱截距為 z 的平行2222直線系， 當(dāng)它在可行域內(nèi)滑動時，由圖可知， 直線 l過點時， z 取得最大值， 當(dāng) l 過點 B 時， z 取得最小值 zmax22818zmin2 222說明： 解決線性規(guī)劃問題，首先應(yīng)明確可行域，再將線性目標(biāo)函數(shù)作平移取得最值典型例題五例 5 用不等式表示以A(1, 4) ， B( 3 , 0) ， C( 2 ,2) 為頂點的三角形內(nèi)部的平面區(qū)域分析：首先要將三點

5、中的任意兩點所確定的直線方程寫出來， 然后結(jié)合圖形考慮三角形內(nèi)部區(qū)域應(yīng)怎樣表示。解： 直線 AB 的斜率為：401，其方程為y x 3 kAB( 3)1可求得直線 BC 的方程為 y2x6 直線 AC 的方程為 y2x2 ABC 的內(nèi)部在不等式xy30 所表示平面區(qū)域內(nèi)，同時在不等式2xy60所表示的平面區(qū)域內(nèi)，同時又在不等式2xy20 所表示的平面區(qū)域內(nèi)（如圖）xy30,所以已知三角形內(nèi)部的平面區(qū)域可由不等式組2xy60, 表示2xy20說明： 用不等式組可以用來平面內(nèi)的一定區(qū)域，注意三角形區(qū)域內(nèi)部不包括邊界線典型例題六例 6 已知 xy5 0 ， x y 100求 x2y2的最大、最小值分

6、析： 令 zx 2y2 ，目標(biāo)函數(shù)是非線性的而zx2y2x2y2 2可看做區(qū)域內(nèi)的點到原點距離的平方問題轉(zhuǎn)化為點到直線的距離問題解： 由xy50,得可行域 (如圖所示 )為 zx2y 2x2y2，而 (0,0)到2xy10 0,x y 50 ， xy100 的距離分別為5 和1022所以 z 的最大、最小值分別是50 和 252說明： 題目中的目標(biāo)函數(shù)是非線性的解決的方法類似于線性規(guī)劃問題可做出圖，利用圖進(jìn)行直觀的分析典型例題七4x3y200,例 7 設(shè) z 7x5y 式中的變量 x 、 y 滿足下列條件x3 y 20,求 z 的最大值xN *, yN * .分析： 先作出不等式組所表示的可行

7、域，需要注意的是這里的x、 yN * ，故只是可行域內(nèi)的整數(shù)點，然后作出與直線7x 5 y 0 平等的直線再進(jìn)行觀察解： 作出直線43y20 0和直線 l2： x 3y20 ，得可行域如圖所示l1：x解方程組4x3y20 0得交點 A(22,4) x3 y2055又作直線 l ：7x5y0，平等移動過點A 時， 7 x5 y 取最大值，然而點A 不是整數(shù)點，故對應(yīng)的 z 值不是最優(yōu)解， 此時過點 A 的直線為 7x5y434 ，應(yīng)考慮可行域中距離45直線 7x 5y34，有 z(B )7 25434 ，應(yīng)注意不是找距最近的整點， 即 B( 2 , 4)5點 A 最近的整點，如點C ( 4 ,

8、1) 為可行域中距A 最近的整點，但z(C)7 45133，它小于 z( B) ，故 z 的最大值為34說明：解決這類題的關(guān)鍵是在可行域內(nèi)找準(zhǔn)整點 若將線性目標(biāo)函數(shù)改為非線性目標(biāo)函數(shù)呢？典型例題八x4 y3,例 8 設(shè) z x2y2，式中的變量 x 、 y 滿足 3x5 y25, 試求 z 的最大值、 最小值x1.分析： 作出不等式組所表示的平面區(qū)域，本題的關(guān)鍵是目標(biāo)函數(shù)z x2y2應(yīng)理解為可行域中的點與坐標(biāo)原點的距離的平方解： 作出直線l1： x4 y30 ， l2：3x5y250 ， l3：x1得到如圖所示的可行域x4 y3 0得 A(5,2)由5y253x0x4 y3 0得 C(1,1)

9、由1x3x5y25022)由1得 B(1,x5由圖可知： 當(dāng) ( x ,y) 為點 C (1, 1) 時， z 取最小值為2；當(dāng) ( x , y) 為點 A(5 , 2) 時， z 取最大值 29x說明： 若將該題中的目標(biāo)函數(shù)改為z，如何來求z 的最大值、最小值呢？請自己探y(tǒng)求（將目標(biāo)函數(shù)理解為點(x , y) 與點 (0 , 0) 邊線的斜率）典型例題九例 9 設(shè) x0 ， y0 ， z0 ； p3xy2z， qx2 y4z ， xyz1，用圖表示出點( p , q) 的范圍分析：題目中的 p ，q 與 x ， y ，z 是線性關(guān)系 可借助于 x ， y ，z 的范圍確定 ( p , q)的

10、范圍x1(8q6 p),3xy2zp,271解 ： 由 x2 y4zq, 得 y(145q 3 p), 由 x0 ， y0 ， z0 得xyz 1,27z1(54 p3q),276 pq80,3 p5q140, 做出不等式所示平面區(qū)域如圖所示3 p4q50,說明： 題目的條件隱蔽，應(yīng)考慮到已有的x ， y ， z 的取值范圍借助于三元一次方程組分別求出x ， y ， z ，從而求出p ， q 所滿足的不等式組找出( p , q) 的范圍典型例題十例 10某糖果廠生產(chǎn)A 、 B 兩種糖果，A 種糖果每箱獲利潤40 元， B 種糖果每箱獲利潤 50 元，其生產(chǎn)過程分為混合、烹調(diào)、包裝三道工序，下表

11、為每箱糖果生產(chǎn)過程中所需平均時間（單位：分鐘）AB混合烹調(diào)包裝153241每種糖果的生產(chǎn)過程中，混合的設(shè)備至多能用12 機器小時，烹調(diào)的設(shè)備至多只能用機器 30 機器小時， 包裝的設(shè)備只能用機器 15 機器小時， 試用每種糖果各生產(chǎn)多少箱可獲得最大利潤分析： 找約束條件，建立目標(biāo)函數(shù)解： 設(shè)生產(chǎn) A 種糖果 x 箱， B 種糖果 y 箱，可獲得利潤z 元，則此問題的數(shù)學(xué)模式在x2y7205x4 y1800約束條件3xy900下，求目標(biāo)函數(shù)z40 x50 y 的最大值，作出可行域，其邊界x 0 y 0OA : y0AB : 3xy 9 0 0 0BC : 5x4 y1800 0CD : x2 y

12、7200DO : x 0由 z 40 x50 y 得 y4 xz ，它表示斜率為4，截5505距為 z 的平行直線系，z 越大， z 越大，從而可知過C 點時截5050距最大， z 取得了最大值解方程組x2 y 720C 120，3005x4 y1800 zmax4012050300 19800 即生產(chǎn) A 種糖果 120 箱，生產(chǎn) B 種糖果 300 箱，可得最大利潤19800 元說明： 由于生產(chǎn) A 種糖果120 箱，生產(chǎn) B 種糖果 300 箱，就使得兩種糖果共計使用的混合時間為 1202× 300720（分），烹調(diào)時間 5×120 4×300 1800（分

13、），包裝時間 3×120 300 660（分），這說明該計劃已完全利用了混合設(shè)備與烹調(diào)設(shè)備的可用時間，但對包裝設(shè)備卻有240 分鐘的包裝時間未加利用，這種“過?！眴栴}構(gòu)成了該問題的“松馳”部分，有待于改進(jìn)研究典型例題十一例 11甲、乙、丙三種食物的維生素A、 B 含量及成本如下表：甲乙丙維生素 A （單位 /千克）600700400維生素 B （單位 /千克）800400500成本（元 /千克）1194某食物營養(yǎng)研究所想用x 千克甲種食物，y 千克乙種食物，z 千克丙種食物配成100千克的混合食物，并使混合食物至少含56000 單位維生素A 和 63000 單位維生素 B （ 1）用

14、 x 、 y 表示混合物成本C （ 2）確定 x 、 y 、 z 的值，使成本最低分析： 找到線性約束條件及目標(biāo)函數(shù)，用平行線移動法求最優(yōu)解解：（ 1）依題意：x 、 y 、 z 滿足 xyz100z100xy成本 C11x9 y4z7x5y400 （元）600x700y400z56000（ 2）依題意800x400y500z630002x3y160z100xy3xy130x0， y0作出不等式組所對應(yīng)的可行域，如圖所示3xy 130聯(lián)立y交點A ，x3160250 20作直線 7x5 y400C 則易知該直線截距越小，C 越小，所以該直線過A 50，20時，直線在 y 軸截距最小，從而C 最

15、小，此時7× 505× 20400 C 850 元 x 50 千克， z 30 千克時成本最低典型例題十二例 12 某工廠有甲、 乙兩種產(chǎn)品， 按計劃每天各生產(chǎn)不少于15 t ，已知生產(chǎn)甲產(chǎn)品1 t 需煤 9 t ，電力 4 kW ，勞力3 個（按工作日計算） ；生產(chǎn)乙產(chǎn)品1 t 需煤 4 t ，電力 5 kW ，勞力 10 個；甲產(chǎn)品每噸價7 萬元， 乙產(chǎn)品每噸價12 萬元；但每天用煤最不得超過300 噸，電力不得超過 200 kW ，勞力只有 300 個問每天各生產(chǎn)甲、乙兩種產(chǎn)品多少 t ，才能既保定完成生產(chǎn)任務(wù)，又能為國家創(chuàng)造最多的財富分析： 先設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)

16、品的產(chǎn)量分別為 xt 和 yt ，建立約束條件和目標(biāo)函數(shù)后，再利用圖形直觀解題解： 設(shè)每天生產(chǎn)甲產(chǎn)品xt ，乙產(chǎn)品 yt ，總產(chǎn)值 St ，依題意約束條件為：x15,y15,9 x4 y300,4x5 y200,3x10y300.目標(biāo)函數(shù)為S7x12 y 約束條件表示的可行域是五條直線所圍成區(qū)域的內(nèi)部的點加上它的邊線上的點(如圖陰影部分 )現(xiàn)在就要在可行域上找出使S7x12 y 取最大值的點( x , y) 作直線 S7x12 y ，隨著 S 取值的變化， 得到一束平行直線，其縱截距為S ，可以看出， 當(dāng)直線的縱截距越大，12S 值也越大從圖中可以看出，當(dāng)直線S7x12 y 經(jīng)過點 A 時，直

17、線的縱截距最大，所以S 也取最大值4x5y2000,解方程組3x10 y3000,得 A(20 , 24) 故當(dāng) x20 ， y 24 時，S最大值 7 20 12 24428 (萬元 ) 答：第天生產(chǎn)甲產(chǎn)品 20 t ，乙產(chǎn)品 24 t ，這樣既保證完成任務(wù)，又能為國家創(chuàng)造最多的財富 428 萬元說明： 解決簡單線性規(guī)劃應(yīng)用題的關(guān)鍵是：(1) 找出線性約束條件和目標(biāo)函數(shù)；(2)準(zhǔn)確畫出可行域；(3)利用S 的幾何意義，求出最優(yōu)解如本例中，S是目標(biāo)函數(shù)S7x12 y12的縱截距典型例題十三例 13有一批鋼管，長度都是4000 mm，要截成500 mm 和 600 mm 兩種毛坯，且這兩種毛坯數(shù)

18、量比大于1 配套，怎樣截最合理？3分析：先設(shè)出未知數(shù)， 建立約束條件和目標(biāo)函數(shù)后，再按求最優(yōu)解是整數(shù)解的方法去求解： 設(shè)截 500 mm的 x 根， 600 mm 的 y 根，根據(jù)題意，得5x6 y40,y3x,且 x, y z x 0,y 0.作出可行域，如下圖中陰影部分目標(biāo)函數(shù)為zxy ，作一組平行直線xyt ，經(jīng)過可行域內(nèi)的點且和原點距離最遠(yuǎn)的直線為過B(0 , 8) 的直線，這時xy8 由 x ， y 為正整數(shù)，知 (0 , 8) 不是最優(yōu)解在可行域內(nèi)找整點，使 x y 7可知點 (2,5)， (3,4)，(4,3)， (5 , 2) ， (6 , 1) 均為最優(yōu)解答：每根鋼管截 50

19、0 mm 的 2 根， 600 mm 的 5 根，或截 500 mm的 3 根， 600 mm 的 4根或截 500 mm 的 4 根，600 mm的 3 根或截 500 mm的 5 根，600 mm 的 2 根或截500mm 的6 根， 600 mm 的 1 根最合理mm 的 x 根， 600 mm 的 y 根，則說明： 本題易出現(xiàn)如下錯解：設(shè)截500500x600y4000,6 y 40,x15xy3x,y,3即0,x0,xy0.y0.其中 x 、 y 均為整數(shù)作出可行域，如下圖所示中陰影部分目標(biāo)函數(shù)為zxy ，作一組平行直線 x y t ，經(jīng)過可行域內(nèi)的點且和原點相距最遠(yuǎn)的直線為過A 點

20、的直線 先求 A 點的坐標(biāo)，y3xx4023解得，5x6 y40120y23故 A 40 ,120，即 xy7 ，調(diào)整為 x2 ， y5 2323經(jīng)檢驗滿足條件，所以每根截500 mm 的 2 根， 600mm 的 5 根最合理本題解法錯誤主要是在作一組平行直線xy t 時沒能準(zhǔn)確作出，而得到經(jīng)過可行域內(nèi)的點且和原點距離最遠(yuǎn)的直線為過A 點的直線此錯誤可檢驗如下：如果直線xyt 通過 A 點，它是經(jīng)過可行域內(nèi)的點且到原點距離最遠(yuǎn)的直線，那么40120t ，即 x y 7 由于 x ， y 為整數(shù)，所以點A(117, 55 ) 不是最優(yōu)解但在可23232323行域內(nèi)除 A 點外，不可能再有其他點

21、滿足x y7，只能在可行域內(nèi)找滿足 xy6 的點如果還沒有整數(shù)點，則只能在可行域內(nèi)找滿足xy5 的整數(shù)點但我們知道x2 ，y5滿足題意，這樣，就出現(xiàn)了矛盾，從而判斷解法錯誤，即xyt 通過 A 點的直線并不是通過可行域內(nèi)的點且和原點距離最遠(yuǎn)的直線典型例題十四例 14 某工廠生產(chǎn)A 、 B 兩種產(chǎn)品，已知生產(chǎn)A 產(chǎn)品 1 kg 要用煤 9 t ，電力 4 kW ， 3個工作日； 生產(chǎn) B 產(chǎn)品 1 kg 要用煤 4 t ，電力 5 kW ，10 個工作日 又知生產(chǎn)出A 產(chǎn)品 1 kg可獲利 7 萬元，生產(chǎn)出B 產(chǎn)品 1 kg 可獲利 12 萬元，現(xiàn)在工廠只有煤360 t ，電力 200 kW ，

22、300 個工作日，在這種情況下生產(chǎn)A ， B 產(chǎn)品各多少千克能獲得最大經(jīng)濟效益分析： 在題目條件比較復(fù)雜時，可將題目中的條件列表產(chǎn)品工作日煤t /電力 /利潤 /萬元kWA 產(chǎn)品3947B 產(chǎn)品104512解： 設(shè)這個工廠應(yīng)分別生產(chǎn)A ， B 產(chǎn)品 xkg ， ykg ，可獲利 z 萬元根據(jù)上表中的條3x10 y300,9x4 y360,目標(biāo)函數(shù)為 z7x 12 y (萬元 )件，列出線性約束條件為5 y200,4xx0, y0,畫出如圖所示的可行域，做直線' 712y0'平行，l ：x，做一組直線 7x 12 y t 與 l3x10y300,得 A 點坐標(biāo)為(20 , 24

23、) 把 A 點坐標(biāo)代入 l 的方當(dāng) l 過點 A 時 t 最大由5y200,4x程，得 t428(萬元 )答：應(yīng)生產(chǎn)A 產(chǎn)品 20 t ， B 產(chǎn)品 24 t ，能獲最大利潤428 萬元說明：把實際問題轉(zhuǎn)化為線性規(guī)劃問題的難點在于找出題目中的所有線性約束條件同時本題的可行域形狀較復(fù)雜，要注意分析目標(biāo)函數(shù)的斜率和各邊界斜率的關(guān)系：從而確定在何處取得最優(yōu)解解應(yīng)用題時還應(yīng)注意設(shè)出未知量和做答這兩個必要步驟典型例題十五例 15 某公司每天至少要運送180 t 貨物公司有 8 輛載重為 6t 的 A 型卡車和 4 輛載重為 10t 的 B 型卡車， A 型卡車每天可往返 4 次， B 型卡車可往返3 次

24、， A 型卡車每天花費320 元， B 型卡車每天花費504 元，問如何調(diào)配車輛才能使公司每天花費最少分析： 設(shè) A 型卡車 x 輛， B 型卡車 y 輛問題轉(zhuǎn)化為線性規(guī)劃問題同時應(yīng)注意到題中的 x ， y 只能取整數(shù)0x8,0x8,0y4,0y4,解： 設(shè) A 型卡車 x 輛， B 型卡車 y 輛，則y10,即y10,xx24 x 30 y 180,4x5 y 30,目標(biāo)函數(shù) z 320x504y 做如圖所示的可行域，做直線' 320x504y0在可行域中打上網(wǎng)格， 找出 (8 , 0) ，(8 , 1) ，(8 , 2) ，(7 , 1) ，l ：(7 , 2) ， (7 , 3)

25、 ，等整數(shù)點做l ：320x 504 yt 與 l ' 平行，可見當(dāng) l 過 (8 , 0) 時 t 最小，即 zmin83202560 (元) 說明：整數(shù)解的線性規(guī)劃問題如果取最小值時不是整數(shù)點，則考慮此點附近的整數(shù)點典型例題十六例 16某工廠利用兩種燃料生產(chǎn)三種不同的產(chǎn)品ABCA、 ，每消耗一噸燃料與產(chǎn)品B 、 C 有下列關(guān)系：現(xiàn)知每噸燃料甲與燃料乙的價格之比為 2 : 3，現(xiàn)需要三種產(chǎn)品 A 、 B 、 C 各 50 噸、 63 噸、 65 噸問如何使用兩種燃料，才能使該廠成本最低？分析： 由于該廠成本與兩種燃料使用量有關(guān)，而產(chǎn)品 A 、 B 、 C 又與這兩種燃料有關(guān)，且這三種產(chǎn)品的產(chǎn)量也有限制， 因此這是一道求線性目標(biāo)函數(shù)在線性約束條件下的最小值問題，這類簡單的線性規(guī)劃問題一般都可以利用二元一次不等式求在可行域上的最優(yōu)解解： 設(shè)該廠使用燃料甲x 噸，燃料乙y