【正文】 多只能建一家工廠；若選 i地建廠，生產(chǎn)能力為 ai噸 /月，其運(yùn)營固定費(fèi)用為 F元 /月；已知址 i至 j區(qū)域市場的運(yùn)價為 cij元 /噸。如何選址和安排調(diào)運(yùn)，可使總費(fèi)用最??？ iF解：選址建廠與否是個 01型決策變量， 假設(shè) yi =1，選擇第 i 址建廠， yi=0，不選擇第 i 址建廠； 計劃從 i 址至區(qū)域市場 j 的運(yùn)輸 運(yùn)量 xij為實(shí)數(shù)型決策變量。 1 1 111m in1 , 2 , ...,1 , 2 , ..., .00 , 1m m ni i ij iji i jnij i ijmij jiijiZ y F c xx y a i mx b j nxy? ? ????????????????? ?????? ? ???76 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 一、舍入化整法 ?為了滿足整數(shù)解的要求，自然想到“舍入”或“截尾”處理，以得到與最優(yōu)解相近的整數(shù)解。 ?這樣做除少數(shù)情況外，一般不可行，因?yàn)榛蟮慕庥锌赡艹隽丝尚杏?，成為非可行解；或者雖是可行解，卻不是最優(yōu)解。 不考慮整數(shù)約束則是一個 LP問題 ,稱為原整數(shù)規(guī)劃的松弛問題 對于例 1的數(shù)學(xué)模型，不考慮整數(shù)約束的最優(yōu)解： x1 *=28/9， x2 * =25/9， Z * =293/9 舍入化整 x1 =3， x2 =3， Z =33，不滿足約束條件 5x1 +7 x2 ≤35，非可行解； x1 =3， x2 =2， Z =28，滿足約束條件，是可行解，但不是最優(yōu)解； x1 =4， x2 =1， Z =29，滿足約束條件，才是最優(yōu)解。 77 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 二、窮舉整數(shù)法 對于決策變量少，可行的整數(shù)解又較少時，這種窮舉法有時是可行的，并且也是有效的。 但對于大型的整數(shù)規(guī)劃問題，可行的整數(shù)解數(shù)量很多，用窮舉法求解是不可能的。 例如，指派問題 。 5x1 +7 x2 =35 2x1 + x2 =9 ? (3,3) ? ? ? ? ? ? ? ? ? ? )972,913(78 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 三、分支定界法 ? 不考慮整數(shù)限制 ， 先求出相應(yīng)線性規(guī)劃 的最優(yōu)解 ， ? 若求得的最優(yōu)解符合整數(shù)要求 ， 則是原 IP的最優(yōu)解； ? 若不滿足整數(shù)條件 ， 則任選一個不滿足整數(shù)條件的變量來構(gòu)造新的約束 ， 在原可行域中剔除部分非整數(shù)解 。 ? 依次在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解 ，直到獲得原整數(shù)規(guī)劃的最優(yōu)解 。 ? 定界的含義： ? IP是在相應(yīng)的 LP基礎(chǔ)上增加整數(shù)約束 ? IP的最優(yōu)解不會優(yōu)于相應(yīng) LP的最優(yōu)解 ? 對 MaxZ，相應(yīng) LP的 Z*是原 IP的上界 79 OR:SM 第二節(jié) 整數(shù)規(guī)劃求解 三、分支定界法 121 623 , 2 , 3277LPx x Z? ? ?：0 1 7 53 , 2 , 329 9 9LPx x Z? ? ?：2 4 , 1 , 29LPx x Z? ? ?：33 , 2 , 28LPx x Z? ? ?：4442 , 3 , 3155LPx Z? ? ?：5462 , 3 , 29LPx x Z? ? ?：6LP ：無 可 行 解1272 , 3 , 27LPx x Z? ? ?：8221 , 4 , 28LPx x Z? ? ?：x1≤3 x1 ≥4 x2≤2 x2 ≥3 x1≤2 x1 ≥3 x2≤3 x2 ≥4 0 9532下界：上界：29 7232下界：上界：29 5431下界：上界：29 7629下界：上界：2929下界：上界：80 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 一、生產(chǎn)基地規(guī)劃 例： 某公司擬建設(shè) A、 B兩種類型的生產(chǎn)基地若干個，兩種類型的生產(chǎn)基地每個占地面積，所需經(jīng)費(fèi)，建成后生產(chǎn)能力及現(xiàn)有資源情況如下表所示。問A、 B類型基地各建設(shè)多少個，可使總生產(chǎn)能力最大？ A B 資源限制 占地（萬 平米 ） 費(fèi)用（萬元） 2 5 5 4 13 24 生產(chǎn)能力（百件 / 年） 20 10 解：設(shè) A、 B兩類基地各建設(shè) x1,x2 個，則其模型為： ????????????且為整數(shù)0,244513521020m a x21212121xxxxxxxxZ81 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 二、人員安排規(guī)劃 某服務(wù)部門各時段 (每 2小時為一時段 )需要的服務(wù)人數(shù)如表： 時段 1 2 3 4 5 6 7 8 服務(wù)員最少數(shù)目 10 8 9 11 13 8 5 3 解：設(shè)第 j 時段開始時上班的服務(wù)員人數(shù)為 xj 第 j 時段來上班的服務(wù)員將在第 j+3 時段結(jié)束時下班，故決策變量有x1,x2,x3,x4,x5 。 ???????????????????????????????????????????皆為整數(shù)54321543215545435432432132121154321,,0,35813119810..m i nxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxZ按規(guī)定，服務(wù)員連續(xù)工作 8小時(4個時段 )為一班。請安排服務(wù)員的工作時間，使服務(wù)員總數(shù)最少 . 82 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 三、項目投資選擇 有 600萬元投資 5個項目，收益如表，求利潤最大的方案？ 項目 投資額 項目收益 約束條件 I 2 10 1 60 II 3 00 2 10 I II 1 50 60 IV 1 30 80 V 2 60 1 80 項目 I 、 II 、 I II 中選 1 項 項目 I II 、 IV 之中選 1 項 選項目 V 必先選項目 I ???? 個項目投資選中第不 個項目投資選中第 jjx j 01 ??????????????????????????10,116002601301503002101808060210160m a x5432115433215432154321或xxxxxxxxxxxxxxxxxxxxxxZ83 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 四、互斥約束問題 ? 例如關(guān)于煤資源的限制，其約束條件為： ? 企業(yè)也可以考慮采用天然氣進(jìn)行加熱處理： ? 這兩個條件是互相排斥的。引入 0—1變量 y，令 ? 互斥問題可由下述的條件來代替，其中 M是充分大的數(shù)。 20234 21 ?? xx 18053 21 ?? xx ???? 作用采用天燃?xì)饧訜峒s束起 采用煤加熱約束起作用01y yMxx Myxx ??? ???? 1 8 053 )1(2 0 054 21 2184 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 五、租賃生產(chǎn)問題 服裝公司租用生產(chǎn)線擬生產(chǎn) T恤、襯衫和褲子。 每年可用勞動力 8200h，布料 8800m2。 T恤 襯衫 褲子 勞動力 3 2 6 布料 售價 250 400 600 可變成本 100 180 300 生產(chǎn)線租金 (萬 ) 20 15 10 假設(shè)： yj=1，要租用生產(chǎn)線 j yi=0，不租用生產(chǎn)線 j 第 j 種服裝生產(chǎn)量 xj ?????????????????????10,0,8 8 0 8 2 0 0623..1 0 0 0 0 01 5 0 0 0 02 0 0 0 0 03 0 02 2 01 5 0m a x321321321321321321或且取整數(shù)yyyxxxxxxxxxtsyyyxxxZ 111 yMx ? 222 yMx ? 333 yMx ?85 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 六、任務(wù)指派問題 甲乙丙丁四個人， ABCD四項任務(wù)，如何指派總時間最短？ A B C D 甲 3 5 8 4 乙 6 8 5 4 丙 2 5 8 5 丁 9 2 5 2 任務(wù) 時間 人員 解： 引入 01變量 xij ， xij =1：任務(wù) j指派人員 i去完成 xij =0：任務(wù) j不派人員 i去完成 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 43 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4m in 3 5 8 4 6 8 5 42 5 8 5 9 2 5 2Z x x x x x x x xx x x x x x x x? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? 一項任務(wù)只由一個人完成 ? 一人只能完成一項任務(wù) 1 1 2 1 3 1 4 11 2 2 2 3 2 4 21 3 2 3 3 3 4 31 4 2 4 3 4 4 41111x x x xx x x xx x x xx x x x? ? ? ?? ? ? ?? ? ? ?? ? ? ? 1 1 1 2 1 3 1 42 1 2 2 2 3 2 43 1 3 2 3 3 3 44 1 4 2 4 3 4 41111x x x xx x x xx x x xx x x x? ? ? ?? ? ? ?? ? ? ?? ? ? ?86 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 七、設(shè)施選址問題 ? 擬定在 2個地點(diǎn)中選址設(shè)立分銷中心，執(zhí)行產(chǎn)品的倉儲和轉(zhuǎn)運(yùn)，一個分銷中心擬定設(shè)立一個倉庫 W W2。 ? 若設(shè)立倉庫 W1，建設(shè)成本為 10萬元，最大庫容為 20萬臺，單位產(chǎn)品的月庫存成本為 2元； ? 若設(shè)立倉庫 W2建造成本為 20萬元，最大庫容為 25萬臺，單位產(chǎn)品的月庫存成本為 3元。 ? 如何選址和安排調(diào)運(yùn)，建造費(fèi)用 +運(yùn)輸費(fèi)用 +倉儲費(fèi)用為最?。? 10jw ???? 擬規(guī)劃建立倉庫 jW 不 規(guī)劃建立倉庫jW 解：設(shè)從供貨源 Si到分銷中心 Wj的運(yùn)輸量為 xij，從分銷中心 到需求市場 Rk的運(yùn)輸量為 yjk。倉庫選址決策引入 01變量 wj ： 87 OR:SM 第三節(jié) 整數(shù)規(guī)劃應(yīng)用 七、設(shè)施選址問題 ? 供應(yīng)能力平衡約束： ? 市場需求平衡約束： ? 倉儲能力限制約束： ? 分銷中心不存留產(chǎn)品： ? 所有變量大于等于零： 1 1 1 2 2 1 2 2 1 1 1 2 1 3 2 1 2 2 2 31 2 1 1 1 2 2 1 2 2m in 2 5 4 2 3 4 5 2 2 31 0 2 0 2 ( ) 3 ( )Z x x x x y y y y y yw w x x x x? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? 1 1 1 22 1 2 250000150000xx?? 1 1 2 11 2 2 21 3 2 35000010000050000yyyyyy?????? 11 12 121 22 2202300250000x x wx x w?? 11 21 11 12 1312 22 21 22 23x x y y yx x y y y? ? ? ?? ? ? ? 1 1 1 2 2 1 2 2 1 1 1 2 1 3 2 1 2 2 2 3, , , , , , , , , 0x x x x y y y y y