1、數(shù)學(xué)建模簡(jiǎn)明教程,國(guó)家精品課程,第一章 規(guī)劃理論及模型,一、引言,二、線性規(guī)劃模型,三、整數(shù)線性規(guī)劃模型,四、0-1整數(shù)規(guī)劃模型,五、非線性規(guī)劃模型,六、多目標(biāo)規(guī)劃模型,七、動(dòng)態(tài)規(guī)劃模型,一、引言,我們從2005年“高教社杯”全國(guó)大學(xué)生數(shù)模競(jìng),賽的B題“DVD在線租賃”問(wèn)題的第二問(wèn)和第三問(wèn),談起.,其中第二個(gè)問(wèn)題是一個(gè)如何來(lái)分配有限資源，,從而達(dá)到人們期望目標(biāo)的優(yōu)化分配數(shù)學(xué)模型. 它,在運(yùn)籌學(xué)中處于中心的地位. 這類問(wèn)題一般可以,歸結(jié)為,數(shù)學(xué)規(guī)劃模型.,規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來(lái),來(lái)越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動(dòng)、軍事,行為核科學(xué)研究的各個(gè)方面，為社會(huì)節(jié)省的財(cái)富、,創(chuàng)造的價(jià)值無(wú)

2、法估量.,特別是在數(shù)模競(jìng)賽過(guò)程中，規(guī)劃模型是最常,見(jiàn)的一類數(shù)學(xué)模型. 從92-06年全國(guó)大學(xué)生數(shù)模競(jìng),越多的人所重視. 隨著計(jì)算機(jī)的逐漸普及，它越,賽試題的解題方法統(tǒng)計(jì)結(jié)果來(lái)看，規(guī)劃模型共出,現(xiàn)了15次，占到了50%，也就是說(shuō)每?jī)傻栏?jìng)賽題,中就有一道涉及到利用規(guī)劃理論來(lái)分析、求解.,二、線性規(guī)劃模型,線性規(guī)劃模型是所有規(guī)劃模型中最基本、最,例1 （食譜問(wèn)題）設(shè)有 n 種食物，各含 m 種營(yíng)養(yǎng),素，第 j 種食物中第 i 中營(yíng)養(yǎng)素的含量為 aij , n 種,食物價(jià)格分別為c1, c2, , cn，請(qǐng)確定食譜中n 種食,物的數(shù)量x1, x2, , xn，要求在食譜中 m 種營(yíng)養(yǎng)素,簡(jiǎn)單的一種.,

3、2.1 線性規(guī)劃模型的標(biāo)準(zhǔn)形式,的含量分別不低于b1, b2, , bm 的情況下，使得總,的費(fèi)用最低.,首先根據(jù)食物數(shù)量及價(jià)格可寫出食譜費(fèi)用為,其次食譜中第 i 種營(yíng)養(yǎng)素的含量為,因此上述問(wèn)題可表述為：,解,上述食譜問(wèn)題就是一個(gè)典型的線性規(guī)劃問(wèn)題，,尋求以線性函數(shù)的最大（?。┲禐槟繕?biāo)的數(shù)學(xué)模型.,它是指在一組線性的等式或不等式的約束條件下，,線性規(guī)劃模型的三種形式,系 數(shù) 矩 陣,目標(biāo)函數(shù) 價(jià)值向量 價(jià)值系數(shù) 決策變量,右端向量, 一般形式, 規(guī)范形式, 標(biāo)準(zhǔn)形式,三種形式的LP問(wèn)題全都是等價(jià)的，即一種形式的LP可以簡(jiǎn)單的變換為另一種形式的LP，且它們有相同的解.,以下我們僅將一般形式化成規(guī)

4、范形式和標(biāo)準(zhǔn)形式.,目標(biāo)函數(shù)的轉(zhuǎn)化,約束條件和變量的轉(zhuǎn)化,為了把一般形式的LP問(wèn)題變換為規(guī)范形式，,可用下述兩個(gè)不等式約束去替代,我們必須消除等式約束和符號(hào)無(wú)限制變量. 在一,般形式的LP中，一個(gè)等式約束,這樣就把一般形式的LP變換為規(guī)范形式.,變量 和 ，并設(shè),對(duì)于一個(gè)無(wú)符號(hào)限制變量 ，引進(jìn)兩個(gè)非負(fù),對(duì)于一個(gè)不等式約束,代替上述的不等式約束.,對(duì)符號(hào)無(wú)限制變量的處理可按上述方法進(jìn)行.,可引入一個(gè)剩余變量 ，,必須消除其不等式約束和符號(hào)無(wú)限制變量.,為了把一般形式的LP問(wèn)題變換為標(biāo)準(zhǔn)形式，,對(duì)于不等式約束,代替上述的不等式約束.,這樣就把一般形式的LP變換為標(biāo)準(zhǔn)形式.,針對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)

