【文章內(nèi)容簡介】 , w6） =（ 1, 5, 7, 0, 0, 0） max y=35 初始解原始、對偶都不可行的問題 0xxx2xx2x5xx3x2x2x2x3zm i n321321321321321??????????????0xxxxxx2xxx2x5xxx3x2x2x2x3zm i n654321632153214321321?????????????????0xxxxxx2xxx2x25xxx3x2x2x2x3zm i n654321632153214321321???????????????????z x1x2x3x4x5x6RH Sz 1 3 2 2 0 0 0 0x40 1 1 1 1 0 0 4x50 2 3 1 0 1 0 5x60 2 2 1 0 0 1 2解法 1：先解決原始可行性 z x1x2x3x4x5x6RH Sz 1 7 0 0 0 2 4 18x40 1 0 0 1 1 2 5x20 0 1 0 0 1 1 7x30 2 0 1 0 2 3 16z x1x2x3x4x5x6R HSz 1 7 2 0 0 0 2 4x40 1 1 0 1 0 1 2x50 0 1 0 0 1 7x30 2 2 1 0 1 2z x1x2x3x4x5x6R HSz 1 0 0 0 7 5 1 0 17x10 1 0 0 1 1 2 5x20 0 1 0 0 1 1 7x30 0 0 1 2 0 1 6在得到原始可行解時同時得到對偶可行解，已獲得最優(yōu)解： （ x1, x2, x3, x4, x5, x6） =（ 5, 7, 6, 0, 0, 0） min z=17 對偶問題的最優(yōu)解為： （ w1, w2, w3, w4, w5, w6） =（ 7, 5, 10, 0, 0, 0） max y=17 z x1x2x3x4x5x6RHSz 1 3 2 2 0 0 0 0x40 1 1 1 1 0 0 4x50 2 3 1 0 1 0 5x60 2 2 1 0 0 1 2z x1x2x3x4x5x6R H Sz 1 5 0 0 2 0 0 8x30 1 1 1 1 0 0 4x50 1 2 0 1 1 0 9x60 1 1 0 1 0 1 2解法 2：先解決對偶可行性 已得到對偶可行解，再用對偶單純形法求解 z x1x2x3x4x5x6RHSz 1 0 0 0 7 5 10 17x30 0 0 1 2 0 1 6x20 0 1 0 0 1 1 7x10 1 0 0 1 1 2 5z x1x2x3x4x5x6R H Sz 1 5 0 0 2 0 0 8x30 1/2 0 1 3/2 1/2 0 17/ 2x20 1/2 1 0 1/2 1/2 0 9/2x60 1/2 0 0 1/2 1/2 1 5/2得到原始可行解，已獲得最優(yōu)解： （ x1, x2, x3, x4, x5, x6） =（ 5, 7, 6, 0, 0, 0） min z=17 對偶問題的最優(yōu)解為： （ w1, w2, w3, w4, w5, w6） =（ 7, 5, 10, 0, 0, 0） max y=17 五、對偶的經(jīng)濟(jì)解釋 原始問題是利潤最大化的生產(chǎn)計劃問題 0xxxxxxbxxaxaxabxxaxaxaxcxcxczm a xmn2n1nn21mmnnmn22m11m22nnn222212111nnn1212111222211??????????????????????????????????單位產(chǎn)品的利潤（ 元 /件） 產(chǎn)品產(chǎn)量（件） 總利潤（元） 資源限量（噸） 單位產(chǎn)品消耗的資源（噸 /件） 剩余的資源（ 噸） 消耗的資源（噸） 對偶問題 0cwwawawacwwawawawbwbwbym i nnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211??????????????????????????????????資源限量（噸） 資源價格（元 /噸） 總利潤（元） 對偶問題是資源定價問題，對偶問題的最優(yōu)解 w w ...、wm稱為 m種資源的 影子價格（ Shadow Price） 原始和對偶問題都取得最優(yōu)解時， 最大利潤 max z=min y 資源影子價格的性質(zhì) ■ 影子價格越大，說明這種資源越是相對緊缺 ■ 影子價格越小，說明這種資源相對不緊缺 ■ 如果最優(yōu)生產(chǎn)計劃下某種資源有剩余，這種資源的影子價格一定等于 0 種資源的邊際利潤第種資源的增量第最大利潤的增量 iibzwiooi ?????mmii2211 wbwbwbwbyz ??????? ??mmiii2211 wbw)bb(wbwbzz ?????????? ??ii wbz ???w1 w2 wm 產(chǎn)品的機(jī)會成本 機(jī)會成本 表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤 mmjiij2j21j1 wawawawa ????? ??增加單位資源可以增加的利潤 減少一件產(chǎn)品可以節(jié)省的資源 0xxxxbxaxaxaxabxaxaxaxabxaxaxaxas .t .xcxcxcxczm axnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211??????????????????????????????????機(jī)會成本 利潤 差額成本 0cwwawawacwwawawawbwbwbym i nnm2m1mm21nnmmmn2n21n122mm2m22211211mm1m221111mm2211??????????????????????????????????產(chǎn)品的差額成本（ Reduced Cost） 差額成本 =機(jī)會成本 利潤 jjTjmjmj22j11jm caWc)awawaw(w ???????? ?互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋 ??????????????????????????0x0w0w0x0wx0w0x0x0w0xwjjmjmjjmjiininiini在利潤最大化的生產(chǎn)計劃中 （ 1）邊際利潤大于 0的資源沒有剩余 （ 2）有剩余的資源邊際利潤等于 0 （ 3）安排生產(chǎn)的產(chǎn)品機(jī)會成本等于利潤 （ 4）機(jī)會成本大于利潤的產(chǎn)品不安排生產(chǎn) 第四章 運(yùn)輸問題 運(yùn)輸問題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表 初始基礎(chǔ)可行解 西北角法、最小元素法 非基變量的檢驗數(shù) 閉回路法、對偶變量法 確定進(jìn)基變量，調(diào)整運(yùn)量，確定離基 變量 2 3 2 1 3 4 1 運(yùn)輸問題網(wǎng)絡(luò)圖 s2=27 s3=19 d1=22 d2=13 d3=12 d4=13 s1=14 供應(yīng)量 供應(yīng)地 運(yùn)價 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 運(yùn)輸問題線性規(guī)劃模型 0xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs .t .x6x10x9x5x7x2x4x8x3x5x7x6zm i n343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211?????????????????????????????????????供應(yīng)地約束 需求地約束 運(yùn)輸問題的表格表示 1 2 3 46 7 5 31x11x12x13x14148 4 2 72x21x22x23x24275 9 10 63x31x32x33x341922 13 12 13初始基礎(chǔ)可行解 — 西北角法 1 2 3 4 6 7 5 3 1 14 8 4 2 7 2 27 5 9 10 6 3 19 22 13 12 13 8 13 13 14 6 6 1 2 3 46 7 5 31 148 4 2 721227 155 9 10 63 1922 13 12 130初始基礎(chǔ)可行解 — 最小元素法（ 1） 最小元素法（ 2） 1 2 3 46 7 5 311314 18 4 2 721227 155 9 10 63 1922 13 12 130 0最小元素法（ 3） 1 2 3 46 7 5 311314 18 4 2 7213 1227 25 9 10 63 1922 13 12 130 0 0最小元素法（ 4） 1 2 3 46 7 5 311314 18 4 2 7213 1227 25 9 10 631919 022 13 12 133 0 0 0最小元素法（ 5） 1 2 3 46 7 5 311 1314 08 4 2 7213 1227 25 9 10 631919 022 13 12 132 0 0 0最小元素法（ 6） 1 2 3 46 7 5 311 1314 08 4 2 722 13 1227 05 9 10 631919 022 13 12 130 0 0 01 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 非基變量 xij的檢驗數(shù) zijcij— 閉回路法 (1) z12c12=(c11c21+c22)c12=68+47=5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 閉回路法 (2) z13c13=(c11c21+c23)c13=68+25=5 5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 閉回路法 (3) z14c14=(c11c21+ c21 c23 + c33 c14)c13=(68+210+6)3=7 7 5 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 閉回路法 (4) z24c24=(c23c33+ c34)c24=(210+6)7=9 9 5 7 1 2 3 46 7 5 3114148 4 2 728 13 6275 9 10 636131922 13 12 135 閉回路法 (5) z31