線性規(guī)劃習題精講

1、線性規(guī)劃常見題型及解法線性規(guī)劃是新教材中新增的內容之一，由已知條件寫出約束條件，并作出可行域，進而通過平移直線在可行域內求線性目標函數(shù)的最優(yōu)解是最常見的題型，除此之外，還有以下六類常見題型。一、求線性目標函數(shù)的取值范圍例1、 若x、y滿足約束條件，則z=x+2y的取值范圍是（）xyO22x=2y =2x + y =2BAA、2,6B、2,5C、3,6D、（3,5解：如圖，作出可行域，作直線l：x+2y0，將l向右上方平移，過點A（2,0）時，有最小值2，過點B（2,2）時，有最大值6，故選A二、求可行域的面積2x + y 6= 0 = 5xy 3 = 0OyxABCMy =2例2、不等式組表示

2、的平面區(qū)域的面積為（）A、4B、1C、5D、無窮大解：如圖，作出可行域，ABC的面積即為所求，由梯形OMBC的面積減去梯形OMAC的面積即可，選B三、求可行域中整點個數(shù)例3、滿足|x|y|2的點（x，y）中整點（橫縱坐標都是整數(shù)）有（）A、9個B、10個C、13個D、14個xyO解：|x|y|2等價于作出可行域如右圖，是正方形內部（包括邊界），容易得到整點個數(shù)為13個，選D四、求線性目標函數(shù)中參數(shù)的取值范圍x + y = 5x y + 5 = 0Oyxx=3例4、已知x、y滿足以下約束條件，使z=x+ay(a>0)取得最小值的最優(yōu)解有無數(shù)個，則a的值為（）A、3B、3C、1D、1解：如圖

3、，作出可行域，作直線l：x+ay0，要使目標函數(shù)z=x+ay(a>0)取得最小值的最優(yōu)解有無數(shù)個，則將l向右上方平移后與直線x+y5重合，故a=1，選D五、求非線性目標函數(shù)的最值2x + y - 2= 0 = 5x 2y + 4 = 03x y 3 = 0OyxA例5、已知x、y滿足以下約束條件，則z=x2+y2的最大值和最小值分別是（）A、13，1B、13，2C、13，D、，解：如圖，作出可行域,x2+y2是點（x，y）到原點的距離的平方，故最大值為點A（2,3）到原點的距離的平方，即|AO|2=13，最小值為原點到直線2xy2=0的距離的平方，即為，選C六、求約束條件中參數(shù)的取值范圍

4、O2x y = 0y2x y + 3 = 0例6、已知|2xym|3表示的平面區(qū)域包含點（0,0）和（1,1），則m的取值范圍是（）A、（-3,6）B、（0,6）C、（0,3）D、（-3,3）解：|2xym|3等價于由右圖可知 ,故0m3，選C線性規(guī)劃的實際應用在科學研究、工程設計、經濟管理等方面，我們都會碰到最優(yōu)化決策的實際問題，而解決這類問題的理論基礎是線性規(guī)劃。利用線性規(guī)劃研究的問題，大致可歸納為兩種類型：第一種類型是給定一定數(shù)量的人力、物力資源，問怎樣安排運用這些資源，能使完成的任務量最大，的效益最大，第二種類型是給定一項任務，問怎樣統(tǒng)籌安排，能使完成這項任務的人力、物力資源量最小。例

5、1、某木器廠生產圓桌和衣柜兩種產品，現(xiàn)有兩種木料，第一種有72m3，第二種有56m3，假設生產每種產品都需要用兩種木料，生產一只圓桌和一個衣柜分別所需木料如下表所示.每生產一只圓桌可獲利6元,生產一個衣柜可獲利10元.木器廠在現(xiàn)有木料條件下,圓桌和衣柜各生產多少,才使獲得利潤最多?產 品木料(單位m3)第 一 種第 二 種圓 桌0.180.08衣 柜0.090.28解：設生產圓桌x只,生產衣柜y個,利潤總額為z元,那么 而z=6x+10y.如上圖所示,作出以上不等式組所表示的平面區(qū)域,即可行域.作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經過可行域

6、上點M,且與原點距離最大,此時z=6x+10y取最大值解方程組,得M點坐標(350,100).答:應生產圓桌350只,生產衣柜100個,能使利潤總額達到最大.指出:資源數(shù)量一定,如何安排使用它們,使得效益最好,這是線性規(guī)劃中常見的問題之一例2、某養(yǎng)雞場有1萬只雞,用動物飼料和谷物飼料混合喂養(yǎng).每天每只雞平均吃混合飼料0.5kg,其中動物飼料不能少于谷物飼料的.動物飼料每千克0.9元,谷物飼料每千克0.28元,飼料公司每周僅保證供應谷物飼料50000kg,問飼料怎樣混合,才使成本最低.解:設每周需用谷物飼料x kg,動物飼料ykg,每周總的飼料費用為z元,那么 ,而z=0.28x+0.9y如下圖

