1、第8章 規(guī)劃分析,線性規(guī)劃 目標(biāo)規(guī)劃 整數(shù)規(guī)劃 動(dòng)態(tài)規(guī)劃,內(nèi)容,提出問(wèn)題 相關(guān)知識(shí)導(dǎo)入 基本概念解釋 線性規(guī)劃求解過(guò)程圖解法 線性規(guī)劃結(jié)果調(diào)整 小結(jié),要求,1 掌握線性規(guī)劃的三要素 2 根據(jù)題目給出的條件能夠建立線性規(guī)劃的模型 3 利用圖解法能夠找到目標(biāo)函數(shù)的最優(yōu)解 4 理解線性規(guī)劃結(jié)果的整數(shù)調(diào)整,提出問(wèn)題,線性規(guī)劃研究的問(wèn)題： 1、在現(xiàn)有的人、財(cái)、物等資源條件下， 研究如何合理地計(jì)劃、安排，可使得 某一目標(biāo)達(dá)到最大，,2、在任務(wù)確定后，如何計(jì)劃、安排，使 用最少的人、財(cái)、物等資源，去實(shí)現(xiàn) 該任務(wù)，,尋求在一定約束條件下使某個(gè)指標(biāo)達(dá)到最優(yōu),如產(chǎn)量、利潤(rùn)等。,如使生產(chǎn)成本、費(fèi)用最少等。,給定一定

2、量的 人力、物力、 資金等資源,完成的任務(wù)量最大 經(jīng)濟(jì)效益最高,給定一項(xiàng)任務(wù),所耗的人力、 物力資源最少,降低成本,獲取最大的利潤(rùn),7 12,360 200 300,9 4 3,例1 資源合理利用問(wèn)題 某工廠在某一計(jì)劃期內(nèi)準(zhǔn)備生產(chǎn)甲、乙兩種產(chǎn)品，生產(chǎn)需要消耗煤、電、油三種資源。有關(guān)數(shù)據(jù)列表如下。試擬訂使計(jì)劃期內(nèi)總收入最大的生產(chǎn)計(jì)劃方案？,線性規(guī)劃問(wèn)題,4 5 10,知識(shí)導(dǎo)入,1.在同一坐標(biāo)系上作出下列直線:,2x+y=0; 2x+y=1;2x+y=-3;2x+y=4;2x+y=7,x,Y,o,這些直線之間什么關(guān)系？,2.畫(huà)出不等式2x+y-60表示的平面區(qū)域,取原點(diǎn)（0，0）， 代入不等式,解

3、：先畫(huà)出直線 2x+y-6=0(畫(huà)成虛線),得左=200660,即原點(diǎn)滿足2x+y-60 所以原點(diǎn)在不等式表示的平面區(qū)域內(nèi),故不等式2x+y-60表示 的平面區(qū)域內(nèi)如圖所示,2x+y-6=0,二元一次不等式Ax+By+C0 在平面直角坐標(biāo)系中表示直線 Ax+By+C=0某一側(cè)所有點(diǎn)組 成的平面區(qū)域。,用不等式表示下列平面區(qū)域：,x-y+10,x+2y-20,二元一次不等式區(qū)域的判斷法： Ax+By=t, 若“”或“”則把直線畫(huà)成虛線；若“”或“” 則把直線畫(huà)成實(shí)線,由于對(duì)直線同一側(cè)的所有點(diǎn)(x,y)選特殊點(diǎn)（0，0）（t不等于零）或（0，1）（t等于零），把它代入不等式，滿足即選這一側(cè)，反之另

4、一側(cè),小結(jié)：畫(huà)線定界，取點(diǎn)定域,實(shí)例分析：設(shè)x,y滿足以下條件： 求z=2x+y的最大值與最小值。,線性約 束條件,目標(biāo)函數(shù) （線性目標(biāo)函數(shù)）,3.不等式組表示的區(qū)域的確定,如圖，分別作出 三條直線，,o,5x+6y=30,y=1,y=3x,y,y=1,y=3x,5x+6y=30,再找出不等式組 所表示的平面區(qū)域的公 共區(qū)域。,可行域,x,二元一次不等式組表示平面區(qū)域： 二元一次不等式組所表示的平面區(qū)域是各個(gè)不等式表示的平面點(diǎn)集的交集，即各個(gè)不等式所表示的平面區(qū)域的公共部分。,基本概念,由x，y 的不等式(或方程)組成的不等式組稱(chēng)為x，y 的約束條件。關(guān)于x，y 的一次不等式或方程組成的不等式

