運(yùn)籌學(xué)之目標(biāo)規(guī)劃

1、第七章 目標(biāo)規(guī)劃7.1 7.1 目標(biāo)規(guī)劃模型目標(biāo)規(guī)劃模型7.2 7.2 目標(biāo)規(guī)劃的幾何意義與圖解法目標(biāo)規(guī)劃的幾何意義與圖解法7.3 7.3 目標(biāo)規(guī)劃求解的單純形方法目標(biāo)規(guī)劃求解的單純形方法 在科學(xué)研究、經(jīng)濟(jì)建設(shè)和生產(chǎn)實(shí)踐中，人們在科學(xué)研究、經(jīng)濟(jì)建設(shè)和生產(chǎn)實(shí)踐中，人們經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我經(jīng)常遇到一類含有多個目標(biāo)的數(shù)學(xué)規(guī)劃問題，我們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目們稱之為多目標(biāo)規(guī)劃。本章介紹一種特殊的多目標(biāo)規(guī)劃叫目標(biāo)規(guī)劃標(biāo)規(guī)劃叫目標(biāo)規(guī)劃(goal programming)，這是美，這是美國學(xué)者國學(xué)者Charnes等在等在1952年提出來的。目標(biāo)規(guī)劃年提出來的。目標(biāo)規(guī)劃

2、在實(shí)踐中的應(yīng)用十分廣泛，它的重要特點(diǎn)是對各在實(shí)踐中的應(yīng)用十分廣泛，它的重要特點(diǎn)是對各個目標(biāo)分級加權(quán)與逐級優(yōu)化，這符合人們處理問個目標(biāo)分級加權(quán)與逐級優(yōu)化，這符合人們處理問題要分別輕重緩急保證重點(diǎn)的思考方式。題要分別輕重緩急保證重點(diǎn)的思考方式。 本章分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義本章分目標(biāo)規(guī)劃模型、目標(biāo)規(guī)劃的幾何意義與圖解法和求解目標(biāo)規(guī)劃的單純形方法等三個部與圖解法和求解目標(biāo)規(guī)劃的單純形方法等三個部分進(jìn)行介紹。分進(jìn)行介紹。 7.1 目標(biāo)規(guī)劃模型 (1) 問題提出問題提出 為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路為了便于理解目標(biāo)規(guī)劃數(shù)學(xué)模型的特征及建模思路, 我們首先舉一個簡單的例子來說明我

3、們首先舉一個簡單的例子來說明. 例例 1 某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和和B ，每周生產(chǎn)線運(yùn)行時間為，每周生產(chǎn)線運(yùn)行時間為60小時，生產(chǎn)一臺小時，生產(chǎn)一臺A產(chǎn)品產(chǎn)品需要需要4小時，生產(chǎn)一臺小時，生產(chǎn)一臺B產(chǎn)品需要產(chǎn)品需要6小時根據(jù)市場預(yù)小時根據(jù)市場預(yù)測，測，A、B產(chǎn)品平均銷售量分別為每周產(chǎn)品平均銷售量分別為每周9、8臺，它們臺，它們銷售利潤分別為銷售利潤分別為12、18萬元。在制定生產(chǎn)計(jì)劃時，萬元。在制定生產(chǎn)計(jì)劃時，經(jīng)理考慮下述經(jīng)理考慮下述4項(xiàng)目標(biāo)：項(xiàng)目標(biāo)： 首先，產(chǎn)量不能超過市場預(yù)測的銷售量；首先，產(chǎn)量不能超過市場預(yù)測的銷售量； 其次，工人加班時間最

4、少；其次，工人加班時間最少； 第三，希望總利潤最大；第三，希望總利潤最大； 最后，要盡可能滿足市場需求最后，要盡可能滿足市場需求, 當(dāng)不能滿足時當(dāng)不能滿足時, 市場認(rèn)為市場認(rèn)為B產(chǎn)品的重要性是產(chǎn)品的重要性是A產(chǎn)品的產(chǎn)品的2倍倍 試建立這個問題的數(shù)學(xué)模型試建立這個問題的數(shù)學(xué)模型討論：討論： 若把總利潤最大看作目標(biāo)，而把產(chǎn)量不能超過市若把總利潤最大看作目標(biāo)，而把產(chǎn)量不能超過市場預(yù)測的銷售量、工人加班時間最少和要盡可能滿場預(yù)測的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標(biāo)看作約束，則可建立一個單目標(biāo)足市場需求的目標(biāo)看作約束，則可建立一個單目標(biāo)線性規(guī)劃模型線性規(guī)劃模型 。設(shè)決策變量設(shè)決策變量

