8-第8課-規(guī)劃分析

1、第第8章章 規(guī)劃分析規(guī)劃分析線性規(guī)劃線性規(guī)劃目標(biāo)規(guī)劃目標(biāo)規(guī)劃整數(shù)規(guī)劃整數(shù)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃內(nèi)容內(nèi)容v提出問題提出問題v相關(guān)知識導(dǎo)入相關(guān)知識導(dǎo)入v基本概念解釋基本概念解釋v線性規(guī)劃求解過程線性規(guī)劃求解過程圖解法圖解法v線性規(guī)劃結(jié)果調(diào)整線性規(guī)劃結(jié)果調(diào)整v小結(jié)小結(jié)要求要求v1 掌握線性規(guī)劃的三要素掌握線性規(guī)劃的三要素v2 根據(jù)題目給出的條件能夠建立線性規(guī)劃的根據(jù)題目給出的條件能夠建立線性規(guī)劃的模型模型v3 利用圖解法能夠找到目標(biāo)函數(shù)的最優(yōu)解利用圖解法能夠找到目標(biāo)函數(shù)的最優(yōu)解v4 理解線性規(guī)劃結(jié)果的整數(shù)調(diào)整理解線性規(guī)劃結(jié)果的整數(shù)調(diào)整提出問題提出問題v線性規(guī)劃研究的問題：線性規(guī)劃研究的問題： 1、在、

2、在現(xiàn)有現(xiàn)有的人、財、物等資源條件下，的人、財、物等資源條件下， 研究如何合理地計劃、安排，可使得研究如何合理地計劃、安排，可使得 某一某一目標(biāo)目標(biāo)達到最大，達到最大， 2、在、在任務(wù)任務(wù)確定后，如何計劃、安排，使確定后，如何計劃、安排，使 用用最少最少的人、財、物等資源，去實現(xiàn)的人、財、物等資源，去實現(xiàn) 該任務(wù)，該任務(wù)，尋求在一定約束條件下使某個指標(biāo)達到最優(yōu)尋求在一定約束條件下使某個指標(biāo)達到最優(yōu)如產(chǎn)量、利潤等。如產(chǎn)量、利潤等。如使生產(chǎn)成本、費用最少等。如使生產(chǎn)成本、費用最少等。給定一定量的給定一定量的人力、物力、人力、物力、資金等資源資金等資源完成的任務(wù)量最大完成的任務(wù)量最大經(jīng)濟效益最高經(jīng)濟效

3、益最高給定一項任務(wù)給定一項任務(wù)所耗的人力、所耗的人力、物力資源最少物力資源最少降低成本降低成本獲取最大的利潤獲取最大的利潤精打細(xì)算精打細(xì)算最優(yōu)方案最優(yōu)方案統(tǒng)籌安排統(tǒng)籌安排最佳方案最佳方案 7 7 1212360200300 9 4 3資源單耗資源單耗 產(chǎn)品產(chǎn)品單位產(chǎn)品價格單位產(chǎn)品價格 煤煤 電電 油油資源限量資源限量甲甲 乙乙資源資源v例例1 資源合理利用問題資源合理利用問題 某工廠在某一計劃期內(nèi)準(zhǔn)備生產(chǎn)甲、乙兩種某工廠在某一計劃期內(nèi)準(zhǔn)備生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)需要消耗煤、電、油三種資源。產(chǎn)品，生產(chǎn)需要消耗煤、電、油三種資源。有關(guān)數(shù)據(jù)列表如下。試擬訂使計劃期內(nèi)總收有關(guān)數(shù)據(jù)列表如下。試擬訂使計劃

