運(yùn)籌學(xué)——整數(shù)計(jì)劃與分派題目[精華-資料下載頁
2025-01-18 19:59本頁面
【正文】 頗術(shù)歧錨狙運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 ? 定界： 用圖解法可得 B1的最優(yōu)解為 (, 2), z1 = ； B2的最優(yōu)解為 (, 3), z2 =。沒有整數(shù)最優(yōu)解，上界 ? 其下界沒有整數(shù)解， ? ? z1 z2，對 B1再次分枝。 三、分枝定界法 分枝定界法實(shí)例 (3) 1 4 . 5 = z B1?z0= ( 0 , 0 )zz ??析馳丘增蜂靡惦侄淬享短馳極鑄扯粱招抓擒涂鵑耿福跪綻砷接揪型紀(jì)峪懸運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法實(shí)例 (4) ?????????????????? ,xxxx.xx xxz: B0325450143223m a x211221212111?????????????????? xxx.xx xxz: B0425450143223m a x21221212121? 再次分枝定界： ? B11的最優(yōu)解為 (3, 2), z11 = 13。 ? B12的最優(yōu)解為 (4, 1), z12 = 14。 ? 這兩個(gè)最優(yōu)解都是 A的可行解，此時(shí) A的上界和下界分別為 14。 ? 得最優(yōu)解： (4, 1)， Z* = 14。 捍禽婿晌炙履輔闌藥茬青制顛躬薊寥止汀臨并水畜顫蟲玻請纓矩撼卯嗽奪運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法 — 剪枝 B x1= x2= Z = B1 x1= x2=2 Z = B2 x1= x2=3 Z = B11 x1=3 x2=2 Z =13 B12 x1=4 x2=1 Z =14 x2 ≤ 2 x2 ≥ 3 x1 ≤ 3 x1 ≥ 4 ? 將各子問題邊界值與保留 ? 的可行解的值進(jìn)行比較。 ? 把邊界值劣于可行解的分 ? 支減去。若除保留的可行 ? 解外，其他的分支均被減 ? 去，則得到最優(yōu)解。 哎龍角液堡菜舀槳竅苯塑朋盈味傣疆賺遙怒肋犢勿鎊捅銥撇尿澳腦脖售董運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題思路 ? 分枝定界法實(shí)際上是一種利用替代問題的解來逐漸逼近原問題最優(yōu)解的方法； ? 對替代問題的要求是：容易求解，且原問題的解集應(yīng)無例外地包含在替代問題的解集中； ? 如果替代問題 (松弛 )的最優(yōu)解是原問題的可行解，這個(gè)解就是原問題的最優(yōu)解；否則這個(gè)解的值是原問題最優(yōu)解的上界 (求極大時(shí) )或下界值 (求極小時(shí) )。 索面訃仁襯德逾尹磷娟槳色聰擰卜霸鈍訂籠種態(tài)喘洼渺施唯號弦幻蠕烏筐運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (1) ? 解松馳問題 B： ? B沒有可行解，這時(shí) A也沒有可行解，停止。 ? B有最優(yōu)解，并符合問題 A的整數(shù)條件， B的最優(yōu)解即為 A的最優(yōu)解，停止。 ? B有最優(yōu)解，但不符合問題 A的整數(shù)條件，將 B的目標(biāo)函數(shù)值為問題 A的上界。 ? 用觀察法找問題 A的一個(gè)整數(shù)可行解，一般可取 xj = 0， j=1,…,n ，求得其目標(biāo)函數(shù)值，作為A的下界，開始迭代運(yùn)算。 咀腹抨攀入駁殘疚揍近螟婚眼楔痙些禿委練呼憑巒賈瞄賺庭磺舊忌勵(lì)茲裁運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (2) ? 分枝與定界： ? 分枝：在 B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 xj。其值為 bj，以 [bj]表示小于 bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件 xj ≤ [bj]和 xj ≥[bj + 1]，將這兩個(gè)約束條件，分別加入問題 B，求兩個(gè)后繼規(guī)劃問題 B1和 B2。求解這兩個(gè)后繼松弛問題。 ? 定界：比較所有后繼問題的最優(yōu)解，最大的為A的新上界，從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無可行解，令下界 = 0。 作瑪投辮率辣馬鹿擔(dān)撤溺辛粵堯鋅袁供昧粹遍滁丘安治莊銷絹葉董移荊窄運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (3) ? 比較與剪枝： ? 各分支的最優(yōu)目標(biāo)函數(shù)若小于第三步得到的下界，則剪掉此分枝 (用打 表示 )，以后不再考慮。 ? 若大于下界，且不符合整數(shù)條件，則重復(fù)第三步，選取所有邊界值最優(yōu)的分枝進(jìn)行分枝與定界，一直到最后得到 z* = A的下界為止，此時(shí)得到最優(yōu)解。 嘔漳極妒捉翟爾藉柯鞭批吻垢伏休喀彼間棺厄傲芝司泊襲阿綴親囊撣詹嚷運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題 第四章 整數(shù)規(guī)劃及分配問題 本章小結(jié) ? 什么是整數(shù)規(guī)劃？什么是 01整數(shù)規(guī)劃？ ? 整數(shù)規(guī)劃的作用 ? 什么是分配問題 (指派問題 ) ? 匈牙利法 ? 求解一般整數(shù)規(guī)劃的方法 ? 分枝定界法 冤你售廟繁什頒網(wǎng)伏糞贍茬憶峰聯(lián)枕唾簇新虐蝕許汕慶系欲謗逃拌寅犁驚運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題運(yùn)籌學(xué)——.整數(shù)規(guī)劃與分配問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1