5、題，其解的理論,分析已經(jīng)很完備，在此基礎(chǔ)上也提出了很好的算,單純形方法是線性規(guī)劃問(wèn)題的最為基礎(chǔ)、也,法單純形方法及其相應(yīng)的變化形式（兩階段,2.2 線性規(guī)劃模型的求解,法，對(duì)偶單純形法等）.,是最核心的算法. 它是一個(gè)迭代算法，先從一個(gè),特殊的可行解（極點(diǎn)）出發(fā)，通過(guò)判別條件去判,斷該可行解是否為最優(yōu)解（或問(wèn)題無(wú)界），若不,是最優(yōu)解，則根據(jù)相應(yīng)規(guī)則，迭代到下一個(gè)更好,的軟件包有LINGO和LINDO.,的可行解（極點(diǎn)），直到最優(yōu)解（或問(wèn)題無(wú)界）.,關(guān)于線性規(guī)劃問(wèn)題解的理論和單純形法具體的求,解過(guò)程可參見(jiàn)文獻(xiàn)1.,然后在實(shí)際應(yīng)用中，特別是數(shù)學(xué)建模過(guò)程中，,遇到線性規(guī)劃問(wèn)題的求解，我們一般都是利用

6、現(xiàn),有的軟件進(jìn)行求解，此時(shí)通常并不要求線性規(guī)劃,問(wèn)題是標(biāo)準(zhǔn)形式. 比較常用的求解線性規(guī)劃模型,運(yùn)輸問(wèn)題,例2 設(shè)要從甲地調(diào)出物資2000噸，從乙地調(diào)出物,資1100噸，分別供給A地1700噸、B地1100噸、C,假定運(yùn)費(fèi)與運(yùn)量成正比. 在這種情況下，采用不,地200噸、D地100噸. 已知每噸運(yùn)費(fèi)如表1.1所示.,同的調(diào)撥計(jì)劃，運(yùn)費(fèi)就可能不一樣. 現(xiàn)在問(wèn)：怎,樣才能找出一個(gè)運(yùn)費(fèi)最省的調(diào)撥計(jì)劃？,解,一般的運(yùn)輸問(wèn)題可以表述如下：,在滿足供需要求的條件下，使總運(yùn)輸費(fèi)用最省.,數(shù)學(xué)模型：,類似與將一般的線性規(guī)劃問(wèn)題轉(zhuǎn)化為其標(biāo)準(zhǔn),否則，稱為不平衡的運(yùn)輸問(wèn)題，包括：,總產(chǎn)量總銷量和總產(chǎn)量總銷量.,形式，

7、我們總可以通過(guò)引入假想的銷地或產(chǎn)地，,將不平衡的運(yùn)輸問(wèn)題轉(zhuǎn)化為平衡的運(yùn)輸問(wèn)題. 從,而，我們的重點(diǎn)就是解決平衡運(yùn)輸問(wèn)題的求解.,若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，,該方法將單純形法與平衡的運(yùn)輸問(wèn)題的特殊性質(zhì),運(yùn)輸問(wèn)題及其解法的進(jìn)一步介紹參加文獻(xiàn)2.,顯然，運(yùn)輸問(wèn)題是一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題，,因而當(dāng)然可以運(yùn)用單純形方法求解.但由于平衡,的運(yùn)輸問(wèn)題的特殊性質(zhì)，它還可以用其它的一些,特殊方法求解，其中最常用的就是表上作業(yè)法，,結(jié)合起來(lái)，很方便地實(shí)行了運(yùn)輸問(wèn)題的求解.關(guān)于,對(duì)于線性規(guī)劃問(wèn)題，如果要求其決策變量取,整數(shù)值，則稱該問(wèn)題為整數(shù)線性規(guī)劃問(wèn)題.,平面法和分支定界法是兩種常用的求解整數(shù)線性,

8、對(duì)于整數(shù)線性規(guī)劃問(wèn)題的求解，其難度和運(yùn),三、整數(shù)線性規(guī)劃模型,算量遠(yuǎn)大于同規(guī)模的線性規(guī)劃問(wèn)題. Gomory割,規(guī)劃問(wèn)題的方法（見(jiàn)文獻(xiàn)1）. 此外，同線性規(guī),劃模型一樣，我們也可以運(yùn)用LINGO和LINDO軟,件包來(lái)求解整數(shù)線性規(guī)劃模型.,如何求解整數(shù)線性規(guī)劃模型.,以1988年美國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題為例，,說(shuō)明整數(shù)線性規(guī)劃模型的建立及用LINGO軟件包,例3 有七種規(guī)格的包裝箱要裝到兩節(jié)鐵路平板車,上去. 包裝箱的寬和高是一樣的，但厚度（t，以,cm 計(jì)）及重量（w，以kg計(jì)）是不同的. 表1給出,了每種包裝箱的厚度、重量以及數(shù)量. 每節(jié)平板,車有10.2 m 長(zhǎng)的地方可用來(lái)裝包裝箱（像

