運(yùn)籌學(xué)——整數(shù)規(guī)劃-在線(xiàn)瀏覽
2024-09-11 15:22本頁(yè)面
【正文】 數(shù)規(guī)劃與其松弛問(wèn)題之間的關(guān)系 ?整數(shù)規(guī)劃問(wèn)題的可行域是它的松弛問(wèn)題可行域的一個(gè)子集； ?整數(shù)規(guī)劃問(wèn)題的最優(yōu)值（最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值）不會(huì)優(yōu)于它的松弛問(wèn)題的最優(yōu)值； ?對(duì)松弛問(wèn)題的最優(yōu)解中不符合整數(shù)要求的分量簡(jiǎn)單地取整，所得到的解不一定是整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，甚至也不一定是整數(shù)規(guī)劃問(wèn)題的可行解。從解問(wèn)題 B開(kāi)始，若其最優(yōu)解不符合 A的整數(shù)條件，那么 B的最優(yōu)目標(biāo)函數(shù)必是 A的最優(yōu)目標(biāo)函數(shù) Z＊ 的上界，記作 Z；而 A的任意可行解對(duì)應(yīng)的目標(biāo)函數(shù)值將是 Z＊ 的一個(gè)下界，記作 Z。逐步減小 Z和增大 Z，最終求得 Z＊ 。 (1)解問(wèn)題 B，可能得到以下情況之一： （ a） B沒(méi)有可行解，這時(shí) A也沒(méi)有可行解，則停止。 （ c） B有最優(yōu)解，但不符合問(wèn)題 A的整數(shù)條件，記它的目標(biāo)函數(shù)值為 Z。以 Z＊表示問(wèn)題 A的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有 進(jìn)行迭代 第一步：分枝，在 B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 xj，其值為 bj，以［ bj］表示小于 bj的最大整數(shù)。 zzz * ??第二節(jié) 分枝定界法 定界，以每個(gè)后繼問(wèn)題為一分枝標(biāo)明求解的結(jié)果，與其它問(wèn)題的解的結(jié)果比較，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界 Z。 第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于 Z者，則剪掉這枝（用打 表示），即以后不再考慮了。一直到最后 Z＊ ＝ Z為止。 第二節(jié) 分枝定界法 用分枝定界法解下列問(wèn)題： ????????????且為整數(shù)0x,x369x4x357x5xs t .3x2xM a x21212121Z????????????且為整數(shù)0x,x369x4x357x5xs t .3x2xM a x21212121Z 問(wèn)題 B x1= x2= Z0= 問(wèn)題 B1 x1=3 x2= Z1=14 問(wèn)題 B2 x1=4 x2= Z2= 問(wèn)題 B6 無(wú)可行解 問(wèn)題 B5 x1= x2=2 Z2=14 問(wèn)題 B3 x1= x2=3 Z1= 問(wèn)題 B4 x1=3 x2=2 Z1=12 x1≤3 x1≥4 x2≥3 x2≤2 x2≤2 x2≥3 第三節(jié) 割平面法 一、什么是割平面法（基本思想） 先不考慮變量的整數(shù)限制，求解其對(duì)應(yīng)的線(xiàn)性規(guī)劃問(wèn)題。 步驟 1：不考慮變量的整數(shù)限制，求解相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題，如果該問(wèn)題無(wú)可行解或最優(yōu)解已是整數(shù)解，則停止計(jì)算，否則轉(zhuǎn)入一下步； 步驟 2：對(duì)上述線(xiàn)性規(guī)劃問(wèn)題的可行域進(jìn)行 “ 切割 ” ，去掉不含整數(shù)解的一部分可行域，即增加適當(dāng)?shù)募s束條件（ Gomory約束 ），然后轉(zhuǎn)入步驟 1。即 其中 i∈ Q(Q指構(gòu)成基變量下標(biāo)的集合 ) k∈ K(K指構(gòu)成非基變量下標(biāo)的集合 ) ( 1 )bxaxkikiki ? ??第三節(jié) 割平面法 將 bi和 aik都分解成整數(shù)部分 N與非負(fù)真分?jǐn)?shù) f之和 ,即 bi=Ni+fi， 其中 0＜ fi＜ 1 aik=Nik+fik， 其中 0≤fik＜ 1 代入（ 1）式得 由于變量有整數(shù)的限制，所以上式左邊必為整數(shù)。決策變量稱(chēng)為 01變量 (二進(jìn)制變量、邏輯變量 )。 ????時(shí)即取當(dāng)決策不取方案時(shí)當(dāng)決策取方案 )PP( 0P 1x一、什么是 01整數(shù)規(guī)劃 第四節(jié) 01整數(shù)規(guī)劃 投資場(chǎng)所的選定－－相互排斥的計(jì)劃 例：某公司擬在市東、西、南三區(qū)建立門(mén)市部，擬議中有 7個(gè)位置 Ai(i=1,2,… ,7)可供選擇。 如選用 Ai點(diǎn)，設(shè)備投資估計(jì)為 bi元，每年可獲利潤(rùn)估計(jì)為 ci元，但投資總額不能超過(guò) B元。今設(shè)運(yùn)貨有車(chē)運(yùn)和船運(yùn)兩種方式，上面的條件系用車(chē)運(yùn)時(shí)的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為 7x1+3x2≤45(船 )。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？ 貨物 甲 乙 托運(yùn)限制 體 積 每箱（米 3） 5 4 24 重 量 每箱（百公斤） 2 5 13 利 潤(rùn) 每箱（百元） 20 10 ?????????????????????變量為為整數(shù)10x,x0,135245372445s t .1020Ma x Z212121212121yxxxxxxxxxx解：設(shè)甲、乙兩種貨物的托運(yùn)箱數(shù)分別為 x1,x2。 +(1y)M +yM 第四節(jié) 01整數(shù)規(guī)劃 二、 01整數(shù)規(guī)劃的解法 ???????????????????????10,64 3 4422.5233213232321321321或例：求解下列問(wèn)題xxxxxxxxxxxxxstxxxM a xZ隱枚舉法：只檢查變量取值的組合的一部分的方法。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成 n項(xiàng)任務(wù)的總效率最高。 第五節(jié) 指派問(wèn)題 二、指派問(wèn)題的數(shù)學(xué)模型 ?????????????????? ???? ?10),2,1(1),2,1(1.111 1或ijnjijniijninjijijxnixnjxstxcM i n Z??????????????nnnnnnccccccccc???????212222111211=(Cij) B1 B2 Bn A1 c11 c12 c1n
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1