管理運(yùn)籌學(xué)整數(shù)規(guī)劃-資料下載頁
2025-01-11 19:41本頁面
【正文】 應(yīng)的 yj = 1 xj ； (3)當(dāng)某個(gè)約束不等式是“ ≥”時(shí)，只需兩端同乘以 1，即變?yōu)椤?≤” ； (4)當(dāng)某個(gè)約束是等式約束時(shí)，可得到兩個(gè)方向相反的不等式。 167。 4整數(shù)規(guī)劃的分枝定界法 (5) 隱枚舉法的基本過程： 將 0— 1規(guī)劃問題化為標(biāo)準(zhǔn)形式，設(shè)其最優(yōu)解為 x*， 最優(yōu)目標(biāo)值為 f* 。顯然 x = 0 時(shí)，目標(biāo)值 f ＝ 0 是不考慮線性不等式約束的最小解，于是 f* ≥ 0。若 x = 0 是可行解，那末 f ＝ 0是該問題的最優(yōu)解，結(jié)束計(jì)算。否則，置所有分量為自由變量。轉(zhuǎn) 2； 任選一自由變量 xk ， 令 xk 為固定變量，分別固定為 xk = 0 與 xk ＝ 1， 令所有自由變量取零值，則得到兩個(gè)分枝。對(duì)每個(gè)分枝的試探解進(jìn)行檢驗(yàn)（把自由變量逐次定為固定變量的順序可以是任意的，在不進(jìn)行先驗(yàn)考察時(shí)，常按指標(biāo)變量從小到大的順序進(jìn)行）。轉(zhuǎn) 3； 檢驗(yàn)當(dāng)前試探解時(shí)，遇到下列 4種情況就剪枝，即不必再向下分枝，在剪枝的子問題下方標(biāo)記“”： 情況一：若子問題的試探解可行，即滿足所有線性不等式約束，則此問題的目標(biāo)值是原問題最優(yōu)目標(biāo)值的一個(gè)上界記為 f175。 即 f* ≤ f175。 。把 f175。 的值記在子問題框的旁邊，并在下方標(biāo)記上“”； 167。 4整數(shù)規(guī)劃的分枝定界法 (6) 情況二：若試探解不可行，且存在一個(gè)線性不等式約束，將所有固定變量值代入后，所得到的不等式中所有負(fù)系數(shù)之和大于右端項(xiàng)或若無負(fù)系數(shù)時(shí)，最小的系數(shù)大于右端項(xiàng)，那么此問題的任何分枝都是不可行的問題。于是在此問題框的下方標(biāo)記“”； 情況三：若試探解不可行，且它的目標(biāo)值與目標(biāo)函數(shù)中對(duì)應(yīng)當(dāng)前自由變量的任一個(gè)系數(shù)之和大于所有已得到的上界中最小者時(shí)，說明在當(dāng)前問題的基礎(chǔ)上，固定任何自由變量都不可能對(duì)目標(biāo)函數(shù)有改善，于是在該問題框的下方標(biāo)記“”； 情況四：若試探解不可行，但所有變量已被置為固定變量，也應(yīng)剪枝，于是在該問題框的下方標(biāo)記“”。 把已標(biāo)記“”的子問題，稱為已探明的枝。轉(zhuǎn) 4。 進(jìn)一步考察。如果所有的枝均為已探明的枝，則停機(jī)結(jié)束計(jì)算。找出所有子問題框邊標(biāo)記 f175。 值的問題，比較得到其中最小者，其對(duì)應(yīng)的試探解即原問題的最優(yōu)解，相應(yīng)值即原問題的最優(yōu)目標(biāo)值 f*；若沒有標(biāo)記 f175。 值的框，則說明原問題無最優(yōu)解，實(shí)際上原問題無可行解。 如果仍存在尚未探明的分枝，則可任選一個(gè)未探明的分枝。轉(zhuǎn) 2。 167。 4整數(shù)規(guī)劃的分枝定界法 (7) 01規(guī)劃的隱枚舉法 例： Max z=100x1+30x2+40x3+45x4 . 50x1+30x2+25x3+10x4≤95 7x1+ 2x2+ 3x3+ 4x4≤11 2x1+ x2+ x3+10x4≤12 x4 ≤ x2+ x3 xj= 0 或 1 ， i = 1,2,3,4 標(biāo)準(zhǔn)化： 取 f’=z=100x130x240x3 45x4 令 y1=1x1, y2=1x2, y3=1x3, y4=1x4 f’=100y1+30y2+40y3 +45y4215, 記 f = f’ + 215, 得到 Min f=100y1+30y2+40y3 +45y4 . 50y130y225y3 10y4≤ 20 7y1 2y2 2y3 4y4≤ 4 2y1 y2 y3 10y4≤ 2 y2+ y3 y4≤ 1 yj= 0 或 1 ， i = 1,2,3,4 第九章 動(dòng)態(tài)規(guī)劃 167。 1 多階段決策過程最優(yōu)化問題舉例 167。 2 基本概念、基本方程與最優(yōu)化原理 167。 3 動(dòng)態(tài)規(guī)劃的應(yīng)用 （見文本） 167。 1 多階段決策過程最優(yōu)化問題舉例 BACBDBCDEC212312312511214106104131211396581052例 1 最短路徑問題 右圖表示從起點(diǎn) A到終點(diǎn)E之間各點(diǎn)的距離 。 求 A到 E的最短路徑 。 如果用窮舉法，則從 A到 E一共有 3 3 2=18條不同的路徑，逐個(gè)計(jì)算每條路徑的長度，總共需要進(jìn)行 4 18=72次加法計(jì)算；對(duì) 18條路徑的長度做兩兩比較，找出其中最短的一條，總共要進(jìn)行 18－ 1=17次比較。如果從 A到 C的站點(diǎn)有 k個(gè)，則總共有 3k1 2條路徑， 用窮舉法求最短路徑總共要進(jìn)行 (k+1)3k1 2次加法， 3k1 21次比較。當(dāng) k的值增加時(shí)，需要進(jìn)行的加法和比較的次數(shù)將迅速增加。例如當(dāng) k=10時(shí)，加法次數(shù)為 433026次，比較39365次。 以上這求從 A到 E的最短路徑問題，可以轉(zhuǎn)化為三個(gè)性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從 B B B3到 E的最短路徑問題。 記從 Bi (i=1, 2, 3) 到 E的最短路徑為 S(Bi)， 則從 A到 E的最短距離 S(A)可以表示為：
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1