簡(jiǎn)單的線性規(guī)劃問題

簡(jiǎn)單的線性規(guī)劃問題第一頁，共四十七頁，2022年，8月28日一、導(dǎo)學(xué)提示，自主學(xué)習(xí)二、新課引入，任務(wù)驅(qū)動(dòng)三、新知建構(gòu)，典例分析四、當(dāng)堂訓(xùn)練，針對(duì)點(diǎn)評(píng)五、課堂總結(jié)，布置作業(yè)3.3.2簡(jiǎn)單線性規(guī)劃問題（2課時(shí)）第二頁，共四十七頁，2022年，8月28日一、導(dǎo)學(xué)提示，自主學(xué)習(xí)1.本節(jié)學(xué)習(xí)目標(biāo)（1）了解線性規(guī)劃的意義以及約束條件、線性目標(biāo)函數(shù)、可行域、最優(yōu)解等相關(guān)的基本概念

．（2）了解線性規(guī)劃的圖解法，并會(huì)用圖解法求線性目標(biāo)函數(shù)的最大（?。┲?/p>

.（3）掌握對(duì)一些實(shí)際優(yōu)化問題建立線性規(guī)劃數(shù)學(xué)模型并運(yùn)用圖解法進(jìn)行求解的基本方法和步驟

．學(xué)習(xí)重點(diǎn)：線性規(guī)劃的圖解法學(xué)習(xí)難點(diǎn)：尋求線性規(guī)劃問題的最優(yōu)解

第三頁，共四十七頁，2022年，8月28日一、導(dǎo)學(xué)提示，自主學(xué)習(xí)2.本節(jié)主要題型題型一求線性目標(biāo)函數(shù)的最值題型二線性規(guī)劃的實(shí)際應(yīng)用3.自主學(xué)習(xí)教材P87-P913.3.2簡(jiǎn)單的線性規(guī)劃問題第四頁，共四十七頁，2022年，8月28日1、二元一次不等式表示哪個(gè)平面區(qū)域的判斷方法：2、二元一次不等式組表示的平面區(qū)域“直線定界、特殊點(diǎn)定域”各個(gè)不等式所表示的平面區(qū)域的公共部分二、新課引入，任務(wù)驅(qū)動(dòng)一.知識(shí)回顧：第五頁，共四十七頁，2022年，8月28日通過本節(jié)的學(xué)習(xí)你能掌握簡(jiǎn)單的線性規(guī)劃問題的解法及步驟嗎？二.任務(wù)驅(qū)動(dòng)：二、新課引入，任務(wù)驅(qū)動(dòng)第六頁，共四十七頁，2022年，8月28日三、新知建構(gòu)，典例分析

一.簡(jiǎn)單線性規(guī)劃有關(guān)概念二.簡(jiǎn)單線性規(guī)劃問題解題步驟

第七頁，共四十七頁，2022年，8月28日某工廠用A,B兩種配件生產(chǎn)甲,乙兩種產(chǎn)品,每生產(chǎn)一件甲種產(chǎn)品使用4個(gè)A配件耗時(shí)1h,每生產(chǎn)一件乙種產(chǎn)品使用4個(gè)B配件耗時(shí)2h,該廠每天最多可從配件廠獲得16個(gè)A配件和12個(gè)B配件,按每天工作8小時(shí)計(jì)算,該廠所有可能的日生產(chǎn)安排是什么?

若生產(chǎn)1件甲種產(chǎn)品獲利2萬元,生產(chǎn)1件乙種產(chǎn)品獲利3萬元,采用哪種生產(chǎn)安排利潤(rùn)最大?三、新知建構(gòu)，典例分析

問題引入:第八頁，共四十七頁，2022年，8月28日32利潤(rùn)(萬元)821所需時(shí)間1240B種配件1604A種配件資源限額

乙產(chǎn)品

(1件)甲產(chǎn)品

