【正文】 1/3 0 1/3 1/12 1/4 1/3 c j z j 2 0 0 0 1/3 1/6 由于 x 1 、 x 2 的值已都是整數(shù)，解題已完成。 ? 引入松弛變量 x5， 得到等式 ? 3x3x4+x5=3 ? 將這新的約束方程加到表 52的最終計算表，得表 53。就是說，右邊的整數(shù)值最大是零。但在等式右邊的 (將上式變量的系數(shù)和常數(shù)項都分解成整數(shù)和非負真分數(shù)兩部分之和 ? (1+0)x1+(1+3/4)x3+1/4x4=0+3/4 ? x2+(3/4)x3+(1/4)x4=1+3/4 ? 然后將整數(shù)部分與分數(shù)部分分開 ， 移到等式左右兩邊 ， 得到 ： ????????????????????43243314143431414343xxxxxxx現(xiàn)考慮整數(shù)條件⑤ ? 要求 x x2都是非負整數(shù)，于是由條件⑥、⑦可知 x x4也都是非負整數(shù) ,這一點對以下推導是必要的，如不都是整數(shù)，則應在引入 xx4之前乘以適當常數(shù)，使之都是整數(shù)。就可以得到整數(shù)的最優(yōu)解。 表 52 c j 1 1 0 0 C B X B b x 1 x 2 x 3 x 4 0 0 x 3 x 4 1 4 1 3 1 1 1 0 0 1 初始計算表 c j z j 0 1 1 0 0 1 1 x 1 x 2 3/4 7/4 1 0 0 1 1 /4 3/4 1/4 1/5 最終計算表 cj z j 5/2 0 0 1/2 1/2 從表 52的最終計算表中，得到非整數(shù)的最優(yōu)解： x1=3/4， x2=7/4， x3=x4=0， max z=5/2 不能滿足整數(shù)最優(yōu)解的要求。 現(xiàn)設想，如能找到像 CD那樣的直線去切割域R(圖 56)，去掉三角形域 ACD，那么具有整數(shù)坐標的 C點 (1， 1)就是域 R′的一個極點， ? 如在域 R′上求解①～④，而得到的最優(yōu)解又恰巧在 C點就得到原問題的整數(shù)解，所以解法的關鍵就是怎樣構造一個這樣的“ 割平面 ” CD，盡管它可能不是唯一的，也可能不是一步能求到的。 以下只討論純整數(shù)線性規(guī)劃的情形 ， 現(xiàn)舉例說明 。 這個方法就是指出怎樣找到適當?shù)母钇矫?(不見得一次就找到 )， 使切割后最終得到這樣的可行域 ， 它的一個有整數(shù)坐標的極點恰好是問題的最優(yōu)解 。 若變量數(shù)目很大 ， 其計算工作量也是相當可觀的 。 它比窮舉法優(yōu)越 。 一直到最后得到 z*為止 ， 得最優(yōu)整數(shù)解 xj*， j=1， …， n。從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作為新的下界，若無可行解， 0?z第二步：比較與剪支 ? 各分支的最優(yōu)目標函數(shù)中若有小于 者 ， 則剪掉這支 (用打 表示 )， 即以后不再考慮了 。 不考慮整數(shù)條件求解這兩個后繼問題 。 以 z*表示問題 A的最優(yōu)目標函數(shù)值；這時有 z_* zzz ???進行迭代 ? 第一步：分支 ， 在 B的最優(yōu)解中任選一個不符合整數(shù)條件的變量 xj， 其值為 bj， 以 ［ bj］ 表示小于 bj的最大整數(shù) 。 ? ② B有最優(yōu)解，并符合問題 A的整數(shù)條件， B的最優(yōu)解即為 A的最優(yōu)解，則停止。 ? (1) 解問題 B， 可能得到以下情況之一 。 繼續(xù)對問題 B2進行分解 解題的過程都列在圖54中 。增加條件x2≤2 者，稱為問題 B3；增加條件 x2≥3 者稱為問題 B4。 得到最優(yōu)解為： 問題 B 1 問題 B 2 z1=349 x1= x2= z2=341 x1= x2= 圖 53 ? x1≤ 4， x1≥ 5 ? 顯然沒有得到全部變量是整數(shù)的解 。 于是對原問題增加兩個約束條件 x1≤ 4，x1≥ 5 ? 可將原問題分解為兩個子問題 B1和 B2(即兩支 )， ? 給每支增加一個約束條件 ， 如圖 53所示 。 而在 x1=0， x2=0時 ， 顯然是問題 A的一個整數(shù)可行解 ， 這時 z=0， 是 z*的一個下界 ， 記作 =0， 即 0≤z*≤ 356 。 現(xiàn)用下例來說明： 例 2 ? 求解 A max z=40x1+90x2 ① 9x1+7x2≤56 ② 7x1+20x2≤70 ③ () x1， x2≥0 ④ x1， x2整數(shù) ⑤ 解 先不考慮條件⑤，即解相應的線性規(guī)劃 B,① ～④(見圖 52)，得最優(yōu)解 x1=， x2=， z0=356 可見它不符合整數(shù)條件⑤。 設有最大化的整數(shù)線性規(guī)劃問題 A， 與它相應的線性規(guī)劃為問題 B， 從解問題 B開始 ， 若其最優(yōu)解不符合 A的整數(shù)條件 ， 那么 B的最優(yōu)目標函數(shù)必是 A的最優(yōu)目標函數(shù) z*的上界 ， 記作；而 A的任意可行解的目標函數(shù)值將是 z*的一個下界 。 在 20世紀 60年代初由 Land Doig和 Dakin等人提出 。所以我們的方法一般應是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。對于大型的問題，可行的整數(shù)組合數(shù)是很大的。 對于小型的問題 ， 變量數(shù)很少 ， 可行的整數(shù)組合數(shù)也是很小時 ， 這個方法是可行的 ， 也是有效的 。因此有必要對整數(shù)線性規(guī)劃的解法進行專門研究 。 這樣 ， z的等值線就由 z=96變到 z=90， 它們的差值 ? Δ z=9690=6 ? 表示利潤的降低 ， 這是由于變量的不可分性(裝箱 )所引起的 。 湊整的(5， 0)點不在可行域內(nèi) ， 而 C點又不