7、所示,作出以上不等式組所表示的平面區(qū)域,即可行域.作一組平行直線0.28x+0.9y=t,其中經過可行域內的點且和原點最近的直線,經過直線x+y=35000和直線的交點,即,時,飼料費用最低.所以,谷物飼料和動物飼料應按5:1的比例混合,此時成本最低.指出:要完成一項確定的任務,如何統(tǒng)籌安排,盡量做到用最少的資源去完成它,這是線性規(guī)劃中最常見的問題之一.(例3圖) (例4圖)例3、下表給出甲、乙、丙三種食物的維生素A、B的含量及成本:甲乙丙維生素A(單位/千克)維生素B(單位/千克)成本(元/千克)400800760020064004005營養(yǎng)師想購這三種食物共10千克,使之所含維生素A不少于

8、4400單位,維生素B不少于4800單位,問三種食物各購多少時,成本最低?最低成本是多少?解:設所購甲、乙兩種食物分別為x千克、y千克,則丙種食物為(10-x-y)千克.x、y應滿足線性條件為 ,化簡得作出可行域如上圖中陰影部分目標函數(shù)為z=7x+6y+5(10-x-y)=2x+y+50,令m=2x+y,作直線l:2x+y=0,則直線2x+y=m經過可行域中A(3,2)時,m最小,即mmin=2´3+2=8，zmin=mmin+50=58答: 甲、乙、丙三種食物各購3千克、2千克、5千克時成本最低,最低成本為58元.指出:本題可以不用圖解法來解,比如,由得z=2x+y+50=(2x-

9、y)+2y+50³4+2´2+50=58,當且僅當y=2,x=3時取等號總結：(1)設出決策變量,找出線性規(guī)劃的約束條件和線性目標函數(shù);(2)利用圖象,在線性約束條件下找出決策變量,使線性目標函數(shù)達到最大(或最小).2.線性規(guī)劃問題的一般數(shù)學模型是:已知(這個式子中的“£”也可以是“³”或“=”號)其中aij (i=1,2,n, j=1,2,m),bi (i=1,2,n)都是常量,xj (j=1,2,m) 是非負變量,求z=c1x1+c2x2+cmxm的最大值或最小值,這里cj (j=1,2,m)是常量. (3)線性規(guī)劃的理論和方法主要在以下兩類問題中得

10、到應用:一是在人力、物力資金等資源一定的條件下,如何使用它們來完成最多的任務；二是給一項任務,如何合理安排和規(guī)劃,能以最少的人力、物力、資金等資源來完成該項任務.線性規(guī)劃中整點最優(yōu)解的求解策略在工程設計、經營管理等活動中，經常會碰到最優(yōu)化決策的實際問題，而解決此類問題一般以線性規(guī)劃為其重要的理論基礎。然而在實際問題中，最優(yōu)解 (x,y) 通常要滿足x,yN ，這種最優(yōu)解稱為整點最優(yōu)解，下面通過具體例子談談如何求整點最優(yōu)解 .1平移找解法 作出可行域后，先打網格，描出整點，然后平移直線l，直線l最先經過或最后經過的那個整點便是整點最優(yōu)解.例1、某木器廠生產圓桌和衣柜兩種產品，現(xiàn)有兩種木料，第一種

11、有72m3，第二種有56m3，假設生產每種產品都需要用兩種木料，生產一只圓桌和一個衣柜分別所需木料如下表所示.每生產一只圓桌可獲利6元,生產一個衣柜可獲利10元.木器廠在現(xiàn)有木料條件下,圓桌和衣柜各生產多少,才使獲得利潤最多?產 品木料(單位m3)第 一 種第 二 種圓 桌0.180.08衣 柜0.090.28解：設生產圓桌x只,生產衣柜y個,利潤總額為z元,那么 而z=6x+10y.如圖所示,作出以上不等式組所表示的平面區(qū)域,即可行域.作直線l:6x+10y=0,即l:3x+5y=0,把直線l向右上方平移至l1的位置時,直線經過可行域上點M,且與原點距離最大,此時z=6x+10y取最大值。解

12、方程組,得M點坐標(350,100).答：應生產圓桌350只,生產衣柜100個,能使利潤總額達到最大.點評：本題的最優(yōu)點恰為直線0.18x+0.09y=72和0.08x+0.28y=56的交點M。例 2 有一批鋼管，長度都是4000mm，要截成500mm和600mm兩種毛坯，且這兩種毛坯按數(shù)量比不小于配套，怎樣截最合理？ 解：設截500mm的鋼管x根，600mm的y根，總數(shù)為z根。根據(jù)題意，得 ，目標函數(shù)為 ，作出如圖所示的可行域內的整點， 作一組平行直線x+y=t，經過可行域內的點且和原點距離最遠的直線為過B（8，0）的直線，這時x+y=8.由于x,y為正整數(shù)，知（8，0）不是最優(yōu)解。顯然要

