簡(jiǎn)單的線性規(guī)劃.ppt

課題 簡(jiǎn)單的線性規(guī)劃 3 線性規(guī)劃的應(yīng)用 解線性規(guī)劃應(yīng)用問(wèn)題的一般步驟 2 設(shè)好變?cè)⒘谐霾坏仁浇M和目標(biāo)函數(shù) 3 由二元一次不等式表示的平面區(qū)域作出可行域 4 在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解 注意整數(shù)解的調(diào)整 1 理清題意 列出表格 5 還原成實(shí)際問(wèn)題 準(zhǔn)確作圖 準(zhǔn)確計(jì)算 畫出線性約束條件所表示的可行域 畫圖力保準(zhǔn)確 法1 移 在線性目標(biāo)函數(shù)所表示的一組平行線中 利用平移的方法找出與可行域有公共點(diǎn)且縱截距最大或最小的直線 法2 算 線性目標(biāo)函數(shù)的最大 小 值一般在可行域的頂點(diǎn)處取得 也可能在邊界處取得 當(dāng)兩頂點(diǎn)的目標(biāo)函數(shù)值相等時(shí)最優(yōu)解落在一條邊界線段上 此法可彌補(bǔ)作圖不準(zhǔn)的局限 應(yīng)用1 有關(guān)二元一次代數(shù)式取值范圍 解 由 同向相加可得 由 得 將上式與 同向相加得 得 以上解法正確嗎 為什么 當(dāng)x 3 y 0時(shí) 得出2x y的最小值為6 但此時(shí)x y 3 點(diǎn) 3 0 不在不等式組的所表示的平面區(qū)域內(nèi) 所以上述解答明顯錯(cuò)了 通過(guò)分析 我們知道上述解法中 是對(duì)的 但用x的最大 小 值及y的最大 小 值來(lái)確定2x y的最大 小 值卻是不合理的 怎么來(lái)解決這個(gè)問(wèn)題和這一類問(wèn)題呢 這就是我們今天要學(xué)習(xí)的線性規(guī)劃問(wèn)題 我們?cè)O(shè)我們?cè)O(shè)z 2x y方程變形為y 2x z 等式表示斜率為 2 縱截距為z的直線 把z看成參數(shù) 方程表示的是一組平行線 要求z的范圍 現(xiàn)在就轉(zhuǎn)化為求這一組平行線中 與陰影區(qū)域有交點(diǎn) 且在y軸上的截距達(dá)到最大和最小的直線 由圖 我們不難看出 這種直線的縱截距的最小值為過(guò)A 3 1 的直線 縱截距最大為過(guò)C 5 1 的直線 所以 過(guò)A 3 1 時(shí) 因?yàn)閦 2x y 所以 同理 過(guò)B 5 1 時(shí) 因?yàn)閦 2x y 所以 y 解 作線形約束條件所表示的平面區(qū)域 即如圖所示四邊形ABCD 作直線 所以 求得A 3 1 B 4 0 C 5 1 D 4 2 例1 若實(shí)數(shù)x y滿足求2x y的取值范圍 解法2 由待定系數(shù)法 設(shè)2x y m x y n x y m n x m n y m n 2 m n 1m 3 2 n 1 2 2x y 3 2 x y 1 2 x y 4 x y 6 2 x y 4 7 2x y 11 例1 若實(shí)數(shù)x y滿足求2x y的取值范圍 例1 某工廠生產(chǎn)甲 乙兩種產(chǎn)品 已知生產(chǎn)甲種產(chǎn)品1t需消耗A種礦石10t B種礦石5t 煤4t 生產(chǎn)乙種產(chǎn)品1噸需消耗A種礦石4t B種礦石4t 煤9t 每1t甲種產(chǎn)品的利潤(rùn)是600元 每1t乙種產(chǎn)品的利潤(rùn)是1000元 工廠在生產(chǎn)這兩種產(chǎn)品的計(jì)劃中要求消耗A種礦石不超過(guò)300t 消耗B種礦石不超過(guò)200t 消耗煤不超過(guò)360t 甲 乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少 精確到0 1t 能使利潤(rùn)總額達(dá)到最大 列表 5 10 4 600 4 4 9 1000 設(shè)生產(chǎn)甲 乙兩種產(chǎn)品 分別為xt yt 利潤(rùn)總額為z元 應(yīng)用2 有關(guān)利潤(rùn)最高 效益最大等問(wèn)題 例題分析 列表 把題中限制條件進(jìn)行轉(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 利潤(rùn)總額為z元 xt yt 例題分析 解 設(shè)生產(chǎn)甲 乙兩種產(chǎn)品 分別為xt yt 利潤(rùn)總額為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噸 能使利潤(rùn)總額達(dá)到最大 12 4 34 4 經(jīng)過(guò)可行域上的點(diǎn)M時(shí) 目標(biāo)函數(shù)在y軸上截距最大 90 30 75 40 50 40 此時(shí)z 600 x 1000y取得最大值 例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 應(yīng)用3 有關(guān)成本最低 運(yùn)費(fèi)最少等問(wèn)題 得點(diǎn)M的坐標(biāo)為 答 每天需要同時(shí)食用食物A約0 143kg 食物B約0 571kg 能夠滿足日常飲食要求 且花費(fèi)最低16元 幻燈片13 幻燈片14 解 設(shè)每天食用xkg食物A ykg食物B 總花費(fèi)為z元 則目標(biāo)函數(shù)為z 28x 21y且x y滿足約束條件 整理為 作出約束條件所表示的可行域 如右圖所示 目標(biāo)函數(shù)可變形為 如圖 作直線 當(dāng)直線 平移經(jīng)過(guò)可行域時(shí) 在 點(diǎn)M處達(dá)到 軸上截距 的最小值 即此時(shí) 有最小值 解方程組 返回幻燈片12 線性規(guī)劃的應(yīng)用練習(xí) 1 已知 1 a b 1 1 a 2b 3 求a 3b的取值范圍 解法1 由待定系數(shù)法 設(shè)a 3b m a b n a 2b m n a m 2n b m n 1 m 2n 3m 5 3 n 2 3 a 3b 5 3 a b 2 3 a 2b 1 a b 1 1 a 2b 3 11 3 a 3b 1 解法2 1 a b 1 1 a 2b 3 2 2a 2b 2 3 2b a 1 1 3 a 5 3 4 3 b 0 13 3 a 3b 5 3 已知 1 a b 1 1 a 2b 3 求a 3b的取值范圍 解法2約束條件為 目標(biāo)函數(shù)為 z a 3b 由圖形知 11 3 z 1即 11 3 a 3b 1 300 600 A 100 400 2 某家具廠有方木材90m3 木工板600m3 準(zhǔn)備加工成書桌和書櫥出售 已知生產(chǎn)每張書桌需要方木料0 1m3 木工板2m3 生產(chǎn)每個(gè)書櫥需要方木料0 2m3 木工板1m3 出售一張書桌可以獲利80元 出售一張書櫥可以獲利120元 1 怎樣安排生產(chǎn)可以獲利最大 2 若只生產(chǎn)書桌可以獲利多少 3 若只生產(chǎn)書櫥可以獲利多少 1 設(shè)生產(chǎn)書桌x張 書櫥y張 利潤(rùn)為z元 則約束條件為 Z 80 x 120y 作出不等式表示的平面區(qū)域 當(dāng)生產(chǎn)100張書桌 400張書櫥時(shí)利潤(rùn)最大為z 80 100 120 400 56000元 2 若只生產(chǎn)書桌可以生產(chǎn)300張 用完木工板 可獲利24000元 3 若只生產(chǎn)書櫥可以生產(chǎn)450張 用完方木料 可獲利54000元 將直線z 80 x 120y平移可知 900 450 求解 3某紡紗廠生產(chǎn)甲 乙兩種棉紗 已知生產(chǎn)甲種棉紗1噸需耗一級(jí)子棉2噸 二級(jí)子棉1噸 生產(chǎn)乙種棉紗需耗一級(jí)子棉1噸 二級(jí)子棉2噸 每1噸甲種棉紗的利潤(rùn)是600元 每1噸乙種棉紗的利潤(rùn)是900元 工廠在生產(chǎn)這兩種棉紗的計(jì)劃中要求消耗一級(jí)子棉不超過(guò)300噸 二級(jí)子棉不超過(guò)250噸 甲 乙兩種棉紗應(yīng)各生產(chǎn)多少 精確到噸 能使利潤(rùn)總額最大 解 設(shè)生產(chǎn)甲 乙兩種棉紗分別為x噸 y噸 利潤(rùn)總額為z元 則 Z 600 x 900y 作出可行域 可知直線Z 600 x 900y通過(guò)點(diǎn)M時(shí)利潤(rùn)最大 解方程組 得點(diǎn)M的坐標(biāo) x 350 3 117 y 200 3 67 答 應(yīng)生產(chǎn)甲 乙兩種棉紗分別為117噸 67噸 能使利潤(rùn)總額達(dá)到最大 4 咖啡館配制兩種飲料 甲種飲料每杯含奶粉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的位置時(shí) 直線經(jīng)過(guò)可行域上的點(diǎn)C 且與原點(diǎn)距離最大 此時(shí)z 0 7x 1 2y取最大值解方程組得點(diǎn)C的坐標(biāo)為 200 240 例2 已知甲 乙兩煤礦每年的產(chǎn)量分別為200萬(wàn)噸和300萬(wàn)噸 需經(jīng)過(guò)東車站和西車站兩個(gè)車站運(yùn)往外地 東車站每年最多能運(yùn)280萬(wàn)噸煤 西車站每年最多能運(yùn)360萬(wàn)噸煤 甲煤礦運(yùn)往東車站和西車站的運(yùn)費(fèi)價(jià)格分別為1元 噸和1 5元 噸 乙煤礦運(yùn)往東車站和西車站的運(yùn)費(fèi)價(jià)格分別為0 8元 噸和1 6元 噸 煤礦應(yīng)怎樣編制調(diào)運(yùn)方案 能使總運(yùn)費(fèi)最少 應(yīng)用3 有關(guān)成本最低 運(yùn)費(fèi)最少等問(wèn)題 解 設(shè)甲煤礦運(yùn)往東車站x萬(wàn)噸 乙煤礦運(yùn)往東車站y萬(wàn)噸 則約束條件為 目標(biāo)函數(shù)為 z x 1 5 200