簡單的線性規(guī)劃問題-完整版課件

3.32簡單的線性規(guī)劃問題XOYABC回顧知識

上一小節(jié)我們已經(jīng)學過了，現(xiàn)實生活中有很多問題可以轉(zhuǎn)化成解二元一次不等式組.

一個一元二次方程表示的應為直線Ax+By+C=0某一側所有的點組成的平面區(qū)域.如何確定直線定界，特殊點定域想想是怎么具體操作的？新課導入

在現(xiàn)實生產(chǎn)、生活中，經(jīng)常會遇到資源利用、人力調(diào)配、生產(chǎn)安排等問題.利用我們今天所學的知識，可以解決很多現(xiàn)實生活中簡單的線性規(guī)劃問題.

下面我們看一個線型規(guī)劃知識解決實際問題的一個小例子.引例

某工廠有A、B兩種配件生產(chǎn)甲、乙兩種產(chǎn)品，每生產(chǎn)一件甲產(chǎn)品使用4個A配件耗時1h,每生產(chǎn)一件乙產(chǎn)品使用4個B配件耗時2h，該廠每天最多可從配件廠獲得16個A配件和12個B配件，按每天8h計算，該廠所有可能的日生產(chǎn)安排是什么？（1）用不等式組表示問題中的限制條件；

（2）畫出不等式組所表示的平面區(qū)域：如上圖，圖中的陰影部分的整點（坐標為整數(shù)的點）就代表所有可能的日生產(chǎn)安排；

（3）提出新問題：

進一步，若生產(chǎn)一件甲產(chǎn)品獲利2萬元，生產(chǎn)一件乙產(chǎn)品獲利3萬元，采用哪種生產(chǎn)安排利潤最大？（4）嘗試解答：

分析：設生產(chǎn)甲產(chǎn)品x件，乙產(chǎn)品y件時，工廠獲得的利潤為z,則z=2x+3y.這樣，上述問題就轉(zhuǎn)化為：當x,y滿足上不等式組并且為非負整數(shù)時，z的最大值是多少？把z=2x+3y變形為

這是斜率為截距為的直線.當z變化時，可以得到一族互相平行的直線，如圖，由于這些直線的斜率是確定的，因此只要給定一個點，（例如（1，2）），就能確定一條直線這說明，截距可以由平面內(nèi)的一個點的坐標唯一確定.可以看到，直線與不等式組的區(qū)域的交點滿足這個不等式組，而且當截距

最大時，z取得最大值.因此，問題可以轉(zhuǎn)化為當直線與不等式組確定的平面區(qū)域有公共點時，在區(qū)域內(nèi)找一個點P，使直線經(jīng)過點P時截距最大

.（5）獲得結果：由圖中可以看出，當實現(xiàn)

x=4與直線x+2y-8=0的交點M（4，2）時，截與直線距的值最大，最大值為這時2x+3y=14.

所以，每天生產(chǎn)甲產(chǎn)品4件，乙產(chǎn)品2件時，工廠可獲得最大利潤14萬元.小結：1、像上題求最大利潤的這種問題，可以轉(zhuǎn)化成求二元一次不等式組與一族直線相交點的問題.2、遇到?jīng)]有學過的問題時，一定要認真思考，看看能不能用平時的知識去解決.概念(1)線性約束條件：在上述問題中，不等式組是一組變量x、y的約束條件，這組約束條件都是關于x、y的一次不等式，故又稱線性約束條件．(2)線性目標函數(shù);關于x、y的一次式z=2x+y是欲達到最大值或最小值所涉及的變量x、y的解析式，叫線性目標函數(shù).(3)線性規(guī)劃問題：一般地，求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題，統(tǒng)稱為線性規(guī)劃問題.(4)可行解、可行域和最優(yōu)解：滿足線性約束條件的解（x,y）叫可行解．由所有可行解組成的集合叫做可行域.

使目標函數(shù)取得最大或最小值的可行解叫線性規(guī)劃問題的最優(yōu)解．思考：(1)在上述問題中，如果生產(chǎn)一件甲產(chǎn)品獲3萬元，每生產(chǎn)一件乙產(chǎn)品獲利2萬元，有應當如何安排生產(chǎn)才能獲得最大利潤？在換幾組數(shù)據(jù)試試.(2)有上述過程，你能得出最優(yōu)解與可行域之間的關系嗎?相同的思路，留給同學們自己思考！實地演練變量x、y滿足下列條件，求z的最大值和最小值.討論下面的問題，設z=2x+y+50，式中的目標函數(shù)（線性目標函數(shù)）約束條件（線性約束條件）最優(yōu)解

求線性目標函數(shù)z的最值的步驟：⑴畫⑷

求⑶移⑵作l。（3，2）(8,2)解：yX01234567123458

由上圖可得當直線z=2x+y+50過點（3，2）時，目標函數(shù)取最小值;當直線過點（8，2）時，目標函數(shù)取的最大值.

答：目標函數(shù)z=2x+y+50的最小值為58，最大值為58.小結：解線性規(guī)劃問題的步驟：

（1）畫：畫出線性約束條件所表示的可行域；

