規(guī)劃理論及模型

規(guī)劃理論及模型第一章規(guī)劃理論及模型一、引言二、線性規(guī)劃模型三、整數(shù)線性規(guī)劃模型四、0-1整數(shù)規(guī)劃模型

五、非線性規(guī)劃模型六、多目標(biāo)規(guī)劃模型目錄下頁返回上頁結(jié)束七、動態(tài)規(guī)劃模型第2頁,共111頁，2024年2月25日，星期天一、引言目錄下頁返回上頁結(jié)束我們從2005年“高教社杯”全國大學(xué)生數(shù)模競賽的B題“DVD在線租賃”問題的第二問和第三問談起.其中第二個問題是一個如何來分配有限資源，從而達(dá)到人們期望目標(biāo)的優(yōu)化分配數(shù)學(xué)模型.它在運籌學(xué)中處于中心的地位.這類問題一般可以歸結(jié)為數(shù)學(xué)規(guī)劃模型.第3頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束規(guī)劃模型的應(yīng)用極其廣泛，其作用已為越來來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事行為核科學(xué)研究的各個方面，為社會節(jié)省的財富、創(chuàng)造的價值無法估量.特別是在數(shù)模競賽過程中，規(guī)劃模型是最常見的一類數(shù)學(xué)模型.從92-06年全國大學(xué)生數(shù)模競越多的人所重視.隨著計算機的逐漸普及，它越賽試題的解題方法統(tǒng)計結(jié)果來看，規(guī)劃模型共出現(xiàn)了15次，占到了50%，也就是說每兩道競賽題中就有一道涉及到利用規(guī)劃理論來分析、求解.

第4頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束二、線性規(guī)劃模型線性規(guī)劃模型是所有規(guī)劃模型中最基本、最例1（食譜問題）設(shè)有n種食物，各含m種營養(yǎng)素，第j種食物中第i中營養(yǎng)素的含量為aij,n種食物價格分別為c1,c2,…,cn，請確定食譜中n種食物的數(shù)量x1,x2,…,xn，要求在食譜中m種營養(yǎng)素簡單的一種.

2.1線性規(guī)劃模型的標(biāo)準(zhǔn)形式

的含量分別不低于b1,b2,…,bm的情況下，使得總總的費用最低.第5頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束首先根據(jù)食物數(shù)量及價格可寫出食譜費用為其次食譜中第i種營養(yǎng)素的含量為因此上述問題可表述為：解第6頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束上述食譜問題就是一個典型的線性規(guī)劃問題，尋求以線性函數(shù)的最大（?。┲禐槟繕?biāo)的數(shù)學(xué)模型.它是指在一組線性的等式或不等式的約束條件下，第7頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

線性規(guī)劃模型的三種形式

系數(shù)矩陣目標(biāo)函數(shù)價值向量價值系數(shù)決策變量右端向量非負(fù)約束自由變量⑴一般形式第8頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束⑵規(guī)范形式⑶標(biāo)準(zhǔn)形式三種形式的LP問題全都是等價的，即一種形式的LP可以簡單的變換為另一種形式的LP，且它們有相同的解.以下我們僅將一般形式化成規(guī)范形式和標(biāo)準(zhǔn)形式.第9頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束目標(biāo)函數(shù)的轉(zhuǎn)化

xoz-z第10頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束約束條件和變量的轉(zhuǎn)化

①．為了把一般形式的LP問題變換為規(guī)范形式，我們必須消除等式約束和符號無限制變量.在一般形式的LP中，一個等式約束可用下述兩個不等式約束去替代

第11頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束這樣就把一般形式的LP變換為規(guī)范形式.

對于一個無符號限制變量，引進(jìn)兩個非負(fù)變量和，并設(shè)第12頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束②．為了把一般形式的LP問題變換為標(biāo)準(zhǔn)形式，必須消除其不等式約束和符號無限制變量.對于一個不等式約束代替上述的不等式約束.

對符號無限制變量的處理可按上述方法進(jìn)行.可引入一個剩余變量