5、x1，x2 分別為產(chǎn)品分別為產(chǎn)品A，B的產(chǎn)量的產(chǎn)量 Max Z = 12x1 + 18x2 s.t. 4x1 + 6x2 60 x1 9 x2 8 x1 , x2 0 n容易求得上述線性規(guī)劃的最優(yōu)解為容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T 到到 (3,8)T 所在線段所在線段上的點(diǎn)上的點(diǎn), 最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為Z* = 180, 即可選方案有多種即可選方案有多種. n在實(shí)際上在實(shí)際上, 這個結(jié)果并非完全符合決策者的要求這個結(jié)果并非完全符合決策者的要求, 它只實(shí)現(xiàn)它只實(shí)現(xiàn)了經(jīng)理的第一、二、三條目標(biāo)，而沒有達(dá)到最后的一個目標(biāo)。了經(jīng)理的第一、二、三條目標(biāo)，而沒有達(dá)到最后的一個目標(biāo)。進(jìn)一步分析

6、可知，要實(shí)現(xiàn)全體目標(biāo)是不可能的。進(jìn)一步分析可知，要實(shí)現(xiàn)全體目標(biāo)是不可能的。(2) 目標(biāo)規(guī)劃模型的基本概念目標(biāo)規(guī)劃模型的基本概念 把例把例1的的4個目標(biāo)表示為不等式個目標(biāo)表示為不等式.仍設(shè)決策仍設(shè)決策變量變量 x1，x2 分別為產(chǎn)品分別為產(chǎn)品A，B的產(chǎn)量的產(chǎn)量. 那么那么, 第一個目標(biāo)為第一個目標(biāo)為: x1 9 ，x2 8 ； 第二個目標(biāo)為第二個目標(biāo)為: 4x1 + 6x2 60 ； 第三個目標(biāo)為第三個目標(biāo)為: 希望總利潤最大，要表示成不希望總利潤最大，要表示成不等式需要找到一個目標(biāo)上界，這里可以估計(jì)為等式需要找到一個目標(biāo)上界，這里可以估計(jì)為252（=12 9 + 18 8），于是有），于是有

7、12x1 + 18x2 252； 第四個目標(biāo)為第四個目標(biāo)為: x1 9，x2 8； 下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念下面引入與建立目標(biāo)規(guī)劃數(shù)學(xué)模型有關(guān)的概念 （1）正、負(fù)偏差變量）正、負(fù)偏差變量d +，d - 我們用正偏差變量我們用正偏差變量d + 表示決策值超過目標(biāo)值的表示決策值超過目標(biāo)值的部分；負(fù)偏差變量部分；負(fù)偏差變量d - 表示決策值不足目標(biāo)值的表示決策值不足目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時又末部分。因決策值不可能既超過目標(biāo)值同時又末達(dá)到目標(biāo)值，故恒有達(dá)到目標(biāo)值，故恒有 d + d - 0 （2）絕對約束和目標(biāo)約束）絕對約束和目標(biāo)約束 我們把所有等式、不等式約束分為

8、兩部分：絕我們把所有等式、不等式約束分為兩部分：絕對約束和目標(biāo)約束。對約束和目標(biāo)約束。絕對約束絕對約束 指必須嚴(yán)格滿足的等式約束和不等式約束；如在線指必須嚴(yán)格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。設(shè)例條件的解稱為非可行解，所以它們是硬約束。設(shè)例1 中生產(chǎn)中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有限制，并且無產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補(bǔ)充，則構(gòu)成絕對約束。法從其它渠道予以補(bǔ)充，則構(gòu)成絕對約束。目標(biāo)約束目標(biāo)約束 目標(biāo)規(guī)劃特有的，我們可以把約束右端項(xiàng)看作要努目標(biāo)規(guī)劃

9、特有的，我們可以把約束右端項(xiàng)看作要努力追求的目標(biāo)值，但允許發(fā)生正式負(fù)偏差，用在約力追求的目標(biāo)值，但允許發(fā)生正式負(fù)偏差，用在約束中加入正、負(fù)偏差變量來表示，于是稱它們是軟束中加入正、負(fù)偏差變量來表示，于是稱它們是軟約束。約束。對于例對于例1, 我們有如下目標(biāo)約束我們有如下目標(biāo)約束 x1 + d1- -d1+ = 9 (1) x2 + d2- -d2+ = 8 (2) 4x1 + 6x2 + d3- -d3+ = 60 (3)12x1+18x2 + d4- -d4+ =252 (4) (3) 優(yōu)先因子與權(quán)系數(shù)優(yōu)先因子與權(quán)系數(shù) 對于多目標(biāo)問題，設(shè)有對于多目標(biāo)問題，設(shè)有L個目標(biāo)函數(shù)個目標(biāo)函數(shù)f1,f2