5、組稱(chēng)為x，y 的線性約束條件。 欲達(dá)到最大值或最小值所涉及的變量x，y 的解析式稱(chēng)為目標(biāo)函數(shù)。關(guān)于x，y 的一次目標(biāo)函數(shù)稱(chēng)為線性目標(biāo)函數(shù)。 求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題。 滿足線性約束條件的解（x，y）稱(chēng)為可行解。所有可行解組成的集合稱(chēng)為可行域。 使目標(biāo)函數(shù)取得最大值或最小值的可行解稱(chēng)為最優(yōu)解。,線性目標(biāo)函數(shù),線性約束條件,線性規(guī)劃問(wèn)題,任何一個(gè)滿足不等式組的（x,y）,可行解,可行域,所有的,（1）滿足約束條件的變量的值，稱(chēng)為可行解。 （2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱(chēng)為最優(yōu)解。 例 max Z=50 x1+30 x2 s.t. 4x1+3x2 12

6、0 2x1+x2 50 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2 120,由 4x1+3x2 120 x1 0 x2 0 圍成的區(qū)域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,由 2x1+x2 50 x1 0 x2 0 圍成的區(qū)域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同時(shí)滿足： 2x1+x2 50 4x1+3x2 120 x1 0 x2 0 的區(qū)域可行域,x2,50,40,30,20,10,10,20,30,40,

7、x1,可行域,O（0，0）,Q1（25，0）,Q2（15，20）,Q3（0，40）,可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問(wèn)題的解的集合。 該問(wèn)題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目標(biāo)函數(shù)是以Z作為參數(shù)的一組平行線 x2 = Z/30-（5/3）x1,x2,50,40,30,20,10,10,20,30,40,x1,可行域,當(dāng)Z值不斷增加時(shí)，該直線 x2 = Z/30-（5/3）x1 沿著其法線方向向右上方移動(dòng)。,x2,50,40,30,20,10,10,20,30,40

8、,x1,可行域,當(dāng)該直線移到Q2點(diǎn)時(shí)，Z（目標(biāo)函數(shù)）值達(dá)到最大： Max Z=5015+30 20=1350 此時(shí)最優(yōu)解=（15，20）,Q2（15，20）,線性規(guī)劃模型的三要素： 決策變量：需決策的量，即待求的未知數(shù)。 目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)到的目標(biāo)，用決策變量的表達(dá)式表示。 約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)受到的限制，用決策變量的等式或不等式表示。,某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消 耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1噸需 消耗A種礦石4t、B種礦石4t、煤9t。每1t甲種產(chǎn)品的利潤(rùn) 是600元,每1t乙種產(chǎn)品的利潤(rùn)是1000元。 工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)

9、劃中要求消耗A種礦石不超過(guò)300t、 消耗B種礦石不超過(guò)200t、消耗煤不超過(guò)360t。 若你是廠長(zhǎng),你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤(rùn)總額達(dá)到最大?,例,請(qǐng)寫(xiě)出目標(biāo)函數(shù)和約束條件 決策變量是什么？,在本例中 決策變量：甲、乙產(chǎn)品的計(jì)劃產(chǎn)量，記為 , 目標(biāo)函數(shù)：總收入記為 , 則 為體現(xiàn)追求極大化，在前面冠以極大號(hào)max； 約束條件：分別來(lái)自資源煤、電、油限量的約束，和產(chǎn)量非負(fù)的約束，表示為,解： 設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為 個(gè)單位（ ）, 獲得總收入為z ，則上述問(wèn)題的數(shù)學(xué)模型為,線性規(guī)劃模型的一個(gè)基本特點(diǎn),目標(biāo)和約束均為變量的線性表達(dá)式 如果模型中出現(xiàn)如 的非線性表