，第13頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束對于不等式約束

代替上述的不等式約束

這樣就把一般形式的LP變換為標(biāo)準(zhǔn)形式.可引入一個松弛變量，用第14頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束針對標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其解的理論分析已經(jīng)很完備，在此基礎(chǔ)上也提出了很好的算單純形方法是線性規(guī)劃問題的最為基礎(chǔ)、也法——單純形方法及其相應(yīng)的變化形式（兩階段2.2線性規(guī)劃模型的求解

法，對偶單純形法等）.是最核心的算法。它是一個迭代算法，先從一個特殊的可行解（極點）出發(fā)，通過判別條件去判斷該可行解是否為最優(yōu)解（或問題無界），若不第15頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束是最優(yōu)解，則根據(jù)相應(yīng)規(guī)則，迭代到下一個更好的可行解（極點），直到最優(yōu)解（或問題無界）.關(guān)于線性規(guī)劃問題解的理論和單純形法具體的求解過程可參見文獻(xiàn)[1].然后在實際應(yīng)用中，特別是數(shù)學(xué)建模過程中，遇到線性規(guī)劃問題的求解，我們一般都是利用現(xiàn)有的軟件進(jìn)行求解，此時通常并不要求線性規(guī)劃問題是標(biāo)準(zhǔn)形式.比較常用的求解線性規(guī)劃模型的軟件包有LINGO和LINDO.第16頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束運輸問題例2設(shè)要從甲地調(diào)出物資2000噸，從乙地調(diào)出物

資1100噸，分別供給A地1700噸、B地1100噸、C假定運費與運量成正比.在這種情況下，采用不地200噸、D地100噸.已知每噸運費如表1.1所示.同的調(diào)撥計劃，運費就可能不一樣.現(xiàn)在問：怎樣才能找出一個運費最省的調(diào)撥計劃？第17頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束1572521甲15375151乙DCBA表1.1銷地運費產(chǎn)地第18頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束解乙甲DCBA第19頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第20頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束一般的運輸問題可以表述如下：第21頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束數(shù)學(xué)模型：

第22頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束類似與將一般的線性規(guī)劃問題轉(zhuǎn)化為其標(biāo)準(zhǔn)若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即否則，稱為不平衡的運輸問題，包括：，則稱該問題為平衡的運輸問題.總產(chǎn)量>總銷量和總產(chǎn)量<總銷量.形式，我們總可以通過引入假想的銷地或產(chǎn)地，將不平衡的運輸問題轉(zhuǎn)化為平衡的運輸問題.從而，我們的重點就是解決平衡運輸問題的求解.第23頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束顯然，運輸問題是一個標(biāo)準(zhǔn)的線性規(guī)劃問題，因而當(dāng)然可以運用單純形方法求解.但由于平衡的運輸問題的特殊性質(zhì)，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業(yè)法，該方法將單純形法與平衡的運輸問題的特殊性質(zhì)結(jié)合起來，很方便地實行了運輸問題的求解.關(guān)于運輸問題及其解法的進(jìn)一步介紹參加文獻(xiàn)[2].