(1件)產(chǎn)品消耗量資源把問題1的有關(guān)數(shù)據(jù)列表表示如下:設(shè)甲,乙兩種產(chǎn)品分別生產(chǎn)x,y件,第九頁，共四十七頁，2022年，8月28日將上面不等式組表示成平面上的區(qū)域,區(qū)域內(nèi)所有坐標(biāo)為整數(shù)的點(diǎn)P(x,y),安排生產(chǎn)任務(wù)x,y都是有意義的.0xy4348設(shè)甲,乙兩種產(chǎn)品分別生產(chǎn)x,y件,由己知條件可得:問題：求利潤(rùn)2x+3y的最大值.第十頁，共四十七頁，2022年，8月28日若設(shè)利潤(rùn)為z,則z=2x+3y,這樣上述問題轉(zhuǎn)化為:當(dāng)x,y在滿足上述約束條件時(shí),z的最大值為多少?當(dāng)點(diǎn)P在可允許的取值范圍變化時(shí),第十一頁，共四十七頁，2022年，8月28日0xy4348M（4，2）問題：求利潤(rùn)z=2x+3y的最大值.第十二頁，共四十七頁，2022年，8月28日象這樣關(guān)于x,y一次不等式組的約束條件稱為線性約束條件Z=2x+3y稱為目標(biāo)函數(shù),(因這里目標(biāo)函數(shù)為關(guān)于x,y的一次式,又稱為線性目標(biāo)函數(shù)在線性約束下求線性目標(biāo)函數(shù)的最值問題,統(tǒng)稱為線性規(guī)劃,一.線性規(guī)劃有關(guān)概念:第十三頁，共四十七頁，2022年，8月28日滿足線性約束的解(x,y)叫做可行解,所有可行解組成的集合叫做可行域使目標(biāo)函數(shù)取得最值的可行解叫做這個(gè)問題的最優(yōu)解變式：若生產(chǎn)一件甲產(chǎn)品獲利1萬元，生產(chǎn)一件乙產(chǎn)品獲利3萬元，采用哪種生產(chǎn)安排利潤(rùn)最大？第十四頁，共四十七頁，2022年，8月28日0xy4348N（2，3）變式：求利潤(rùn)z=x+3y的最大值.第十五頁，共四十七頁，2022年，8月28日名稱意義約束條件由變量x,y組成的不等式組線性約束條件由x,y的一次不等式（或方程）組成的不等式組目標(biāo)函數(shù)關(guān)于x,y的函數(shù)解析式，如z=2x+3y等線性目標(biāo)函數(shù)關(guān)于x,y的一次解析式可行解滿足線性約束條件的解（x,y)可行域所有可行解組成的集合最優(yōu)解使目標(biāo)函數(shù)取得最大值或最小值的可行解線性規(guī)劃問題

在線性約束條件下求線性目標(biāo)函數(shù)的最大值或最小值問題線性規(guī)劃有關(guān)概念:第十六頁，共四十七頁，2022年，8月28日172、畫：

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

3、移：

在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；

4、求：通過解方程組求出最優(yōu)解；

5、答：作出答案。

1、找

找出線性約束條件、目標(biāo)函數(shù)；

二.線性規(guī)劃問題解題步驟:三、新知建構(gòu)，典例分析

第十七頁，共四十七頁，2022年，8月28日說明:二、最優(yōu)解一般在可行域的頂點(diǎn)處取得，也有可能在邊界處取得．四、在哪個(gè)頂點(diǎn)取得不僅與B的符號(hào)有關(guān)，而且還與直線Z=Ax+By的斜率有關(guān)．一、先定可行域和平移方向，再找最優(yōu)解。三、新知建構(gòu)，典例分析

三、求線性目標(biāo)函數(shù)的最優(yōu)解，要注意分析線性目標(biāo)函數(shù)所表示的幾何意義

--------與y軸上的截距相關(guān)的數(shù)。第十八頁，共四十七頁，2022年，8月28日2.典例分析：題型一求線性目標(biāo)函數(shù)的最值題型二線性規(guī)劃的實(shí)際應(yīng)用三、新知建構(gòu)，典例分析第十九頁，共四十七頁，2022年，8月28日

x－4y≤－3，例1.已知變量x，y滿足3x＋5y≤25，求z＝2x＋y的

x≥1，最大值和最小值．