10、達(dá)式，則不屬于線性規(guī)劃。,求解過(guò)程圖解法,實(shí)例分析：設(shè)x,y滿足以下條件： 求z=2x+y的最大值與最小值。,如圖，分別作出 三條直線，,o,5x+6y=30,y=1,y=3x,y,y=1,y=3x,5x+6y=30,再找出不等式組 所表示的平面區(qū)域的公 共區(qū)域。,可行域,x,設(shè)z=0,畫(huà)出直線l0， 即l0:2x+y=0。,o,5x+6y=30,y=1,y=3x,y,x,l0:2x+y=0,如圖，平移直線l0，,所對(duì)應(yīng)的z隨之增大；,所對(duì)應(yīng)的z隨之減小。,當(dāng)直線l0向上平移時(shí)，,當(dāng)直線l0向下平移 時(shí),o,5x+6y=30,y=1,y=3x,y,l0:2x+y=0,l1:2x+y=2,l2:

11、2x+y=4,l3:2x+y=-3,此時(shí)所對(duì)應(yīng)的Z最??；,此時(shí)所對(duì)應(yīng)的Z最大。,從而得到：,zmin,zmax,=2 +1=,=2 +1=,o,5x+6y=30,y=1,y=3x,y,x,A,B,C,l0:2x+y=0,如圖，在把l0向上平移過(guò)程中，直線與平面區(qū) 域首先相交于點(diǎn)A ，,當(dāng)相交于點(diǎn)B ，,l1,l2,總結(jié)： 從這個(gè)問(wèn)題的求解過(guò)程可以 看出，最優(yōu)解一般在可行域的邊 界上，而且通常在可行域的頂點(diǎn) 處取得。,線性目標(biāo)函數(shù),Z的最大值為44,線性約束條件,圖解法,線性約 束條件,可行域,線性目 標(biāo)函數(shù) Z=Ax+By,最優(yōu)解,尋找平行線組 的縱截距 最值,四個(gè)步驟：,1、列,4、答,3、

12、移,2、畫(huà),三個(gè)轉(zhuǎn)化,四個(gè)步驟：,1、列（設(shè)出未知數(shù),列出約束條件,確定目標(biāo)函數(shù)）,三個(gè)轉(zhuǎn)化,4、答（求出點(diǎn)的坐標(biāo)，并轉(zhuǎn)化為最優(yōu)解）,3、移（平移直線L 。尋找使縱截距取得最值時(shí)的點(diǎn)）,2、畫(huà)（畫(huà)可行域）,圖解法,線性約束條件,可行域,線性目標(biāo)函數(shù) Z=Ax+By,最優(yōu)解,尋找平行線組的 最大（小）縱截距,某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消 耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1噸需 消耗A種礦石4t、B種礦石4t、煤9t.每1t甲種產(chǎn)品的利潤(rùn) 是600元,每1t乙種產(chǎn)品的利潤(rùn)是1000元. 工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗A種礦石不超過(guò)300t、 消耗B種

13、礦石不超過(guò)200t、消耗煤不超過(guò)360t. 若你是廠長(zhǎng),你應(yīng)如何安排甲乙兩種產(chǎn)品的產(chǎn)量(精確到0.1t),才能使利潤(rùn)總額達(dá)到最大?,例,分 析 問(wèn) 題:,1.本問(wèn)題給定了哪些原材料(資源)?,2.該工廠生產(chǎn)哪些產(chǎn)品?,3.各種產(chǎn)品對(duì)原材料(資源)有怎樣的要求?,4.該工廠對(duì)原材料(資源)有何限定條件?,5.每種產(chǎn)品的利潤(rùn)是多少?利潤(rùn)總額如何計(jì)算?,原 材 料,每噸產(chǎn)品消耗的原材料,A種礦石,B種礦石,煤,甲產(chǎn)品(t) x,乙產(chǎn)品(t),10,5,4,4,4,9,原 材料限 額,300,200,360,利 潤(rùn),600,1000,y,把題中限制條件進(jìn)行轉(zhuǎn)化：,約束條件,10 x+4y300,5x+

