《《簡單的線性規(guī)劃問題2》.ppt》由會員分享，可在線閱讀，更多相關(guān)《《簡單的線性規(guī)劃問題2》.ppt（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

,使z=2x+y取得最大值的可行解為，且最大值為；,,,復(fù)習(xí)引入,1.已知二元一次不等式組,（1）畫出不等式組所表示的平面區(qū)域；,滿足的解(x,y)都叫做可行解；,z=2x+y叫做；,（2）設(shè)z=2x+y，則式中變量x,y滿足的二元一次不等式組叫做x,y的；,,y=-1,,x-y=0,,x+y=1,,,,2x+y=0,,,,,,,,,,,,,,(-1,-1),,,(2,-1),,使z=2x+y取得最小值的可行解，且最小值為。,,,線性約束條件,線性目標(biāo)函數(shù),線性約束條件,(2,-1),(-1,-1),3,-3,1、已知x、y滿足,且z＝2x＋4y的最小值為－6，則常數(shù)k等于(),關(guān)鍵是找準(zhǔn)幾何意義,,例1:某工廠生產(chǎn)甲、乙兩種產(chǎn)品.已知生產(chǎn)甲種產(chǎn)品1t需消耗A種礦石10t、B種礦石5t、煤4t；生產(chǎn)乙種產(chǎn)品1t需消耗A種礦石4t、B種礦石4t、煤9t.每1t甲種產(chǎn)品的利潤是600元,每1t乙種產(chǎn)品的利潤是1000元.工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗A種礦石不超過300t、消耗B種礦石不超過200t、消耗煤不超過360t.甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少噸(精確到0.1t),能使利潤總額達到最大?,列表：,5,10,4,600,4,4,9,1000,設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為xt、yt,利潤總額為z元,,列表：,把題中限制條件進行轉(zhuǎn)化：,,約束條件,10 x+4y≤300,5x+4y≤200,4x+9y≤360,x≥0,y≥0,z=600 x+1000y.,目標(biāo)函數(shù)：,設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為xt、yt,利潤總額為z元,xt,yt,學(xué)車問答學(xué)車問題開車問題學(xué)車怎么辦？駕校大全中國駕校報名考試?yán)碚搶W(xué)習(xí)地址介紹英格駕考車類小游戲?qū)W車小游戲大全,,,解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為xt、yt,利潤總額為z=600 x+1000y元,那么,{,10 x+4y≤300,5x+4y≤200,4x+9y≤360,x≥0,y≥0,z=600 x+1000y.,作出以上不等式組所表示的可行域,作出一組平行直線600 x+1000y=t，,,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噸,能使利潤總額達到最大。,(12.4,34.4),,,,,,,,,,,,經(jīng)過可行域上的點M時,目標(biāo)函數(shù)在y軸上截距最大.,90,30,75,40,50,40,,,此時z=600 x+1000y取得最大值.,,例2要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：,解：設(shè)需截第一種鋼板x張，第一種鋼板y張，則,2x+y≥15,,{,x+2y≥18,,x+3y≥27,,x≥0,y≥0,作出可行域（如圖）,目標(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,,,作出一組平行直線z=x+y，,目標(biāo)函數(shù)z=x+y,,,,,,,當(dāng)直線經(jīng)過點A時z=x+y=11.4,,x+y=12,在可行域內(nèi)，直線x+y=12經(jīng)過的整點是B(3,9)和C(4,8)，它們是最優(yōu)解,調(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)的整點B(3,9)和C(4,8)時，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)過點A時t=x+y=11.4,但它不是最優(yōu)整數(shù)解，,將直線x+y=11.4繼續(xù)向上平移，,1,2,1,2,18,27,15,9,7,8,不等式組表示的平面區(qū)域內(nèi)的整數(shù)點共有（）個,鞏固練習(xí)1:,,,,,,,,,,,1234x,y43210,,4x+3y=12,,,,,,,,,,,,在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù)解問題的一般方法是：,1.若區(qū)域“頂點”處恰好為整點，那么它就是最優(yōu)解；（在包括邊界的情況下）2.若區(qū)域“頂點”不是整點或不包括邊界時，應(yīng)先求出該點坐標(biāo)，并計算目標(biāo)函數(shù)值Z，然后在可行域內(nèi)適當(dāng)放縮目標(biāo)函數(shù)值，使它為整數(shù)，且與Z最接近，在這條對應(yīng)的直線中，取可行域內(nèi)整點，如果沒有整點，繼續(xù)放縮，直至取到整點為止。3.在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng)絡(luò)、找整點、平移直線、找出整數(shù)最優(yōu)解,解線性規(guī)劃應(yīng)用問題的一般步驟：,2）設(shè)好變元并列出不等式組和目標(biāo)函數(shù),3）由二元一次不等式表示的平面區(qū)域做出可行域；,4）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解,1）理清題意，列出表格：,5)還原成實際問題,(準(zhǔn)確作圖，準(zhǔn)確計算),1、求z=2x+y的最大值，使式中x、y滿足下列條件：,,答案:當(dāng)x=1，y=0時，z=2x+y有最大值2。,練習(xí),,2：求z=3x+y的最大值，使式中x、y滿足下列條件：,,3x+y=0,3x+y=29,答案：當(dāng)x=9,y=2時，z=3x+y有最大值29.,,練習(xí),,求z=300 x+900y的最大值和最小值，使式中x、y滿足下列條件：,,,x+3y=0,300 x+900y=0,300 x+900y=112500,答案：當(dāng)x=0,y=0時，z=300 x+900y有最小值0.,當(dāng)x=0,y=125時，z=300 x+900y有最大值112500.,,,表示的平面區(qū)域的面積是(),則D中的點到直線x+y=10距離的最大值是_________,3.某家具廠有方木料90m3，木工板600m3，準(zhǔn)備加工成書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料0.1m3、木工板2m3；生產(chǎn)每個書櫥需要方木料0.2m3，木工板1m3，出售一張書桌可以獲利80元，出售一張書櫥可以獲利120元；,（1）怎樣安排生產(chǎn)可以獲利最大？,（2）若只生產(chǎn)書桌可以獲利多少？,（3）若只生產(chǎn)書櫥可以獲利多少？,由上表可知：（1）只生產(chǎn)書桌，用完木工板了，可生產(chǎn)書桌6002=300張,可獲利潤:80300=24000元,但木料沒有用完,（2）只生產(chǎn)書櫥，用完方木料，可生產(chǎn)書櫥900.2=450張,可獲利潤120450=54000元,但木工板沒有用完,分析：,,300,600,,,A(100,400),,,3.某家具廠有方木料90m3，木工板600m3，準(zhǔn)備加工成書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料0.1m3、木工板2m3；生產(chǎn)每個書櫥需要方木料0.2m3，木工板1m3，出售一張書桌可以獲利80元，出售一張書櫥可以獲利120元,（1）怎樣安排生產(chǎn)可以獲利最大？,（2）若只生產(chǎn)書桌可以獲利多少？,（3）若只生產(chǎn)書櫥可以獲利多少？,（1）設(shè)生產(chǎn)書桌x張，書櫥y張，利潤為z元，則約束條件為,Z=80 x+120y,作出不等式表示的平面區(qū)域，,當(dāng)生產(chǎn)100張書桌，400張書櫥時利潤最大為z=80100+120400=56000元,（2）若只生產(chǎn)書桌可以生產(chǎn)300張，用完木工板，可獲利24000元；,（3）若只生產(chǎn)書櫥可以生產(chǎn)450張，用完方木料，可獲利54000元。,將直線z=80 x+120y平移可知：,,,,,,,,,,900,450,解：,,,,4,x=8,y=4,,x+y=10,,4x+5y=30,,,,,,,,,,,,,,,,320 x+504y=0,,,,4.某運輸公司接受了向抗洪搶險地區(qū)每天至少運送180噸支援物資的任務(wù)，該公司有8輛載重量為6噸的A型卡車和4輛載重量為10噸的B型卡車，有10名駕駛員；每輛卡車每天往返的次數(shù)為A型卡車4次，B型卡車3次，每輛卡車每天往返的成本費A型卡車為320元，B型卡車為504元，問如何安排車輛才能使該公司所花的成本費最低，最低為多少元？(要求每型卡車至少安排一輛）,解：設(shè)每天調(diào)出的A型車x輛，B型車y輛，公司所花的費用為z元，則,Z=320 x+504y,作出可行域中的整點，,可行域中的整點（5，2）使Z=320 x+504y取得最小值，且Zmin=2608元,作出可行域,,,5、咖啡館配制兩種飲料．甲種飲料每杯含奶粉9g、咖啡4g、糖3g,乙種飲料每杯含奶粉4g、咖啡5g、糖10g．已知每天原料的使用限額為奶粉3600g，咖啡2000g糖3000g,如果甲種飲料每杯能獲利0.7元，乙種飲料每杯能獲利1.2元，每天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大？,,解：將已知數(shù)據(jù)列為下表：,設(shè)每天應(yīng)配制甲種飲料x杯，乙種飲料y杯，則,作出可行域：目標(biāo)函數(shù)為：z=0.7x+1.2y作直線l:0.7x+1.2y=0，把直線l向右上方平移至l1的位置時，直線經(jīng)過可行域上的點C，且與原點距離最大，此時z=0.7x+1.2y取最大值解方程組得點C的坐標(biāo)為（200，240）,,,,,,,,,,,,,,,二元一次不等式表示平面區(qū)域,直線定界，特殊點定域,簡單的線性規(guī)劃,約束條件,目標(biāo)函數(shù),可行解,可行域,最優(yōu)解,,,求解方法：畫、移、求、答,,2.附加練習(xí),深圳市福田區(qū)水泥制品廠生產(chǎn)兩種水泥，已知生產(chǎn)甲種水泥制品1噸，需礦石4噸，煤3噸；生產(chǎn)乙種水泥制品1噸，需礦石5噸，煤10噸，每1噸甲種水泥制品的利潤為7萬元，每1噸乙種水泥制品的利潤是12萬元，工廠在生產(chǎn)這兩種水泥制品的計劃中，要求消耗的礦石不超過200噸，煤不超過300噸，甲乙兩種水泥制品應(yīng)生產(chǎn)多少，能使利潤達到最大值？,思考題：求不等式|x|+|y|≤2表示的平面區(qū)域的面積,,S=8,,