目標(biāo)規(guī)劃典型例題

1、§6.4 主要解題方法和典型例題分析題型i 目標(biāo)規(guī)劃數(shù)學(xué)模型的建立當(dāng)線性規(guī)劃問題有多個目標(biāo)需要滿足時，就可以通過建立目標(biāo)規(guī)劃數(shù)學(xué)模型來描述。目標(biāo)規(guī)劃數(shù)學(xué)模型的建立步驟為：第一步，確定決策變量；第二步，確定各目標(biāo)的優(yōu)先因子；第三步，寫出硬約束和軟約束；第四步，確定目標(biāo)函數(shù)。例6-1 某公司生產(chǎn)甲、乙兩種產(chǎn)品，分別經(jīng)由i、ii兩個車間生產(chǎn)。已知除外購?fù)?，生產(chǎn)一件甲產(chǎn)品需要i車間加工4小時，ii車間裝配2小時，生產(chǎn)一件乙產(chǎn)品需i車間加工1小時，ii車間裝配3小時，這兩種產(chǎn)品生產(chǎn)出來以后均需經(jīng)過檢驗、銷售等環(huán)節(jié)。已知每件甲產(chǎn)品的檢驗銷售費用需40元，每件乙產(chǎn)品的檢驗銷售費用需50元。i車間每

2、月可利用的工時為150小時，每小時的費用為80元；ii車間每月可利用的工時為200小時，每小時的費用為20元，估計下一年度平均每月可銷售甲產(chǎn)品100臺，乙產(chǎn)品80臺。公司根據(jù)這些實際情況定出月度計劃的目標(biāo)如下：p1：檢驗和銷售費用每月不超過6000元；p2：每月售出甲產(chǎn)品不少于100件；p3：i、ii兩車間的生產(chǎn)工時應(yīng)該得到充分利用；p4：i車間加班時間不超過30小時；p5：每月乙產(chǎn)品的銷售不少于80件。試確定該公司為完成上述目標(biāo)應(yīng)制定的月度生產(chǎn)計劃，建立其目標(biāo)規(guī)劃模型。解：先建立目標(biāo)規(guī)劃的數(shù)學(xué)模型。設(shè)x1為每月計劃生產(chǎn)的甲產(chǎn)品件數(shù)，x2為每月生產(chǎn)的乙產(chǎn)品的件數(shù)。根據(jù)題目中給出的優(yōu)先等級條件，

3、有以下目標(biāo)及約束：（1） 檢驗及銷售費用目標(biāo)及約束；（2） 每月甲產(chǎn)品的銷售目標(biāo)及約束；（3） i、ii兩車間工時利用情況目標(biāo)及約束i車間，ii車間（4） i車間加班時間目標(biāo)及約束（5） 每月乙產(chǎn)品銷售目標(biāo)及約束根據(jù)優(yōu)先等級層次，確定優(yōu)先因子和權(quán)系數(shù)，得出目標(biāo)規(guī)劃的數(shù)學(xué)模型如下：例6-2 有三個產(chǎn)地向四個銷地供應(yīng)物資。產(chǎn)地ai(i=1,2,3)的供應(yīng)量ai、銷地bj(j=1,2,3,4)的需要量bj、各產(chǎn)銷地之間的單位物資運費cij如表5-1所示。表中，ai和bj的單位為噸，cij的單位為元/噸。編制調(diào)運方案時要求按照相應(yīng)的優(yōu)先級依次考慮下列六個目標(biāo)：p1：b4是重點保證單位，其需要量應(yīng)盡可能

4、全部滿足；p2：a3向b1提供的物資不少于100噸；p3：每個銷地得到的物資數(shù)量不少于其需要量的80%；p4：實際的總運費不超過當(dāng)不考慮p1至p6各目標(biāo)時的最小總運費的110%；p5：因路況原因，盡量避免安排a2的物資運往b4；p6：對b1和b3的供應(yīng)率要盡可能相同；試建立該問題的目標(biāo)規(guī)劃模型。表6-1 bj cijaib1b2b3b4aia15267300a23546200a34523400bj200100450250解：設(shè)xij為從ai運往bj的運輸量，首先求出當(dāng)不考慮p1至p6各目標(biāo)時的最小總運費為2950元。在各級目標(biāo)中沒有涉及到供應(yīng)量，因此供應(yīng)量構(gòu)成硬約束：根據(jù)各優(yōu)先級目標(biāo)，可寫出相

