線性規(guī)劃整數(shù)規(guī)劃0-1規(guī)劃.ppt

1、一、引言,二、線性規(guī)劃模型,三、整數(shù)線性規(guī)劃模型,四、0-1整數(shù)規(guī)劃模型,五、非線性規(guī)劃模型,六、多目標(biāo)規(guī)劃模型,七、動(dòng)態(tài)規(guī)劃模型,一、引言,我們從2005年“高教社杯”全國(guó)大學(xué)生數(shù)模競(jìng),談起.,其中第二個(gè)問題是一個(gè)如何來(lái)分配有限資源，,從而達(dá)到人們期望目標(biāo)的優(yōu)化分配數(shù)學(xué)模型.,這類問題一般可以歸結(jié)為數(shù)學(xué)規(guī)劃模型.,賽的B題“DVD在線租賃”問題的第二問和第三問,規(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ú)法估量.,特別是在數(shù)模競(jìng)賽過(guò)程中，規(guī)劃模型是最常,見的一類數(shù)學(xué)模型. 從歷年全國(guó)大學(xué)生數(shù)模競(jìng)

2、賽,越多的人所重視. 隨著計(jì)算機(jī)的逐漸普及，它越,試題的解題方法統(tǒng)計(jì)結(jié)果來(lái)看，每年至少有一道,題涉及到利用規(guī)劃理論來(lái)分析、求解.,二、線性規(guī)劃模型,線性規(guī)劃模型是所有規(guī)劃模型中最基本、最,例1.（食譜問題）設(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)單的一種.,2.1 線性規(guī)劃模型的標(biāo)準(zhǔn)形式,的含量分別不低于b1, b2, , bm 的情況下，使得總,總的費(fèi)用最低.,首先根據(jù)食物數(shù)量及價(jià)格可寫出食譜費(fèi)用為,其次食

3、譜中第 i 種營(yíng)養(yǎng)素的含量為,因此上述問題可表述為：,解,上述食譜問題就是一個(gè)典型的線性規(guī)劃問題，,尋求以線性函數(shù)的最大（?。┲禐槟繕?biāo)的數(shù)學(xué)模,型.,它是指在一組線性的等式或不等式的約束條件下，,線性規(guī)劃模型的三種形式, 一般形式,目標(biāo)函數(shù) 價(jià)值向量 價(jià)值系數(shù) 決策變量,右端向量,系 數(shù) 矩 陣, 規(guī)范形式, 標(biāo)準(zhǔn)形式,三種形式的LP問題全都是等價(jià)的，即一種形式的LP可以簡(jiǎn)單的變換為另一種形式的LP，且它們有相同的解 .,以下我們僅將一般形式化成規(guī)范形式和標(biāo)準(zhǔn)形式.,目標(biāo)函數(shù)的轉(zhuǎn)化,約束條件和變量的轉(zhuǎn)化,為了把一般形式的LP問題變換為規(guī)范形式，我們必須消除等式約束和符號(hào)無(wú)限制變量.在一般形式的

4、LP中，一個(gè)等式約束,可用下述兩個(gè)不等式約束去替代,這樣就把一般形式的LP變換為規(guī)范形式.,對(duì)于一個(gè)無(wú)符號(hào)限制變量 ，引進(jìn)兩個(gè)非負(fù)變量 和 ，并設(shè),為了把一般形式的LP問題變換為標(biāo)準(zhǔn)形式，必須消除其不等式約束和符號(hào)無(wú)限制變量.,對(duì)于一個(gè)不等式約束,代替上述的不等式約束.,對(duì)符號(hào)無(wú)限制變量的處理可按上述方法進(jìn)行.,可引入一個(gè)剩余變量 ，,用,對(duì)于不等式約束,代替上述的不等式約束,這樣就把一般形式的LP變換為標(biāo)準(zhǔn)形式 .,可引入一個(gè)松弛變量,，用,針對(duì)標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其解的理論,分析已經(jīng)很完備，在此基礎(chǔ)上也提出了很好的算,單純形方法是線性規(guī)劃問題的最為基礎(chǔ)、也,法單純形方法及其相應(yīng)的變化形

