3.3.2簡單的線性規(guī)劃2

1、2008、10、25,課題：簡單的線性規(guī)劃（2）-調(diào)整最優(yōu)解,漢壽縣第三中學(xué),艾鎮(zhèn)南,B,A,C,若實(shí)數(shù)x , y滿足 ,求z=2x+y的取值范圍.,使z=2x+y取得最大值的可行解為 ， 且最大值為 ；,（1）畫出不等式組所表示的平面區(qū)域；,滿足 的解(x,y)都叫做可行解；,z=2x+y 叫做 ；,（2）設(shè)z=2x+y，則式中變量x,y滿足的二元一次不等式組叫做x,y的 ；,使z=2x+y取得最小值的可行解 ， 且最小值為 ； 這兩個(gè)最值都叫做問題的 。,線性目標(biāo)函數(shù),線性約束條件,(5,2),(1, 1),12,3,最優(yōu)解,線性約束條件,復(fù)習(xí)引入:,B,A,C,解：不等式組表示的平面區(qū)域

2、如圖所示：,作斜率為-2的直線,使之與平面區(qū)域有公共點(diǎn),A(5,2), B(1,1),例1.若實(shí)數(shù)x , y滿足 求z=2x+y的取值范圍,由圖可知,當(dāng)l過B(1,1)時(shí)的值最小，當(dāng)l過A(5,2)時(shí)， z的值最大.,分析：目標(biāo)函數(shù)變形為,把z看成參數(shù)，同樣是一組平行線，且平行線與可行域有交點(diǎn)。,最小截距為過A(5,2) 的直線,同理，當(dāng)直線取最小截距時(shí)，z有最大值,最大截距為過 的直線,變題：上例若改為求z=x-2y的最大值、最小值呢？,變題：若改為求z=3x+5y的最大值、最小值呢？,解：不等式組表示的平面區(qū)域如圖所示：,作斜率為的直線,或,本題以最大值解為坐標(biāo)的點(diǎn)落在線段AC上，即線段A

3、C上所有點(diǎn)的坐標(biāo)為最大值解,例題分析：關(guān)于取整數(shù)解的問題,例2 要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ：,解：設(shè)需截第一種鋼板x張，第一種鋼板y張，則,2x+y15,x+2y18,x+3y27,x0,y0,作出可行域（如圖）,目標(biāo)函數(shù)為 z=x+y,今需要A,B,C三種規(guī)格的成品分別為15，18，27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。,X張,y張,例題分析,2x+y=15,x+3y=27,x+2y=18,x+y =0,直線x+y=12經(jīng)過的整點(diǎn)是B(3,9)和C(4,8)，它們是最優(yōu)解.,作出一

4、組平行直線z=x+y，,目標(biāo)函數(shù)z= x+y,當(dāng)直線經(jīng)過點(diǎn)A時(shí)z=x+y=11.4,x+y=12,解得交點(diǎn)B,C的坐標(biāo)B(3,9)和C(4,8),調(diào)整優(yōu)值法,2,4,6,18,12,8,27,2,4,6,8,10,15,但它不是最優(yōu)整數(shù)解.,作直線x+y=12,答（略）,例題分析,2x+y=15,x+3y=27,x+2y=18,x+y =0,經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和C(4,8)時(shí)，t=x+y=12是最優(yōu)解.,答:(略),作出一組平行直線t = x+y，,目標(biāo)函數(shù)t = x+y,打網(wǎng)格線法,在可行域內(nèi)打出網(wǎng)格線，,當(dāng)直線經(jīng)過點(diǎn)A時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，,將直線x+y=

5、11.4繼續(xù)向上平移，,1,2,1,2,18,27,15,9,7,8,在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù)解問題的一般方法是：,1.若區(qū)域“頂點(diǎn)”處恰好為整點(diǎn)，那么它就是最優(yōu)解；（在包括邊界的情況下） 2.若區(qū)域“頂點(diǎn)”不是整點(diǎn)或不包括邊界時(shí)，應(yīng)先求出該點(diǎn)坐標(biāo)，并計(jì)算目標(biāo)函數(shù)值Z，然后在可行域內(nèi)適當(dāng)放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與Z最接近，在這條對(duì)應(yīng)的直線中，取可行域內(nèi)整點(diǎn)，如果沒有整點(diǎn)，繼續(xù)放縮，直至取到整點(diǎn)為止。 3.在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng)絡(luò)、找整點(diǎn)、平移直線、找出整數(shù)最優(yōu)解；還可以用調(diào)整最優(yōu)值法。,不等式組 表示的平面區(qū)域內(nèi)的整數(shù)點(diǎn)共有（ ）個(gè),鞏固練習(xí)1:,1 2

6、 3 4 x,y 4 3 2 1 0,4x+3y=12,練習(xí)2：求滿足 | x | + | y | 4 的整點(diǎn)（橫、縱坐標(biāo)為整數(shù)）的個(gè)數(shù)。,共有： 9 + 2 ( 7 + 5 + 3 + 1 ) = 41,4,x=8,y=4,x+y=10,4x+5y=30,320 x+504y=0,3.某運(yùn)輸公司接受了向抗洪搶險(xiǎn)地區(qū)每天至少運(yùn)送180噸支援物資的任務(wù)，該公司有8輛載重量為6噸的A型卡車和4輛載重量為10噸的B型卡車，有10名駕駛員；每輛卡車每天往返的次數(shù)為A型卡車4次，B型卡車3次，每輛卡車每天往返的成本費(fèi)A型卡車為320元，B型卡車為504元，問如何安排車輛才能使該公司所花的成本費(fèi)最低，最低

7、為多少元？(要求每型卡車至少安排一輛）,解：設(shè)每天調(diào)出的A型車x輛，B型車y輛，公司所花的費(fèi)用為z元，則,Z=320 x+504y,作出可行域中的整點(diǎn)，,可行域中的整點(diǎn)（5，2）使Z=320 x+504y取得最小值，且Zmin=2608元,作出可行域,15,課后練習(xí):,2.,3.深圳市福田區(qū)水泥制品廠生產(chǎn)兩種水泥，已知生產(chǎn)甲種水泥制品1噸，需礦石4噸，煤3噸；生產(chǎn)乙種水泥制品1噸，需礦石5噸，煤10噸，每1噸甲種水泥制品的利潤為7萬元，每1噸乙種水泥制品的利潤是12萬元，工廠在生產(chǎn)這兩種水泥制品的計(jì)劃中，要求消耗的礦石不超過200噸，煤不超過300噸，甲乙兩種水泥制品應(yīng)生產(chǎn)多少，能使利潤達(dá)到最大值？,（圖1）,【練習(xí)4】 如圖1所示，已知ABC中的三頂點(diǎn) A(2,4) ,B(-1,2),C(1,0),點(diǎn)P(x,y),在ABC內(nèi)部及邊界運(yùn)動(dòng)， 請(qǐng)你探究并討論以下問題：,在_處有最大值_，在_處有最小值_；, 你能否設(shè)計(jì)一個(gè)目標(biāo)函數(shù)，使得其取最優(yōu)解的 情況有無窮多個(gè)？ 請(qǐng)你分別設(shè)計(jì)目標(biāo)函數(shù)，使得最值點(diǎn)分別 在A處、B處、C處取得？ (課后思考題）若目標(biāo)函數(shù)是,你知道其幾何意義嗎？,？如果是,或,在_處有最大值_，在_處有最小值_；,呢？,你能否借助其幾何意義求得,z=x+y,z=x-y,z=x2+y2 ，,zmin和zmax,A(2,4