10、,fL, 決策決策者在要求達(dá)到這些目標(biāo)時，一般有主次之分。為此，者在要求達(dá)到這些目標(biāo)時，一般有主次之分。為此，我們引入優(yōu)先因子我們引入優(yōu)先因子Pi ，i = 1,2,L.無妨設(shè)預(yù)期的目無妨設(shè)預(yù)期的目標(biāo)函數(shù)優(yōu)先順序?yàn)闃?biāo)函數(shù)優(yōu)先順序?yàn)閒1,f2,fL,我們把要求第一位達(dá)到我們把要求第一位達(dá)到的目標(biāo)賦于優(yōu)先因子的目標(biāo)賦于優(yōu)先因子P1，次位的目標(biāo)賦于優(yōu)先因子，次位的目標(biāo)賦于優(yōu)先因子P2、，并規(guī)定，并規(guī)定 Pi Pi+1，i = 1,2,L-1. 即在計(jì)算過程中即在計(jì)算過程中, 首先保證首先保證P1級目標(biāo)的實(shí)現(xiàn)，這時級目標(biāo)的實(shí)現(xiàn)，這時可不考慮次級目標(biāo)；而可不考慮次級目標(biāo)；而P2級目標(biāo)是在實(shí)現(xiàn)級目標(biāo)是在實(shí)

11、現(xiàn)P1級目標(biāo)級目標(biāo)的基礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同的基礎(chǔ)上考慮的，以此類推。當(dāng)需要區(qū)別具有相同優(yōu)先因子的若干個目標(biāo)的差別時，可分別賦于它們優(yōu)先因子的若干個目標(biāo)的差別時，可分別賦于它們不同的權(quán)系數(shù)不同的權(quán)系數(shù)wj 。優(yōu)先因子及權(quán)系數(shù)的值，均由決。優(yōu)先因子及權(quán)系數(shù)的值，均由決策者按具體情況來確定策者按具體情況來確定 （4）目標(biāo)規(guī)劃的目標(biāo)函效）目標(biāo)規(guī)劃的目標(biāo)函效 目標(biāo)規(guī)劃的目標(biāo)函數(shù)是通過各目標(biāo)約束目標(biāo)規(guī)劃的目標(biāo)函數(shù)是通過各目標(biāo)約束的正、負(fù)偏差變量和賦于相應(yīng)的優(yōu)先等級來的正、負(fù)偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的構(gòu)造的 決策者的要求是盡可能從某個方向縮小決策者的要求是盡可能從某個方向縮小偏

12、離目標(biāo)的數(shù)值。于是，目標(biāo)規(guī)劃的目標(biāo)函偏離目標(biāo)的數(shù)值。于是，目標(biāo)規(guī)劃的目標(biāo)函數(shù)應(yīng)該是求極?。簲?shù)應(yīng)該是求極?。篗in f f （d +，d -) 其基本形式有三種：其基本形式有三種： 要求恰好達(dá)到目標(biāo)值，即使相應(yīng)目標(biāo)約要求恰好達(dá)到目標(biāo)值，即使相應(yīng)目標(biāo)約束的正、負(fù)偏差變量都要盡可能地小。束的正、負(fù)偏差變量都要盡可能地小。 這時取這時取 Min （d + + d - )； 要求不超過目標(biāo)值，即使相應(yīng)目標(biāo)約束要求不超過目標(biāo)值，即使相應(yīng)目標(biāo)約束的正偏差變量要盡可能地小。的正偏差變量要盡可能地小。 這時取這時取 Min （d + )； 要求不低于目標(biāo)值，即使相應(yīng)目標(biāo)約束要求不低于目標(biāo)值，即使相應(yīng)目標(biāo)約束的負(fù)

13、偏差變量要盡可能地小。的負(fù)偏差變量要盡可能地小。 這時取這時取 Min （d - )； 對于例對于例 1, 我們根據(jù)決策者的考慮知我們根據(jù)決策者的考慮知 第一優(yōu)先級要求第一優(yōu)先級要求 Min（d1+ + d2+ )； 第二優(yōu)先級要求第二優(yōu)先級要求 Min（d3+ )； 第三優(yōu)先級要求第三優(yōu)先級要求 Min（d4- )； 第四優(yōu)先級要求第四優(yōu)先級要求 Min（d1- + 2d2- )， 這里這里, 當(dāng)不能滿足市場需求時當(dāng)不能滿足市場需求時, 市場認(rèn)為市場認(rèn)為B產(chǎn)產(chǎn)品的重要性是品的重要性是A產(chǎn)品的產(chǎn)品的2倍即減少倍即減少B產(chǎn)品的產(chǎn)品的影響是影響是A產(chǎn)品的產(chǎn)品的2倍，因此我們引入了倍，因此我們引入了

14、2:1的的權(quán)系數(shù)。權(quán)系數(shù)。 綜合上述分析，可得到下列目標(biāo)規(guī)劃模型綜合上述分析，可得到下列目標(biāo)規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ = 252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. (3) (3) 目標(biāo)規(guī)劃模型的一般形式目標(biāo)規(guī)劃模型的一般形式 ,L1,2,0,l,dd,n1,2,0,jx,m1,2,