9、面包片,那樣），載重為40t. 由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)于,C5, C6, C7 類包裝箱的總數(shù)有一個(gè)特別的限制：這,類箱子所占的空間（厚度）不能超過(guò)302.7cm. 試,把包裝箱裝到平板車上，使得浪費(fèi)的空間最小.,下面我們建立該問(wèn)題的整數(shù)線性規(guī)劃模型.,1) 約束條件,兩節(jié)車的裝箱數(shù)不能超過(guò)需要裝的件數(shù)，即：,每節(jié)車可裝的長(zhǎng)度不能超過(guò)車能提供的長(zhǎng)度：,每節(jié)車可裝的重量不超過(guò)車能夠承受的重量：,對(duì)于C5, C6, C7類包裝箱的總數(shù)的特別限制：,2) 目標(biāo)函數(shù),浪費(fèi)的空間最小，即包裝箱的總厚度最大：,3) 整數(shù)線性規(guī)劃模型,4) 模型求解,運(yùn)用LINGO軟件求解得到：,5) 最優(yōu)解的分析說(shuō)明,優(yōu)

10、的裝車方案，此時(shí)裝箱的總長(zhǎng)度為1019.7cm，,兩節(jié)車共裝箱的總長(zhǎng)度為2039.4cm.,但是，上述求解結(jié)果只是其中一種最優(yōu)的裝,車方案，即此答案并不唯一.,0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，它要求,線性規(guī)劃模型中的決策變量 xij 只能取值為0或1.,單隱枚舉法，該方法是一種基于判斷條件（過(guò)濾,0-1整數(shù)規(guī)劃模型的求解目前并沒(méi)有非常好的,四、0-1整數(shù)規(guī)劃模型,算法，對(duì)于變量比較少的情形，我們可以采取簡(jiǎn),條件）的窮舉法.,我們也可以利用LINGO和LINDO軟件包來(lái)求,解0-1整數(shù)規(guī)劃模型.,例4 有 n 個(gè)物品，編號(hào)為 1, 2, , n，第 i 件物品,重 ai 千克，價(jià)值為 ci

11、元，現(xiàn)有一個(gè)載重量不超過(guò),大，應(yīng)如何裝載這些物品？,a 千克的背包，為了使裝入背包的物品總價(jià)值最,用變量 xi 表示物品 i 是否裝包，i =1, 2, , n，,并令：,解,可得到背包問(wèn)題的規(guī)劃模型為：,例5 有n 項(xiàng)任務(wù)，由 n 個(gè)人來(lái)完成，每個(gè)人只能,做一件， 第 i 個(gè)人完成第 j 項(xiàng)任務(wù)要 cij 小時(shí)，如,何合理安排時(shí)間才能使總用時(shí)最??？,引入狀態(tài)變量 xij ，并令：,解,則總用時(shí)表達(dá)式為：,可得到指派問(wèn)題的規(guī)劃模型為：,上面介紹的指派問(wèn)題稱為指派問(wèn)題的標(biāo)準(zhǔn)形,式，還有許多其它的諸如人數(shù)與任務(wù)數(shù)不等、及,但一般可以通過(guò)一些轉(zhuǎn)化，將其變?yōu)闃?biāo)準(zhǔn)形式.,某人可以完成多個(gè)任務(wù)，某人不可以

12、完成任務(wù)，,某任務(wù)必須由某人完成等特殊要求的指派問(wèn)題.,對(duì)于標(biāo)準(zhǔn)形式的指派問(wèn)題，我們可以利用匈,牙利算法實(shí)現(xiàn)求解. 它將指派問(wèn)題中的系數(shù)構(gòu)成,一個(gè)矩陣，利用矩陣上簡(jiǎn)單的行和列變換，結(jié)合,解的判定條件，實(shí)現(xiàn)求解（見(jiàn)文獻(xiàn)2）.,DVD在線租賃第二個(gè)問(wèn)題的求解,問(wèn)題二的分析,盡量小，會(huì)員滿意度最大.,經(jīng)營(yíng)成本和會(huì)員的滿意度是被考慮的兩個(gè)相互,制約的重要因素.在忽略郵寄成本的前提下，經(jīng)營(yíng),成本主要體現(xiàn)為DVD的數(shù)量. 我們主要考慮在會(huì)員,向網(wǎng)站提供需求信息，且滿足一定要求的前提下，,對(duì)給定數(shù)量DVD進(jìn)行分配決策，使得DVD的數(shù)量,DVD，否則不進(jìn)行租賃.,沒(méi)有預(yù)定的DVD對(duì)其滿意度的貢獻(xiàn)為0.,假設(shè)按