4、期內(nèi)總收入最大的生產(chǎn)計劃方案？入最大的生產(chǎn)計劃方案？線性規(guī)劃問題線性規(guī)劃問題 4 5 10知識導(dǎo)入知識導(dǎo)入1.在同一坐標(biāo)系上作出下列直線在同一坐標(biāo)系上作出下列直線:2x+y=0; 2x+y=1;2x+y=-3;2x+y=4;2x+y=7平行。的直線與形如結(jié)論02)0(2:yxttyxxYo這些直線之間什么關(guān)系？這些直線之間什么關(guān)系？2.畫出不等式2x+y-60表示的平面區(qū)域取原點（取原點（0 0，0 0），），代入不等式代入不等式解：先畫出直線解：先畫出直線2x+y-6=0(2x+y-6=0(畫成畫成虛線虛線) )得左得左=2=20 00 06 66060即原點即原點滿足滿足2x+y-602x

5、+y-60所以原點所以原點在在不等式表示不等式表示的平面的平面區(qū)域內(nèi)區(qū)域內(nèi)故不等式故不等式2x+y-602x+y-60在平面直角坐標(biāo)系中表示直線在平面直角坐標(biāo)系中表示直線Ax+By+C=0某一側(cè)所有點組某一側(cè)所有點組成的平面區(qū)域。成的平面區(qū)域。用不等式表示下列平面區(qū)域：用不等式表示下列平面區(qū)域：xyo1-1（1 1）xyo12（2 2）x-y+10 x+2y-20二元一次不等式區(qū)域的判斷法：二元一次不等式區(qū)域的判斷法：Ax+By=t 若若“”或或“”則把直線畫成則把直線畫成虛線虛線；若；若“”或或“” 則把直線畫成則把直線畫成實線實線由于對直線同一側(cè)的所有點由于對直線同一側(cè)的所有點(x,y)選

6、特殊選特殊點（點（0，0）（）（t不等于零）或（不等于零）或（0，1）（）（t等于零）等于零），把它代入不等式，把它代入不等式，滿足滿足即選即選這一側(cè)，這一側(cè)，反之反之另一側(cè)另一側(cè) 小結(jié)小結(jié)：畫線定界，取點定域畫線定界，取點定域?qū)嵗治觯簩嵗治觯涸O(shè)設(shè)x,y滿足以下條件：滿足以下條件： 求求z=2x+y的最大值與最小值。的最大值與最小值。 133065yxyyx線性約線性約束條件束條件 目標(biāo)函數(shù)目標(biāo)函數(shù)（線性目標(biāo)函數(shù)）（線性目標(biāo)函數(shù)）3.不等式組表示的區(qū)域的確定不等式組表示的區(qū)域的確定如圖，分別作出如圖，分別作出 三條三條直線，直線，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+

7、6y=30 再找出不等式組再找出不等式組所表示的平面區(qū)域的所表示的平面區(qū)域的公公共區(qū)域共區(qū)域?？尚杏蚩尚杏騲二元一次不等式組表示平面區(qū)域：二元一次不等式組表示平面區(qū)域：二元一次不等式組所表示的平面區(qū)二元一次不等式組所表示的平面區(qū)域是各個不等式表示的平面點集的域是各個不等式表示的平面點集的交集交集，即各個不等式所表示的平面，即各個不等式所表示的平面區(qū)域的區(qū)域的公共部分公共部分?；靖拍罨靖拍?由由x，y 的不等式的不等式(或方程或方程)組成的組成的不等式組不等式組稱為稱為x，y 的的約束條件約束條件。關(guān)于。關(guān)于x，y 的的一次一次不等式或方程組成的不不等式或方程組成的不等式組稱為等式組稱為x，

8、y 的的線性線性約束條件約束條件。 欲達到最大值或最小值所涉及的變量欲達到最大值或最小值所涉及的變量x，y 的解析式的解析式稱為稱為目標(biāo)函數(shù)目標(biāo)函數(shù)。關(guān)于。關(guān)于x，y 的一次目標(biāo)函數(shù)稱為的一次目標(biāo)函數(shù)稱為線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)。 求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值問題稱為值問題稱為線性規(guī)劃問題線性規(guī)劃問題。 滿足線性約束條件的解（滿足線性約束條件的解（x，y）稱為）稱為可行解可行解。所有。所有可行解組成的集合稱為可行解組成的集合稱為可行域可行域。 使目標(biāo)函數(shù)取得最大值或最小值的可行解稱為使目標(biāo)函數(shù)取得最大值或最小值的可行解稱為最優(yōu)最優(yōu)解