15、i,b,xa,L1,2,l,gddxcs.t.ddMMinlljn1jijijn1jllljljK1kL1llkllklk式中的第二行是式中的第二行是L個目標(biāo)約束，第三行是個目標(biāo)約束，第三行是m個絕對約束，個絕對約束，clj 和和gl 是目標(biāo)參數(shù)。是目標(biāo)參數(shù)。n例例2n 甲甲 乙乙 有效工時有效工時 金工金工 4 2 400 裝配裝配 2 4 500 收益收益 100 80 nLP： Max Z=100X1 + 80X2 2X1+4X2 500 s.t 4X1+2X2 400 X* =(50,100) X1 , X2 0 Z* =13000 目標(biāo)：去年總收益目標(biāo)：去年總收益9000，增長要求，

16、增長要求11.1% 即：今年希望總收益不低于即：今年希望總收益不低于10000引入引入 d+：決策超過目標(biāo)值部分：決策超過目標(biāo)值部分(正偏差變量正偏差變量) d-：決策不足目標(biāo)值部分：決策不足目標(biāo)值部分(負(fù)偏差變量負(fù)偏差變量)目標(biāo)約束：目標(biāo)約束： 100X1+80X2 -d+d- =10000 d+d- =0 d+,d- 0Min Z= d- 100X1+80X2 -d+d- =10000 4X1+ 2X2 400 2X1+ 4X2 500 X1 , X2 , d- , d+ 0 d+d- =0例例3n 資源擁有量資源擁有量 原材料原材料(公斤公斤) 2 1 11 設(shè)備設(shè)備(小時小時) 1 2

17、 10 利潤利潤(千元千元/件件) 8 101.原材料價格上漲，超計(jì)劃要高價購買，所以要嚴(yán)原材料價格上漲，超計(jì)劃要高價購買，所以要嚴(yán)格控制格控制2.市場情況，產(chǎn)品市場情況，產(chǎn)品銷售量下降，產(chǎn)品銷售量下降，產(chǎn)品的產(chǎn)量不的產(chǎn)量不大于產(chǎn)品大于產(chǎn)品的產(chǎn)量的產(chǎn)量3.充分利用設(shè)備，不希望加班充分利用設(shè)備，不希望加班4.盡可能達(dá)到并超過利潤計(jì)劃指標(biāo)盡可能達(dá)到并超過利潤計(jì)劃指標(biāo)56千元千元建模：建模：1.設(shè)定約束條件。設(shè)定約束條件。(目標(biāo)約束、絕對約束目標(biāo)約束、絕對約束)2.規(guī)定目標(biāo)約束優(yōu)先級規(guī)定目標(biāo)約束優(yōu)先級3.建立模型建立模型 設(shè)設(shè)X1 ，X2為產(chǎn)品為產(chǎn)品，產(chǎn)品，產(chǎn)品產(chǎn)量產(chǎn)量。2X1+X2 11X1 -X

18、2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56X1 , X2 , di- , di+ 0 di- di+ =0d1- : X1產(chǎn)量不足產(chǎn)量不足X2 部分部分d1+ : X1產(chǎn)量超過產(chǎn)量超過X2 部分部分d2- : 設(shè)備使用不足設(shè)備使用不足10 部分部分d2+ :設(shè)備使用超過設(shè)備使用超過10 部分部分d3- : 利潤不足利潤不足56 部分部分d3+ :利潤超過利潤超過56 部分部分或或 Min Z1 = d1+ Min Z2 = d2- +d2+ Min Z3 = d3- Min Z=p1d1+p2(d2-+d2+)+p3(d3-)

19、例例4 電視機(jī)廠裝配電視機(jī)廠裝配25寸和寸和21寸兩種彩電，每臺電視機(jī)寸兩種彩電，每臺電視機(jī)需裝備時間需裝備時間1小時，每周裝配線計(jì)劃開動小時，每周裝配線計(jì)劃開動40小時，小時，預(yù)計(jì)每周預(yù)計(jì)每周25寸彩電銷售寸彩電銷售24臺，每臺可獲利臺，每臺可獲利80元，元，每周每周21寸彩電銷售寸彩電銷售30臺，每臺可獲利臺，每臺可獲利40元。元。該廠目標(biāo)：該廠目標(biāo)：1. 充分利用裝配線，避免開工不足。充分利用裝配線，避免開工不足。2. 允許裝配線加班，但盡量不超過允許裝配線加班，但盡量不超過10小時。小時。3. 盡量滿足市場需求。盡量滿足市場需求。解：設(shè)解：設(shè)X1 , X2 分別表示分別表示25寸，寸，

20、21寸彩電產(chǎn)量寸彩電產(chǎn)量Min Z=p1d1-+p2d2+p3(2d3-+d4-)X1+X2 +d1- -d1+=40X1 +X2+d2- -d2+=50X1 +d3- -d3+=24 X2 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4) 對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，對只具有兩個決策變量的目標(biāo)規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來分析求解通過圖解示例，可我們可以用圖解法來分析求解通過圖解示例，可以看到目標(biāo)規(guī)劃中優(yōu)先因子，正、負(fù)偏差變量及權(quán)以看到目標(biāo)規(guī)劃中優(yōu)先因子，正、負(fù)偏差變量及權(quán)系數(shù)等的幾何意義。系數(shù)等的幾何意義。 下面用圖解法來求解例下