第24頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束對于線性規(guī)劃問題，如果要求其決策變量取整數(shù)值，則稱該問題為整數(shù)線性規(guī)劃問題.平面法和分支定界法是兩種常用的求解整數(shù)線性對于整數(shù)線性規(guī)劃問題的求解，其難度和運三、整數(shù)線性規(guī)劃模型算量遠(yuǎn)大于同規(guī)模的線性規(guī)劃問題.Gomory割規(guī)劃問題的方法（見文獻(xiàn)[1]）.此外，同線性規(guī)劃模型一樣，我們也可以運用LINGO和LINDO軟件包來求解整數(shù)線性規(guī)劃模型.第25頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束以1988年美國大學(xué)生數(shù)學(xué)建模競賽B題為例，說明整數(shù)線性規(guī)劃模型的建立及用LINGO軟件包如何求解整數(shù)線性規(guī)劃模型.例3有七種規(guī)格的包裝箱要裝到兩節(jié)鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以cm計）及重量（w，以kg計）是不同的.表1給出了每種包裝箱的厚度、重量以及數(shù)量.每節(jié)平板車有10.2m長的地方可用來裝包裝箱（像面包片那樣），載重為40t.由于當(dāng)?shù)刎涍\的限制，對于第26頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束C5,C6,C7類包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm.試把包裝箱裝到平板車上，使得浪費的空間最小.種類C1C2C3C4C5C6C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648第27頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束為在第節(jié)車上裝載第件包裝箱的解令下面我們建立該問題的整數(shù)線性規(guī)劃模型。第28頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束1)約束條件兩節(jié)車的裝箱數(shù)不能超過需要裝的件數(shù)，即：每節(jié)車可裝的長度不能超過車能提供的長度：每節(jié)車可裝的重量不超過車能夠承受的重量：第29頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束對于C5,C6,C7類包裝箱的總數(shù)的特別限制：2)目標(biāo)函數(shù)浪費的空間最小，即包裝箱的總厚度最大：第30頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束3)整數(shù)線性規(guī)劃模型第31頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束4)模型求解運用LINGO軟件求解得到：5)最優(yōu)解的分析說明優(yōu)的裝車方案，此時裝箱的總長度為1019.7cm，兩節(jié)車共裝箱的總長度為2039.4cm.由上一步中的求解結(jié)果可以看出，即為最但是，上述求解結(jié)果只是其中一種最優(yōu)的裝車方案，即此答案并不唯一.第32頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，它要求線性規(guī)劃模型中的決策變量xij只能取值為0或1.單隱枚舉法，該方法是一種基于判斷條件（過濾

0-1整數(shù)規(guī)劃模型的求解目前并沒有非常好的四、0-1整數(shù)規(guī)劃模型

算法，對于變量比較少的情形，我們可以采取簡條件）的窮舉法.我們也可以利用LINGO和LINDO軟件包來求解0-1整數(shù)規(guī)劃模型.第33頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束例4

有n個物品，編號為1,2,…,n，第i件物品重ai千克，價值為ci

元，現(xiàn)有一個載重量不超過大，應(yīng)如何裝載這些物品？a千克的背包，為了使裝入背包的物品總價值最用變量xi

表示物品i是否裝包，i=1,2,…,n，并令：解第34頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束可得到背包問題的規(guī)劃模型為：第35頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束例5

有n項任務(wù)，由n個人來完成，每個人只能做一件，第i個人完成第j項任務(wù)要cij小時，如何合理安排時間才能使總用時最?。恳霠顟B(tài)變量xij

，并令：解則總用時表達(dá)式為：第36頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束可得到指派問題的規(guī)劃模型為：第37頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束上面介紹的指派問題稱為指派問題的標(biāo)準(zhǔn)形式，還有許多其它的諸如人數(shù)與任務(wù)數(shù)不等、及但一般可以通過一些轉(zhuǎn)化，將其變?yōu)闃?biāo)準(zhǔn)形式.某人可以完成多個任務(wù)，某人不可以完成任務(wù)，某任務(wù)必須由某人完成等特殊要求的指派問題.對于標(biāo)準(zhǔn)形式的指派問題，我們可以利用匈牙利算法實現(xiàn)求解.它將指派問題中的系數(shù)構(gòu)成一個矩陣，利用矩陣上簡單的行和列變換，結(jié)合解的判定條件，實現(xiàn)求解（見文獻(xiàn)[2]）.第38頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束DVD在線租賃第二個問題的求解問題二的分析經(jīng)營成本和會員的滿意度是被考慮的兩個相互制約的重要因素.在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為DVD的數(shù)量.我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量DVD進(jìn)行分配決策，使得DVD的數(shù)量盡量小，會員滿意度最大.第39頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束假設(shè)按照公歷月份進(jìn)行的租賃業(yè)務(wù)，即會員無論兩次租賃還是一次租賃，必須在當(dāng)月內(nèi)完成DVD的租與還.同時假設(shè)網(wǎng)站對其會員進(jìn)行一次租賃業(yè)務(wù)時，只能向其提供3張該會員已經(jīng)預(yù)定的DVD，否則不進(jìn)行租賃.經(jīng)觀察，可以認(rèn)為在線訂單中每個會員的預(yù)定DVD的表示偏好程度的數(shù)字反映了會員對所預(yù)定不同DVD的滿意程度，且當(dāng)會員租到其預(yù)定排序為1，2，3的三張DVD時，滿意度達(dá)到100%.會員沒有預(yù)定的DVD對其滿意度的貢獻(xiàn)為0.第40頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束利用層次分析法，對此滿意指數(shù)的合理性進(jìn)行了簡單分析.