思維突破：把z看成直線在y軸上的截距，先畫出可行域，再求z的最值．三、新知建構(gòu)，典例分析題型一.求線性目標(biāo)函數(shù)的最值:第二十頁，共四十七頁，2022年，8月28日自主解答：作出不等式組所表示的可行域，如圖:設(shè)直線l0：2x＋y＝0，直線l：2x＋y＝z，則z的幾何意義是直線y＝－2x＋z在y軸上的截距

顯然，當(dāng)直線越往上移動(dòng)時(shí)，對(duì)應(yīng)在y軸上的截距越大，即z越大；當(dāng)直線越往下移動(dòng)時(shí)，對(duì)應(yīng)在y軸上的截距越小，即z越?。?、新知建構(gòu)，典例分析第二十一頁，共四十七頁，2022年，8月28日作一組與直線l0平行的直線系l，上下平移，可得：點(diǎn)A(5,2)時(shí)，zmax＝2×5＋2＝12；當(dāng)直線l移動(dòng)到直線l2

時(shí)，即過當(dāng)直線l移動(dòng)到直線l1

時(shí)，即過點(diǎn)B(1,1)時(shí)，zmin＝2×1＋1正確作出可行域后，將目標(biāo)函數(shù)變?yōu)橹本€方程的斜截式的形式，應(yīng)注意該直線在y軸上的截距與目標(biāo)函數(shù)z取值的關(guān)系．再注意該直線的斜率與可行域邊界直線的斜率關(guān)系，以便準(zhǔn)確找到最優(yōu)解．＝3.三、新知建構(gòu)，典例分析第二十二頁，共四十七頁，2022年，8月28日

y≥1，例2.已知實(shí)數(shù)x，y滿足y≤2x－1，

x＋y≤m，如果目標(biāo)函數(shù)z＝x－y的最小值為－1，則實(shí)數(shù)m＝()A．7B．5C．4D．3

思維突破：畫出x，y滿足的可行域，可得直線y＝2x－1與直線x＋y＝m的交點(diǎn)使目標(biāo)函數(shù)z＝x－y取得最小值．三、新知建構(gòu)，典例分析第二十三頁，共四十七頁，2022年，8月28日答案：B三、新知建構(gòu)，典例分析第二十四頁，共四十七頁，2022年，8月28日線性規(guī)劃的理論和方法主要在兩類問題中得到應(yīng)用:一、在人力、物力、資金等資源一定的條件下，如何使用它們來完成最多的任務(wù)；二、給定一項(xiàng)任務(wù)，如何合理安排和規(guī)劃，能以最少的人力、物力、資金等資源來完成該項(xiàng)任務(wù)下面我們就來看看線性規(guī)劃在實(shí)際中的一些應(yīng)用：

三、新知建構(gòu)，典例分析題型二.線性規(guī)劃的實(shí)際應(yīng)用:第二十五頁，共四十七頁，2022年，8月28日例3.營(yíng)養(yǎng)學(xué)家指出,成人良好的日常飲食應(yīng)該至少提供0.075kg的碳水化合物,0.06kg的蛋白質(zhì),0.06kg的脂肪.1kg食物A含有0.105kg碳水化合物,0.07kg蛋白質(zhì),0.14kg脂肪,花費(fèi)28元;而1kg食物B含有0.105kg碳水化合物,0.14kg蛋白質(zhì),0.07kg脂肪,花費(fèi)21元.為了滿足營(yíng)養(yǎng)專家指出的日常飲食要求,同時(shí)使花費(fèi)最低,需要同時(shí)食用食物A和食物B多少kg？三、新知建構(gòu)，典例分析第二十六頁，共四十七頁，2022年，8月28日食物／kg碳水化合物／kg蛋白質(zhì)/kg脂肪／kgA0.1050.070.14B0.1050.140.07分析：將已知數(shù)據(jù)列成表格三、新知建構(gòu)，典例分析第二十七頁，共四十七頁，2022年，8月28日解：設(shè)每天食用xkg食物A，ykg食物B，總成本為z，那么目標(biāo)函數(shù)為：z＝28x＋21y作出二元一次不等式組所表示的平面區(qū)域，即可行域1、找三、新知建構(gòu)，典例分析第二十八頁，共四十七頁，2022年，8月28日把目標(biāo)函數(shù)z＝28x＋21y變形為xyo/575/76/73/73/76/7

