1、3.3.23.3.2簡單的線性規劃問題簡單的線性規劃問題(2)(2)20110507解線性規劃問題的步驟：解線性規劃問題的步驟： （2 2）移：在線性目標函數所表示的一組平行）移：在線性目標函數所表示的一組平行 線中，利用平移的方法找出與可行線中，利用平移的方法找出與可行 域有公共點且縱截距最大或最小的域有公共點且縱截距最大或最小的 直線；直線； （3 3）求：通過解方程組求出最優解；）求：通過解方程組求出最優解；（一般（一般 在直線的交點處取得，所以可帶入在直線的交點處取得，所以可帶入 各交點檢驗）各交點檢驗） （4 4）答：作出答案。）答：作出答案。 （1 1）畫：畫出線性約束條件所表示的

2、可行域；）畫：畫出線性約束條件所表示的可行域；例例1:某工廠生產某工廠生產 甲甲,乙乙 種產品種產品,已知生產甲種產已知生產甲種產品品1t 需耗需耗A種種 礦石礦石10t, B種種礦石礦石5t, 煤煤4t ;生產生產乙種產品乙種產品1t 需耗需耗 A種種礦石礦石 4t,B種種礦石礦石4t, 煤煤9t. 每每1t 甲種甲種產品的利潤是產品的利潤是 600元元,每每1t 乙種乙種產品的產品的利潤利潤 是是 1000 元元. 工廠在生產這兩種產品的計劃工廠在生產這兩種產品的計劃中要求消耗中要求消耗 A種種礦石不超過礦石不超過 300t, B種種礦石不超礦石不超過過200t ,煤煤不超過不超過360t

3、. 甲甲,乙這兩種產品應各生乙這兩種產品應各生產多少產多少 (精確到精確到1t) , 能使利潤總額達到最大能使利潤總額達到最大? 產品消耗量資源甲產品 (t)乙產品 (t)資源限額 (t)A種礦石 (t) 104300 5 4200 4 9 360600 1000 B種礦石 (t)煤 (t)利潤 (元)解：設生產甲，乙兩種產品分別為解：設生產甲，乙兩種產品分別為x(t)，y(t)，利潤，利潤總額為總額為z元，則元，則10 x +4 y3005 x +4 y 2004 x +9 y 360 x 0 y 0z=600 x +1000 yM解：解： 5 x +4 y =200 4 x +9 y =3

4、60解：設生產甲，乙兩種產品分別為解：設生產甲，乙兩種產品分別為x(t)，y(t)利潤總額為利潤總額為z元，由題意得：元，由題意得：作出以上不等式組所表作出以上不等式組所表示的平面區域，即可行示的平面區域，即可行 域。域。目標函數目標函數: z=600 x+1000yl作直線作直線l : 600 x+1000y=0即即l : 3x+5y=0當直線經過可行域上的點當直線經過可行域上的點M時，截距最大，時，截距最大，Z最大最大12得：得： x = 360/29 y =1000/29 34max600 12 1000 3441200zt此時答：解線性規劃應用問題總體步驟：解線性規劃應用問題總體步驟：

5、設變量設變量找約束條件，找目標函數找約束條件，找目標函數圖圖 解解 法法找出可行域找出可行域運運 動動 變變 化化求出最優解求出最優解例例2 2、要將兩種大小不同的鋼板截成、要將兩種大小不同的鋼板截成A,B,CA,B,C三種規格，每張鋼板可同時截得三種規格三種規格，每張鋼板可同時截得三種規格的小鋼板的塊數如下表所示：的小鋼板的塊數如下表所示：第一種鋼板第一種鋼板第二種鋼板第二種鋼板A規格規格B規格規格C規格規格規格類型規格類型鋼板類型鋼板類型211132今需要今需要A,B,CA,B,C三種規格的成品分別至少為三種規格的成品分別至少為1515、1818、2727塊，問各截這兩種鋼板多少張可得所塊

6、，問各截這兩種鋼板多少張可得所需三種規格成品，且使所用鋼板張數最少。需三種規格成品，且使所用鋼板張數最少。x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*作出一組平行直線作出一組平行直線 z = x+y，目標函數目標函數z= x+yB(3,9)C(4,8)A(18/5,39/5)法一：打網格線法法一：打網格線法在可行域內打出網格線，在可行域內打出網格線，當直線經過點當直線經過點A時時 z=x+y=11.4,但它不是最優整數解，但它不是最優整數解，將直線將直線x+y=11.4繼續向上平移，經過可行域內的整點繼續向上平

7、移，經過可行域內的整點B(3,9)和和C(4,8)且和原點距且和原點距離最近的直線是離最近的直線是x+y=12，它們是最優解，它們是最優解.作出可行域作出可行域x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*直線直線x+y=12經過的整點是經過的整點是B(3,9)和和C(4,8)，它們是最優解，它們是最優解. 作出一組平行直線作出一組平行直線 z= x+y，當直線經過點，當直線經過點A時時 z=x+y=11.4,但它不是最優整數解但它不是最優整數解.作直線作直線x+y=12，目標函數目標函數z= x+yB(3,9)

8、C(4,8)A(18/5,39/5)x+y=12解得交點解得交點B,C的坐標的坐標B(3,9)和和C(4,8) .二、調整優值法：二、調整優值法：在可行域內找出最優解、線性規劃整數在可行域內找出最優解、線性規劃整數解問題的一般方法是：解問題的一般方法是：1.若區域若區域“頂點頂點”處恰好為整點，那么它就是最處恰好為整點，那么它就是最優解；（在包括邊界的情況下）優解；（在包括邊界的情況下）2. 調整優值法：調整優值法：若區域若區域“頂點頂點”不是整點或不包不是整點或不包括邊界時，應先求出該點坐標，并計算目標函數括邊界時，應先求出該點坐標，并計算目標函數值值Z，然后在可行域內適當放縮目標函數值，使然后在可行域內適當放縮目標函數值，使它為整數，它為整數，且與且與Z最接近，在這條對應的直線中，最接近，在這條對應的直線中，取可行域內整點，如果沒有整點，繼續放縮，直取可行域內整點，如果沒有整點，繼續放縮，直至取到整點為止。至取到整點為止。3.平移找解法：平移找解法： 在可行域內找整數解，一般采用在可行域內找整數解，一般采用平移找解法，即打網絡、找整點、平移直線、找平移找解法，即打網絡、找整點、平移直線、找出整數最優解出整數最優解2210,20220(1)34(2)6210314.3xy