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

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