13、照公歷月份進(jìn)行的租賃業(yè)務(wù)，即會(huì)員,無(wú)論兩次租賃還是一次租賃，必須在當(dāng)月內(nèi)完成,DVD的租與還. 同時(shí)假設(shè)網(wǎng)站對(duì)其會(huì)員進(jìn)行一次,租賃業(yè)務(wù)時(shí)，只能向其提供3張?jiān)摃?huì)員已經(jīng)預(yù)定的,經(jīng)觀察，可以認(rèn)為在線訂單中每個(gè)會(huì)員的預(yù)定,DVD的表示偏好程度的數(shù)字反映了會(huì)員對(duì)所預(yù)定,不同DVD的滿意程度，且當(dāng)會(huì)員租到其預(yù)定排序,為1，2，3的三張DVD時(shí)，滿意度達(dá)到100%. 會(huì)員,利用層次分析法，對(duì)此滿意指數(shù)的合理性進(jìn),行了簡(jiǎn)單分析.,進(jìn)行求解.,該問(wèn)題要求根據(jù)現(xiàn)有的100種DVD的數(shù)量和,當(dāng)前需要處理的1000位會(huì)員的在線訂單，制定分,配策略，使得會(huì)員達(dá)到最大的滿意度. 因而我們,認(rèn)為只需對(duì)這些DVD進(jìn)行一次性分

14、配，使得會(huì)員,的總體滿意度達(dá)到最大.為此考慮建立優(yōu)化模型，,問(wèn)題二的模型及求解,又根據(jù)假設(shè)，網(wǎng)站只向會(huì)員提供其預(yù)定的DVD，,進(jìn)行分配. 故引入約束,進(jìn)一步，對(duì)每個(gè)會(huì)員每次租賃只能獲得3張其,預(yù)定的DVD或不能得到，有,在上述約束的前提下，我們追求會(huì)員的總體,會(huì)員的最大滿意指數(shù)為10+9+827，1000個(gè),為了更好地表示滿意度，我們將目標(biāo)轉(zhuǎn)化為,滿意指數(shù)和 達(dá)到最大，顯然每個(gè),會(huì)員最大的滿意指數(shù)和為,用百分?jǐn)?shù)表示的滿意度為：,，,由此，可得問(wèn)題二的0-1整數(shù)線性規(guī)劃模型如下：,配方案（見(jiàn)表3）.,會(huì)員全都得到了3張預(yù)定的DVD.,根據(jù)所得的0-1整數(shù)線性規(guī)劃模型，利用,LINGO軟件進(jìn)行求解

15、，我們得到了一組最優(yōu)分,該組最優(yōu)解其目標(biāo)函數(shù)會(huì)員總體最大滿意,度為91.56%，只有6人未成功租賃（如：前30,名會(huì)員中C0008被分配到DVD），其余994個(gè),五、非線性規(guī)劃模型,即非線性規(guī)劃問(wèn)題.,前面介紹了線性規(guī)劃問(wèn)題，即目標(biāo)函數(shù)和約束條,件都是線性函數(shù)的規(guī)劃問(wèn)題，但在實(shí)際工作中，還,常常會(huì)遇到另一類更一般的規(guī)劃問(wèn)題，即目標(biāo)函數(shù),和約束條件中至少有一個(gè)是非線性函數(shù)的規(guī)劃問(wèn)題，,事實(shí)上，客觀世界中的問(wèn)題許多是非線性,的，給予線性大多是近似的，是在作了科學(xué),的假設(shè)和簡(jiǎn)化后得到的. 為了利用線性的,知識(shí)，許多非線性問(wèn)題常進(jìn)行線性化處理.,但在實(shí)際問(wèn)題中，有一些是不能進(jìn)行線性化,處理的，否則將嚴(yán)

