2021/6/301xyo線性規(guī)劃的簡單應(yīng)用線性規(guī)劃的簡單應(yīng)用 2021/6/302使使z=2x+y取得取得最大值最大值的可行解為的可行解為 ，且最大值為且最大值為 ；復(fù)習引入復(fù)習引入1.已知二元一次不等式組已知二元一次不等式組x-y0 x+y-10y-1（1）畫出不等式組所表示的平面區(qū)域；）畫出不等式組所表示的平面區(qū)域；滿足滿足 的的解解(x,y)都叫做都叫做可行解可行解；z=2x+y 叫做叫做 ；（2）設(shè)）設(shè)z=2x+y，則式中變量，則式中變量x,y滿足的二元一滿足的二元一次不等式組叫做次不等式組叫做x,y的的 ；y=-1x-y=0 x+y=12x+y=0返回返回(-1,-1) (2,-1)使使z=2x+y取得取得最小值最小值的可行解的可行解 ，且最小值為且最小值為 ；這兩個這兩個最值最值都叫做問題的都叫做問題的 。線性約束條件線性約束條件線性目標函數(shù)線性目標函數(shù)線性約束條件線性約束條件(2,-1)(-1,-1)3-3最優(yōu)解最優(yōu)解xy0112021/6/303例題分析例題分析例例1:某工廠生產(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.甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少甲、乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少(精精確到確到0.1t),能使利潤總額達到最大能使利潤總額達到最大? 甲產(chǎn)品甲產(chǎn)品 （1t） 乙產(chǎn)品乙產(chǎn)品 （1t） 資源限額資源限額 （t）A種礦石（種礦石（t） B種礦石（種礦石（t） 煤（煤（t） 利潤（元）利潤（元） 產(chǎn)品產(chǎn)品消耗量消耗量資源資源列表列表：51046004491000300200360設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z元元2021/6/304例題分析例題分析 甲產(chǎn)品甲產(chǎn)品 （1t） 乙產(chǎn)品乙產(chǎn)品 （1t） 資源限額資源限額 （t）A種礦石（種礦石（t） B種礦石（種礦石（t） 煤（煤（t） 利潤（元）利潤（元） 產(chǎn)品產(chǎn)品消耗量消耗量資源資源列表列表：51046004491000300200360把題中限制條件進行把題中限制條件進行轉(zhuǎn)化：轉(zhuǎn)化：約束條件約束條件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目標函數(shù)：目標函數(shù)：設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z元元xtyt2021/6/305例題分析解解:設(shè)生產(chǎn)甲、乙兩種產(chǎn)品設(shè)生產(chǎn)甲、乙兩種產(chǎn)品.分別為分別為x t、yt,利潤總額為利潤總額為z=600 x+1000y. 元元,那么那么10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.作出以上不等式組所表示的可行域作出以上不等式組所表示的可行域作出一組平行直線作出一組平行直線 600 x+1000y=t，解得交點解得交點M的坐標為的坐標為(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時時,目標函數(shù)目標函數(shù)在在y軸上截距最大軸上截距最大.ll l9030 0 xy10 201075405040此時此時z=600 x+1000y取得最大值取得最大值.2021/6/306例題分析例例2 要將兩種大小不同規(guī)格的鋼板截成要將兩種大小不同規(guī)格的鋼板截成A、B、C三種規(guī)格，三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 ： 解：解：設(shè)需截第一種鋼板設(shè)需截第一種鋼板x張，第一種鋼板張，第一種鋼板y張，則張，則 規(guī)格類型規(guī)格類型鋼板類型鋼板類型第一種鋼板第一種鋼板第二種鋼板第二種鋼板A規(guī)格規(guī)格B規(guī)格規(guī)格C規(guī)格規(guī)格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如圖）作出可行域（如圖）目標函數(shù)為目標函數(shù)為 z=x+y今需要今需要A,B,C三種規(guī)格的成品分別為三種規(guī)格的成品分別為15，18，27塊，問塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少。用鋼板張數(shù)最少。X張張y張張2021/6/307例題分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xNy0 yN直線直線x+y=12經(jīng)過的經(jīng)過的整點是整點是B(3,9)和和C(4,8)，它們是最優(yōu)解，它們是最優(yōu)解. 作出一組平行直線作出一組平行直線z=x+y，目標函數(shù)目標函數(shù)z= x+yB(3,9)C(4,8)A(18/5,39/5)當直線經(jīng)過點當直線經(jīng)過點A時時z=x+y=11.4,x+y=12解得交點解得交點B,C的坐標的坐標B(3,9)和和C(4,8)調(diào)整優(yōu)值法調(diào)整優(yōu)值法2 4 6181282724681015但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解.作直線作直線x+y=12答（略）答（略）2021/6/308例題分析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)時，時，t=x+y=12是最優(yōu)解是最優(yōu)解.答答:(略略)作出一組平行直線作出一組平行直線t = x+y，目標函數(shù)目標函數(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)格線，當直線經(jīng)過點當直線經(jīng)過點A時時t=x+y=11.4,但它不是最優(yōu)整數(shù)解但它不是最優(yōu)整數(shù)解，將直線將直線x+y=11.4繼續(xù)向上平移繼續(xù)向上平移，12121827159782021/6/309不等式組不等式組 表示的平面區(qū)域內(nèi)的表示的平面區(qū)域內(nèi)的整數(shù)點整數(shù)點共有共有（ ）個）個123400yxyx鞏固練習鞏固練習1:1 2 3 4 xy432104x+3y=122021/6/3010在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù)在可行域內(nèi)找出最優(yōu)解、線性規(guī)劃整數(shù)解問題的一般方法是：解問題的一般方法是：1.若區(qū)域若區(qū)域“頂點頂點”處恰好為整點，那么它就是最優(yōu)解；處恰好為整點，那么它就是最優(yōu)解；（在包括邊界的情況下）（在包括邊界的情況下）2.若區(qū)域若區(qū)域“頂點頂點”不是整點或不包括邊界時，應(yīng)先求出不是整點或不包括邊界時，應(yīng)先求出該點坐標，并計算目標函數(shù)值該點坐標，并計算目標函數(shù)值Z，然后在可行域內(nèi)適當，然后在可行域內(nèi)適當放縮目標函數(shù)值，使它為整數(shù)，且與放縮目標函數(shù)值，使它為整數(shù)，且與Z最接近，在這條最接近，在這條對應(yīng)的直線中，取可行域內(nèi)整點，如果沒有整點，繼續(xù)對應(yīng)的直線中，取可行域內(nèi)整點，如果沒有整點，繼續(xù)放縮，直至取到整點為止。放縮，直至取到整點為止。3.在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng)在可行域內(nèi)找整數(shù)解，一般采用平移找解法，即打網(wǎng)絡(luò)、找整點、平移直線、找出整數(shù)最優(yōu)解絡(luò)、找整點、平移直線、找出整數(shù)最優(yōu)解2021/6/3011解線性規(guī)劃應(yīng)用問題的一般步驟解線性規(guī)劃應(yīng)用問題的一般步驟：2）設(shè)好變元并列出不等式組和目標函數(shù)）設(shè)好變元并列出不等式組和目標函數(shù)3）由二元一次不等式表示的平面區(qū)域做出可行域；由二元一次不等式表示的平面區(qū)域做出可行域；4）在可行域內(nèi)求目標函數(shù)的最優(yōu)解在可行域內(nèi)求目標函數(shù)的最優(yōu)解1）理清題意，列出表格：）理清題意，列出表格：5)還原成實際問題還原成實際問題 ( (準確作圖，準確計算準確作圖，準確計算)2021/6/3012咖啡館配制兩種飲料甲種飲料每杯含奶粉咖啡館配制兩種飲料甲種飲料每杯含奶粉9g 、咖啡、咖啡4g、糖糖3g,乙種飲料每杯含奶粉乙種飲料每杯含奶粉4g 、咖啡、咖啡5g、糖、糖10g已知每天已知每天原料的使用限額為奶粉原料的使用限額為奶粉3600g ，咖啡，咖啡2000g糖糖3000g,如果如果甲種飲料每杯能獲利甲種飲料每杯能獲利0.7元，乙種飲料每杯能獲利元，乙種飲料每杯能獲利1.2元，每元，每天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種天在原料的使用限額內(nèi)飲料能全部售出，每天應(yīng)配制兩種飲料各多少杯能獲利最大飲料各多少杯能獲利最大？解：將已知數(shù)據(jù)列為下表：解：將已知數(shù)據(jù)列為下表： 消耗量消耗量資源資源甲產(chǎn)品（甲產(chǎn)品（1 杯）杯）乙產(chǎn)品乙產(chǎn)品(1杯杯)資源限額（資源限額（g）奶粉（奶粉（g g）9 94 436003600咖啡咖啡(g)(g)4 45 520002000糖糖(g)(g)3 3101030003000利潤（元）利潤（元）0.70.71.21.2產(chǎn)品產(chǎn)品2021/6/3013設(shè)每天應(yīng)配制甲種飲料設(shè)每天應(yīng)配制甲種飲料x x杯，乙種飲料杯，乙種飲料y y杯，則杯，則003000103200054360049yxyxyxyx作出可行域：作出可行域：目標函數(shù)為：目標函數(shù)為：z =0.7x +1.2yz =0.7x +1.2y作直線作直線l:0.7x+1.2y=0l:0.7x+1.2y=0，把直線把直線l l向右上方平移至向右上方平移至l l1 1的位置的位置時，時，直線經(jīng)過可行域上的點直線經(jīng)過可行域上的點C C，且與原，且與原點距離最大，點距離最大，此時此時z =0.7x +1.2yz =0.7x +1.2y取最大值取最大值解方程組解方程組 得點得點C C的坐標為（的坐標為（200200，240240）,3000103,200054yxyx_0_ 9 x + 4 y = 3600_ C (200,240)_ 4 x + 5 y = 2000_ 3 x + 10 y = 3000_ 7 x + 12 y = 0_ 400_ 400_ 300_ 500_ 1000_ 900_ 0_ x_ y2021/6/3014二元一次不等式二元一次不等式表示平面區(qū)域表示平面區(qū)域直線定界，直線定界，特殊點定域特殊點定域簡單的線性規(guī)劃簡單的線性規(guī)劃約束條件約束條件目標函數(shù)目標函數(shù)可行解可行解可行域可行域最優(yōu)解最優(yōu)解應(yīng)用應(yīng)用求解方法：畫、求解方法：畫、移、求、答移、求、答2021/6/30152021/6/3016練習鞏固1.某家具廠有方木材某家具廠有方木材90m3，木工板，木工板600m3，準備加工成，準備加工成書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料0.1m3、木工板木工板2m3；生產(chǎn)每個書櫥需要方木料；生產(chǎn)每個書櫥需要方木料0.2m3，木工板，木工板1m3，出售一張書桌可以獲利，出售一張書桌可以獲利80元，出售一張書櫥可以元，出售一張書櫥可以獲利獲利120元；元；（1）怎樣安排生產(chǎn)可以獲利最大？）怎樣安排生產(chǎn)可以獲利最大？（2）若只生產(chǎn)書桌可以獲利多少？）若只生產(chǎn)書桌可以獲利多少？（3）若只生產(chǎn)書櫥可以獲利多少？）若只生產(chǎn)書櫥可以獲利多少？2021/6/3017由上表可知：（1）只生產(chǎn)書桌，用完木工板了，可生產(chǎn)書桌 6002=300張,可獲利潤:80300=24000元,但木料沒有用完 （2）只生產(chǎn)書櫥，用完方木料，可生產(chǎn)書櫥900.2=450 張,可獲利潤120450=54000元,但木工板沒有用完產(chǎn)品 資源 書桌（張） 書櫥（張） 資源限額 m 3方木料 m 3 01 02 90 木工板m 321600利潤 （元）80120分析：分析：2021/6/3018xy02x+y-600=0300600 x+2y-900=0A(100,400)1.某家具廠有方木材某家具廠有方木材90m3，木工板，木工板600m3，準備加工成書桌和書櫥出售，準備加工成書桌和書櫥出售，已知生產(chǎn)每張書桌需要方木料已知生產(chǎn)每張書桌需要方木料0.1m3、木工板、木工板2m3；生產(chǎn)每個書櫥需要方木；生產(chǎn)每個書櫥需要方木料料0.2m3，木工板，木工板1m3，出售一張書桌可以獲利，出售一張書桌可以獲利80元，出售一張書櫥可以獲元，出售一張書櫥可以獲利利120元；元；（1）怎樣安排生產(chǎn)可以獲利最大？）怎樣安排生產(chǎn)可以獲利最大？（2）若只生產(chǎn)書桌可以獲利多少？）若只生產(chǎn)書桌可以獲利多少？（3）若只生產(chǎn)書櫥可以獲利多少？）若只生產(chǎn)書櫥可以獲利多少？（1）設(shè)生產(chǎn)書桌）設(shè)生產(chǎn)書桌x張，書櫥張，書櫥y張，利張，利潤為潤為z元，元， 則約束條件為則約束條件為 0.1x+0.2y900.1x+0.2y902x+y6002x+y600 x x，yNyN* *Z=80 x+120yZ=80 x+120y作出不等式表示的平面區(qū)域，作出不等式表示的平面區(qū)域，當生產(chǎn)當生產(chǎn)100張書桌，張書桌，400張書櫥時利潤最大為張書櫥時利潤最大為z=80100+120400=56000元元（2）若只生產(chǎn)書桌可以生產(chǎn)）若只生產(chǎn)書桌可以生產(chǎn)300張，用完木工板，可獲利張，用完木工板，可獲利 24000元；元；（3）若只生產(chǎn)書櫥可以生產(chǎn)）若只生產(chǎn)書櫥可以生產(chǎn)450張，用完方木料，可獲利張，用完方木料，可獲利54000元。元。將直線將直線z=80 x+120y平移可知：平移可知：900450求解：求解：2021/6/3019Xy084x=8y=47654321321x+y=104x+5y=30320 x+504y=02.某運輸公司接受了向抗洪搶險地區(qū)每天至少運送某運輸公司接受了向抗洪搶險地區(qū)每天至少運送180噸支援物資噸支援物資的任務(wù)，該公司有的任務(wù)，該公司有8輛載重量為輛載重量為6噸的噸的A型卡車和型卡車和4輛載重量為輛載重量為10噸噸的的B型卡車，有型卡車，有10名駕駛員；每輛卡車每天往返的次數(shù)為名駕駛員；每輛卡車每天往返的次數(shù)為A型卡車型卡車4次，次，B型卡車型卡車3次，每輛卡車每天往返的成本費次，每輛卡車每天往返的成本費A型卡車為型卡車為320元，元，B型卡車為型卡車為504元，問如何安排車輛才能使該公司所花的成本費最元，問如何安排車輛才能使該公司所花的成本費最低，最低為多少元？低，最低為多少元？(要求每型卡車至少安排一輛）要求每型卡車至少安排一輛）解：解：設(shè)每天調(diào)出的設(shè)每天調(diào)出的A型車型車x輛，輛，B型車型車y輛，公司所花的費用為輛，公司所花的費用為z元，則元，則x8y4x+y10 x,yN*4x+5y30Z=320 x+504y作出可行域中的整點，作出可行域中的整點，可行域中的整點（可行域中的整點（5，2）使）使Z=320 x+504y取得最取得最小值，且小值，且Zmin=2608元元作出可行域作出可行域2021/6/30202.附加練習附加練習深圳市福田區(qū)水泥制品廠生產(chǎn)兩種水泥，已知生產(chǎn)甲種水泥深圳市福田區(qū)水泥制品廠生產(chǎn)兩種水泥，已知生產(chǎn)甲種水泥制品制品1噸，需礦石噸，需礦石4噸，煤噸，煤3噸；生產(chǎn)乙種水泥制品噸；生產(chǎn)乙種水泥制品1噸，需礦噸，需礦石石5噸，煤噸，煤10噸，每噸，每1噸甲種水泥制品的利潤為噸甲種水泥制品的利潤為7萬元，每萬元，每1噸噸乙種水泥制品的利潤是乙種水泥制品的利潤是12萬元，工廠在生產(chǎn)這兩種水泥制品萬元，工廠在生產(chǎn)這兩種水泥制品的計劃中，要求消耗的礦石不超過的計劃中，要求消耗的礦石不超過200噸，煤不超過噸，煤不超過300噸，噸，甲乙兩種水泥制品應(yīng)生產(chǎn)多少，能使利潤達到最大值？甲乙兩種水泥制品應(yīng)生產(chǎn)多少，能使利潤達到最大值？ 若有不當之處，請指正，謝謝！若有不當之處，請指正，謝謝！