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

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