16、重影響模型對(duì)實(shí)際問(wèn)題,近似的可依賴型.,由于非線性規(guī)劃問(wèn)題在計(jì)算上常是困難的，,理論上的討論也不能像線性規(guī)劃那樣給出簡(jiǎn)潔,的結(jié)果形式和全面透徹的結(jié)論.這點(diǎn)又限制了非,線性規(guī)劃的應(yīng)用，所以，在數(shù)學(xué)建模時(shí)，要進(jìn),行認(rèn)真的分析，對(duì)實(shí)際問(wèn)題進(jìn)行合理的假設(shè)、,簡(jiǎn)化，首先考慮用線性規(guī)劃模型，若線性近似,誤差較大時(shí)，則考慮用非線性規(guī)劃.,非線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為：,其中， 為 維歐式空間 中的向量，,中至少有一個(gè)是非線性函數(shù).,非線性規(guī)劃模型按約束條件可分為以下三類：, 等式約束非線性規(guī)劃模型：, 無(wú)約束非線性規(guī)劃模型：, 不等式約束非線性規(guī)劃模型：,針對(duì)上述三類非線性規(guī)劃模型，其常用求解的基,本思路可歸

17、納如下：,（下降迭代法）尋找，該方法的基本步驟如下：,所以往往根據(jù)目標(biāo)函數(shù)的特征采用搜索的方法,1) 無(wú)約束的非線性規(guī)劃問(wèn)題,止迭代，用 來(lái)近似問(wèn)題的最優(yōu)解，否則轉(zhuǎn)至.,從 出發(fā)，沿方向 ,按某種方法確定步長(zhǎng) ,令 ，然后置 ，返回,使得：,檢驗(yàn) 是否滿足停止迭代的條件，如是，則停,線性規(guī)劃可以用一維搜索方法求得最優(yōu)解，一維搜,最常用的搜索方法就是最速下降法.,在下降迭代算法中，搜索方向起著關(guān)鍵的作,用，而當(dāng)搜索方向確定后，步長(zhǎng)又是決定算法好壞,的重要因素. 非線性規(guī)劃只含一個(gè)變量，即一維非,索方法主要有進(jìn)退法和黃金分割法. 二維的非線性,規(guī)劃也可以像解線性規(guī)劃那樣用圖形求解. 對(duì)于二,維非線

18、性規(guī)劃，使用搜索方法是要用到梯度的概念，,約束問(wèn)題求解.,近的方法將非線性規(guī)劃問(wèn)題化為線性規(guī)劃問(wèn)題.,2) 只有等式約束的非線性規(guī)劃問(wèn)題通?？捎孟?元法、拉格朗日乘子法或反函數(shù)法，將其化為無(wú),3) 具有不等式約束的非線性規(guī)劃問(wèn)題解起來(lái)很,復(fù)雜，求解這一類問(wèn)題，通常將不等式化為等式,約束，再將約束問(wèn)題化為無(wú)約束問(wèn)題，用線性逼,規(guī)劃問(wèn)題可用拉格朗日方法求解.,下面介紹一個(gè)簡(jiǎn)單的非線性規(guī)劃問(wèn)題的例,子，其中的一些約束條件是等式，這類非線性,客戶的速度.,例7 （石油最優(yōu)儲(chǔ)存方法）有一石油運(yùn)輸公,司，為了減少開支，希望作了節(jié)省石油的存儲(chǔ),空間.但要求存儲(chǔ)的石油能滿足客戶的要求.為,簡(jiǎn)化問(wèn)題，假設(shè)只經(jīng)營(yíng)

19、兩種油，各種符號(hào)表示,的意義如表4所示.其中供給率指石油公司供給,表4 各種符號(hào)表示意義表,由歷史數(shù)據(jù)得到的經(jīng)驗(yàn)公式為 :,且提供數(shù)據(jù)如表5所示：,表5 數(shù)據(jù)表,已知總存儲(chǔ)空間,代入數(shù)據(jù)后得到的模型為：,拉格朗日函數(shù)的形式為：,模型求解：,即:,對(duì) 求各個(gè)變量的偏導(dǎo)數(shù)，并令它們,等于零，得:,解這個(gè)線性方程組得：,從而可得最小值是12.71.,間由24變?yōu)?5時(shí)，最優(yōu)值會(huì)由12.71變?yōu)?表示當(dāng)約束條件右邊的值增大一個(gè)單位后，相,應(yīng)目標(biāo)函數(shù)值的增加值。比如說(shuō)：如總存儲(chǔ)空,六、多目標(biāo)規(guī)劃模型,許多實(shí)際問(wèn)題中，衡量一個(gè)方案的好壞標(biāo)準(zhǔn),往往不止一個(gè). 例如設(shè)計(jì)一個(gè)導(dǎo)彈，既要射程,最遠(yuǎn)，又要燃料最省，