21、面用圖解法來求解例1 我們先在平面直角坐標(biāo)系的第一象限內(nèi)，作出與我們先在平面直角坐標(biāo)系的第一象限內(nèi)，作出與各約束條件對應(yīng)的直線，然后在這些直線旁分別標(biāo)各約束條件對應(yīng)的直線，然后在這些直線旁分別標(biāo)上上 G-i ，i = 1，2，3，4。圖中。圖中x，y分別表示問題分別表示問題的的x1和和x2；各直線移動使之函數(shù)值變大、變小的方；各直線移動使之函數(shù)值變大、變小的方向用向用 +、- 表示表示 di+ ,di- 7.2 目標(biāo)規(guī)劃的幾何意義及圖解法圖圖 10 5 10 15 20 yx2015105+-G-1+-G-2+-G-3G-4+- 下面我們根據(jù)目標(biāo)函數(shù)的優(yōu)先因子來分下面我們根據(jù)目標(biāo)函數(shù)的優(yōu)先因子

22、來分析求解首先考慮第一級具有析求解首先考慮第一級具有P1優(yōu)先因子的優(yōu)先因子的目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)目標(biāo)的實(shí)現(xiàn)，在目標(biāo)函數(shù)中要求實(shí)現(xiàn)Min（d1+ d2+ ),取取d1+=d2+ =0.圖圖2 中淺紅色陰影中淺紅色陰影部分即表示出該最優(yōu)解集合的所有點(diǎn)。部分即表示出該最優(yōu)解集合的所有點(diǎn)。 我們在第一級目標(biāo)的最優(yōu)解集合中找滿我們在第一級目標(biāo)的最優(yōu)解集合中找滿足第二優(yōu)先級要求足第二優(yōu)先級要求Min（d3+ )的最優(yōu)解的最優(yōu)解.取取d3+= 0 ,可得到圖可得到圖3 中淺綠陰影部分即是滿足中淺綠陰影部分即是滿足第一、第二優(yōu)先級要求的最優(yōu)解集合。第一、第二優(yōu)先級要求的最優(yōu)解集合。 圖圖 20 5

23、 10 15 20 yx2015105+-G-1+-G-2+-G-3G-4+-圖圖 30 5 10 15 20 yx2015105+-G-1+-G-2+-G-3G-4+- 第三優(yōu)先級要求第三優(yōu)先級要求 Min（d4-)，根據(jù)圖示可知，根據(jù)圖示可知，d4- 不可能取不可能取0值，我們?nèi)∈怪担覀內(nèi)∈筪4- 最小的值最小的值72得到圖得到圖4中兩陰影部分的交線中兩陰影部分的交線(紅色粗線紅色粗線)，其表示滿足第，其表示滿足第一、第二及第三優(yōu)先級要求的最優(yōu)解集合。一、第二及第三優(yōu)先級要求的最優(yōu)解集合。 最后，考慮第四優(yōu)先級要求最后，考慮第四優(yōu)先級要求 Min（d1- + 2d2- ) ，即要在黑色粗

24、線段中找出最優(yōu)解。由于即要在黑色粗線段中找出最優(yōu)解。由于d1- 的權(quán)因的權(quán)因子小于子小于d2- ，因此在這里可以考慮取，因此在這里可以考慮取d2- =0。于是。于是解得解得d1-=5，最優(yōu)解為，最優(yōu)解為A點(diǎn)點(diǎn)x = 3，y = 8。 圖圖 40 5 10 15 20 yx2015105+-G-1+-G-2+-G-3G-4+-A(3,8)7.3 7.3 目標(biāo)規(guī)劃的單純形方法目標(biāo)規(guī)劃的單純形方法 目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的數(shù)學(xué)模型,特別是約束的結(jié)構(gòu)與特別是約束的結(jié)構(gòu)與線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)線性規(guī)劃模型沒有本質(zhì)的區(qū)別，只是它的目標(biāo)不止是一個不止是一個,雖然其利用優(yōu)先因子和權(quán)系數(shù)把

25、雖然其利用優(yōu)先因子和權(quán)系數(shù)把目標(biāo)寫成一個函數(shù)的形式目標(biāo)寫成一個函數(shù)的形式, 但在計(jì)算中無法按但在計(jì)算中無法按單目標(biāo)處理單目標(biāo)處理, 所以可用單純形法進(jìn)行適當(dāng)改進(jìn)所以可用單純形法進(jìn)行適當(dāng)改進(jìn)后求解。在組織、構(gòu)造算法時，我們要考慮目后求解。在組織、構(gòu)造算法時，我們要考慮目標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定：標(biāo)規(guī)劃的數(shù)學(xué)模型一些特點(diǎn)，作以下規(guī)定： (1) 因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求因?yàn)槟繕?biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是最小化，所以檢驗(yàn)數(shù)的最優(yōu)準(zhǔn)則與線性規(guī)劃是相同的；相同的； (2) 因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級的因?yàn)榉腔兞康臋z驗(yàn)數(shù)中含有不同等級的優(yōu)先