該問題要求根據(jù)現(xiàn)有的100種DVD的數(shù)量和當(dāng)前需要處理的1000位會員的在線訂單，制定分配策略，使得會員達(dá)到最大的滿意度.因而我們認(rèn)為只需對這些DVD進(jìn)行一次性分配，使得會員的總體滿意度達(dá)到最大.為此考慮建立優(yōu)化模型，進(jìn)行求解.第41頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束問題二的模型及求解經(jīng)營成本和會員的滿意度是被考慮的兩個相互制約的重要因素.在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為DVD的數(shù)量.我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量DVD進(jìn)行分配決策，使得DVD的數(shù)量盡量小，會員滿意度最大.第42頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第43頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第44頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第45頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束由此，可得問題二的0-1整數(shù)線性規(guī)劃模型如下：第46頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束根據(jù)所得的0-1整數(shù)線性規(guī)劃模型，利用LINGO軟件進(jìn)行求解，我們得到了一組最優(yōu)分配方案.該組最優(yōu)解其目標(biāo)函數(shù)會員總體最大滿意度為91.56%，只有6人未成功租賃（如：前30名會員中C0008被分配到DVD），其余994個會員全都得到了3張預(yù)定的DVD.第47頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束五、非線性規(guī)劃模型

前面介紹了線性規(guī)劃問題，即目標(biāo)函數(shù)和約束條件都是線性函數(shù)的規(guī)劃問題，但在實際工作中，還常常會遇到另一類更一般的規(guī)劃問題，其中目標(biāo)函數(shù)和約束條件至少有一個是非線性函數(shù)的規(guī)劃問題，即非線性規(guī)劃問題.第48頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

事實上，客觀世界中的問題許多是非線性的，給予線性大多是近似的，是在作了科學(xué)的假設(shè)和簡化后得到的.為了利用線性的知識，許多非線性問題常進(jìn)行線性化處理.但在實際問題中，有一些是不能進(jìn)行線性化處理的，否則將嚴(yán)重影響模型對實際問題近似的可依賴型.第49頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

由于非線性規(guī)劃問題在計算上常是困難的，理論上的討論也不能像線性規(guī)劃那樣給出簡潔的結(jié)果形式和全面透徹的結(jié)論.這點又限制了非線性規(guī)劃的應(yīng)用，所以，在數(shù)學(xué)建模時，要進(jìn)行認(rèn)真的分析，對實際問題進(jìn)行合理的假設(shè)、簡化，首先考慮用線性規(guī)劃模型，若線性近似誤差較大時，則考慮用非線性規(guī)劃.第50頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束非線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：第51頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束非線性規(guī)劃模型按約束條件可分為以下三類：⑵

