運(yùn)籌學(xué)整數(shù)規(guī)劃習(xí)題

1、第四章一一 1 第四章整數(shù)規(guī)劃 4.1某工廠生產(chǎn)甲、乙兩種設(shè)備，已知生產(chǎn)這兩種設(shè)備需要消耗材料 A、材料B,有關(guān)數(shù)據(jù)如 下，問這兩種設(shè)備各生產(chǎn)多少使工廠利潤最大？（只建模不求解） 表 4 1 設(shè)備 材料 甲 乙 資源限量 材料 A (kg) 2 3 14 材料 B (kg) 1 0.5 4.5 利潤（元/件） 3 2 max 3x1 2x2 2x1 3x2 14 x1 0.5x2 4.5 xx 2 0 xx 2為整 割平面法求解。（下表為最優(yōu)表） 5 7 9 0 0 b CB XB X1 X2 X3 X4 9 X2 0 1 7/22 1/22 7/2 7 X1 1 0 1/22 3/22 9/

2、2 Cj z 0 0 28/11 15/11 解: 線性規(guī)劃的最優(yōu)解為: x1 9/ 2, x2 7/2,x3 x4 O,maxz 63 由最終表中得： 7 1 x3 x4 22 3 22 4 將系數(shù)和常數(shù)項分解成整數(shù)和非負(fù)真分式之和，上式化為; 移項后得:解：設(shè)生產(chǎn)甲、乙這兩種設(shè)備的數(shù)量分別為 建立模型如下： XI、X2,由于是設(shè)備臺數(shù)，則其變量都要求為整數(shù), 4.2 max z 7x1 9x2 X1 3x2 6 s.t 7x1 X2 35 X1，X2 0 且為整 x2 7 22 22 X4 第四章一一 2 在的最優(yōu)單純形表中加上此約束，用對偶單純形法求解: Cj 7 9 0 0 0 0 b

3、 CB XB X1 X2 X3 X4 X5 X6 9 X2 0 1 0 0 1 0 3 7 X1 1 0 0 1/7 1/7 0 32/7 0 X3 0 0 1 1/7 22/7 0 11/7 0 X6 0 0 0 * 1/7 6/7 1 4/7 Cj z 0 0 0 1 8 0 9 X2 0 1 0 0 1 0 3 7 X1 1 0 0 0 1 1 4 0 X3 0 0 1 0 4 1 1 0 X4 0 0 0 1 6 7 4 Cj z 0 0 0 0 2 7 則最優(yōu)解為x； 4, x； 3，最優(yōu)目標(biāo)函數(shù)值為 z*=55。 max z= 4x1 + 3x2+ 2x3即: 7 1 1 22X3

4、 22x4 2 22 X3 1 22 X4 只要把增加的約束條件加到 B問題的最優(yōu)單純形表中。 Cj 7 9 0 0 0 b CB XB x1 X2 X3 X4 X5 9 X2 0 1 7/22 1/22 0 7/2 7 X1 1 0 1/22 3/22 0 9/2 0 x5 0 0 * 7/22 1/22 1 1/2 Cj z 0 0 28/11 15/11 0 Cj 7 9 0 0 0 b CB XB X1 X2 X3 X4 X5 9 X2 0 1 0 0 1 3 7 X1 1 0 0 1/7 1/7 32/7 0 X3 0 0 1 1/7 22/7 11/7 a -zj 0 0 0 1

5、8 X1 1 X4 32 7 將系數(shù)和常數(shù)項分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和: 得到新的約束條件: 1 6 4 X1 -X4 X5 X5 4 7 7 7 1 6 4 X4 X5 7 7 7 1 6 4 X4 XX6 7 7 7 4.3 表 4 3 第四章一一 3 2x1 5x2 3x3 4 4x1 x2 3x3 3 s.t X2 X3 1 x1, x2, x3 0 或 1 隱枚舉法 解：(1 )先用試探的方法找出一個初始可行解，如 X1 = X2= 0, X3= 1。滿足約束條件，選其作為 初始可行解，目標(biāo)函數(shù) zo= 2。 (2)附加過濾條件 以目標(biāo)函數(shù)z z0作為過濾約束： 4x1 3x2 2x

