《(精品)規(guī)劃理論及模型(數(shù)模)》由會員分享，可在線閱讀，更多相關《(精品)規(guī)劃理論及模型(數(shù)模)（47頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標題樣式,下,回,停,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標題樣式,一、引言,二、線性規(guī)劃模型,三、整數(shù)線性規(guī)劃模型,第一講 規(guī)劃理論及模型,四、,0-1,整數(shù)規(guī)劃模型,五、非線性規(guī)劃模型,六、多目標規(guī)劃模型,七、動態(tài)規(guī)劃模型,一、引言,我們從,2005,年“高教社杯”全國大學生數(shù)模競,談起,.,其中第二個問題是一個如何來分配有限資源，,從而達到人們期望目標的優(yōu)化分配數(shù)學模型,.,它,在運籌學中處于中心的地位,.,這類問題一般可以,歸結為,數(shù)學規(guī)劃模型,.,賽的,B,題“,DVD,在線租賃”問題的第二問和第三問,規(guī)
2、劃模型的應用極其廣泛，其作用已為越來,來越急速地滲透于工農(nóng)業(yè)生產(chǎn)、商業(yè)活動、軍事,行為核科學研究的各個方面，為社會節(jié)省的財富、,創(chuàng)造的價值無法估量,.,特別是在數(shù)模競賽過程中，規(guī)劃模型是最常,見的一類數(shù)學模型,.,從,92-06,年全國大學生數(shù)模競,越多的人所重視,.,隨著計算機的逐漸普及，它越,賽試題的解題方法統(tǒng)計結果來看，規(guī)劃模型共出,現(xiàn)了,15,次，占到了,50%,，也就是說每兩道競賽題,中就有一道涉及到利用規(guī)劃理論來分析、求解,.,二、線性規(guī)劃模型,線性規(guī)劃模型是所有規(guī)劃模型中最基本、最,例,1.,（,食譜問題）設有,n,種食物，各含,m,種營養(yǎng),素，第,j,種食物中第,i,中營養(yǎng)素的
3、含量為,a,ij,n,種,食物價格分別為,c,1, c,2, ,c,n,，,請確定食譜中,n,種食,物的數(shù)量,x,1, x,2, ,x,n,，,要求在食譜中,m,種營養(yǎng)素,簡單的一種,.,2.1,線性規(guī)劃模型的標準形式,的含量分別不低于,b,1, b,2, ,b,m,的情況下，使得總,總的費用最低,.,首先根據(jù)食物數(shù)量及價格可寫出食譜費用為,其次食譜中第,i,種營養(yǎng)素的含量為,因此上述問題可表述為：,解,上述食譜問題就是一個典型的線性規(guī)劃問題，,尋求以線性函數(shù)的最大（?。┲禐槟繕说臄?shù)學模,型.,它是指在一組線性的等式或不等式的約束條件下，,線性規(guī)劃模型的三種形式, 一般形式,目標函數(shù),價值向量
4、,價值系數(shù),決策變量,右端向量,系,數(shù),矩,陣,非負約束,自由變量, 規(guī)范形式, 標準形式,三種形式的,LP,問題全都是等價的，即一種形式的,LP,可以簡單的變換為另一種形式的,LP,，,且它們有相同的解,.,以下我們僅將一般形式化成規(guī)范形式和標準形式,.,目標函數(shù)的轉化,x,o,z,-z,約束條件和變量的轉化,為了把一般形式的,LP,問題變換為規(guī)范形式，我們必須消除等式約束和符號無限制變量,.,在一般形式的,LP,中，一個等式約束,可用下述兩個不等式約束去替代,這樣就把一般形式的,LP,變換為規(guī)范形式,.,對于一個無符號限制變量 ，引進兩個非負變量 和 ，并設,為了把一般形式的,LP,問題變
5、換為標準形式，必須消除其不等式約束和符號無限制變量,.,對于一個不等式約束,代替上述的不等式約束,.,對符號無限制變量的處理可按上述方法進行,.,可引入一個,剩余變量,，,用,對于不等式約束,代替上述的不等式約束,這樣就把一般形式的,LP,變換為標準形式,.,可引入一個,松弛變量,，用,針對標準形式的線性規(guī)劃問題，其解的理論,分析已經(jīng)很完備，在此基礎上也提出了很好的算,單純形方法是線性規(guī)劃問題的最為基礎、也,法,單純形方法及其相應的變化形式（兩階段,2.2,線性規(guī)劃模型的求解,法，對偶單純形法等）,.,是最核心的算法。它是一個迭代算法，先從一個,特殊的可行解（極點）出發(fā)，通過判別條件去判,斷該
6、可行解是否為最優(yōu)解（或問題無界），若不,是最優(yōu)解，則根據(jù)相應規(guī)則，迭代到下一個更好的可行解（極點），直到最優(yōu)解（或問題無界）,.,關于線性規(guī)劃問題解的理論和單純形法具體的求解過程可參見文獻,1.,然后在實際應用中，特別是數(shù)學建模過程中，遇到線性規(guī)劃問題的求解，我們一般都是利用現(xiàn)有的軟件進行求解，此時通常并不要求線性規(guī)劃問題是標準形式,.,比較常用的求解線性規(guī)劃模型的軟件包有,LINGO,和,LINDO.,運輸問題,例,2.,設要從甲地調(diào)出物資,2000,噸，從乙地調(diào)出物,資,1100,噸，分別供給,A,地,1700,噸、,B,地,1100,噸、,C,假定運費與運量成正比,.,在這種情況下，采用
7、不,地,200,噸、,D,地,100,噸,.,已知每噸運費如表,1.1,所示,.,同的調(diào)撥計劃，運費就可能不一樣,.,現(xiàn)在問：怎,樣才能找出一個運費最省的調(diào)撥計劃？,15,7,25,21,甲,15,37,51,51,乙,D,C,B,A,表,1.1,銷,地,運,費,產(chǎn),地,乙,甲,D,C,B,A,解,一般的運輸問題可以表述如下：,數(shù)學模型：,若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即,類似與將一般的線性規(guī)劃問題轉化為其標準,否則，稱為不平衡的運輸問題，包括：,，則稱該問題為平衡的運輸問題,.,總產(chǎn)量,總銷量和總產(chǎn)量,總銷量,.,形式，我們總可以通過引入假想的銷地或產(chǎn)地，,將不平衡的運輸問題轉化為
8、平衡的運輸問題,.,從,而，我們的重點就是解決平衡運輸問題的求解,.,顯然，運輸問題是一個標準的線性規(guī)劃問題，因而當然可以運用單純形方法求解,.,但由于平衡的運輸問題的特殊性質(zhì)，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業(yè)法，該方法將單純形法與平衡的運輸問題的特殊性質(zhì)結合起來，很方便地實行了運輸問題的求解,.,關于運輸問題及其解法的進一步介紹參加文獻,2.,對于線性規(guī)劃問題，如果要求其決策變量取,整數(shù)值，則稱該問題為整數(shù)線性規(guī)劃問題,.,平面法和分支定界法是兩種常用的求解整數(shù)線性,對于整數(shù)線性規(guī)劃問題的求解，其難度和運,三、整數(shù)線性規(guī)劃模型,算量遠大于同規(guī)模的線性規(guī)劃問題,.,G
9、omory,割,規(guī)劃問題的方法（見文獻,1,）,.,此外，同線性規(guī),劃模型一樣，我們也可以運用,LINGO,和,LINDO,軟,件包來求解整數(shù)線性規(guī)劃模型,.,以,1988,年美國大學生數(shù)學建模競賽,B,題為例，說明整數(shù)線性規(guī)劃模型的建立及用,LINGO,軟件包如何求解整數(shù)線性規(guī)劃模型。,例,3.,有七種規(guī)格的包裝箱要裝到兩節(jié)鐵路平板車,上去。包裝箱的寬和高是一樣的，但厚度（,t,，以,cm,計）及重量（,w,，以,kg,計）是不同的,.,表,1,給出,了每種包裝箱的厚度、重量以及數(shù)量。每節(jié)平板,車有,10.2,m,長的地方可用來裝包裝箱（像面包片,那樣），載重為,40,t,.,由于當?shù)刎涍\的
10、限制，對于,C,5,C,6,C,7,類包裝箱的總數(shù)有一個特別的限制：這,類箱子所占的空間（厚度）不能超過,302.7,cm,.,試,把包裝箱裝到平板車上，使得浪費的空間最小,.,種類,C,1,C,2,C,3,C,4,C,5,C,6,C,7,t,/,cm,48.7,53.0,61.3,72.0,48.7,52.0,64.0,w,/,kg,2000,3000,1000,500,4000,2000,1000,n,/,件,8,7,9,6,6,4,8,為在第 節(jié)車上裝載第 件包裝箱的,解,令,下面我們建立該問題的整數(shù)線性規(guī)劃模型。,1),約束條件,兩節(jié)車的裝箱數(shù)不能超過需要裝的件數(shù)，即：,每節(jié)車可裝的長
11、度不能超過車能提供的長度：,每節(jié)車可裝的重量不超過車能夠承受的重量：,對于,C,5,C,6,C,7,類包裝箱的總數(shù)的特別限制：,2),目標函數(shù),浪費的空間最小，即包裝箱的總厚度最大：,3),整數(shù)線性規(guī)劃模型,由上一步中的求解結果可以看出，,4),模型求解,運用,LINGO,軟件求解得到：,5),最優(yōu)解的分析說明,的裝車方案，此時裝箱的總長度為,1019.7,cm,，,兩節(jié)車共裝箱的總長度為,2039.4,cm,.,即為最優(yōu),但是，上述求解結果只是其中一種最優(yōu)的,裝車方案，即此答案并不唯一,.,0-1,整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，它要求,線性規(guī)劃模型中的決策變量,x,ij,只能取值為,0,或,
12、1.,單隱枚舉法，該方法是一種基于判斷條件（過濾,0-1,整數(shù)規(guī)劃模型的求解目前并沒有非常好的,四、,0-1,整數(shù)規(guī)劃模型,算法，對于變量比較少的情形，我們可以采取簡,條件）的窮舉法,.,我們也可以利用,LINGO,和,LINDO,軟件包來求,解,0-1,整數(shù)規(guī)劃模型,.,背包問題,例,4.,有,n,個物品，編號為,1, 2, ,n,，第,i,件物品,重,a,i,千克，價值為,c,i,元，現(xiàn)有一個載重量不超過,大，應如何裝載這些物品？,a,千克的背包，為了使裝入背包的物品總價值最,用變量,x,i,表示物品,i,是否裝包，,i,=,1, 2, ,n,，,并令：,解,可得到背包問題的規(guī)劃模型為：,
13、指派問題,例,5.,有,n,項任務，由,n,個人來完成，每個人只能,做一件， 第,i,個人完成第,j,項任務要,c,ij,小時，如,何合理安排時間才能使總用時最小？,引入狀態(tài)變量,x,ij,，并令：,解,則總用時表達式為：,可得到指派問題的規(guī)劃模型為：,上面介紹的指派問題稱為指派問題的標準形,式，還有許多其它的諸如人數(shù)與任務數(shù)不等、及,但一般可以通過一些轉化，將其變?yōu)闃藴市问?.,某人可以完成多個任務，某人不可以完成任務，,某任務必須由某人完成等特殊要求的指派問題,.,對于標準形式的指派問題，我們可以利用匈,牙利算法實現(xiàn)求解,.,它將指派問題中的系數(shù)構成,一個矩陣，利用矩陣上簡單的行和列變換，
14、結合,解的判定條件，實現(xiàn)求解（見文獻,2,）,.,DVD,在線租賃第二個問題的求解,問題二的分析,經(jīng)營成本和會員的滿意度是被考慮的兩個相互制約的重要因素,.,在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為,DVD,的數(shù)量,.,我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量,DVD,進行分配決策，使得,DVD,的數(shù)量盡量小，會員滿意度最大,.,假設按照公歷月份進行的租賃業(yè)務，即會員無論兩次租賃還是一次租賃，必須在當月內(nèi)完成,DVD,的租與還,.,同時假設網(wǎng)站對其會員進行一次租賃業(yè)務時，只能向其提供,3,張該會員已經(jīng)預定的,DVD,，否則不進行租賃,.,經(jīng)觀察，可以認為在線訂
15、單中每個會員的預定,DVD,的表示偏好程度的數(shù)字反映了會員對所預定不同,DVD,的滿意程度，且當會員租到其預定排序為,1,，,2,，,3,的三張,DVD,時，滿意度達到,100% .,會員沒有預定的,DVD,對其滿意度的貢獻為,0 .,利用層次分析法，對此滿意指數(shù)的合理性進,行了簡單分析,.,該問題要求根據(jù)現(xiàn)有的,100,種,DVD,的數(shù)量和當前需要處理的,1000,位會員的在線訂單，制定分配策略，使得會員達到最大的滿意度,.,因而我們認為只需對這些,DVD,進行一次性分配，使得會員的總體滿意度達到最大,.,為此考慮建立優(yōu)化模型，進行求解,.,問題二的模型及求解,經(jīng)營成本和會員的滿意度是被考慮
16、的兩個相互制約的重要因素,.,在忽略郵寄成本的前提下，經(jīng)營成本主要體現(xiàn)為,DVD,的數(shù)量,.,我們主要考慮在會員向網(wǎng)站提供需求信息，且滿足一定要求的前提下，對給定數(shù)量,DVD,進行分配決策，使得,DVD,的數(shù)量盡量小，會員滿意度最大,.,由此，可得問題二的,0-1,整數(shù)線性規(guī)劃模型如下：,根據(jù)所得的,0-1,整數(shù)線性規(guī)劃模型，利用,LINGO,軟件進行求解，我們得到了一組最優(yōu)分配方案（見表,3,）,.,該組最優(yōu)解其目標函數(shù)會員總體最大滿意度為,91.56%,，只有,6,人未成功租賃（如：前,30,名會員中,C0008,被分配到,DVD,），其余,994,個會員全都得到了,3,張預定的,DVD,.,再見,
(精品)規(guī)劃理論及模型(數(shù)模)