等式約束非線性規(guī)劃模型：⑴無約束非線性規(guī)劃模型：第52頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束⑶不等式約束非線性規(guī)劃模型：1)無約束的非線性規(guī)劃問題.針對上述三類非線性規(guī)劃模型，其常用求解的基本思路可歸納如下：第53頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束(表示函數(shù)的梯度）求出最優(yōu)解，但求解往往是很困難的.

若目標(biāo)函數(shù)的形式簡單，可以通過求解方程（下降迭代法）尋找，該方法的基本步驟如下：所以往往根據(jù)目標(biāo)函數(shù)的特征采用搜索的方法第54頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束②檢驗是否滿足停止迭代的條件，如是，則停止迭代，用來近似問題的最優(yōu)解，否則轉(zhuǎn)至③.④從出發(fā)，沿方向，按某種方法確定步長，使得：⑤令，然后置，返回②適當(dāng)選取初始點，令③按某種規(guī)則確定處的搜索方向.第55頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

在下降迭代算法中，搜索方向起著關(guān)鍵的作用，而當(dāng)搜索方向確定后，步長又是決定算法好壞的重要因素.非線性規(guī)劃只含一個變量，即一維非線性規(guī)劃可以用一維搜索方法求得最優(yōu)解，一維搜索方法主要有進(jìn)退法和黃金分割法.二維的非線性規(guī)劃也可以像解線性規(guī)劃那樣用圖形求解.對于二維非線性規(guī)劃，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.第56頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束2)只有等式約束的非線性規(guī)劃問題通?？捎孟?、拉格朗日乘子法或反函數(shù)法，將其化為無約束問題求解.3)

具有不等式約束的非線性規(guī)劃問題解起來很復(fù)雜，求解這一類問題，通常將不等式化為等式約束，再將約束問題化為無約束問題，用線性逼近的方法將非線性規(guī)劃問題化為線性規(guī)劃問題.第57頁,共111頁，2024年2月25日，星期天下面介紹一個簡單的非線性規(guī)劃問題的例子，其中的一些約束條件是等式，這類非線性規(guī)劃問題可用拉格朗日方法求解.第58頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束例7（石油最優(yōu)儲存方法）有一石油運輸公司，為了減少開支，希望作了節(jié)省石油的存儲空間.但要求存儲的石油能滿足客戶的要求.為簡化問題，假設(shè)只經(jīng)營兩種油，各種符號表示的意義如表4所示.其中供給率指石油公司供給客戶的速度.第59頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束表4

各種符號表示意義表第i種油的存儲量第i種油的價格第i種油的供給率第i種油的每單位的存儲費用第i種油的每單位的存儲空間總存儲公式第60頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束由歷史數(shù)據(jù)得到的經(jīng)驗公式為:且提供數(shù)據(jù)如表5所示：第61頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束表5數(shù)據(jù)表已知總存儲空間石油的種類1930.5022450.24第62頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束代入數(shù)據(jù)后得到的模型為：模型求解：拉格朗日函數(shù)的形式為：

第63頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束即:對求各個變量的偏導(dǎo)數(shù)，并令它們等于零，得:第64頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束解這個線性方程組得：從而可得最小值是12.71

.

表示當(dāng)約束條件右邊的值增大一個單位后，相應(yīng)目標(biāo)函數(shù)值的增加值。比如說：如總存儲空間由24變?yōu)?5時，最優(yōu)值會由12.71變?yōu)榈?5頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束六、多目標(biāo)規(guī)劃模型

在許多實際問題中，衡量一個方案的好壞標(biāo)準(zhǔn)往往不止一個，例如設(shè)計一個導(dǎo)彈，既要射程最遠(yuǎn)，又要燃料最省，還要精度最高.這一類問題統(tǒng)稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題.我們先來看一個生產(chǎn)計劃的例子.第66頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束能耗不得超過160t標(biāo)準(zhǔn)煤其它數(shù)據(jù)如下表：布料生產(chǎn)數(shù)量（m/h）利潤（元/m）最大銷售量（m/周）能耗（t/km）A14000.15400001.2A25100.13510001.3A33600.20300001.4問每周應(yīng)生產(chǎn)三種布料各多少m，才能使該廠的利潤最高，而能源消耗最少？，該廠兩班生產(chǎn)，每周生產(chǎn)時間為80h，例8（生產(chǎn)計劃問題）某廠生產(chǎn)三種布料第67頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束，總利潤為（元），總能耗為解