26、因子，優(yōu)先因子， Pi Pi+1，i = 1,2,L-1. 于是從每于是從每個檢驗(yàn)數(shù)的整體來看：個檢驗(yàn)數(shù)的整體來看： Pi+1（i = 1,2,L-1）優(yōu)）優(yōu)先級第先級第k個檢驗(yàn)數(shù)的正、負(fù)首先決定于個檢驗(yàn)數(shù)的正、負(fù)首先決定于 P1 ，P2 ， ，Pi 優(yōu)先級第優(yōu)先級第k個檢驗(yàn)數(shù)的正、負(fù)。若個檢驗(yàn)數(shù)的正、負(fù)。若P1 級第級第k個檢驗(yàn)數(shù)為個檢驗(yàn)數(shù)為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于，則此檢驗(yàn)數(shù)的正、負(fù)取決于P2級第級第k個檢驗(yàn)數(shù)；若個檢驗(yàn)數(shù)；若P2 級第級第k個檢驗(yàn)數(shù)仍為個檢驗(yàn)數(shù)仍為0，則此檢驗(yàn)數(shù)的正、負(fù)取決于則此檢驗(yàn)數(shù)的正、負(fù)取決于P3級第級第k個檢驗(yàn)數(shù)，個檢驗(yàn)數(shù)，依次類推。換一句話說，當(dāng)某依次類推。

27、換一句話說，當(dāng)某Pi 級第級第k個檢驗(yàn)數(shù)個檢驗(yàn)數(shù)為負(fù)數(shù)時，計(jì)算中不必再考察為負(fù)數(shù)時，計(jì)算中不必再考察Pj（ j I ）級第）級第k個檢驗(yàn)數(shù)的正、負(fù)情況；個檢驗(yàn)數(shù)的正、負(fù)情況； （3）根據(jù)目標(biāo)規(guī)劃模型特征，當(dāng)不含絕對約束）根據(jù)目標(biāo)規(guī)劃模型特征，當(dāng)不含絕對約束時，時，di- （i=1,2, ,K）構(gòu)成了一組基本可行解。在）構(gòu)成了一組基本可行解。在尋找單純形法初始可行點(diǎn)時，這個特點(diǎn)是很有用的。尋找單純形法初始可行點(diǎn)時，這個特點(diǎn)是很有用的。 解目標(biāo)規(guī)劃問題的單純形法的計(jì)算步驟解目標(biāo)規(guī)劃問題的單純形法的計(jì)算步驟 (1)建立初始單純形表在表中將檢驗(yàn)數(shù)行按優(yōu)建立初始單純形表在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個數(shù)分別

28、列成先因子個數(shù)分別列成K行。初始的檢驗(yàn)數(shù)需根據(jù)初行。初始的檢驗(yàn)數(shù)需根據(jù)初始可行解計(jì)算出來，方法同基本單純形法。當(dāng)不含始可行解計(jì)算出來，方法同基本單純形法。當(dāng)不含絕對約束時，絕對約束時，di- （i=1,2, ,K）構(gòu)成了一組基本可）構(gòu)成了一組基本可行解，這時只需利用相應(yīng)單位向量把各級目標(biāo)行中行解，這時只需利用相應(yīng)單位向量把各級目標(biāo)行中對應(yīng)對應(yīng)di- （i=1,2, ,K）的量消成）的量消成0即可得到初始單即可得到初始單純形表。置純形表。置k 1； (2)檢查當(dāng)前第檢查當(dāng)前第k行中是否存在小于行中是否存在小于0，且對應(yīng)的前，且對應(yīng)的前k-1行的同列檢驗(yàn)數(shù)為零的檢驗(yàn)數(shù)。若有取其中最小行的同列檢驗(yàn)數(shù)

29、為零的檢驗(yàn)數(shù)。若有取其中最小者對應(yīng)的變量為換入變量，轉(zhuǎn)者對應(yīng)的變量為換入變量，轉(zhuǎn)(3)。若無這樣的檢驗(yàn)。若無這樣的檢驗(yàn)數(shù)，則轉(zhuǎn)數(shù)，則轉(zhuǎn)(5)； (3)按單純形法中的最小比值規(guī)則確定換出變量，按單純形法中的最小比值規(guī)則確定換出變量，當(dāng)存在兩個和兩個以上相同的最小比值時，選取具當(dāng)存在兩個和兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)（有較高優(yōu)先級別的變量為換出變量，轉(zhuǎn)（4）；）； (4)按單純形法進(jìn)行換基運(yùn)算，建立新的單純形表，按單純形法進(jìn)行換基運(yùn)算，建立新的單純形表，（注意：要對所有的行進(jìn)行初等變換運(yùn)算）返回（注意：要對所有的行進(jìn)行初等變換運(yùn)算）返回(2)； (5)當(dāng)當(dāng)k