13、往下平移該直線，在可行域內找整點，使x+y=7，可知點（2，5），（3，4），（4，3），（5，2），（6，1）均為最優(yōu)解答：略點評：本題與上題的不同之處在于，直線x+y=t經過可行域內且和原點距離最遠的點B（8，0）并不符合題意，此時必須往下平移該直線，在可行域內找整點，比如使x+y=7，從而求得最優(yōu)解。 從這兩例也可看到，平移找解法一般適用于其可行域是有限區(qū)域且整點個數(shù)又較少，但作圖要求較高。二、整點調整法先按“平移找解法”求出非整點最優(yōu)解及最優(yōu)值，再借助不定方程的知識調整最優(yōu)值，最后篩選出整點最優(yōu)解 例3已知滿足不等式組，求使取最大值的整數(shù)解：不等式組的解集為三直線：，：，：所圍成的三角

14、形內部（不含邊界），設與，與，與交點分別為，則坐標分別為，作一組平行線：平行于：，當往右上方移動時，隨之增大，當過點時最大為，但不是整數(shù)解，又由知可取，當時，代入原不等式組得， ；當時，得或， 或；當時， ，故的最大整數(shù)解為或3.逐一檢驗法由于作圖有時有誤差，有時僅有圖象不一定就能準確而迅速地找到最優(yōu)解，此時可將若干個可能解逐一校驗即可見分曉 例4 一批長4000mm 的條形鋼材，需要將其截成長分別為518mm與698mm的甲、乙兩種毛坯，求鋼材的最大利用率 解：設甲種毛坯截 x 根，乙種毛坯截 y 根，鋼材的利用率為 P ，則 ，目標函數(shù)為 ，線性約束條件表示的可行域是圖中陰影部分的整點表示

15、與直線518x+698y=4000平行的直線系。所以使P取得最大值的最優(yōu)解是陰影內最靠近直線518x+698y=4000的整點坐標如圖看到(0，5)，(1，4)，(2，4)，(3，3)，(4，2)，(5，2)，(6，1)，(7，0)都有可能是最優(yōu)解，將它們的坐標逐一代入進行校驗，可知當x=5,y=2時， 答：當甲種毛坯截5根，乙種毛坯截2根，鋼材的利用率最大，為99.65% 解線性規(guī)劃問題的關鍵步驟是在圖（可行域）上完成的，所以作圖時應盡可能精確，圖上操作盡可能規(guī)范，但考慮到作圖時必然會有誤差，假如圖上的最優(yōu)點并不十分明顯易辨時，不妨將幾個有可能是最優(yōu)點的坐標都求出來，然后逐一進行校驗，以確定

16、整點最優(yōu)解.線性規(guī)劃的實際應用習題精選 1某家俱公司生產甲、乙兩種型號的組合柜，每種柜的制造白坯時間、油漆時間及有關數(shù)據(jù)如下：問該公司如何安排這兩種產品的生產，才能獲得最大的利潤最大利潤是多少？ 2要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格小鋼板的塊數(shù)如下：每張鋼板的面積，第一種為1m2，第二種為2m2，今需要A、B、C三種規(guī)格的成品各12，15，17塊，問各截這兩種鋼板多少張，可得所需三種規(guī)格成品，且使所用鋼板面積最小 3某人承攬一項業(yè)務，需做文字標牌2個，繪畫標牌3個，現(xiàn)有兩種規(guī)格的原料，甲種規(guī)格每張3m2，可做文字標牌1個，繪畫標牌2個，乙種規(guī)格每張2m2，

17、可做文字標牌2個，繪畫標牌1個，求兩種規(guī)格的原料各用多少張，才能使總的用料面積最小 4某蔬菜收購點租用車輛，將100噸新鮮黃瓜運往某市銷售，可供租用的大卡車和農用車分別為10輛和20輛，若每輛卡車載重8噸，運費960元，每輛農用車載重2.5噸，運費360元，問兩種車各租多少輛時，可全部運完黃瓜，且動費最低并求出最低運費 5某木器廠生產圓桌和衣柜兩種產品，現(xiàn)有兩種木料，第一種有72立方米，第二種有56立方米，假設生產每種產品都需要兩種木料生產一只圓桌需用第一種木料0.18立方米，第二種木料0.08立方米，可獲利潤60元，生產一個衣柜需用第一種木料0.09立方米，第二種0.28立方米，可獲利潤10

18、0元，木器廠在現(xiàn)有木料情況下，圓桌和衣柜應各生產多少，才能使所獲利潤最多解答提示：1設x，y分別為甲、乙兩種柜的日產量，目標函數(shù)z=200x240y，線性約束條件：作出可行域 z最大=200×4240×8=2720答：該公司安排甲、乙兩種柜的日產量分別為4臺和8臺，可獲最大利潤2720元 2設需截第一種鋼板x張，第二種鋼板y張，所用鋼板面積zm2目標函數(shù)z=x2y，線性約束條件：作出可行域作一組平行直線x2y=t的整點中，點(4，8)使z取得最小值答：應截第一種鋼板4張，第二種鋼板8張，能得所需三種規(guī)格的鋼板，且使所用鋼板的面積最小 3設用甲種規(guī)格原料x張，乙種規(guī)格原料y張，所用原料的總面積是zm2，目標函數(shù)z=3x2y，線性約束條件，作出可行域作一組平等直線3x2y=t A不是整點，A不是最優(yōu)解在可行域內的整點中，點B(1，1)使z取得最小值 z最小=3×12×1=5，答：用甲種規(guī)格的