它表示斜率為縱截距隨z變化的一組平行直線

是直線在y軸上的截距，當(dāng)截距最小時(shí)，z的值最小。M如圖可見，當(dāng)直線z＝28x＋21y經(jīng)過可行域上的點(diǎn)M時(shí)，縱截距最小，即z最小。2、畫3、移第二十九頁，共四十七頁，2022年，8月28日M點(diǎn)是兩條直線的交點(diǎn)，解方程組得M點(diǎn)的坐標(biāo)為：所以zmin＝28x＋21y＝16

由此可知，每天食用食物A143g，食物B約571g，能夠滿足日常飲食要求，又使花費(fèi)最低，最低成本為16元。4、求5、答第三十頁，共四十七頁，2022年，8月28日31解線性規(guī)劃問題的步驟：

（1）2、畫：

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

（2）3、移：

在線性目標(biāo)函數(shù)所表示的一組平行線中，利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線；

（3）4、求：通過解方程組求出最優(yōu)解；

（4）5、答：作出答案。

1、找

找出線性約束條件、目標(biāo)函數(shù)；

三、新知建構(gòu)，典例分析第三十一頁，共四十七頁，2022年，8月28日例4.某工廠現(xiàn)有兩種大小不同規(guī)格的鋼板可截成A、B、C三種規(guī)格，每張鋼板可同時(shí)截得三種規(guī)示：格的小鋼板的塊數(shù)如下表所解：設(shè)需截第一種鋼板x張，第二種鋼板y張，鋼板總張數(shù)為Z則,規(guī)格類型鋼板類型第一種鋼板第二種鋼板A規(guī)格B規(guī)格C規(guī)格2121312x+y≥15,x+2y≥18,x+3y≥27,x≥0y≥0

某顧客需要A,B,C三種規(guī)格的成品分別為15，18，27塊，若你是經(jīng)理,問各截這兩種鋼板多少張既能滿足顧客要求又使所用鋼板張數(shù)最少。分析問題:標(biāo)目函數(shù):z=x+y第三十二頁，共四十七頁，2022年，8月28日x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,y≥0直線x+y=12經(jīng)過的整點(diǎn)是B(3,9)和C(4,8)，它們是最優(yōu)解.

作出直線L:x+y=0，目標(biāo)函數(shù):z=