30、K 時，計(jì)算結(jié)束。表中的解即為滿意解。時，計(jì)算結(jié)束。表中的解即為滿意解。否則置否則置k = k+1，返回（，返回（2）。）。 例例 1 試用單純形法來求解例試用單純形法來求解例1的目標(biāo)規(guī)劃模型的目標(biāo)規(guī)劃模型 Min f = P1（d1+ + d2+ ) + P2 d3+ + P3 d4- + P4（d1- + 2d2- ) s.t. x1 + d1- -d1+ = 9 x2 + d2- -d2+ = 8 4x1 + 6x2 + d3- -d3+ = 60 12x1 + 18x2 +d4- -d4+ =252 x1 , x2 , di- ,di+ 0 , i = 1,2,3,4. 解解: 首先處

31、理初始基本可行解對應(yīng)的各級檢驗(yàn)數(shù)。首先處理初始基本可行解對應(yīng)的各級檢驗(yàn)數(shù)。Cj 0 0 P1 P4 P1 2 P4 P2 0 0 P3 CB XB b x1 x2 d1+ d1- d2+ d2- d3+ d3- d4+ d4- P4 d1- 9 1 0 -1 1 0 0 0 0 0 0 2 P4 d2- 8 0 1 0 0 -1 1 0 0 0 0 0 d3- 60 4 6 0 0 0 0 -1 1 0 0 P3 d4- 252 12 18 0 0 0 0 0 0 -1 1 P1 0 0 1 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 0 P3 -12 -18 0 0

32、 0 0 0 0 1 0 P4 -1 -2 -1 0 2 0 0 0 0 0 （1）k = 1，在初始單純形表中基變量為，在初始單純形表中基變量為 （d1-,d2-,d3-,d4-)T =（9，8 ， 60，252)T ；（2）因?yàn)椋┮驗(yàn)镻1與與P2優(yōu)先級的檢驗(yàn)數(shù)均已經(jīng)為非負(fù)，所優(yōu)先級的檢驗(yàn)數(shù)均已經(jīng)為非負(fù)，所以這個單純形表對以這個單純形表對P1與與P2優(yōu)先級是最優(yōu)單純形表；優(yōu)先級是最優(yōu)單純形表；（3）下面考慮）下面考慮P3優(yōu)先級，第二列的檢驗(yàn)數(shù)為優(yōu)先級，第二列的檢驗(yàn)數(shù)為-18，此，此為進(jìn)基變量，計(jì)算相應(yīng)的比值為進(jìn)基變量，計(jì)算相應(yīng)的比值 bi/aij 寫在寫在 列。通列。通過比較，得到過比較，得

33、到d2- 對應(yīng)的比值最小，于是取對應(yīng)的比值最小，于是取a22（標(biāo)（標(biāo)為為 * 號）為主元進(jìn)行矩陣行變換得到新的單純形表；號）為主元進(jìn)行矩陣行變換得到新的單純形表； （4）下面繼續(xù)考慮）下面繼續(xù)考慮P3優(yōu)先級，第一列的檢驗(yàn)數(shù)為優(yōu)先級，第一列的檢驗(yàn)數(shù)為 -12，此為進(jìn)基變量，計(jì)算相應(yīng)的比值此為進(jìn)基變量，計(jì)算相應(yīng)的比值 bi/aij ，得到，得到d3- 對應(yīng)對應(yīng)的比值最小，于是取的比值最小，于是取a31（標(biāo)為（標(biāo)為 * 號）為轉(zhuǎn)軸元進(jìn)行號）為轉(zhuǎn)軸元進(jìn)行矩陣行變換得到新的單純形表；矩陣行變換得到新的單純形表； Cj 0 0 P1 P4 P1 2 P4 P2 0 0 P3 CB XB b x1 x2 d

34、1+ d1- d2+ d2- d3+ d3- d4+ d4- P4 d1- 9 1 0 -1 1 0 0 0 0 0 0 0 x2 8 0 1 0 0 -1 1 0 0 0 0 0 d3- 12 4 0 0 0 6 -6 -1 1 0 0 P3 d4- 108 12 0 0 0 18 -18 0 0 -1 1 P1 0 0 1 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 0 P3 -12 0 0 0 -18 18 0 0 1 0 P4 -1 0 1 0 0 2 0 0 0 0 （5）當(dāng)前的單純形表各優(yōu)先級的檢驗(yàn)數(shù)均滿足了上述條）當(dāng)前的單純形表各優(yōu)先級的檢驗(yàn)數(shù)均滿足了上

35、述條件件, 故為最優(yōu)單純形表。我們得到最優(yōu)解故為最優(yōu)單純形表。我們得到最優(yōu)解x1=3，x2=8 。 Cj 0 0 P1 P4 P1 2 P4 P2 0 0 P3 CB XB b x1 x2 d1+ d1- d2+ d2- d3+ d3- d4+ d4- P4 d1- 6 0 0 -1 1 -3/2 3/2 1/4 -1/4 0 0 0 x2 8 0 1 0 0 -1 1 0 0 0 0 0 x1- 3 1 0 0 0 3/2 -3/2 -1/4 1/4 0 0 P3 d4- 72 0 0 0 0 0 0 3 -3 -1 1 P1 0 0 1 0 1 1/2 0 0 0 0 P2 0 0 0 0

