【正文】 4 ≥b 3 ? x1,x2,x3,x4 ≥0 小知識 ? 明尼蘇達(dá)大學(xué)建立食物營養(yǎng)價值評估數(shù)據(jù)庫，可對每天需要的營養(yǎng)與食物作最優(yōu)化選擇 ? 作業(yè)：建立自己的小營養(yǎng)優(yōu)化選擇 例題分析 3：人力資源分配問題 例 2．某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下： 班次 時間 所需人數(shù) 1 6 ： 00 —— 10 ： 00 60 2 10 ： 00 —— 14 ： 00 70 3 14 ： 00 —— 18 ： 00 60 4 18 ： 00 —— 22 ： 00 50 5 22 ： 00 —— 2 ： 00 20 6 2 ： 00 —— 6 ： 00 30 設(shè)司機和乘務(wù)人員分別在各時間段一開始時上班，并連續(xù)工作 八小時 (注意每班次才 4小時 )，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員 ? 例題分析 3：人力資源分配問題 解：設(shè) xi 表示從第 i班次開始上班的司機和乘務(wù)人員數(shù)(i=1,2,3,4,5,6),這樣我們建立如下的數(shù)學(xué)模型。這樣我們建立如下的數(shù)學(xué)模型。已知： 項目 A：從第一 年 到第五年每年年初都可投資，當(dāng)年末能收回本利 110%； 項目 B：從第一年到第四年每年年初都可投資，次年末能收回本利 125%，但規(guī)定每年最大投資額不能超過 30萬元； 項目 C：需在第三年年初投資，第五年末能收回本利 140%，但規(guī)定最大投資額不能超過 80萬元； 項目 D：需在第二年年初投資，第五年末能收回本利 155%，但規(guī)定最大投資額不能超過 100萬元。這樣我們建立如下的決策變量： ? 1 2 3 4 5 ? A x11 x21 x31 x41 x51 ? B x12 x22 x32 x42 ? C x33 ? D x24 例題分析 5：投資問題 Max z = + + + . x11+ x12 = 200 x21 + x22+ x24 = (第二年的投資與第一年投資回收的本利金相等 ) x31 + x32+ x33 = + x41 + x42 = + x51 = + xi2 ≤ 30 ( i =1 、 4 ) x33 ≤ 80 x24 ≤ 100 xij ≥ 0 ( i = 1 、 5； j = 4） 線性規(guī)劃解法（圖解法） ?變量： x表示 A的臺數(shù)， y表示 B的臺數(shù) ?目標(biāo)函數(shù)：利潤最大 max f(x,y)=x 6＋ y 7 ?約束條件： 2x+3y=24 2x+y=16 x， y=0 圖作業(yè)法 0 5 10 x Y 10 5 0 2x+y=16 2x+3y=24 A(0,0) 0 B(8,0) 48 C(6,4) 64 D(0,8) 56 E 表達(dá)式 Min S(x,y)=+ . 5x+2y=60 3x+2y=40 5x+y=35 x=0 y=0 線性規(guī)劃的圖解法 P97 例 4： Max S(x,y)=7x+12y 9x+4y=360 4x+5y=200 3x+10y=300 F (0,90) G( 0,40) A (0,30) D( 40,0) H (50,0) E (100,0) B C O(0,0) 9x+4y=360 4x+5y=200 3x+10y=300 A(0,30) B(20,24) C(1000/29,360/29) D(40,0) O(0,0) 最優(yōu)解在直線圍成的多邊形的頂點取得。 交點的求法 A， D， O容易求出，對于 B、 C 4x+5y=200 3x+10y=300 9x+4y=360 4x+5y=200 x=(2005y)/4代入 3x+10y=300， (60015y)/4+10y=300， 60015y+40y=1200， y=24，代入 3x+10y=300，有 3x=60， x=20，所以 B為（ 20， 24） x=(2005y)/4代入 9x+4y=360， (180045y)/4+4y=360， 7200180y+16y=1440， y=(72001440)/(18016)=1000/29，代入4x+5y=200，有 x=360/29，所以 C為 (1000/29,360/29) 另一個例子： Min S(x,y)=200x+160y 6x+2y=12 2x+2y=8 4x+12y=24 0=x=7， 0=y=7 2 4 6 7 7 6 4 2 6x+2y=12 2x+2y=8 4x+12y=24 y=7 x=7 E(0,7) D(0,6) (0,4) (0,2) (0,0) (2,0) (4,0) A(6,0)G(7,0) F(7,7) C(1,3) B(3,1) 圓圈表示可行域的邊界 最優(yōu)解在圓圈所在的點取得 把這些點分別代入目標(biāo)函數(shù)，求得 S值分別為： A1200， B760， C680，D960， E1120， F2520，G1400，所以 C為最優(yōu)點。如唯一一定在凸多邊形的某頂點上；如是無窮則一定充滿凸多邊形的一條邊界上 ? 如有可行解，但沒有有限最優(yōu)解，這時凸多邊形是無界的，反之不一定成立（如上例） ? 沒有可行解，即可行解集是空集 用 EXCEL進(jìn)行線性規(guī)劃 ? 例：學(xué)校準(zhǔn)備為學(xué)生添加營養(yǎng)餐，每個學(xué)生每月至少要補充 60單位碳水傾到物， 40單位蛋白質(zhì)和 35單位脂肪。所提供的原材料有： ? 花生餅，每噸單價 500元，含 25%蛋白質(zhì)、 2%脂肪、10%淀粉、 2%纖維素 ? 花生秧，每噸 50元，含 8%蛋白質(zhì)、 1%脂肪、 5%淀粉、 40%纖維素 ? 骨粉，每噸 350元， 20%蛋白質(zhì)、 8%脂肪、 1%淀粉、%纖維素 ? 玉米，每噸 450元， 7%蛋白質(zhì)、 5%脂肪、 40%淀粉、 6%纖維素 ? 滿足營養(yǎng)成分前提下，配合費用最低 建模 ? 決策變量：四種原料，各自需要為 X X X X4 ? 目標(biāo)函數(shù)： max=500X1+50X2+350X3+450X4 ? 約束條件： 25%x1+8%x2+20%x3+7%x4≥15% ? 2%x1+1%x2+8%x3+5%x4≥% ? 10%x1+5%x2+1%x3+40%x4≥30% ? 2%x1+40%x2+%x3+6%x4≤10% ? X1,X2,X3,X4 ≥0 ? X1+X2+X3+X4=1(歸一條件 ) 發(fā)現(xiàn)問題 ? 總量沒有為 1而是 ? 所以要增加約束條件，決策總量單元格 G6=1 ? 計算后發(fā)現(xiàn)無解 ,需要重新調(diào)整原料和降低營養(yǎng)成份 對偶問題與影子價格 ? 在經(jīng)濟活動中可以追求最大利潤，也可以追求最低成本，這是一個問題兩種不同表現(xiàn)形式。 ? 對偶問題變換規(guī)則 原問題 對偶問題 目標(biāo)函數(shù) max 目標(biāo)函數(shù) min 約束條件 = 約束條件 = 約束條件 = 約束條件 = 對偶變量 = 對偶變量 = 對偶變量 = 對偶變量 = 約束條件 = 自由變量 自由變量 約束條件 = 例題分析 1：生產(chǎn)計劃 問題對偶問題 ?例 1. 某工廠在計劃期內(nèi)要安排 Ⅰ 、 Ⅱ 兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及 A、 B兩種原材料的消耗、資源的限制，如下表： Ⅰ Ⅱ 資源限制 設(shè)備 1 1 300 臺時 原料 A 2 1 400 千克 原料 B 0 1 250 千克 單位產(chǎn)品獲利 50 元 100 元 問：工廠應(yīng)分別生產(chǎn)多少單位 Ⅰ 、 Ⅱ 產(chǎn)品才能使工廠獲利最多？ 對偶問題 ? 設(shè)備 x1,原料 Ax2，原料 Bx3 ? 目標(biāo)函數(shù) minZ=300*x1+400*x2+250*x3 ? ? X1+2*x2=50 ? X1+x2+x3=100 ? X X X3=0 習(xí)題：食品營養(yǎng)例中的對偶問題 Min S(x,y)=+ . 5x+2y=60 3x+2y=40 5x+y=35 X,y=0 對偶 Max S(Z1,Z2,Z)=60*Z1+40*z2+35*z3 . 5*z1+3*z2+5*z3= 2*z1+2*z2+z3= z1,z2,z3=0 敏感性分析 ? 注意線性模型與假定非負(fù)勾選上 敏感性分析作用 ? 低于陰影價格購買或應(yīng)用該約束條件是好的決策 ? 可以分析哪個約束條件比較敏感，對此部分條件因素要變化時要慎重決策 第二節(jié) 運輸問題和 指派問題（特殊的線性規(guī)劃問題） ?一、運輸問題 ?二、指派問題 案例：產(chǎn)銷平衡問題 ?例 1 某公司從兩個產(chǎn)地 A A2將物品運往三個銷地B B B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？