5、應(yīng)的目標(biāo)及目標(biāo)約束。p1：b4是重點保證單位，其需要量應(yīng)盡可能全部滿足p2：a3向b1提供的物資不少于100噸p3：每個銷地得到的物資數(shù)量不少于其需要量的80%p4：實際的總運費不超過當(dāng)不考慮p1至p6各目標(biāo)時的最小總運費的110%。p5：因路況原因，盡量避免安排a2的物資運往b4p6：對b1和b3的供應(yīng)率要盡可能相同綜上所述，將該問題列成優(yōu)先目標(biāo)規(guī)劃模型：題型ii 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法就是通過圖形來確定所給目標(biāo)規(guī)劃的滿意解，雖然比較直觀，但因為是平面圖，所以最多只能求解包含兩個決策變量的目標(biāo)規(guī)劃問題。其解題步驟是：第一步，建立直角坐標(biāo)系，作出硬約束的限制區(qū)域；第二步，作出其他約束

6、條件當(dāng)偏差變量為0時的圖形，確定其它各約束條件的限制區(qū)域；第三步，結(jié)合決策變量的可行范圍，按優(yōu)先因子考察各偏差變量的變化對目標(biāo)函數(shù)的影響，確定盡可能滿足目標(biāo)的滿意解。例6-3 用圖解法找出以下目標(biāo)規(guī)劃問題的滿意解。解：第一步，因為本題沒有硬約束，所以先作出偏差變量為0時，各目標(biāo)約束所確定的直線，如圖5-1所示。第二步，按優(yōu)先因子考慮各偏差變量的變化對目標(biāo)函數(shù)的影響，確定約束條件所限定的x1,x2范圍。要滿足，只能在cd射線上取得滿意解；顯然，在cd射線上，。其次，在cd射線上使達到極小點的只能是c點。第三步，確定滿意解。由圖6-1可知，滿意解為x1dc50100/8ba20/304f100/6

7、ex2-53x1+5x2=208x1+6x2=100x1-10x2=50圖6-1例6-4 用圖解法找出以下目標(biāo)規(guī)劃問題的滿意解。解：第一步，首先作出硬約束等式直線ab：第二步，再作出偏差變量為0時，各目標(biāo)約束所確定的直線di和ch，如圖6-2所示。第三步，按優(yōu)先因子考慮各偏差變量的變化對目標(biāo)函數(shù)的影響，確定約束條件所限定的x1,x2范圍。要滿足，并且滿足硬約束所在范圍，只能在gc線段上取得滿意解；而要滿足，滿意解又只能是在ce線段上。第三步，確定滿意解。由圖6-2可得滿意解為c(0，5.2)和e（0.6，4.7）連線上任一點。0dcbefgahix2x1x1+2x2=1010x1+12x2=6

8、2.42x1+x2=8圖6-2題型iii 目標(biāo)規(guī)劃的單純形法例6-5 用單純形法求以下目標(biāo)規(guī)劃問題的滿意解。解：第一步，將原規(guī)劃化為標(biāo)準(zhǔn)型第二步，取為初始基變量，列初始單純形表，如表6-2所示。表6-2cj000p20p1p1cbxbbx1x2x3p2101201-10010/2p162.410120001-162.4/120x3821100008/1cj-zjp1-10-1200002p2-1-200100第三步，取k=1，檢查檢驗數(shù)的p1行的負數(shù)，取最小者-12對應(yīng)的變量x2為換入變量，并用最小比值原則確定換出變量為，見表6-3。表6-3cj000p20p1p1cbxbbx1x2x30x2

9、51/2101/2-1/200-p12.4400-661-12.4/60x333/201-1/21/2003/(1/2)cj-zjp1-4006-602p20001000第四步，還是取k=1，檢查檢驗數(shù)的p1行的負數(shù)，取最小值-6對應(yīng)的變量為換入變量，并用最小比值規(guī)則確定換出變量，見表6-4。表6-4cj000p20p1p1cbxbbx1x2x30x25.25/610001/12-1/12-00.42/300-111/6-1/60x32.87/60100-1/121/12cj-zjp10000011p20001000第五步，檢查檢驗數(shù)的p1行，p2行，都沒有負數(shù)了，故得到滿意解。且因為非基變量

10、x1的檢驗數(shù)為0，所以存在多重解。例6-6用單純形法求解下列目標(biāo)規(guī)劃問題。解：第一步：該問題已經(jīng)化為標(biāo)準(zhǔn)形，以，為基變量，建立初始單純形表，如表6-5所示。表6-5 初始單純性表b10111-1000000410001-10000565300001-10012110000001-1cj-zjp10002030000p20000000001p3-5-300000100第二步：在表6-5中，檢驗數(shù)矩陣中第一列、第二列均有負數(shù)，因此此表對應(yīng)的解不是滿意解，需要進行迭代。以為進基變量，為出基變量，進行基變換運算，結(jié)果如表6-6所示。表6-6 第一次迭代表b6011-1-110000410001-10000360300-551-10080100-11001-1cj-zjp10002030000p20000000001p30-3005-50100第三步：在表5-6中，檢驗數(shù)矩陣中第二列仍有負數(shù)，以為進基變量，為出基變量，進行基變換運算，結(jié)果如表6-7所示。表6-7 第二次迭代表b6011-1-110000410001-1000