運(yùn)籌學(xué)——整數(shù)規(guī)劃與分配問(wèn)題(參考版)
2025-05-18 22:11本頁(yè)面
【正文】 ? 若大于下界，且不符合整數(shù)條件，則重復(fù)第三步，選取所有 邊界值最優(yōu)的分枝 進(jìn)行分枝與定界，一直到最后得到 z* = A的下界為止，此時(shí)得到最優(yōu)解。 ? 定界： 比較所有后繼問(wèn)題的最優(yōu)解，最大的為 A的新上界，從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無(wú)可行解，令下界 = 0。構(gòu)造兩個(gè)約束條件 xj ≤ [ bj]和 xj ≥[ bj + 1]，將這兩個(gè)約束條件，分別加入問(wèn)題 B，求兩個(gè)后繼規(guī)劃問(wèn)題 B1和 B2。 三、分枝定界法 分枝定界法的解題步驟 (2) 3. 分枝與定界： ? 分枝： 在 B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量 xj。 ?B有最優(yōu)解，但不符合問(wèn)題 A的整數(shù)條件，將 B的目標(biāo)函數(shù)值為問(wèn)題 A的上界。 三、分枝定界法 分枝定界法的解題步驟 (1) 1. 解松馳問(wèn)題 B： ?B沒(méi)有可行解，這時(shí) A也沒(méi)有可行解，停止。若除保留的可行 解外，其他的分支均被減 去，則得到最優(yōu)解。 三、分枝定界法 分枝定界法 — 剪枝 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)行比較。 ? 這兩個(gè)最優(yōu)解都是 A的可行解，此時(shí) A的上界和下界分別為 14。 三、分枝定界法 分枝定界法實(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。 三、分枝定界法 分枝定界法實(shí)例 (2) ??????????????? ,xxx.xx xxz B025450143223m a x:2122121211??????????????? xx.xx xxz B035450143223m a x:2121212124. 定界： 用圖解法可得 B1的最優(yōu)解為 (, 2), z1 = ； B2的最優(yōu)解為 (, 3), z2 =。 ?z0?z3. 分枝： 在 B的最優(yōu)解中，任取一個(gè)非整數(shù)變量，如 x2 = ；因 x2 的最近鄰整數(shù)解為 x2 = 2或 x2 = 3， 其最優(yōu)整數(shù)解區(qū)間只能是 x2 ≥ 3或 x2 ≤ 2。分支定界法就是將 B的可行域分成子區(qū)域 (稱為 分枝 )的方法，逐步減小和增大上、下界，最終得到整數(shù)規(guī)劃問(wèn)題 A的 z*。 第四章 整數(shù)規(guī)劃及分配問(wèn)題 作 業(yè) 一 ? 求下面指派問(wèn)題的最優(yōu)解 ????????????????9107104106614159141217766698979712第三節(jié) 分枝定界法 第四章 整數(shù)規(guī)劃及分配問(wèn)題 三、分枝定界法 分枝定界法的基本思想 ? 分枝定界法 可用于 全部類型 的整數(shù)規(guī)劃問(wèn)題。根據(jù)定理 1，這種轉(zhuǎn)換是等價(jià)的。 工作 人 I II III IV 1 2 3 4 5 6 3 7 3 6 5 5
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1