設(shè)該廠每周生產(chǎn)布料的小時數(shù)為（t標(biāo)準(zhǔn)煤），其中，則上述問題的數(shù)學(xué)模型為第68頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束其中，，.有顯然這是一個多目標(biāo)線性規(guī)劃問題.一般的多目標(biāo)規(guī)劃問題都可寫成如下的形式：第69頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束多目標(biāo)規(guī)劃問題的解法大致可分為兩類：直接解法和間接解法.到目前為止，常用的多為間接解法，即根據(jù)問題的實際背景和特征，設(shè)法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，從而得到滿意解的方法.

許解.多目標(biāo)規(guī)劃問題與前面講的規(guī)劃問題的主要區(qū)別在于：目標(biāo)函數(shù)不止一個，而是p個（）.稱為多目標(biāo)規(guī)劃問題的可行集或容許集，稱為可行解或容第70頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束在多目標(biāo)優(yōu)化問題中，若能從p個目標(biāo)中，確定一個目標(biāo)為主要目標(biāo)，例如，主要目標(biāo)法而把其余目標(biāo)作為次要目標(biāo)，并根據(jù)實際情況，確定適當(dāng)?shù)慕缦拗?，這樣就可以把次要目標(biāo)作為約束來處理，而將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為求解如下的線性或非線性規(guī)劃問題：第71頁,共111頁，2024年2月25日，星期天把多目標(biāo)規(guī)劃問題中的p個目標(biāo)按其重要程度排一個次序，假設(shè)最重要，次之，目錄下頁返回上頁結(jié)束令，其中界限值取為，再次之，L，最后一個目標(biāo).先求出以第一個目標(biāo)為目標(biāo)函數(shù)而原問題則此非線性規(guī)劃問題得最優(yōu)解必為原問題的弱有效解.因此，用主要目標(biāo)法求得的解必是多目標(biāo)優(yōu)化問題的弱有效解或有效解.2）分層序列法第72頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束變的問題：的最優(yōu)解及最優(yōu)值，再求問題：的最優(yōu)解及最優(yōu)值，即，其中：為問題的可行域.第73頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束再求解問題：得最優(yōu)解及最優(yōu)值，L，如此繼續(xù)下去，直到求出第p個問題：得最優(yōu)解及最優(yōu)值，則就是原多目標(biāo)規(guī)劃問題在分層序列意義下得最優(yōu)解，為其最優(yōu)值.第74頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束，其最優(yōu)解是唯一的，則問題的最優(yōu)解也是唯一的，且。因此常將分層序列法修改如下：選取一組適當(dāng)?shù)男≌龜?shù)，成為寬容值，把上述的問題修改如下：再按上述方法依次求解各問題.容易看出，在使用分層序列法時，若對某個問題p.第75頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束對多目標(biāo)規(guī)劃問題中的p個目標(biāo)按期重要程度給以適當(dāng)?shù)臋?quán)系數(shù)

，且，然后用作為新的目得最優(yōu)解，取作為多目標(biāo)規(guī)劃問題的解.3）線性加權(quán)求和法標(biāo)函數(shù)，成為評價（目標(biāo)）函數(shù)，再求解問題第76頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束在一定條件下，用線性加權(quán)求和法求得的最優(yōu)解必是原多目標(biāo)規(guī)劃問題的有效解或弱有效解.例9．求解引言中DVD在線租賃的第三個問題.下面以引言中2005年全國大學(xué)生數(shù)模競賽“DVD在線租賃”問題第三問為例，介紹多目標(biāo)線性規(guī)劃模型以及利用主要目標(biāo)法求解該模型.第77頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束此問是在現(xiàn)有的在線訂單基礎(chǔ)上，為滿足一個月內(nèi)95%的會員得到他想看的DVD，我們進(jìn)行購買量預(yù)算和分配決策，使得會員的滿意度最大.預(yù)算購買量的目的是在盡可能地減少DVD購買量的前提下，滿足要求，進(jìn)行合理分配使得會員的滿意度最大.問題三的分析第78頁,共111頁，2024年2月25日，星期天