（2）移：在線性目標函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點且縱截距最大或最小的直線；（3）求：通過解方程組求出最優(yōu)解；（4）答：作出答案.例：1

若需在長為4000mm的圓鋼上，截出長為698mm和518mm兩種毛坯，問怎樣截取才能使殘料最少？

初步分析：

可以先考慮兩種“極端”的情況：全部截出長為698mm的甲件，一共可截出5件，殘料長為510mm；全部截出長為518mm的乙件，一共可截出7件，殘料長為374mm.從而x與y應搭配使用.解：截x個甲件，y個乙件，則截取條件數(shù)學化地表示出來就是698x+518y4000同時x與y都是非負整數(shù)；目標函數(shù)為約束條件為698x+518y4000x≥0，y≥0，x∈N，y∈NXOYL：698x+518y=4000

將目標函數(shù)代表的直線族畫出，然后尋找使目標函數(shù)最大的點即可.x和y都是整數(shù)！例：2

要將兩種大小不同的鋼板截成A、B、C三種規(guī)格，每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示：規(guī)格類型鋼板類型A規(guī)格B規(guī)格C規(guī)格第一種鋼板211第二種鋼板123

今需要A、B、C三種規(guī)格的成品分別為15、18、27塊，問各截這兩種鋼板多少張可得所需三種規(guī)格成品，且使所用鋼板張數(shù)最少？

分析：本題是給定一項任務，如何合理安排和規(guī)劃，能以最少的資源來完成該項任務.我們應該搞清各量之間的關系，建立線性規(guī)劃的模型.第一種鋼板x張，第二種鋼板y張，所用解：鋼板數(shù)為z張，則z=x+y

；由題中表格得

作出以上不等式組所表示的平面區(qū)域,即可行域.

作直線L:x+y=0,

把直線L向右上方平移至直線經(jīng)過可行域上的點A，且與原點距離最近，此時z=x+y取最小值.

oxy816248162x+y=15x+2y=18x+2y=18A解方程組得交點A的由于兩個坐標都不是整數(shù)，所以這個解不是最優(yōu)解；

將直線向可行域內(nèi)平移，最先到達的整點為B(3,9)和C(4,8)它們是最優(yōu)解，此時z取得最小值12.坐標

答：要截得所需規(guī)格的三種鋼板，且使所截兩種鋼板的張數(shù)最少的方法有兩種，第一種截法是截第一種鋼板3張、第二種鋼板9張；第二種截法是截第一種鋼板4張、第二種鋼板8張，兩種方法都最少要截得兩種鋼板共12張.2x+y=15oxy81624816x+2y=18x+2y=18A例：3

某工廠生產(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)多少（精確到1t），能使利潤總額達到最大？

分析：這是線性規(guī)劃的理論和方法的應用中的第一類問題．即在人力、物力資源一定的條件下，如何使用它們來完成最多任務．解題一般步驟為：①設出所求的未知數(shù)；②列出約束條件③建立目標函數(shù)；④作出可行域；⑤運用圖解法求出最優(yōu)解．依據(jù)題中已知條件，列表如下：

甲產(chǎn)品（1t）乙產(chǎn)品（1t）資源限額（t）A種礦石（t）104300B種礦石（t）54200煤（t）49360利潤（元）6001000

資源消耗品產(chǎn)品解：生產(chǎn)甲、乙兩種產(chǎn)品分別為xt,

yt,利潤總額為z，由題意可得已知變量x與y滿足約束條件利用圖解法可求出最大值.此時，課堂小結1、線性目標函數(shù)的最大（?。┲狄话阍诳尚杏虻捻旤c處取得，也可能在邊界處取得.2、求線性目標函數(shù)的最優(yōu)解，要注意分析線性目標函數(shù)所表示的幾何意義—在y軸上的截距或其相反數(shù).3、解線性規(guī)劃問題的步驟：畫、移、求、答.課堂練習1、求z=2x+y的最大值，使式中的x、y滿足約束條件解：用圖形表示出不等式組表示的平面區(qū)域；當x=0,y=0時，z=2x+y=0作一組與直線平行的直線:2x+y=t,t∈R.

可知，在經(jīng)過不等式組所表示的公共區(qū)域內(nèi)的點且平行于的直線中，以經(jīng)過點A（2，-1）的直線所對應的t最大.2、某公司承擔了每天至少搬運280t水泥的任務，已知該公司有6輛A型卡車和B型卡車，已知A型卡車每天每輛的運載量為30t，成本費為0.9千元，B型卡車每天每輛的運載量為40t，成本費為1千元.

（1）假如你是公司的調(diào)度員，請你按要求設計出公司每天的派車方案；

（2）設每天派出A型卡車x輛，B型卡車y輛，公司每天所花成本費z千元，寫出x、y應滿足的條件以及z與x、y之間的函數(shù)關系式；(3)如果你是公司的經(jīng)理，為使公司所花的成本費最小，每天應派出A型卡車、B型卡車各為多少輛？解：由已知條件可知，Z=0.9x+y式中x與y變量應滿足：3x+4y≥280≤x≤6