9、解。1255334xyxyx設(shè)設(shè)z=2x+y,求滿足求滿足時時,求求z的最大值和最小值的最大值和最小值.線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)線性約線性約束條件束條件線性規(guī)線性規(guī)劃問題劃問題任何一個滿足任何一個滿足不等式組的不等式組的（x,yx,y）可行解可行解可行域可行域所有的所有的最優(yōu)解最優(yōu)解x2504030201010203040 x1x2504030201010203040 x1x2504030201010203040 x12x1+x2 504x1+3x2 120 x2504030201010203040 x1O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）x2504030201010

10、203040 x1x2504030201010203040 x1x2504030201010203040 x1Q2（15，20）線性規(guī)劃模型的三要素：線性規(guī)劃模型的三要素： 決策變量：決策變量：需決策的量，即待求的未知數(shù)。需決策的量，即待求的未知數(shù)。目標(biāo)函數(shù)：目標(biāo)函數(shù)：需優(yōu)化的量，即欲達到的目標(biāo)，需優(yōu)化的量，即欲達到的目標(biāo)，用決策變量的表達式表示。用決策變量的表達式表示。約束條件：約束條件：為實現(xiàn)優(yōu)化目標(biāo)受到的限制，用為實現(xiàn)優(yōu)化目標(biāo)受到的限制，用決策變量的等式或不等式表示。決策變量的等式或不等式表示。 某工廠生產(chǎn)甲、乙兩種產(chǎn)品某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品已知生產(chǎn)甲種產(chǎn)品1t需消需

11、消耗耗A種礦石種礦石10t、B種礦石種礦石5t、煤、煤4t；生產(chǎn)乙種產(chǎn)品；生產(chǎn)乙種產(chǎn)品1噸需噸需消耗消耗A種礦石種礦石4t、B種礦石種礦石4t、煤、煤9t。每。每1t甲種產(chǎn)品的利潤甲種產(chǎn)品的利潤是是600元元,每每1t乙種產(chǎn)品的利潤是乙種產(chǎn)品的利潤是1000元。元。 工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗A種礦石不超種礦石不超過過300t、 消耗消耗B種礦石不超過種礦石不超過200t、消耗煤不超過、消耗煤不超過360t。 若你是廠長若你是廠長,你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到精確到0.1t),才能使利潤總額達到最大才能使利潤

12、總額達到最大?例例請寫出目標(biāo)函數(shù)和約請寫出目標(biāo)函數(shù)和約束條件束條件決策變量是什么？決策變量是什么？v在本例中在本例中決策變量決策變量：甲、乙產(chǎn)品的計劃產(chǎn)量，記為：甲、乙產(chǎn)品的計劃產(chǎn)量，記為 ,目標(biāo)函數(shù)目標(biāo)函數(shù)：總收入記為：總收入記為 , 則則為體現(xiàn)追求極大化，在前面冠以極大號為體現(xiàn)追求極大化，在前面冠以極大號max；約束條件約束條件：分別來自資源煤、電、油限量的約束，：分別來自資源煤、電、油限量的約束，和產(chǎn)量非負(fù)的約束，表示為和產(chǎn)量非負(fù)的約束，表示為z1x2x211000600 xxz0,3004102004536094. .21212121xxxxxxxxtsjx2 , 1j2, 1,030