6、3 2 原模型變?yōu)椋?max z = 4x1 + 3x2 + 2x3 2x1 5X2 3x3 4 4x1 X2 3x3 3 X2 X3 1 4x1 3x2 2x3 2 x1, x2, x3 0 或 1 求解過程如表所示。 占 八、 過濾條件 約束 z 值 4x1 + 3x2+ 2x3 2 (0, 0, 0) T X (0, 0,1) T n V V V V 2 (0, 1, 0) T V V X (0, 1, 1) T V V V V 5 4x1 + 3x2+ 2x3 5 (1, 0, 0) T X (1, 0 , 1) T V X (1, 1 , 0) T 1 V V V V 7 4x1 +

7、 3x2+ 2x3 7 (1, 1 , 1) T V V V V 9 所以該0 1規(guī)劃最優(yōu)解為x, x2 x3 1,z 9。 4.4 某公司擬在市東、西、南三區(qū)中建立門市部，有 7個點(diǎn)Ai (i = 1, 2，7)可供選擇， 要求滿足以下條件： (1) 在東區(qū)，在 A1, A2, A3三個點(diǎn)中至多選兩個； (2) 在西區(qū)，A4, A5兩個點(diǎn)中至少選一個； (3) 在南區(qū)，A6, A7兩個點(diǎn)為互斥點(diǎn)。 (4) 選A2點(diǎn)必選A5點(diǎn)。 若Ai點(diǎn)投資為bi萬元，每年可獲利潤為 Ci萬元，投資總額為 B萬元，試建立利潤最大化的 0- 1規(guī)劃模型。 解：設(shè)決策變量為 Xi 1, 0, 當(dāng) A 點(diǎn)被選用 當(dāng)

8、A點(diǎn)未被選用 i 1,2, ,7 第四章一一 4 建立0- 1規(guī)劃模型如下:第四章一一 5 7 maxz c1X1 C2X2 C7X7 cix 7 i 1 bi Xi B X1 X2 X3 2 S.t X4 X5 1 X6 X7 1 X2 X5 0 Xi 0, 或 1,i 1,2, ,7 4.5某城市消防隊布點(diǎn)問題。該城市共有 6個區(qū)，每個區(qū)都可以建消防站，市政府希望設(shè)置的 消防站最少，但必須滿足在城市任何地區(qū)發(fā)生火警時，消防車要在 15分鐘內(nèi)趕到現(xiàn)場。據(jù)實地測 定，各區(qū)之間消防車行駛的時間見表 4 9,請幫助該市制定一個布點(diǎn)最少的計劃。 表 4 9消防車在各區(qū)間行駛時間表 單位：min 地區(qū)

9、 1 地區(qū) 2 地區(qū) 3 地區(qū) 4 地區(qū) 5 地區(qū) 6 地區(qū) 1 0 10 16 28 27 20 地區(qū) 2 10 0 24 32 17 10 地區(qū) 3 16 24 0 12 27 21 地區(qū) 4 28 32 12 0 15 25 地區(qū) 5 27 17 27 15 0 14 地區(qū) 6 20 10 21 25 14 0 解：引入0 1變量Xi作決策變量，令 目標(biāo)函數(shù)為 min Z= X1+ X2 + X3+ X4 + X5 + X6 本問題的約束方程是要保證每個地區(qū)都有一個消防站在 可知，在地區(qū)1及地區(qū)2內(nèi)設(shè)消防站都能達(dá)到此要求，即 X1 + X2 1 因此本問題的數(shù)學(xué)模型為: min Z= X

10、1+ X2 + X3+ X4 + X5 + X6 廣 X1 + X2 1 X1 + X2 + X6 1 X3 + X4 1 S.t 1 X4 + X5 + X6 1 X2 + X5 + X6 1 .Xi = 1 或 0 （i = 1，6） 4.7 一個登山隊員，他需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相器材、通信 器材等，每種物品的重量及重要性系數(shù)見表 4- 10所示，能攜帶的最大重量為 25 kg，試選擇該隊員 所應(yīng)攜帶的物品。 表 4 10 序號 1 2 3 4 5 6 7 物品 食品 氧氣 冰鎬 繩索 帳篷 照相器材 通信設(shè)備 重量 kg 5 5 2 5 10 2 3 1, X 0, 表示在地區(qū) i 設(shè)消防站 表示在地區(qū) i 不設(shè)消防站 i 1,2, ,6 15分鐘行程內(nèi)。如地區(qū) 1,由表4 9 第四章一一 6 重要性系數(shù) 20 15 16 14 8 14 9 第四章 7 解：引入 0 1 變量 xi