20、還要精度最高. 這一類,問(wèn)題統(tǒng)稱為多目標(biāo)最優(yōu)化問(wèn)題或多目標(biāo)規(guī)劃問(wèn),題. 我們先來(lái)看一個(gè)生產(chǎn)計(jì)劃的例子.,能耗不得超過(guò)160t標(biāo)準(zhǔn)煤其它數(shù)據(jù)如下表：,問(wèn)每周應(yīng)生產(chǎn)三種布料各多少m，才能使該廠,的利潤(rùn)最高，而能源消耗最少？,，該廠兩班生產(chǎn)，每周生產(chǎn)時(shí)間為80h，,例8 （生產(chǎn)計(jì)劃問(wèn)題）某廠生產(chǎn)三種布料,解 設(shè)該廠每周生產(chǎn)布料 的小時(shí)數(shù)為,，總利潤(rùn)為 （元），總能耗為,（t標(biāo)準(zhǔn)煤），其中 ，,則上述問(wèn)題的數(shù)學(xué)模型為,其中， ， .,有,顯然這是一個(gè)多目標(biāo)線性規(guī)劃問(wèn)題. 一般的多目,標(biāo)規(guī)劃問(wèn)題都可寫成如下的形式：,從而得到滿意解的方法.,主要區(qū)別在于：目標(biāo)函數(shù)不止一個(gè)，而是p 個(gè),（ ）.,問(wèn)題的可行

21、集或容許集， 稱為可行解或容,稱為多目標(biāo)規(guī)劃,許解. 多目標(biāo)規(guī)劃問(wèn)題與前面講的規(guī)劃問(wèn)題的,多目標(biāo)規(guī)劃問(wèn)題的解法大致可分為兩類：直,接解法和間接解法. 到目前為止，常用的多為,間接解法，即根據(jù)問(wèn)題的實(shí)際背景和特征，設(shè),法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，,一個(gè)目標(biāo)為主要目標(biāo)，例如 ，而把其余目,主要目標(biāo)法,線性規(guī)劃問(wèn)題：,多目標(biāo)優(yōu)化問(wèn)題中，若能從p 個(gè)目標(biāo)中，確定,標(biāo)作為次要目標(biāo)，并根據(jù)實(shí)際情況，確定適當(dāng)?shù)?界限值，這樣就可以把次要目標(biāo)作為約束來(lái)處理，,而將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為求解如下的線性或非,其中界限值取為 ，則,目標(biāo)優(yōu)化問(wèn)題的弱有效解或有效解.,令,此非線性規(guī)劃問(wèn)題得最優(yōu)解必為原問(wèn)題的

22、弱,有效解. 因此，用主要目標(biāo)法求得的解必是多,排一個(gè)次序，假設(shè) 最重要， 次之，,再次之，最后一個(gè)目標(biāo) .,先求出以第一個(gè)目標(biāo) 為目標(biāo)函數(shù)，而原,2) 分層序列法,把多目標(biāo)規(guī)劃問(wèn)題中的p 個(gè)目標(biāo)按其重要程度,問(wèn)題中的約束條件不變的問(wèn)題 ：,的最優(yōu)解 及最優(yōu)值 ，再求問(wèn)題 ：,的最優(yōu)解 及最優(yōu)值 ，即 ，,的可行域.,再求解問(wèn)題 ：,得最優(yōu)解 及最優(yōu)值 ，如此繼續(xù)下去，,直到求出第p 個(gè)問(wèn)題 ：,原多目標(biāo)規(guī)劃問(wèn)題在分層序列意義下得最優(yōu)解，,為其最優(yōu)值.,得最優(yōu)解 及最優(yōu)值 ，則 就是,P, 其最優(yōu)解是唯一的，則問(wèn)題 的最優(yōu)解,也是唯一的，且 。因此常將分層,序列法修改如下：選取一組適當(dāng)?shù)男≌龜?shù)

23、,成為寬容值，把上述的問(wèn)題 修改如下：,再按上述方法依次求解各問(wèn)題 .,容易看出，在使用分層序列法時(shí)，若對(duì)某個(gè)問(wèn)題,.,3）線性加權(quán)求和法,程度給以適當(dāng)?shù)臋?quán)系數(shù) ，且,，然后用 作為新的目標(biāo),得最優(yōu)解 ，取 作為多目標(biāo)規(guī)劃,函數(shù)，成為評(píng)價(jià)（目標(biāo)）函數(shù)，再求解問(wèn)題,對(duì)多目標(biāo)規(guī)劃問(wèn)題中的p個(gè)目標(biāo)按期重要,問(wèn)題的解.,優(yōu)解必是原多目標(biāo)規(guī)劃問(wèn)題的有效解或弱有效解.,例9 求解引言中DVD在線租賃的第三個(gè)問(wèn)題.,性規(guī)劃模型以及利用主要目標(biāo)法求解該模型.,在一定條件下，用線性加權(quán)求和法求得的最,下面以引言中2005年全國(guó)大學(xué)生數(shù)模競(jìng)賽,“DVD在線租賃”問(wèn)題第三問(wèn)為例，介紹多目標(biāo)線,得會(huì)員的滿意度最大.,