我們假設(shè)會員得到他想看的DVD就是指：會員租賃到了他預(yù)定的DVD中的三張；且假設(shè)會員每次租賃前都需要提交新的在線訂單.此問中要求在一個月內(nèi)進(jìn)行分配，因而存在部分DVD的兩次被租賃，但因為是處理同一份訂單，因而存在會員的第二次租賃.第79頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束基于這個假設(shè)，為了最小化購買量，我們在允許當(dāng)前某些會員無法被滿足租賃要求，讓其等待，利用部分會員還回的DVD對其進(jìn)行租賃.根據(jù)問題一，我們認(rèn)為，一個月中每張DVD有0.6的概率被租賃兩次，0.4的概率被租賃一次.即在二次租賃的情況下，每張DVD相當(dāng)于發(fā)揮了張DVD的作用.第80頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束由此，在問題二建立的0-1整數(shù)規(guī)劃模型的求，考慮DVD可能的兩次分配，進(jìn)一步追求DVD基礎(chǔ)上，滿足95%的會員得到他想看DVD的要進(jìn)行求解.總的購買數(shù)量最小.建立雙目標(biāo)整數(shù)規(guī)劃模型第81頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束設(shè)表示第j種DVD需要的購買量.對每種DVD，問題三的模型要求分配的總量不超過相應(yīng)的現(xiàn)有數(shù)量的1.6倍.即:為了讓95%的會員可以得到他想看的3張DVD，即:第82頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束我們希望購買DVD的總數(shù)量最小，即:由此，可以得到問題三的雙目標(biāo)整數(shù)線性規(guī)劃模型如下：第83頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第84頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束對于該雙目標(biāo)整數(shù)線性規(guī)劃模型，我們引入總體滿意度水平（即最小的滿意度）將其滿意度的目標(biāo)轉(zhuǎn)換為約束，如下：問題三的求解與檢驗第85頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束第86頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束利用Lingo軟件，調(diào)整總體滿意度水平進(jìn)行求解。實際計算中，如果要求為整數(shù)，無法求得可行解，因而我們?nèi)∠似湔麛?shù)約束進(jìn)行計算。求得解后，對其進(jìn)行取整。當(dāng)時，我們解得DVD總的最小購買量，其中第j種DVD需要的購買量如下表：第87頁,共111頁，2024年2月25日，星期天表6當(dāng)時最小購買量的值目錄下頁返回上頁結(jié)束DVD編號D01D02D03D04D05D06D07D08D09D10最少購買量14211724121719212214DVD編號D11D12D13D14D15D16D17D18D19D20最少購買量18181717172418161823DVD編號D21D22D23D24D25D26D27D28D29D30最少購買量20182214181715121624DVD編號D31D32D33D34D35D36D37D38D39D40最少購買量19222019222213171717DVD編號D41D42D43D44D45D46D47D48D49D50最少購買量32201621221620152020第88頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束續(xù)上表DVD編號D51D52D53D54D55D56D57D58D59D60最少購買量24171917191819172021DVD編號D61D62D63D64D65D66D67D68D69D70最少購買量16191920171917212019DVD編號D71D72D73D74D75D76D77D78D79D80最少購買量21221520151412171917DVD編號D81D82D83D84D85D86D87D88D89D90最少購買量18101412211322151317DVD編號D91D92D93D94D95D96D97D98D99D100最少購買量24171514251522201122第89頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

我們利用規(guī)劃模型求得每種DVD的購買量后，需要對其進(jìn)行可行性校驗，測試此結(jié)果是否可以且具有盡可能大的總體滿意度.滿足一個月內(nèi)比例為95%的會員得到他想看DVD，第90頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束校驗方法：