5、式（兩階段,2.2 線性規(guī)劃模型的求解,法，對(duì)偶單純形法等）.,是最核心的算法。它是一個(gè)迭代算法，先從一個(gè),特殊的可行解（極點(diǎn)）出發(fā)，通過(guò)判別條件去判,斷該可行解是否為最優(yōu)解（或問題無(wú)界），若不,是最優(yōu)解，則根據(jù)相應(yīng)規(guī)則，迭代到下一個(gè)更好的可行解（極點(diǎn)），直到最優(yōu)解（或問題無(wú)界）.關(guān)于線性規(guī)劃問題解的理論和單純形法具體的求解過(guò)程可參見文獻(xiàn)1.,在實(shí)際應(yīng)用中，特別是數(shù)學(xué)建模過(guò)程中，遇到線性規(guī)劃問題的求解，我們一般都是利用現(xiàn)有的軟件進(jìn)行求解，此時(shí)通常并不要求線性規(guī)劃問題是標(biāo)準(zhǔn)形式. 比較常用的求解線性規(guī)劃模型的軟件包有LINGO和LINDO.,運(yùn)輸問題,例2. 設(shè)要從甲地調(diào)出物資2000噸，從乙地

6、調(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)在問：怎,樣才能找出一個(gè)運(yùn)費(fèi)最省的調(diào)撥計(jì)劃？,解,一般的運(yùn)輸問題可以表述如下：,數(shù)學(xué)模型：,若其中各產(chǎn)地的總產(chǎn)量等于各銷地的總銷量，即,類似與將一般的線性規(guī)劃問題轉(zhuǎn)化為其標(biāo)準(zhǔn),否則，稱為不平衡的運(yùn)輸問題，包括：,，則稱該問題為平衡的運(yùn)輸問題.,總產(chǎn)量總銷量和總產(chǎn)量總銷量.,形式，我們總可以通過(guò)引入假想的銷地或產(chǎn)地，,將不平衡的運(yùn)輸問題轉(zhuǎn)化為平衡的運(yùn)輸問題. 從,而，我們的重點(diǎn)就是解決平衡運(yùn)輸

7、問題的求解.,產(chǎn)銷不平衡問題的處理 在實(shí)際中遇到的運(yùn)輸問題常常不是產(chǎn)銷平衡的，而是下列的一般運(yùn)輸問題模型 m n min f = cij xij （1） i=1 j=1 n s.t. xij ai i = 1,2,m （2） j=1 m xij (=,)bj j = 1,2,n (3） i=1 xij 0 (i=1,2,m;j=1,2,n) （4）,我們可以通過(guò)增加虛設(shè)產(chǎn)地或銷地（加、減松弛變量）把問題轉(zhuǎn)換成產(chǎn)銷平衡問題，下面分別來(lái)討論。 1.產(chǎn)量大于銷量的情況 m n 考慮 ai bj 的運(yùn)輸問題，得到的數(shù)學(xué)模 i=1 j=1 型為,m n min f = cij xij i=1 j=1 n

8、 s.t. xij ai i = 1,2,m j=1 m xij =bj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n),只要在模型中的產(chǎn)量限制約束（前m個(gè)不等式約束）中引入m個(gè)松弛變量 xi,n+1 i= 1, 2, , m 即可，變?yōu)椋?n xij+xin+1=ai i=1,2,m j=1 然后，需設(shè)一個(gè)銷地Bn+1,它的銷量為： m n bn+1= ai- bj i=1 j=1,這里，松弛變量 xi n+1 可以視為從產(chǎn)地 A i 運(yùn)往銷地 Bn+1 的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為 ci n+1=0 i= 1,2,m。 于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)