24、問(wèn)題三的分析,此問(wèn)是在現(xiàn)有的在線訂單基礎(chǔ)上，滿足一個(gè),月內(nèi)95%的會(huì)員得到他預(yù)訂的DVD，我們進(jìn)行,購(gòu)買量預(yù)算和分配決策，使得會(huì)員的滿意度最,大.預(yù)算購(gòu)買量的目的是在盡可能地減少DVD,購(gòu)買量的前提下，滿足要求，進(jìn)行合理分配使,在一個(gè)月內(nèi)進(jìn)行分配，因而存在部分DVD的兩次,員的第二次租賃.,我們假設(shè)會(huì)員得到他想看的DVD就是指：會(huì)員,租賃到了他預(yù)定的DVD中的三張；且假設(shè)會(huì)員每,次租賃前都需要提交新的在線訂單. 此問(wèn)中要求,被租賃，但因?yàn)槭翘幚硗环萦唵?，因而存在?huì),了 張DVD的作用.,基于這個(gè)假設(shè)，為了最小化購(gòu)買量，我們?cè)?允許當(dāng)前某些會(huì)員無(wú)法被滿足租賃要求，讓其,等待，利用部分會(huì)員還回的

25、DVD對(duì)其進(jìn)行租賃.,根據(jù)問(wèn)題一，我們認(rèn)為，一個(gè)月中每張DVD,有0.6的概率被租賃兩次，0.4的概率被租賃一次.,即在二次租賃的情況下，每張DVD相當(dāng)于發(fā)揮,由此，在問(wèn)題二建立的0-1整數(shù)規(guī)劃模型的,求，考慮DVD可能的兩次分配，進(jìn)一步追求DVD,基礎(chǔ)上，滿足95%的會(huì)員得到他想看DVD的要,進(jìn)行求解.,總的購(gòu)買數(shù)量最小. 建立雙目標(biāo)整數(shù)規(guī)劃模型,設(shè) 表示第j種DVD需要的購(gòu)買量.對(duì)每種DVD，,問(wèn)題三的模型,要求分配的總量不超過(guò)相應(yīng)的現(xiàn)有數(shù)量的1.6倍.即:,為了讓95%的會(huì)員可以得到他想看的3張DVD，即:,我們希望購(gòu)買DVD的總數(shù)量最小，即 :,由此，可以得到問(wèn)題三的雙目標(biāo)整數(shù)線性規(guī)劃

26、,模型如下：,總體滿意度水平 （即最小的滿意度）,將其滿意度的目標(biāo)轉(zhuǎn)換為約束，如下：,問(wèn)題三的求解與檢驗(yàn),對(duì)于該雙目標(biāo)整數(shù)線性規(guī)劃模型，我們引入,利用Lingo軟件，調(diào)整總體滿意度水平 進(jìn)行,求解。實(shí)際計(jì)算中，如果要求 為整,約束進(jìn)行計(jì)算。求得解 后，對(duì)其,進(jìn)行取整。當(dāng) 時(shí)，我們解得DVD總的最小,購(gòu)買量 ，其中第j種DVD需要的購(gòu)買,量 如下表：,數(shù)，無(wú)法求得可行解，因而我們?nèi)∠似湔麛?shù),表6 當(dāng) 時(shí)最小購(gòu)買量的 值,續(xù)上表,我們利用規(guī)劃模型求得每種DVD的購(gòu)買量后，,需要對(duì)其進(jìn)行可行性校驗(yàn)，測(cè)試此結(jié)果是否可以,且具有盡可能大的總體滿意度.,滿足一個(gè)月內(nèi)比例為95%的會(huì)員得到他想看DVD，,

