LP問題的對偶問題習(xí)題集

1、習(xí)題3.1 試建立下述 LP 問題的對偶關(guān)系表，并寫出其對偶問題： （ 1 ）max z=4x1+3x2+6x3602x12x23x340s.t.2x12x2x36x10,x20,x30（ 2 ）min w=60x 1+10x 2+20x 33x1x2x3 2x1x2 x3 1s.t.x12x2x3 1x10,x20,x30（ 3 ）min w=5x 1-3x22x1x24x32x1x2 2x3 1s.t.3x1x2x3 3x10,x20,x30（ 4 ）max z=4x 1+3x 2 +6x3x12x24x310s.t.2x15x23x315x10,x20,x303.2 試寫出下述 LP 問

2、題的對偶問題（ 1 ）1.1（1）題（ 2 ）1.5 題 （ 5 ）min w=2x 1+2x 2+4x 32x13x25x323x1x27x33s.t.x14x26x35x20,x303x1x2x3（6） min w=2x 1+3x2+6x3+x43）2.4（5）題 （4）2.4 （7）題4x24x37x4212x17x23x38x418x12x25x33x4x10,x20,x4 03.3 試證明LP問題（儀）是（D2）的對偶，（P2 ）是（D2 ）的對偶。3.4 試寫出下述 LP 問題的對偶問題：（ 1 ） min w=C TXAX bX a（ 0）mn(2) min z=cij xiji

3、 1 j 1nxij ai ,i 1,2,.mj1ms.t.xij bj , j 1,2,.ni1xij 0n(3) max z=cj xjj1naij xj bi ,i 1,2,., rj1ns.t.aij xj bi,i r 1,r 2,., mj1xj 0, j 1,2,., s( n)3.5 已知 LP 問題： min z= 5x 1+6x2+3x 35x15x23x350x1x2 x3207x16x29x330x1x2 x372x14x215x3106x15x245x210x320x10,x20,x30試通過求解其對偶問題來確定該 LP 問題的最優(yōu)解。3.6 已知 LP 問題： ma

4、x z= x1+2x2x1 x2 2s.t. x1 x2 1x1 0,x2 0（1）試證明它與其對偶問題均無可行解。（2）試構(gòu)造一個 LP 問題，使其本身及其對偶問題均無可行解。3.7已知（I）（U）兩個LP問題：n（I） max z1= cjxjj1aij xjbi,i 1,2,., ms.t. j 1 xj 0, j 1,2,., nn(D) max Z2=CjXjj1naij xj bi ki,i 1,2,., mj1xj 0, j 1,2,., n其中 aij ， bi ， ki 均為已知常數(shù)。設(shè)Z-1 , Z2分別為(I) , (n )的最優(yōu)值，yi (i=1,2,m)為(1)的對偶

5、問題的最優(yōu)解，求證:mZ2 Z1ki yii13.8 不用單純形法，利用對偶性質(zhì)和其它簡便方法求解下述 LP 問題:(1) max w=4x 1+3x 2+6x 33x1x23x330s.t.2x12x23x340x10,x20,x30(2) max Z=x1-x 2 +x3x1x34x1x22x33x1 0,x2 0,x3 03.9 已知 LP 問題: max Z= 6x 1+8x 25x12x220s.t. x12x210x10,x20(1) 寫出它的對偶問題。(2) 用圖解發(fā)求解原始、對偶問題。識別兩個問題的所有極點解。(3) 用單純形法求解原始問題。在每個單純形表中，識別此問題的基本可

6、行解及對偶問題的互補基本解。指 出它們相應(yīng)于圖解法中哪個極點。(4) 按表 3-8 的格式，列出該問題的全部互補基本解。(5) 用對偶單純形法求解對偶問題，并將結(jié)果與(3)中結(jié)果進行對比。(6) 該問題是否滿足互補松弛性？為什么？3.10 用對偶單純形法求解下述 LP 問題:(1)min Z= x 1+x2506Xi2x2Xi3x1X2XiOX(2) min z= 3x 1+2X2+X3XiX2X3XiX3XiX2X3O,x20,X302.4（4）題3.11某廠擬生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要在A，B兩種設(shè)備上加工，有關(guān)數(shù)據(jù)如下表所示:產(chǎn)品設(shè)備單耗（臺時/件）設(shè)備有效臺時甲乙丙A121400B212500產(chǎn)值（千元/件）321(1)(2)如何充分發(fā)揮設(shè)備能力，使產(chǎn)品總產(chǎn)值最大？若為了提高產(chǎn)量，以每臺時 350元租金租用外廠 A設(shè)備，問是否合算?3.i2用對偶單純形法求解下述LP問題:max z= 3xi-2x2-X3XiX2X34X22X38X2X32Xi,X2, X30(i)(2) max z= 2x i-x2+2x3XiX2X32xiX32x?X3Xi,X2,X3(3) m