9、銷平衡的問題。,2.銷量大于產(chǎn)量的情況 m n 考慮 aibj 的運(yùn)輸問題，得到的數(shù)學(xué)模型為 i=1 j=1,m n Min f = cij xij i=1 j=1 n s.t. xij =ai i = 1,2,m j=1 m xij bj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n),只要在模型中的產(chǎn)量限制約束（后n個(gè)不等式約束）中引入n個(gè)松弛變量xm+1j j = 1,2,n即可，變?yōu)椋?m xij+xm+1j=bj j=1,2,m i=1 然后，需設(shè)一個(gè)產(chǎn)地A m+1,它的銷量為： n m am+1= bj- ai j=1 i=1,這里，松弛變量 x m+1,j

10、 可以視為從產(chǎn)地 A m+1 運(yùn)往銷地 B j 的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為 c m+1,j = 0 j = 1,2,n。于是，這個(gè)運(yùn)輸問題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷平衡的問題。,顯然，運(yùn)輸問題是一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃問題，因而當(dāng)然可以運(yùn)用單純形方法求解. 但由于平衡的運(yùn)輸問題的特殊性質(zhì)，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業(yè)法，該方法將單純形法與平衡的運(yùn)輸問題的特殊性質(zhì)結(jié)合起來(lái)，很方便地實(shí)行了運(yùn)輸問題的求解. 關(guān)于運(yùn)輸問題及其解法的進(jìn)一步介紹參考文獻(xiàn)2.,對(duì)于線性規(guī)劃問題，如果要求其決策變量取,整數(shù)值，則稱該問題為整數(shù)線性規(guī)劃問題.,平面法和分支定界法是兩種常用的求解整數(shù)

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

12、包片,那樣），載重為40t. 由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì)于,C5, C6, C7 類包裝箱的總數(shù)有一個(gè)特別的限制：這,類箱子所占的空間（厚度）不能超過(guò)302.7cm. 試,把包裝箱裝到平板車上，使得浪費(fèi)的空間最小.,為在第 節(jié)車上裝載第 件包裝箱的,解 令,下面我們建立該問題的整數(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ī)劃模型,由上一步中的求解結(jié)果可以看出，,

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

14、 n 個(gè)物品，編號(hào)為1, 2, , n，第 i 件物品,重 ai 千克，價(jià)值為 ci 元，現(xiàn)有一個(gè)載重量不超過(guò),大，應(yīng)如何裝載這些物品？,a 千克的背包，為了使裝入背包的物品總價(jià)值最,用變量 xi 表示物品 i 是否裝包，i =1, 2, , 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á)式為：,可得到指派問題的規(guī)劃模型為：,上面介紹的指派問題稱為指派問題的標(biāo)準(zhǔn)形,式，還有許多其它的諸如

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

16、會(huì)員滿意度最大.,假設(shè)按照公歷月份進(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ù)定的DVD，否則不進(jìn)行租賃.,經(jīng)觀察，可以認(rèn)為在線訂單中每個(gè)會(huì)員的預(yù)定DVD的表示偏好程度的數(shù)字反映了會(huì)員對(duì)所預(yù)定不同DVD的滿意程度，且當(dāng)會(huì)員租到其預(yù)定排序?yàn)?，2，3的三張DVD時(shí)，滿意度達(dá)到100% .會(huì)員沒有預(yù)定的DVD對(duì)其滿意度的貢獻(xiàn)為0 .,利用層次分析法，對(duì)此滿意指數(shù)的合理性進(jìn),行了簡(jiǎn)單分析.,該問題要求根據(jù)現(xiàn)有的100種DVD的數(shù)量和當(dāng)前需要處理的1000位會(huì)員的在線訂單，制定分配策略，使得會(huì)員達(dá)到最大的滿意度. 因而我們認(rèn)為,只需對(duì)這些DVD進(jìn)行一次性分配，使得會(huì)員的總體滿意度達(dá)到最大. 為此考慮建立優(yōu)化模型，進(jìn)行求解.,問題二的模型及求解,經(jīng)營(yíng)成本和會(huì)員的滿意度是被考慮的兩個(gè)相互制約的重要因素