27、校驗(yàn)方法：,（一）根據(jù)訂單和求得的DVD購(gòu)買數(shù)量，利用問(wèn)題,二的規(guī)劃模型進(jìn)行第一次分配，對(duì)分配情況：租,賃的會(huì)員，DVD的分配情況，剩余的各種DVD,數(shù)量作記錄；同時(shí)將已租賃的會(huì)員在滿意指數(shù),矩陣的指數(shù)全變?yōu)?，即不考慮對(duì)其進(jìn)行第二次,分配.,第一次未分配到DVD的會(huì)員進(jìn)行第二次分配；,（二）隨機(jī)從第一次得到DVD的會(huì)員中抽取60%，,將這部分人所還回的DVD與第一次分配余下的,DVD合在一起，作為第二次分配時(shí)各種DVD的,現(xiàn)有量.然后，利用問(wèn)題二的0-1線性規(guī)劃模型對(duì),（三）統(tǒng)計(jì)出經(jīng)過(guò)兩次分配后，得到DVD的會(huì)員,使得到DVD的會(huì)員大于95%，則認(rèn)為模型三是合,種算法進(jìn)行多次隨機(jī)模擬，若大多

28、數(shù)情況下可以,的比例，若大于95%，則此次分配成功.利用這,理的.,校驗(yàn)結(jié)果：,因?yàn)槊看螜z驗(yàn)需時(shí)約1小時(shí)，我們只對(duì)問(wèn)題三,表7 7次模擬結(jié)果每次的觀看比例列表,觀看比例大于95%）.下面給出7次模擬得到的觀,求得的結(jié)果進(jìn)行了7次模擬，其中6次符合要求（,看比例（表7）：,七、動(dòng)態(tài)規(guī)劃模型,過(guò)程中的最優(yōu)控制問(wèn)題.,動(dòng)態(tài)規(guī)劃所研究的對(duì)象是多階段對(duì)策問(wèn)題，,是在20世紀(jì)50年代初期由美國(guó)數(shù)學(xué)家R.Bellman等,人提出的一類規(guī)劃模型. 動(dòng)態(tài)規(guī)劃是現(xiàn)代管理領(lǐng)域,的一種重要的決策方法，其主要應(yīng)用有最優(yōu)路徑,問(wèn)題、資源分配問(wèn)題、投資決策問(wèn)題、生產(chǎn)計(jì)劃,與庫(kù)存問(wèn)題、排序問(wèn)題、貨物裝載問(wèn)題以及生產(chǎn),理多階段

29、決策問(wèn)題的最優(yōu)化原理.,效益的總和達(dá)到最優(yōu).,多階段決策問(wèn)題是指一類活動(dòng)過(guò)程，它可分,為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要做,出決策，這個(gè)決策不僅決定這一階段的效益，而,定以后，就得到一個(gè)決策序列，稱為策略. 多階,段決策問(wèn)題就是求一個(gè)策略，使各階段的效益的,下面我們通過(guò)講解一個(gè)最短路問(wèn)題來(lái)引出處,且決定下一階段的初始狀態(tài)，每個(gè)階段的決策確,例10 有一輛汽車要把貨物從A城運(yùn)到E城，而,可供選擇，選取怎樣的路線才能使路程最短？,從A城到E城必須經(jīng)過(guò)一些城市，整段路程可以,分為若干個(gè)階段，而每個(gè)階段又有若干個(gè)城市,假定從A城到E城的所有路線如下圖所示：,圖1 從A城到E城的路線,途中的數(shù)字表

30、示兩城之間的距離（以10千米為,其中 B1,B2,C1,C2,D1,D2是可供選擇的城市，,單位）.,很明顯，前面各階段的決策如何選擇，直接影響著,段選擇一個(gè)決策，使由它們決定的總路程最短.,顯然，這是一個(gè)多階段決策問(wèn)題：從A到E可以分為,4個(gè)階段. 從A點(diǎn)出發(fā)到B1或B2為第一階段，這時(shí)有,兩個(gè)選擇：走到B1或者走到B2. 若我們選擇走到B1,的決策，則B1就是下一個(gè)階段的起點(diǎn). 在下一階段，,我們從B1出發(fā)，有一個(gè)可供選擇的決策集合C1 ,C2，,其余各階段的行進(jìn)路線，我們的目的就是在各個(gè)階,動(dòng)態(tài)規(guī)劃的基本概念.,階段的終點(diǎn)又是第k+1階段的起點(diǎn)，記為Sk，,下面我們來(lái)求此問(wèn)題的最短路線，并以此來(lái),說(shuō)明處理多階段決策問(wèn)題的最優(yōu)化原理.先引入,令k表示由某點(diǎn)至終點(diǎn)之間的階段數(shù).例如從A,到E可以分為4個(gè)階段，從B1到E是5個(gè)階段；第k,個(gè)階段時(shí)所選擇的一個(gè)決策；在各個(gè)階段上選擇,令xk(sk)為決策變量，它表示當(dāng)處于狀態(tài)時(shí)還有,態(tài)全體可用狀態(tài)集合來(lái)描述.例如：S2=B1,B2；,稱為狀態(tài)變