13、04102004536094.1000600max21212121jxxxxxxxtsxxzj解：解： 設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為 個單位個單位（ ）, 獲得總收入為獲得總收入為z ，則上述問題的，則上述問題的數(shù)學(xué)模型為數(shù)學(xué)模型為線性規(guī)劃模型的一個基本特點線性規(guī)劃模型的一個基本特點v目標(biāo)和約束均為變量的目標(biāo)和約束均為變量的線性線性表達式表達式v如果模型中出現(xiàn)如如果模型中出現(xiàn)如v的非線性表達式，則不屬于線性規(guī)劃。的非線性表達式，則不屬于線性規(guī)劃。32211ln2xxx、求解過程求解過程圖解法圖解法實例分析：實例分析：設(shè)設(shè)x,y滿足以下條件：滿足以下條件： 求求z=2x+y的

14、最大值與最小值。的最大值與最小值。 133065yxyyx如圖，分別作出如圖，分別作出 三條三條直線，直線，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+6y=30 再找出不等式組再找出不等式組所表示的平面區(qū)域的公所表示的平面區(qū)域的公共區(qū)域。共區(qū)域?？尚杏蚩尚杏騲設(shè)設(shè)z=0,畫出直線畫出直線l0，即即l0:2x+y=0。o5x+6y=30y=1y=3xyxl0:2x+y=0如圖，平移直線如圖，平移直線l0， 所對應(yīng)的所對應(yīng)的z隨之增大；隨之增大； 所對應(yīng)的所對應(yīng)的z隨之減小。隨之減小。當(dāng)直線當(dāng)直線l0向上平移時，向上平移時， 當(dāng)直線當(dāng)直線l0向下平向下平移移時時, o5x+6y=

15、30y=1y=3xyl0:2x+y=0l1:2x+y=2l2:2x+y=4l3:2x+y=-3(13,1) 此時所對應(yīng)的此時所對應(yīng)的Z最??；最?。?245,1)此時所對應(yīng)的此時所對應(yīng)的Z最大。最大。從而得到：從而得到：zminzmax=2 +1= =2 +1= 1324553535o5x+6y=30y=1y=3xyxABCl0:2x+y=0如圖，在把如圖，在把l0向上平移過程中，直線與平面區(qū)向上平移過程中，直線與平面區(qū)域首先相交于點域首先相交于點A ，當(dāng)相交于點當(dāng)相交于點B ，l1l2總結(jié)：總結(jié)： 從這個問題的求解過程可以從這個問題的求解過程可以看出，最優(yōu)解一般在可行域的看出，最優(yōu)解一般在可行

