《簡單的線性規(guī)劃問題2》.ppt

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