【正文】 ≥120 () 3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0 X1≥0 X2≥0 OR1 53 原問題一般模型： 對偶問題一般模型： maxZ=CX min ω=Yb AX ≤b YA ≥C X ≥0 Y ≥0 OR1 54 對偶規(guī)則 ? 原問題有 m個(gè)約束條件，對偶問題有 m個(gè)變量 ? 原問題有 n個(gè)變量，對偶問題有 n個(gè)約束條件 ? 原問題的價(jià)值系數(shù)對應(yīng)對偶問題的右端項(xiàng) ? 原問題的右端項(xiàng)對應(yīng)對偶問題的價(jià)值系數(shù) ? 原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣 ? 原問題的約束條件與對偶問題方向相反 ? 原問題與對偶問題優(yōu)化方向相反 OR1 55 對偶規(guī)則 . 原問題 對偶問題 目標(biāo)函數(shù) max min 目標(biāo)函數(shù) 約束條件 ≤ ≥ = ≥ 變量 ≤ 無約束 ≥ 變量符號(hào) ≤ 無約束 ≥ ≤ 約束條件 = OR1 56 對偶規(guī)則簡捷記法 ?原問題標(biāo)準(zhǔn)則對偶問題標(biāo)準(zhǔn) ?原問題不標(biāo)準(zhǔn)則對偶問題不標(biāo)準(zhǔn) ?例題 2 max ω=7y1+4y22y3 minZ=3x1+2x26x3+x5 2y1+ y2 y3 ≤3 2x1+x24x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 x4 ≤ 4 4y1+ 2y2 ≤6 x1+3x2 x4+ x5 =2 y1 y2 y3 ≥ 0 x1， x2， x3 ≥0。x5無限制 y1 ≥ 0y2 ≤ 0y3 無約束 OR1 57 ? 對稱性：對偶問題的對偶問題是原問題 ? 弱對偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對偶問題任意可行解的目標(biāo)函數(shù)值 (鞍型圖 ) ? 無界性：原問題無界，對偶問題無可行解 ? 對偶定理：若一個(gè)問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。在 Y確定的前提下，每增加一個(gè)單位的 i種資源，對目標(biāo)函數(shù)的貢獻(xiàn)。 y3=… ? 影子價(jià)格所含有的信息： 資源緊缺狀況 確定資源轉(zhuǎn)讓基價(jià) 參見： P40 取得緊缺資源的代價(jià) OR1 59 ? 為什么進(jìn)行靈敏度分析？ ? 靈敏度分析的兩把尺子： ?σj =CjCBB1pj≤ 0； ? xB= B1b ≥0 價(jià)值系數(shù)的靈敏度分析 Cj變化到什么程度可以保持最優(yōu)基不變？用 ? （參看 P96） 例題 4： ≤ C2 ≤ ； 36 ≤ C1 ≤ 96 OR1 60 靈敏度分析 ? 右端項(xiàng)的靈敏度分析： bi變化到什么程度可以保持最優(yōu)基不變？用尺度 ? xB= B1b ≥0 例題 5： 1 360 B1b= 0 200 ≥0 0 b3 b3的變化范圍： ≤ b3 ≤ 400 OR1 61 其它形式的靈敏度分析 新產(chǎn)品的分析： 在資源結(jié)構(gòu)沒有變化的條件下，是否生產(chǎn)這種新 產(chǎn)品，就看它的競爭力如何。 OR1 62 ? 例題 7 參見 P102 OR1 63 習(xí)題課： ? P78—— （ 1）唯一最優(yōu)解： H3 ≤ 0 ， H5≤ 0 ， H1 ≥0 （ 2）無窮多最優(yōu)解： H3=0， H1 ≥0， H5? 0 ， H20 或 H5=0， H1 ≥0， H3 ? 0， H40 （ 3）無界解： H5≥0， H4 ? 0 ， H1 ≥0， H3? 0 （ 4）退化 最優(yōu) 解： H1=0 ， H3? 0 ， H5? 0 （ 5）非最優(yōu)解， X1進(jìn)基， X2出基： H1 ≥0， H30 ， H20， 5 H2 H1 7 OR1 64 習(xí)題課： ? P79—— ? 對 錯(cuò)，可能有最優(yōu)解 對 ? 對 錯(cuò) 錯(cuò) 錯(cuò)在“可行” ? 對 錯(cuò) OR1 65 習(xí)題課： ? P81—— ? 設(shè)白天電視廣告 X1個(gè)，黃金時(shí)間電視廣告 X2個(gè)，廣播廣告 X3個(gè)，雜志廣告 X4個(gè) ? maxZ=40X1+90X2+50X3+2X4 8X1+15X2+6X3+3X4 ≤16 30X1+40X2+20X3+X4 ≥200 8X1+15X2 ≤10 X1 ≥3 X2 ≥2 X3 ≥5 X3 ≤10 X4 ≥5 X4 ≤10 X j≥0 j= 4 OR1 66 習(xí)題課： ? P81—— ? 設(shè) A產(chǎn)品生產(chǎn) X1單位， B產(chǎn)品生產(chǎn) X2單位，C產(chǎn)品銷毀 X3單位 ? maxZ=5X1+10X2+3（ 2X2X3） 1X3 ? 2X1+3X2 ≤200 ? 3X1+4X2 ≤240 ? 2X2X3 ≤10 X X X3 ≥0 OR1 67 習(xí)題課： ? P107—— ? 對，根據(jù)若對偶性 ? 對，同上 ? 對，同上 ? 對，因?yàn)橛白觾r(jià)格是每增加一個(gè)單位的某種資源，對目標(biāo)函數(shù)的貢獻(xiàn)程度 ? 對，根據(jù)強(qiáng)對偶定理 OR1 68 習(xí)題課 ? P107—— 注：目標(biāo)函數(shù)為最大化 ? 這是線性規(guī)劃的逆運(yùn)算 ? 對偶問題最優(yōu)解 ： ? Y1= Y2= Y3=0、 Y4= Y5=0 OR1 69 習(xí)題課 ? P109—— ? 原問題的最優(yōu)解： X1=6， X5=10，其余為零