16、域的邊邊界上界上，而且通常在可行域的，而且通常在可行域的頂點頂點處處取得。取得。5x+4y=202x+3y=12線性目標(biāo)函數(shù)線性目標(biāo)函數(shù)),(M720712Z的最大值為的最大值為44已知實數(shù)已知實數(shù)x,y滿足下列條件滿足下列條件:5x+4y 202x+3y 12x 0y0求求z=9x+10y的最大值的最大值.最優(yōu)解最優(yōu)解可行域可行域9x+10y=0線性約束線性約束條件條件 01 2345 6123456xy圖解法圖解法轉(zhuǎn)化轉(zhuǎn)化線性約線性約束條件束條件可行域可行域轉(zhuǎn)化轉(zhuǎn)化線性目線性目標(biāo)函數(shù)標(biāo)函數(shù)Z=Ax+By一組平行線一組平行線B BZ Zx xy y 轉(zhuǎn)化轉(zhuǎn)化最優(yōu)解最優(yōu)解尋找平行線組尋找平行線

17、組的縱截距的縱截距 最值最值 四個步驟：四個步驟：1、列列4、答答3、移移2、畫畫三個轉(zhuǎn)化三個轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化轉(zhuǎn)化四個步驟四個步驟：1、列（設(shè)出未知數(shù)、列（設(shè)出未知數(shù),列出約束條件列出約束條件,確定目標(biāo)函數(shù)）確定目標(biāo)函數(shù)）三個轉(zhuǎn)化三個轉(zhuǎn)化4、答答（求出點的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）（求出點的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）3、移移（平移直線（平移直線L 。尋找使縱截距取得最值時的點）。尋找使縱截距取得最值時的點）2、畫（畫可行域）、畫（畫可行域）圖解法圖解法線性約束條件線性約束條件可行域可行域線性目標(biāo)函數(shù)線性目標(biāo)函數(shù)Z=Ax+By一組平行線一組平行線BZxy最優(yōu)解最優(yōu)解尋找平行線組的尋找平行線組的

18、最大（?。┛v截距最大（小）縱截距 某工廠生產(chǎn)甲、乙兩種產(chǎn)品某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品已知生產(chǎn)甲種產(chǎn)品1t需消需消耗耗A種礦石種礦石10t、B種礦石種礦石5t、煤、煤4t；生產(chǎn)乙種產(chǎn)品；生產(chǎn)乙種產(chǎn)品1噸需噸需消耗消耗A種礦石種礦石4t、B種礦石種礦石4t、煤、煤9t.每每1t甲種產(chǎn)品的利潤甲種產(chǎn)品的利潤是是600元元,每每1t乙種產(chǎn)品的利潤是乙種產(chǎn)品的利潤是1000元元. 工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗A種礦石不超種礦石不超過過300t、 消耗消耗B種礦石不超過種礦石不超過200t、消耗煤不超過、消耗煤不超過360t. 若你是廠長若你是廠

19、長,你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到精確到0.1t),才能使利潤總額達到最大才能使利潤總額達到最大?例例分分析析問問題題:1.本問題給定了哪些原材料本問題給定了哪些原材料(資源資源)?2.該工廠生產(chǎn)哪些產(chǎn)品該工廠生產(chǎn)哪些產(chǎn)品?3.各種產(chǎn)品對原材料各種產(chǎn)品對原材料(資源資源)有怎樣的要求有怎樣的要求?4.該工廠對原材料該工廠對原材料(資源資源)有何限定條件有何限定條件?5.每種產(chǎn)品的利潤是多少每種產(chǎn)品的利潤是多少?利潤總額如何計算利潤總額如何計算? 原原 材材料料每噸產(chǎn)品消耗的原材料每噸產(chǎn)品消耗的原材料A種礦石種礦石B種礦石種礦石煤煤甲產(chǎn)品甲產(chǎn)品(t) x乙產(chǎn)

20、品乙產(chǎn)品(t)1054449原原 材料限材料限 額額300200360利利 潤潤6001000y把題中限制條件進行轉(zhuǎn)化：把題中限制條件進行轉(zhuǎn)化：約束條件約束條件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目標(biāo)函數(shù)目標(biāo)函數(shù)：設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x、y,利潤總額為利潤總額為z元元解解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x、y,利潤總額為利潤總額為z元元,那么那么10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.畫畫出以上不等式組所表示的可行域出以上不等式

21、組所表示的可行域作作出直線出直線L 600 x+1000y=0.解得交點解得交點M的坐標(biāo)為的坐標(biāo)為(12.4,34.4)5x+4y=2004x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M答答:應(yīng)生產(chǎn)甲產(chǎn)品約應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品噸，乙產(chǎn)品34.4噸，能使利潤總額達到最大。噸，能使利潤總額達到最大。(12.4,34.4)經(jīng)過可行域上的點經(jīng)過可行域上的點M時時,目標(biāo)函數(shù)目標(biāo)函數(shù)在在y軸上截距最大軸上截距最大.9030 0 xy10 201075405040此時此時z=600 x+1000y取得最大值取得最大值.483429100

22、0411229360.y.x把直線把直線L向右上方平向右上方平移移？，2 . 1，7 . 0g。3000g、2000g、3600g。10g、5g、4;g3g、4g、9，利最大兩種飲料各多少杯能獲每天應(yīng)配制全部售出料的使用限額內(nèi)飲料能每天在原元乙種飲料每杯能獲利元利如果甲種飲料每杯能獲糖咖啡額為奶粉已知每天原料的使用限糖咖啡乙種飲料每杯含奶粉糖咖啡甲種飲料每杯含奶粉咖啡館配制兩種飲料y2 . 1x7 . 0z。y、x：咖啡館每天獲利杯乙種飲料杯設(shè)每天應(yīng)配制甲種飲料解0y, 0 x,3000y10 x3,2000y5x4,3600y4x9xy03600y4x93000y10 x32000y5x40

