運籌學(xué)線性規(guī)劃的對偶問題(完整版)
【正文】 = = 0 , . 0 . max max X b IX AX t s X b AX t s CX Z CX Z s ? 理論上 11 ?? ?? BCNBCC BBN 與檢驗數(shù)為解時線性規(guī)劃問題有最優(yōu)并且當(dāng) 00 11 ???? ?? BCNBCC BBN，稱為單純形乘子令 1?= BCY B因為 Y的上界為無限大 ,所以Ｙ只能有最小值。39。39。 對偶問題 :Y在 b和 A的左邊（左右對換） 對偶問題的基本性質(zhì)和基本定理 1. 對稱性定理：對偶問題的對偶是原問題 證明： 設(shè)原問題為 ?????=0..m a xXbAXtsCXZ ?????=0..m i nYCYAtsYb? ????????=?0)(..)()m a x (YCAYtsbY? ????????=?0..)m i n (39。 由于 z=C X（ 0） = CBXB（ 0） = CBB1b= Y（ 0） b（目標(biāo)值相等） 由最優(yōu)性定理可知 Y（ 0） 為對偶問題的最優(yōu)解。由此原問題也無最優(yōu)解。 例： A、 B、 C三廠生產(chǎn)車床、刨床，若只生產(chǎn)一種產(chǎn)品，效率表如右圖。 解： A、 B、 C三廠編號為 1， 2， 3 車、刨床的編號為 1， 2 效率 車床 刨床 A B C 1 4 5 2 2 3 ijx 為第 i廠生產(chǎn)第 j種產(chǎn)品的時間比例 則： 11 21 3152x x x??12 22 324 2 3xxx??車床總數(shù)： 刨床總數(shù)： 1 1 2 1 3 11 2 2 2 3 252 14 2 3 2x x xxxx?? =??11 21 31 12 22 322 10 4 4 2 3 0x x x x x x? ? ? ? ? =展開得： )2,1,3,2,1(0111323122211211==???????jixxxxxxxij11 21 31 12 22 3221 2221 2231 3211 21 31 12 22 32m a x 5 2 4 2 311.12 10 4 4 2 3 00( 1 , 2 , 3 , 1 , 2)ijx x x x x xxxxxstxxx x x x x xx i j? ? ? ? ????????????? ? ? ? ? ? =?? = =總套數(shù)： 解得： 11 1221 2231 320 , 13 / 4 , 1 / 40 , 1xxxxxx??????======生產(chǎn)車床： 3/4 5=15/4（臺） 生產(chǎn)刨床：4 1+1/4 2+3 1=15/2（臺） 322212312111 32425 xxxxxx ?????A廠只生產(chǎn)刨床， B廠 3/4生產(chǎn)車床， 1/4生產(chǎn)刨床 C廠只生產(chǎn)刨床 此計劃能否執(zhí)行要看單獨生產(chǎn)獲利增加情況 A廠單獨生產(chǎn)： 11 1211121142xxxx?=??? =??解得 1 1 1 221,33xx==A廠生產(chǎn)能力： 2/3 1=2/3臺車床 1/3 4=4/3臺刨床 B廠單獨生產(chǎn)： 21 22212215 122xxxx?=??? =??2 1 2 215,66xx==B廠生產(chǎn)能力： 1/6 5=5/6臺車床 5/6 2=5/3臺刨床 解得： C廠單獨生產(chǎn)： 31 32313212 132xxxx?=???=??解得： C廠生產(chǎn)能力： 3/7 2=6/7臺車床 4/7 3=12/7臺刨床 3 1 3 234,77xx==A、 B、 C各單獨生產(chǎn)共可生產(chǎn)： 5/6+2/3+6/7=33/14 套 單獨生產(chǎn)比合作少生產(chǎn)： 15/433/14=39/28套 合作得以進行，應(yīng)如何分配成品產(chǎn)量，使各廠利益合理？ 利
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1