36、 0 0 1 0 0 0 P3 0 0 0 0 0 0 -3 3 1 0 P4 0 0 1 0 3/2 0 -1/4 1/4 0 0 例例4 4、電視機(jī)廠裝配、電視機(jī)廠裝配2525寸和寸和2121寸兩種彩電，每臺寸兩種彩電，每臺電視機(jī)需裝備時間電視機(jī)需裝備時間1 1小時，每周裝配線計(jì)劃開小時，每周裝配線計(jì)劃開動動4040小時，預(yù)計(jì)每周小時，預(yù)計(jì)每周2525寸彩電銷售寸彩電銷售2424臺，每臺臺，每臺可獲利可獲利8080元，每周元，每周2121寸彩電銷售寸彩電銷售3030臺，每臺可臺，每臺可獲利獲利4040元。元。該廠目標(biāo)：該廠目標(biāo)：1 1、充分利用裝配線，避免開工不足。、充分利用裝配線，避免開

37、工不足。2 2、允許裝配線加班，但盡量不超過、允許裝配線加班，但盡量不超過1010小時。小時。3 3、盡量滿足市場需求。、盡量滿足市場需求。解：設(shè)解：設(shè)X X1 1 , , X X2 2 分別表示分別表示2525寸，寸，2121寸彩電產(chǎn)量寸彩電產(chǎn)量Min Z=p1d1-+p2d2+p3(2d3-+d4-)X1+X2 +d1- -d1+=40X1 +X2+d2- -d2+=50X1+d3- -d3+=24X2 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4)Cj 0 0 0 p1 p2 0 0 2p3 0 p3 CB XB b x1 x2 d1+ d1-

38、 d2+ d2- d3+ d3- d4+ d4- p1 d1- 40 1 1 -1 1 0 0 0 0 0 0 0 d2- 50 1 1 0 0 -1 1 0 0 0 0 2 p3 d3- 24 1 0 0 0 0 0 -1 1 0 0 p3 d4- 30 0 1 0 0 0 0 0 0 -1 1 p1 -1 -1 1 0 0 0 0 0 0 0 p2 0 0 0 0 1 0 0 0 0 0 p3 -2 -1 0 0 0 0 2 0 1 0 Cj 0 0 0 p1 p2 0 0 2p3 0 p3 CB XB b x1 x2 d1+ d1- d2+ d2- d3+ d3- d4+ d4- p1

39、d1- 16 0 1 -1 1 0 0 1 -1 0 0 0 d2- 26 0 1 0 0 -1 1 1 -1 0 0 0 x1 24 1 0 0 0 0 0 -1 1 0 0 p3 d4- 30 0 1 0 0 0 0 0 0 -1 1 p1 0 -1 1 0 0 0 -1 1 0 0 p2 0 0 0 0 1 0 0 0 0 0 p3 0 -1 0 0 0 0 0 2 1 0 Cj 0 0 0 p1 p2 0 0 2p3 0 p3 CB XB b x1 x2 d1+ d1- d2+ d2- d3+ d3- d4+ d4- 0 x2 16 0 1 -1 1 0 0 1 -1 0 0 0 d2

40、- 10 0 0 1 -1 -1 1 0 0 0 0 0 x1 24 1 0 0 0 0 0 -1 1 0 0 p3 d4- 14 0 0 1 -1 0 0 -1 1 -1 1 p1 0 0 0 1 0 0 0 0 0 0 p2 0 0 0 0 1 0 0 0 0 0 p3 0 0 -1 1 0 0 1 1 1 0 Cj 0 0 0 p1 p2 0 0 2p3 0 p3 CB XB b x1 x2 d1+ d1- d2+ d2- d3+ d3- d4+ d4- 0 x2 26 0 1 0 0 -1 1 1 -1 0 0 0 d1+ 10 0 0 1 -1 -1 1 0 0 0 0 0 x1 24 1 0 0 0 0 0 -1 1 0 0 p3 d4- 4 0 0 0 0 1 -1 -1 1 -1 1 p1 0 0 0 1 0 0 0 0 0 0 p2 0 0 0 0 1 0 0 0 0 0 p3 0 0 0 0 -1 1 1 1 1 0 第七章習(xí)題2 選2 、6成本如下表：成本如下表：和單位生產(chǎn)和單位生產(chǎn)間和加班時間生產(chǎn)能力間和加班時間生產(chǎn)能力同類產(chǎn)品，該廠正常時同類產(chǎn)品，該廠正常時月月末提供不同數(shù)量的月月末提供不同數(shù)量的某廠根據(jù)合同要在三個某廠根據(jù)合同要在三個20040320月份月份 需求量需求量(件件)最大產(chǎn)量最大產(chǎn)量(件件)單位生產(chǎn)成本單位生產(chǎn)成本(元元)正常