23、y12x70y, 0 x,3000y10 x3,2000y5x4,3600y4x9y2 . 1x7 . 0zABCDC240，200C3000y10 x32000y5x4得解方程組實際問題實際問題線性規(guī)劃問題線性規(guī)劃問題尋找約束條件尋找約束條件建立目標(biāo)函數(shù)建立目標(biāo)函數(shù)列表列表設(shè)立變量設(shè)立變量轉(zhuǎn)化轉(zhuǎn)化1.約束條件要寫全約束條件要寫全; 3.解題格式要規(guī)范解題格式要規(guī)范. 2.作圖要準(zhǔn)確作圖要準(zhǔn)確,計算也要準(zhǔn)確計算也要準(zhǔn)確;注意注意: :總結(jié)總結(jié)解線性規(guī)劃應(yīng)用問題的步驟：解線性規(guī)劃應(yīng)用問題的步驟： （3）移：作出）移：作出z=Ax+By=0時的直線時的直線L，在線性目標(biāo)函，在線性目標(biāo)函數(shù)所表示的一

24、組平行線中，利用平移的方法找出與可數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點且縱截距最大或最小的直線；行域有公共點且縱截距最大或最小的直線； （4）答：通過解方程組求出最優(yōu)解；）答：通過解方程組求出最優(yōu)解； （1）列：設(shè)出未知數(shù)）列：設(shè)出未知數(shù),列出約束條件列出約束條件,確定目標(biāo)函數(shù)；確定目標(biāo)函數(shù)；（2）畫：畫出線性約束條件所表示的可行域；）畫：畫出線性約束條件所表示的可行域；注：注：1.線性目標(biāo)函數(shù)的最大（小）值一般在可行域的頂線性目標(biāo)函數(shù)的最大（?。┲狄话阍诳尚杏虻捻旤c處取得，也可能在邊界處取得。點處取得，也可能在邊界處取得。2.求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線性目標(biāo)函

25、數(shù)求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線性目標(biāo)函數(shù)所表示的幾何意義所表示的幾何意義 在在 y 軸上的截距或其相反數(shù)。軸上的截距或其相反數(shù)。結(jié)果調(diào)整結(jié)果調(diào)整某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ： 解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第二種鋼板張，第二種鋼板y張，張，鋼板鋼板總總張數(shù)為張數(shù)為Z,則則 規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第二種鋼板A規(guī)格規(guī)格B規(guī)格規(guī)格C規(guī)格規(guī)格2121312x+y

