《簡單的線性規(guī)劃》PPT課件.ppt

《《簡單的線性規(guī)劃》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《簡單的線性規(guī)劃》PPT課件.ppt（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

使z 2x y取得最大值的可行解為 且最大值為 復(fù)習(xí)引入 1 已知二元一次不等式組 1 畫出不等式組所表示的平面區(qū)域 滿足的解 x y 都叫做可行解 z 2x y叫做 2 設(shè)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取得最小值的可行解 且最小值為 這兩個最值都叫做問題的 線性約束條件 線性目標(biāo)函數(shù) 線性約束條件 2 1 1 1 3 3 最優(yōu)解 例題分析 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)品的利潤是600元 每1t乙種產(chǎn)品的利潤是1000元 工廠在生產(chǎn)這兩種產(chǎn)品的計劃中要求消耗A種礦石不超過300t 消耗B種礦石不超過200t 消耗煤不超過360t 甲 乙兩種產(chǎn)品應(yīng)各生產(chǎn)多少 精確到0 1t 能使利潤總額達(dá)到最大 列表 5 10 4 600 4 4 9 1000 設(shè)生產(chǎn)甲 乙兩種產(chǎn)品 分別為xt yt 利潤總額為z元 例題分析 列表 把題中限制條件進(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 利潤總額為z元 xt yt 例題分析 解 設(shè)生產(chǎn)甲 乙兩種產(chǎn)品 分別為xt yt 利潤總額為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噸 能使利潤總額達(dá)到最大 12 4 34 4 經(jīng)過可行域上的點M時 目標(biāo)函數(shù)在y軸上截距最大 90 30 75 40 50 40 此時z 600 x 1000y取得最大值 例題分析 2要將兩種大小不同規(guī)格的鋼板截成A B C三種規(guī)格 每張鋼板可同時截得三種規(guī)格的小鋼板的塊數(shù)如下表所示 解 設(shè)需截第一種鋼板x張 第一種鋼板y張 則 2x y 15 x 2y 18 x 3y 27 x 0 y 0 作出可行域 如圖 目標(biāo)函數(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 直線x y 12經(jīng)過的整點是B 3 9 和C 4 8 它們是最優(yōu)解 作出一組平行直線z x y 目標(biāo)函數(shù)z x y 當(dāng)直線經(jīng)過點A時z x y 11 4 x y 12 解得交點B C的坐標(biāo)B 3 9 和C 4 8 調(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 目標(biāo)函數(shù)t x y 打網(wǎng)格線法 在可行域內(nèi)打出網(wǎng)格線 當(dā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ù)點共有 個 鞏固練習(xí)1 1234x y43210 4x 3y 12 在可行域內(nèi)找出最優(yōu)解 線性規(guī)劃整數(shù)解問題的一般方法是 1 若區(qū)域 頂點 處恰好為整點 那么它就是最優(yōu)解 在包括邊界的情況下 2 若區(qū)域 頂點 不是整點或不包括邊界時 應(yīng)先求出該點坐標(biāo) 并計算目標(biāo)函數(shù)值Z 然后在可行域內(nèi)適當(dāng)放縮目標(biāo)函數(shù)值 使它為整數(shù) 且與Z最接近 在這條對應(yīng)的直線中 取可行域內(nèi)整點 如果沒有整點 繼續(xù)放縮 直至取到整點為止 3 在可行域內(nèi)找整數(shù)解 一般采用平移找解法 即打網(wǎng)絡(luò) 找整點 平移直線 找出整數(shù)最優(yōu)解 解線性規(guī)劃應(yīng)用問題的一般步驟 2 設(shè)好變元并列出不等式組和目標(biāo)函數(shù) 3 由二元一次不等式表示的平面區(qū)域做出可行域 4 在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解 1 理清題意 列出表格 5 還原成實際問題 準(zhǔn)確作圖 準(zhǔn)確計算 咖啡館配制兩種飲料 甲種飲料每杯含奶粉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的位置時 直線經(jīng)過可行域上的點C 且與原點距離最大 此時z 0 7x 1 2y取最大值解方程組得點C的坐標(biāo)為 200 240 二元一次不等式表示平面區(qū)域 直線定界 特殊點定域 簡單的線性規(guī)劃 約束條件 目標(biāo)函數(shù) 可行解 可行域 最優(yōu)解 求解方法 畫 移 求 答 練習(xí)鞏固 1 某家具廠有方木材90m3 木工板600m3 準(zhǔn)備加工成書桌和書櫥出售 已知生產(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)書桌600 2 300張 可獲利潤 80 300 24000元 但木料沒有用完 2 只生產(chǎn)書櫥 用完方木料 可生產(chǎn)書櫥90 0 2 450張 可獲利潤120 450 54000元 但木工板沒有用完 分析 300 600 A 100 400 1 某家具廠有方木材90m3 木工板600m3 準(zhǔn)備加工成書桌和書櫥出售 已知生產(chǎn)每張書桌需要方木料0 1m3 木工板2m3 生產(chǎn)每個書櫥需要方木料0 2m3 木工板1m3 出售一張書桌可以獲利80元 出售一張書櫥可以獲利120元 1 怎樣安排生產(chǎn)可以獲利最大 2 若只生產(chǎn)書桌可以獲利多少 3 若只生產(chǎn)書櫥可以獲利多少 1 設(shè)生產(chǎn)書桌x張 書櫥y張 利潤為z元 則約束條件為 Z 80 x 120y 作出不等式表示的平面區(qū)域 當(dāng)生產(chǎn)100張書桌 400張書櫥時利潤最大為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 求解 4 x 8 y 4 x y 10 4x 5y 30 320 x 504y 0 2 某運(yùn)輸公司接受了向抗洪搶險地區(qū)每天至少運(yùn)送180噸支援物資的任務(wù) 該公司有8輛載重量為6噸的A型卡車和4輛載重量為10噸的B型卡車 有10名駕駛員 每輛卡車每天往返的次數(shù)為A型卡車4次 B型卡車3次 每輛卡車每天往返的成本費(fèi)A型卡車為320元 B型卡車為504元 問如何安排車輛才能使該公司所花的成本費(fèi)最低 最低為多少元 要求每型卡車至少安排一輛 解 設(shè)每天調(diào)出的A型車x輛 B型車y輛 公司所花的費(fèi)用為z元 則 Z 320 x 504y 作出可行域中的整點 可行域中的整點 5 2 使Z 320 x 504y取得最小值 且Zmin 2608元 作出可行域 2 附加練習(xí) 深圳市福田區(qū)水泥制品廠生產(chǎn)兩種水泥 已知生產(chǎn)甲種水泥制品1噸 需礦石4噸 煤3噸 生產(chǎn)乙種水泥制品1噸 需礦石5噸 煤10噸 每1噸甲種水泥制品的利潤為7萬元 每1噸乙種水泥制品的利潤是12萬元 工廠在生產(chǎn)這兩種水泥制品的計劃中 要求消耗的礦石不超過200噸 煤不超過300噸 甲乙兩種水泥制品應(yīng)生產(chǎn)多少 能使利潤達(dá)到最大值