• 運籌學1至6章習題參考答案 聯系客服

    運籌學(第3版) 習題答案 45

    ?10?6x1,若x1?0?15?10x2,若x2?0 f(x1)??,g(x2)??若x1?0若x2?0?0,?0,滿足約束條件

    (1)x1≥8或x2≥6 (2)|x1-x2|=0,4或8

    (3)x1+2x2≥20、2x1+x2≥20及x1+x2≥20 三個約束中至少一個滿足 (4)x1≥0,x2≥0

    將此問題歸結為混合整數規劃的數學模型。

    minZ?10y1?6x1?15y2?10x2?x1?y1M;x2?y2M?x?8?yM3?1?x2?6?(1?y3)M??x1?x2?0y4?4y5?4y6?8y7?8y8【解】??y4?y5?y6?y7?y8?1??x1?2x2?20?y9M?2x1?x2?20?y10M??x1?x2?20?y11M?y?y?y?21011?911??x1?0,x2?0;yj?0或1,j?1,2,?,3.8用分枝定界法求解下列IP問題

    條件(1)條件(2)條件(3)

    條件(4)maxZ?x1?4x2minZ?x1?2x2?3x1?2x2?9?3x1?x2?10(1)? (2)?

    2x?4x?85x?6x?30?1?122?x,x?0且為整數?x,x?0且為整數?12?12【解】(1)X=(4,0),Z=4 (雙擊打開PPT)

    運籌學(第3版) 習題答案 46

    習題3.8(1)maxZ?x1?4x2x24.53x1?2x2?9?3x1?2x2?9LP0:?2x?4x?8?12?x,x?0?122x1?4x2?82松弛問題LP0的最優解X=(2.5,0.75),Z0=5.5o34x1 (2) X(1)=(2,4),X(2)=(0,5);Z=10 (雙擊打開PPT)

    習題3.8(2)x210minZ?x1?2x23x1?x2?10LP0:?3x1?x2?10??5x1?6x2?30?x,x?0?125x1?6x2?305松弛問題LP0的最優解X=(2.31, 3.08),Z0=8.46o3.336x1 3.9用割平面法求解下列IP問題

    maxZ?2x1?x2(1)?minZ?2x1?3x2?4x1?2x2?14?x1?2x2?9 (2)?

    ?2x1?x2?10?2x1?x2?10?x,x?0且為整數?x,x?0且為整數?12?12【解】(1) 加入松弛變量x3、x4,單純形表如下:

    運籌學(第3版) 習題答案 47

    1 0 0 CB XB X2 X3 X4 0 X3 2 1 0 0 X4 1 0 1 C(j)-Z(j) 1 0 0 2 X1 1/2 1/4 0 0 X4 0 -1/2 1 C(j)-Z(j) 0 -1/2 0 X1行為來源行,割平面方程為:s1?2x2?x3??2,插入到最優表得到

    C(j) CB XB 2 X1 0 X4 0 S1 C(j)-Z(j) 2 X1 0 X4 1 X2 C(j)-Z(j) 2 S1 0 X4 1 X2 C(j)-Z(j) 2 X1 1 0 0 0 1 0 0 0 4 0 2 0 1 X2 1/2 0 [-2] 0 0 0 1 0 0 0 1 0 0 X3 1/4 -1/2 -1 -1/2 0 -1/2 1/2 -1/2 0 -1/2 1/2 -1/2 0 X4 0 1 0 0 0 1 0 0 0 1 0 0 0 S1 0 0 1 0 [1/4] 0 -1/2 0 1 0 0 0 C(j) 2 X1 4 2 2 1 0 0 b 14 10 0 7/2 3 -7 b 7/2 3 -2 -7 3 3 1 -7 12 3 7 -7 從表中看出,有兩個最優解:X(1)=(3,1),X(2)=(0,7);Z=7 (2) 加入松弛變量x3、x4,單純形表如下: 3 0 0 b CB XB X2 X3 X4 0 X3 -2 1 0 -9 0 X4 -1 0 1 -10 C(j)-Z(j) 3 0 0 0 0 X3 [-3/2] 1 -1/2 -4 2 X1 1/2 0 -1/2 5 C(j)-Z(j) 2 0 1 -10 3 X2 1 -2/3 1/3 8/3 2 X1 0 1/3 -2/3 11/3 C(j)-Z(j) 0 4/3 1/3 -46/3 以X1行為來源行,割平面方程為:s2?x3?x4??2,插入到最優表得到

    C(j) CB 3 2 0 XB X2 X1 S2 2 X1 0 1 0 3 X2 1 0 0 0 X3 -2/3 1/3 -1 0 X4 1/3 -2/3 [-1] 0 S2 0 0 1 b 8/3 11/3 -2 C(j) 2 X1 -1 [-2] 2 0 1 0 0 1 0 運籌學(第3版) 習題答案 48

    C(j)-Z(j) 3 X2 2 X1 0 X4 C(j)-Z(j) 0 0 1 0 0 0 1 0 0 0 4/3 -1 1 1 1 1/3 0 0 1 0 0 1/3 -2/3 -1 1/3 -46/3 2 5 2 -16 最優解X=(5,2);最優值Z=16

    3.10用隱枚舉法求解下列BIP問題

    ??x1?x2?4x3?2x4?5?5x1?2x2?x3?6?(1)? (2)?3x1?x2?2x3?2x4?4??4x1?2x2?3x3?8?x1?3x2?2x3?x4?9?x?0或1,j?1,2,3?j?xj?0或1,j?1,2,3,4?【解】(1)X=(1,0,1),Z=8 (2)X=(1,0,1,0),Z=9

    3.11思考與簡答題 (1)“整數規劃的最優解是求其松弛問題最優解后取整得到”為什么不對。 (2)解釋“分支”與“定界”的含義。 (3)簡述分支定界法的基本步驟。

    (4)高莫雷方程是怎樣得到的,在割平面法中起到什么作用。

    (5)割平面法計算過程中,什么時候可以去掉單純形表中一行和一列。

    maxZ?4x1?3x2+4x3minZ?4x1?2x2?5x3?3x4

    返回頂部