26、15,x+2y18,x+3y27,x0y0 某顧客需要某顧客需要A,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為15，18，27塊，塊，若你是若你是經(jīng)理經(jīng)理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少。數(shù)最少。X張張y張張分分析析問問題題: :例例目標(biāo)函數(shù)目標(biāo)函數(shù): z=x+y) )N Ny y, ,x x( ( x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, y0直線直線x+y=12經(jīng)過的經(jīng)過的整點是整點是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解

27、. 作出直線作出直線L:x+y=0，目標(biāo)函數(shù)目標(biāo)函數(shù):z= x+yA(3.6,7.8)當(dāng)直線當(dāng)直線L經(jīng)過點經(jīng)過點A時時z=x+y=11.4,x+y=12解得交點解得交點B,C的坐標(biāo)的坐標(biāo)B(3,9)和和C(4,8)2 4 6181282724681015但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12約束條件約束條件:畫可行域畫可行域平移平移L找交點及交點坐標(biāo)找交點及交點坐標(biāo)) )N Ny y, ,x x( ( 調(diào)整優(yōu)解法調(diào)整優(yōu)解法1.滿足哪些條件的解才是最優(yōu)解滿足哪些條件的解才是最優(yōu)解?2.目標(biāo)函數(shù)經(jīng)過目標(biāo)函數(shù)經(jīng)過A(3.6,7.8)時時Z的值是多少的值是多少?Z的最小值可能是

28、多少的最小值可能是多少?C(4,8)B(3,9)x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*經(jīng)過可行域內(nèi)的整點經(jīng)過可行域內(nèi)的整點B(3,9)和和C(4,8)且和原點距離最近的直線是且和原點距離最近的直線是x+y=12，它們是最優(yōu)解，它們是最優(yōu)解.作出一組平行直線作出一組平行直線t = x+y，目標(biāo)函數(shù)目標(biāo)函數(shù)t = x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法打網(wǎng)格線法在可行域內(nèi)打出網(wǎng)格線，在可行域內(nèi)打出網(wǎng)格線，當(dāng)直線經(jīng)過點當(dāng)直線經(jīng)過點A時時t=x+y=11.4,但它不是最優(yōu)整數(shù)解，但它不是

29、最優(yōu)整數(shù)解，將直線將直線x+y=11.4繼續(xù)向上平移，繼續(xù)向上平移，1212182715978xy00y,0 x40y3x560y5x60y3x460y5x640y3x5滿足約束條件使式中的的最大值求y, x，y150 x200zy150 x200z0y, 0 x8000y600 x1000180y15x18且8 , 3B12, 0C760,720A.12, 0C8 , 3B為所求或即 即先求非整數(shù)條件下的最優(yōu)解，即先求非整數(shù)條件下的最優(yōu)解，調(diào)整調(diào)整Z的值使不定方程的值使不定方程Ax+By=Z存在最大（?。┐嬖谧畲螅ㄐ。┑恼c值，最后篩選出整點最優(yōu)解的整點值，最后篩選出整點最優(yōu)解 即先打網(wǎng)格，

30、描出可行域內(nèi)的即先打網(wǎng)格，描出可行域內(nèi)的整點整點，平移直線，最先經(jīng)過或最后經(jīng)過的整點平移直線，最先經(jīng)過或最后經(jīng)過的整點坐標(biāo)即為最優(yōu)整解坐標(biāo)即為最優(yōu)整解線性規(guī)劃求最優(yōu)整數(shù)解的一般方法線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:1. 1.平移找解法：平移找解法： 2. 2.調(diào)整優(yōu)解法調(diào)整優(yōu)解法：總結(jié)總結(jié)小小 結(jié)結(jié)實際問題實際問題列表列表設(shè)出變量設(shè)出變量尋找約束條件尋找約束條件建立目標(biāo)函數(shù)建立目標(biāo)函數(shù)轉(zhuǎn)化轉(zhuǎn)化建模建模線性規(guī)劃問題線性規(guī)劃問題圖解法圖解法最優(yōu)解最優(yōu)解三個轉(zhuǎn)化三個轉(zhuǎn)化四個步驟四個步驟作答作答調(diào)整調(diào)整最優(yōu)整數(shù)解最優(yōu)整數(shù)解平移找解法平移找解法調(diào)整優(yōu)值法調(diào)整優(yōu)值法常用方法常用方法目標(biāo)函數(shù)目標(biāo)函數(shù)距離距離,斜率等斜率等結(jié)論：結(jié)論：1.線性目標(biāo)函數(shù)的最大（?。┲狄话阍诳删€性目標(biāo)函數(shù)的最大（小）值一般在可行域的頂點處取得，也可能在邊界處取得。行域的頂點處取得，也可能在邊界處取得。2.求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線性目標(biāo)函數(shù)所表示的幾何意義線性目標(biāo)函數(shù)所表示的幾何意義 在在 y 軸上的截距或其相反數(shù)軸上的截距或其相反數(shù)。時間時間所需售貨員所需售貨員 人數(shù)人數(shù)星期日星期日28人人星期一星期一15人人星期二星期二24人人星期三星期三25人人星期四