管理運籌學(xué)整數(shù)規(guī)劃(參考版)
2025-01-14 19:41本頁面
【正文】 記從 Bi (i=1, 2, 3) 到 E的最短路徑為 S(Bi)， 則從 A到 E的最短距離 S(A)可以表示為： 。例如當(dāng) k=10時，加法次數(shù)為 433026次，比較39365次。如果從 A到 C的站點有 k個，則總共有 3k1 2條路徑， 用窮舉法求最短路徑總共要進(jìn)行 (k+1)3k1 2次加法， 3k1 21次比較。 求 A到 E的最短路徑 。 3 動態(tài)規(guī)劃的應(yīng)用 （見文本） 167。 1 多階段決策過程最優(yōu)化問題舉例 167。 167。 如果仍存在尚未探明的分枝，則可任選一個未探明的分枝。 值的問題，比較得到其中最小者，其對應(yīng)的試探解即原問題的最優(yōu)解，相應(yīng)值即原問題的最優(yōu)目標(biāo)值 f*；若沒有標(biāo)記 f175。如果所有的枝均為已探明的枝，則停機結(jié)束計算。轉(zhuǎn) 4。于是在此問題框的下方標(biāo)記“”； 情況三：若試探解不可行，且它的目標(biāo)值與目標(biāo)函數(shù)中對應(yīng)當(dāng)前自由變量的任一個系數(shù)之和大于所有已得到的上界中最小者時，說明在當(dāng)前問題的基礎(chǔ)上，固定任何自由變量都不可能對目標(biāo)函數(shù)有改善，于是在該問題框的下方標(biāo)記“”； 情況四：若試探解不可行，但所有變量已被置為固定變量，也應(yīng)剪枝，于是在該問題框的下方標(biāo)記“”。 的值記在子問題框的旁邊，并在下方標(biāo)記上“”； 167。 。轉(zhuǎn) 3； 檢驗當(dāng)前試探解時，遇到下列 4種情況就剪枝，即不必再向下分枝，在剪枝的子問題下方標(biāo)記“”： 情況一：若子問題的試探解可行，即滿足所有線性不等式約束，則此問題的目標(biāo)值是原問題最優(yōu)目標(biāo)值的一個上界記為 f175。轉(zhuǎn) 2； 任選一自由變量 xk ， 令 xk 為固定變量，分別固定為 xk = 0 與 xk ＝ 1， 令所有自由變量取零值，則得到兩個分枝。若 x = 0 是可行解，那末 f ＝ 0是該問題的最優(yōu)解，結(jié)束計算。 4整數(shù)規(guī)劃的分枝定界法 (5) 隱枚舉法的基本過程： 將 0— 1規(guī)劃問題化為標(biāo)準(zhǔn)形式，設(shè)其最優(yōu)解為 x*， 最優(yōu)目標(biāo)值為 f* 。那么，可以令相應(yīng)的 yj = 1 xj ； (3)當(dāng)某個約束不等式是“ ≥”時，只需兩端同乘以 1，即變?yōu)椤?≤” ； (4)當(dāng)某個約束是等式約束時，可得到兩個方向相反的不等式。隱枚舉法的基本思想是根據(jù) 0— 1規(guī)劃的特點，進(jìn)行分技逐步求解。 例： Min f = 5x14x2 . 3x1+4x2 ≤ 24 9x1+5x2 ≤ 45 x1,x2 ≥ 0 整數(shù) 167。 167。 分枝定界法當(dāng)所有子問題都剪枝了，即沒有需要處理的子問題時，達(dá)到當(dāng)前上界 z175。 。 比較與剪枝： 對當(dāng)前子問題進(jìn)行考察，若不需再進(jìn)行計算，則稱之為剪枝。 對一般迭代步，設(shè)根據(jù)分枝定界方法得到了原問題 (A)的一個同層子問題 (AI )， i＝ 1， 2， ...，n 之和的分解。構(gòu)造兩個附加約束： xr ≤ [xr] 和 xr ≥ [xr]+1 ，對 (A)分別加入這兩個約束，可得到兩個子問題 (A1)和 (A2)， 顯然這兩個子問題的可行解集的并是 (A)的可行解集； 定界： 根據(jù)前面分析，對每個當(dāng)前問題 (A)可以通過求解松弛問題 (B)，以及找 (A)的可行解得到當(dāng)前問題的上、下界 z175。 )，轉(zhuǎn) 2，進(jìn)行以下一般步的迭代； 167。＝ +?， 而先不必費很大力量去求較好的上界。 即得到 z ＜ z* ＜ z175。我們?nèi)握?(A)問題的一個可行解，那么對應(yīng)的目標(biāo)函數(shù)值是 (A)最優(yōu)值的一個上界 z175。根據(jù)上面分析，若出現(xiàn)情況①，②則停機。這時得到當(dāng)前問題 (A)最優(yōu)目標(biāo)值的一個下界 z ＝ z ,于是通過以下判斷可對此問題進(jìn)一步計算。 4整數(shù)規(guī)劃的分枝定界法 (1) 問題（ A） Min z = c1 x1 + c2 x2 + … + c n xn 記 問題（ B） 為去掉整數(shù)約束的問題（ A） . a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ， x2 ， … ， xn ≥ 0 為整數(shù) 在分枝定界法過程中求解問題 (B)，應(yīng)有以下情況之一： ① (B)無可行解，則 (A)亦無可行解，停止對此問題 的計算； ② (B)有最優(yōu)解，并滿足整數(shù)約束，即同時為 (A)的最優(yōu)解，那么 z*同時是當(dāng)前問題 (A)最優(yōu)目標(biāo)值的上界 和下界。 關(guān)于項目 C的投資額規(guī)定 : x2C = 20220y2C ， y2C = 0， 1， 2， 3， 4。 3整數(shù)規(guī)劃的應(yīng)用 (6) 2）約束條件： 第一年：年初有 10000
公司管理相關(guān)推薦
鄂ICP備17016276號-1