x+yB(3,9)C(4,8)A(3.6,7.8)當(dāng)直線L經(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)246181282724681015但它不是最優(yōu)整數(shù)解.作直線x+y=12約束條件:畫可行域平移L找交點(diǎn)及交點(diǎn)坐標(biāo)調(diào)整優(yōu)解法第三十三頁，共四十七頁，2022年，8月28日x0y2x+y=15x+3y=27x+2y=18x+y=02x+y≥15,{x+2y≥18,x+3y≥27,x≥0,x∈N*y≥0y∈N*經(jīng)過可行域內(nèi)的整點(diǎn)B(3,9)和C(4,8)且和原點(diǎn)距離最近的直線是x+y=12，它們是最優(yōu)解.作出一組平行直線t

=

x+y，目標(biāo)函數(shù)t

=

x+yB(3,9)C(4,8)A(18/5,39/5)打網(wǎng)格線法在可行域內(nèi)打出網(wǎng)格線，當(dāng)直線經(jīng)過點(diǎn)A時(shí)t=x+y=11.4,但它不是最優(yōu)整數(shù)解，將直線x+y=11.4繼續(xù)向上平移，1212182715978第三十四頁，共四十七頁，2022年，8月28日在可行域內(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)解第三十五頁，共四十七頁，2022年，8月28日例5.一個(gè)化肥廠生產(chǎn)甲、乙兩種混合肥料，生產(chǎn)1車皮甲種肥料的主要原料是磷酸鹽4t、硝酸鹽18t；生產(chǎn)1車皮乙種肥料需要的主要原料是磷酸鹽1t、硝酸鹽15t?，F(xiàn)庫存磷酸鹽10t、硝酸鹽66t，在此基礎(chǔ)上生產(chǎn)這兩種混合肥料。列出滿足生產(chǎn)條件的數(shù)學(xué)關(guān)系式，并畫出相應(yīng)的平面區(qū)域。并計(jì)算生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大的利潤(rùn)？解：設(shè)x、y分別為計(jì)劃生產(chǎn)甲、乙兩種混合肥料的車皮數(shù)，于是滿足以下條件：xyo第三十六頁，共四十七頁，2022年，8月28日例6在上一節(jié)例4（P85）中，若生產(chǎn)1車皮甲種肥料，產(chǎn)生的利潤(rùn)為10000元；生產(chǎn)1車皮乙種肥料，產(chǎn)生的利潤(rùn)為5000元，那么分別生產(chǎn)甲、乙兩種肥料各多少車皮，能夠產(chǎn)生最大利潤(rùn)？解：設(shè)生產(chǎn)甲種肥料x車皮、乙種肥料y車皮，能夠產(chǎn)生利潤(rùn)Z萬元。目標(biāo)函數(shù)為：可行域如圖。把z=x+0.5y變形為得到斜率為-2，在y軸上的截距為2z,隨z變化的一族平行直線。xy0M由圖可以看出，當(dāng)直線y=-2x+2z經(jīng)過可行域上的點(diǎn)M時(shí)，截距2z最大，即Z最大。第三十七頁，共四十七頁，2022年，8月28日xy0M解方程組得M的坐標(biāo)為（2，2）所以答：生產(chǎn)甲種、乙種肥料各2車皮，能夠產(chǎn)生最大利潤(rùn)，最大利潤(rùn)為3萬元。第三十八頁，共四十七頁，2022年，8月28日即先求非整數(shù)條件下的最優(yōu)解，調(diào)整Z的值使不定方程Ax+By=Z存在最大（?。┑恼c(diǎn)值，最后篩選出整點(diǎn)最優(yōu)解．即先打網(wǎng)格，描出可行域內(nèi)的整點(diǎn)，平移直線，最先經(jīng)過或最后經(jīng)過的整點(diǎn)坐標(biāo)即為最優(yōu)整解．線性規(guī)劃求最優(yōu)整數(shù)解的一般方法:1.平移找解法：

2.調(diào)整優(yōu)解法：三、新知建構(gòu)，典例分析第三十九頁，共四十七頁，2022年，8月28日

x－2y＋4≥0，1．已知實(shí)數(shù)x，y滿足約束條件2x＋y－2≥0，

3x－y－3≤0，則目標(biāo)函數(shù)z＝x＋2y的最大值的可行解為________．(2,3)四、當(dāng)堂訓(xùn)練，針對(duì)點(diǎn)評(píng)變式訓(xùn)練1-1：第四十頁，共四十七頁，2022年，8月28日x－y＋5≥0，2．已知x，y滿足x≤3，

x＋y＋k≥0，且z＝2x＋4y的最小值)為－6，則常數(shù)k＝( A．2

B．9C．3D．0解析：畫圖后知：當(dāng)x＝3時(shí)z＝2x＋4y取最小值－6.D四、當(dāng)堂訓(xùn)練，針對(duì)點(diǎn)評(píng)第四十一頁，共四十七頁，2022年，8月28日2.某廠擬生產(chǎn)甲、乙兩種適銷產(chǎn)品，每件銷售收入分別為3000元、2000元，甲、乙產(chǎn)品都需要在A、B兩種設(shè)備上加工，在每臺(tái)A、B上加工1件甲所需工時(shí)分別為1h、2h，A、B兩種設(shè)備每月有效使用臺(tái)數(shù)分別為400h和500h。如何安排生產(chǎn)可使收入最大？

解：設(shè)每月生產(chǎn)甲產(chǎn)品x件，生產(chǎn)乙產(chǎn)品y件，每月收入為z，目標(biāo)函數(shù)為Z＝3x＋2y，滿足的條件是：變式訓(xùn)練2-1：第