14、4y200,4x+9y360,x0,y 0,z=600 x+1000y.,目標(biāo)函數(shù)：,設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為x、y,利潤(rùn)總額為z元,解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為x、y,利潤(rùn)總額為z元,那么,10 x+4y300,5x+4y200,4x+9y360,x0,y 0,z=600 x+1000y.,畫(huà)出以上不等式組所表示的可行域,作出直線L 600 x+1000y=0.,10 x+4y=300,5x+4y=200,4x+9y=360,600 x+1000y=0,M,答:應(yīng)生產(chǎn)甲產(chǎn)品約12.4噸，乙產(chǎn)品34.4噸，能使利潤(rùn)總額達(dá)到最大。,(12.4,34.4),經(jīng)過(guò)可行域上的點(diǎn)M時(shí),目標(biāo)函數(shù)在

15、y軸上截距最大.,90,30,75,40,50,40,此時(shí)z=600 x+1000y取得最大值.,把直線L向右上方平移,線性規(guī)劃問(wèn)題,尋找約束條件 建立目標(biāo)函數(shù),1.約束條件要寫(xiě)全;,3.解題格式要規(guī)范.,2.作圖要準(zhǔn)確,計(jì)算也要準(zhǔn)確;,注意:,總結(jié),解線性規(guī)劃應(yīng)用問(wèn)題的步驟：,（3）移：作出z=Ax+By=0時(shí)的直線L，在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；,（4）答：通過(guò)解方程組求出最優(yōu)解；,（1）列：設(shè)出未知數(shù),列出約束條件,確定目標(biāo)函數(shù)；,（2）畫(huà)：畫(huà)出線性約束條件所表示的可行域；,注：1.線性目標(biāo)函數(shù)的最大（小）值一般在可行域

16、的頂點(diǎn)處取得，也可能在邊界處取得。 2.求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線性目標(biāo)函數(shù)所表示的幾何意義 在 y 軸上的截距或其相反數(shù)。,結(jié)果調(diào)整,某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ：,解：設(shè)需截第一種鋼板x張，第二種鋼板y張，鋼板總張數(shù)為Z,則,2x+y15,x+2y18,x+3y27,x0,y0,某顧客需要A,B,C三種規(guī)格的成品分別為15，18，27塊，若你是經(jīng)理,問(wèn)各截這兩種鋼板多少?gòu)埣饶軡M足顧客要求又使所用鋼板張數(shù)最少。,X張,y張,分 析 問(wèn) 題:,例,目標(biāo)函數(shù): z=x+y,2x+y=15,x+3y=27,

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

18、+y =0,經(jīng)過(guò)可行域內(nèi)的整點(diǎn)B(3,9)和C(4,8)且和原點(diǎn)距離最近的直線是x+y=12，它們是最優(yōu)解.,作出一組平行直線t = x+y，,目標(biāo)函數(shù)t = x+y,打網(wǎng)格線法,在可行域內(nèi)打出網(wǎng)格線，,當(dāng)直線經(jīng)過(guò)點(diǎn)A時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，,將直線x+y=11.4繼續(xù)向上平移，,1,2,1,2,18,27,15,9,7,8,即先求非整數(shù)條件下的最優(yōu)解，調(diào)整Z的值使不定方程Ax+By=Z存在最大（?。┑恼c(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解,即先打網(wǎng)格，描出可行域內(nèi)的整點(diǎn)，平移直線，最先經(jīng)過(guò)或最后經(jīng)過(guò)的整點(diǎn)坐標(biāo)即為最優(yōu)整解,線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:,1.平移找解法：,2.調(diào)整優(yōu)解法：,總結(jié),小 結(jié),實(shí)際問(wèn)題,線性規(guī)劃問(wèn)題,圖解法,最優(yōu)解,最優(yōu)整數(shù)解,平移找解法,調(diào)整優(yōu)值法,距離,斜率等,結(jié)論：,1.線性目標(biāo)函數(shù)的最大（?。┲狄话阍诳?行域的頂點(diǎn)處取得，也可能在邊界處取得。 2.求線性目標(biāo)函數(shù)的最優(yōu)解