運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題-資料下載頁(yè)
2025-05-14 22:11本頁(yè)面
【正文】 143223m a x:2121212124. 定界： 用圖解法可得 B1的最優(yōu)解為 (, 2), z1 = ； B2的最優(yōu)解為 (, 3), z2 =。 沒(méi)有整數(shù)最優(yōu)解，上界 5. 其下界沒(méi)有整數(shù)解， 6. 7. z1 z2， 對(duì) B1再次分枝 。 三、分枝定界法 分枝定界法實(shí)例 (3) 1 4 . 5 = z B1?z0= ( 0 , 0 )zz ??三、分枝定界法 分枝定界法實(shí)例 (4) ?????????????????? ,xxxx.xx xxz: B0325450143223m a x211221212111?????????????????? xxx.xx xxz: B0425450143223m a x212212121215. 再次分枝定界： 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。 三、分枝定界法 分枝定界法 — 剪枝 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 將各子問(wèn)題邊界值與保留 的可行解的值進(jìn)行比較。 把邊界值劣于可行解的分 支減去。若除保留的可行 解外，其他的分支均被減 去，則得到最優(yōu)解。 三、分枝定界法 分枝定界法的解題思路 ? 分枝定界法實(shí)際上是一種利用替代問(wèn)題的解來(lái)逐漸逼近原問(wèn)題最優(yōu)解的方法； ? 對(duì)替代問(wèn)題的要求是：容易求解，且原問(wèn)題的解集應(yīng)無(wú)例外地包含在替代問(wèn)題的解集中； ? 如果替代問(wèn)題 (松弛 )的最優(yōu)解是原問(wèn)題的可行解，這個(gè)解就是原問(wèn)題的最優(yōu)解；否則這個(gè)解的值是原問(wèn)題最優(yōu)解的上界 (求極大時(shí) )或下界值 (求極小時(shí) )。 三、分枝定界法 分枝定界法的解題步驟 (1) 1. 解松馳問(wèn)題 B： ?B沒(méi)有可行解，這時(shí) A也沒(méi)有可行解，停止。 ?B有最優(yōu)解，并符合問(wèn)題 A的整數(shù)條件， B的最優(yōu)解即為 A的最優(yōu)解，停止。 ?B有最優(yōu)解，但不符合問(wèn)題 A的整數(shù)條件，將 B的目標(biāo)函數(shù)值為問(wèn)題 A的上界。 2. 用觀察法找問(wèn)題 A的一個(gè)整數(shù)可行解，一般可取 xj = 0， j=1,?,n ， 求得其目標(biāo)函數(shù)值，作為 A的下界，開始迭代運(yùn)算。 三、分枝定界法 分枝定界法的解題步驟 (2) 3. 分枝與定界： ? 分枝： 在 B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 xj。其值為 bj，以 [bj]表示小于 bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件 xj ≤ [ bj]和 xj ≥[ bj + 1]，將這兩個(gè)約束條件，分別加入問(wèn)題 B，求兩個(gè)后繼規(guī)劃問(wèn)題 B1和 B2。求解這兩個(gè)后繼松弛問(wèn)題。 ? 定界： 比較所有后繼問(wèn)題的最優(yōu)解，最大的為 A的新上界，從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無(wú)可行解，令下界 = 0。 三、分枝定界法 分枝定界法的解題步驟 (3) 4. 比較與剪枝： ? 各分支的最優(yōu)目標(biāo)函數(shù)若小于 第三步得到的下界 ，則剪掉此分枝 (用打 表示 )，以后不再考慮。 ? 若大于下界，且不符合整數(shù)條件，則重復(fù)第三步，選取所有 邊界值最優(yōu)的分枝 進(jìn)行分枝與定界，一直到最后得到 z* = A的下界為止，此時(shí)得到最優(yōu)解。 第四章 整數(shù)規(guī)劃及分配問(wèn)題 本章小結(jié) ? 什么是整數(shù)規(guī)劃？ 什么是 01整數(shù)規(guī)劃？ ? 整數(shù)規(guī)劃的作用 ? 什么是分配問(wèn)題 (指派問(wèn)題 ) ?匈牙利法 ? 求解一般整數(shù)規(guī)劃的方法 ?分枝定界法
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1