（一）根據(jù)訂單和求得的DVD購買數(shù)量，利用問題二的規(guī)劃模型進(jìn)行第一次分配，對分配情況：租賃的會員，DVD的分配情況，剩余的各種DVD數(shù)量作記錄；同時將已租賃的會員在滿意指數(shù)矩陣的指數(shù)全變?yōu)?，即不考慮對其進(jìn)行第二次分配.第91頁,共111頁，2024年2月25日，星期天

（二）隨機從第一次得到DVD的會員中抽取60%，將這部分人所還回的DVD與第一次分配余下的DVD合在一起，作為第二次分配時各種DVD的現(xiàn)有量.然后，利用問題二的0-1線性規(guī)劃模型對第一次未分配到DVD的會員進(jìn)行第二次分配；第92頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束

（三）統(tǒng)計出經(jīng)過兩次分配后，得到DVD的會得到DVD的會員大于95%，則認(rèn)為模型三是合理的.種算法進(jìn)行多次隨機模擬，若大多數(shù)情況下可以使員的比例，若大于95%，則此次分配成功.利用這第93頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束校驗結(jié)果：

因為每次檢驗需時約1小時，我們只對問題三表77次模擬結(jié)果每次的觀看比例列表驗證次數(shù)1234567觀看比例95.8％96.6％93.4％95.3％95.9％96.1％95.7％觀看比例大于95%）.下面給出7次模擬得到的觀求得的結(jié)果進(jìn)行了7次模擬，其中6次符合要求（看比例（表7）：第94頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束七、動態(tài)規(guī)劃模型過程中的最優(yōu)控制問題.

動態(tài)規(guī)劃所研究的對象是多階段對策問題，是在20世紀(jì)50年代初期由美國數(shù)學(xué)家R.Bellman等人提出的一類規(guī)劃模型.動態(tài)規(guī)劃是現(xiàn)代管理領(lǐng)域的一種重要的決策方法，其主要應(yīng)用有最優(yōu)路徑問題、資源分配問題、投資決策問題、生產(chǎn)計劃與庫存問題、排序問題、貨物裝載問題以及生產(chǎn)第95頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束理多階段決策問題的最優(yōu)化原理.效益的總和達(dá)到最優(yōu).多階段決策問題是指一類活動過程，它可分為若干個相互聯(lián)系的階段，在每個階段都需要做出決策，這個決策不僅決定這一階段的效益，而定以后，就得到一個決策序列，稱為策略.多階段決策問題就是求一個策略，使各階段的效益的下面我們通過講解一個最短路問題來引出處且決定下一階段的初始狀態(tài)，每個階段的決策確第96頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束例10有一輛汽車要把貨物從A城運到E城，而可供選擇，選取怎樣的路線才能使路程最短？從A城到E城必須經(jīng)過一些城市，整段路程可以分為若干個階段，而每個階段又有若干個城市假定從A城到E城的所有路線如下圖所示：第97頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束圖1從A城到E城的路線其中B1,B2,C1,C2,D1,D2是可供選擇的城市，途中的數(shù)字表示兩城之間的距離（以10千米為單位）.561327424146第98頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束顯然，這是一個多階段決策問題：從A到E可以分為4個階段.從A點出發(fā)到B1或B2為第一階段，這時有兩個選擇：走到B1或者走到B2.若我們選擇走到B1的決策，則B1就是下一個階段的起點.在下一階段，我們從B1出發(fā)，有一個可供選擇的決策集合{C1,C2}，很明顯，前面各階段的決策如何選擇，直接影響著其余各階段的行進(jìn)路線，我們的目的就是在各個階段選擇一個決策，使由它們決定的總路程最短.第99頁,共111頁，2024年2月25日，星期天目錄下頁返回上頁結(jié)束下面我們來求此問題的最短路線，并以此來說明處理多階段決策問題的最優(yōu)化原理.先引入動態(tài)規(guī)劃的基本概念.令k表示由某點至終點之間的階段數(shù).例如從A到E可以分為4個階段，從B1到E是5個階段；第k階段的終點又是第k+1階段的起點，記為Sk，第100頁,共111頁，20