二次規(guī)劃和鋼管運(yùn)輸問(wèn)題模型剖析

二次規(guī)劃和鋼管運(yùn)輸問(wèn)題模型剖析第一頁(yè)，共三十七頁(yè)，編輯于2023年，星期六若數(shù)學(xué)規(guī)劃模型中目標(biāo)函數(shù)或約束條件中有一個(gè)或多個(gè)是變量的非線性函數(shù)，則這樣的規(guī)劃模型叫做非線性規(guī)劃模型。和此模型相比，前面我們介紹的多是線性問(wèn)題。非線性規(guī)劃的求解相對(duì)線性問(wèn)題要復(fù)雜的多，對(duì)非線性規(guī)劃而言，不同的問(wèn)題有不同的求解方法。非線性問(wèn)題規(guī)劃中有一類較簡(jiǎn)單的問(wèn)題----二次規(guī)劃，許多實(shí)際問(wèn)題的數(shù)學(xué)模型會(huì)歸結(jié)為二次規(guī)劃。此處，簡(jiǎn)單介紹它的解法。第一部分：二次規(guī)劃模型第二頁(yè)，共三十七頁(yè)，編輯于2023年，星期六一般的非線性規(guī)劃模型其中，均為的函數(shù)。是其中使得有定義的一個(gè)開集。若約束條件都不存在，就是無(wú)約束模型。若目標(biāo)和約束滿足下面條件，問(wèn)題就稱為二次規(guī)劃。第三頁(yè)，共三十七頁(yè)，編輯于2023年，星期六二次規(guī)劃模型其中，是一個(gè)對(duì)稱矩陣，此問(wèn)題為一般的二次規(guī)劃模型。第四頁(yè)，共三十七頁(yè)，編輯于2023年，星期六凸二次規(guī)劃的若干特殊結(jié)論若模型（2）求最小值時(shí)，Q是半正定（正定）矩陣，則此二次規(guī)劃為凸（嚴(yán)格凸）二次規(guī)劃。（若為最大化問(wèn)題，則需Q負(fù)定或半負(fù)定）眾所周知，一般非線性規(guī)劃問(wèn)題，求得的往往是局部最優(yōu)解，而全局最優(yōu)解并不一定存在，而且即使存在的話，也多半不唯一，但如果問(wèn)題是凸二次規(guī)劃的話，結(jié)果則不同。凸二次規(guī)劃有如下結(jié)論（不加證明的給出）：第五頁(yè)，共三十七頁(yè)，編輯于2023年，星期六定理：對(duì)凸（二次）規(guī)劃問(wèn)題，K-T點(diǎn)即是最優(yōu)解點(diǎn)，即K-T條件是最優(yōu)解存在的充分必要條件。定理：對(duì)嚴(yán)格凸（二次）規(guī)劃問(wèn)題，全局極小點(diǎn)（如果存在）是唯一的。定理：對(duì)凸（二次）規(guī)劃問(wèn)題，任何局部極小點(diǎn)都是全局極小點(diǎn)，且極小點(diǎn)的集合為凸集。第六頁(yè)，共三十七頁(yè)，編輯于2023年，星期六二次規(guī)劃的K-T條件設(shè)x*是上述二次規(guī)劃問(wèn)題的解，則由非線性規(guī)劃的K-T條件結(jié)論得二次規(guī)劃對(duì)應(yīng)的K-T條件：存在Lagrange乘子使得K-T條件是一般非線性規(guī)劃局部最優(yōu)解存在的必要條件第七頁(yè)，共三十七頁(yè)，編輯于2023年，星期六若令則K-T條件可以寫成第八頁(yè)，共三十七頁(yè)，編輯于2023年，星期六等式約束二次規(guī)劃的解法其中，是一個(gè)對(duì)稱矩陣，x,q為n維列向量，考慮等式約束二次規(guī)劃：且rank(A)=m，即A列滿秩。由以上命題和K-T條件，易得以下結(jié)論：第九頁(yè)，共三十七頁(yè)，編輯于2023年，星期六定理：設(shè)Q是半正定矩陣，則x是上述問(wèn)題的全局最優(yōu)解，是相應(yīng)乘子向量的充要條件是：x，是線性方程組的解定理表明，求解等式約束二次規(guī)劃問(wèn)題可轉(zhuǎn)化為求解線性方程組問(wèn)題。線性方程組的解法很多，常用的比如消去法等第十頁(yè)，共三十七頁(yè)，編輯于2023年，星期六不等式約束二次規(guī)劃的求解方法對(duì)于一般的包含不等式約束的凸二次規(guī)劃，求解的方法有很多，比如Lemke方法、Wolfe方法、序列二次規(guī)劃法、有效集法（又稱積極集法）等，近年來(lái)，有效集法在中等規(guī)模實(shí)際問(wèn)題的求解中使用較廣泛。第十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期六目錄題目來(lái)源題目題目重述基本假設(shè)問(wèn)題分析題目求解的思路題目求解方法第二部分：2000年B題剖析第十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期六題目來(lái)源2000年全國(guó)數(shù)模競(jìng)賽B題命題的主要思路是結(jié)合當(dāng)時(shí)的大事－－西氣東輸給出的，但為了適應(yīng)數(shù)模要求在三天完成，時(shí)間較短的特點(diǎn)，對(duì)問(wèn)題做了適當(dāng)簡(jiǎn)化。第十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期六題目第十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期六第十五頁(yè)，共三十七頁(yè)，編輯于2023年，星期六第十六頁(yè)，共三十七頁(yè)，編輯于2023年，星期六第十七頁(yè)，共三十七頁(yè)，編輯于2023年，星期六題目重述要求：簡(jiǎn)潔的表述清楚題目要求，一般不要毫無(wú)改動(dòng)的照抄原題（此處略掉）第十八頁(yè)，共三十七頁(yè)，編輯于2023年，星期六基本假設(shè)要求：根據(jù)題目要求，提出符合常規(guī)的假設(shè)或?yàn)榱朔奖憬忸}提出的一些簡(jiǎn)化問(wèn)題的假設(shè)。例（此題假設(shè)）1.鋼管運(yùn)輸過(guò)程中若用火車則直接把鋼管運(yùn)到公路與鐵路交接處,即下了火車不上火車；2.假設(shè)運(yùn)輸單位可提供足夠的火車與汽車；3.費(fèi)用計(jì)算時(shí)按鋼管數(shù)量算，不考慮其他計(jì)費(fèi)方法及因素。4.運(yùn)費(fèi)中不足整公里部分按整公里計(jì)。5.假設(shè)向每個(gè)鋼管廠都訂購(gòu)鋼管。6.設(shè)１km主管道鋼管為１單位鋼管。7.路中鋪設(shè)的鋼管只允許由其相鄰站點(diǎn)提供。8.不計(jì)各個(gè)環(huán)節(jié)中的裝卸費(fèi)用

。。。。。。第十九頁(yè)，共三十七頁(yè)，編輯于2023年，星期六問(wèn)題分析

本題要鋪設(shè)一條的天然氣管道，使得總費(fèi)用最小?？梢赃@樣考慮問(wèn)題：先把鋼廠生產(chǎn)的鋼管運(yùn)到各個(gè)站點(diǎn)再往兩邊運(yùn)送，再計(jì)算出總的費(fèi)用使之最小。

首先應(yīng)該想到的是運(yùn)輸問(wèn)題模型，但由于鐵路、公路運(yùn)費(fèi)的不同還有鋼管出廠銷價(jià)的差別，這不是一個(gè)簡(jiǎn)單的運(yùn)輸問(wèn)題。第二十頁(yè)，共三十七頁(yè)，編輯于2023年，星期六題目求解方法法一：運(yùn)輸問(wèn)題方法這是多數(shù)同學(xué)首先想到的方法。最簡(jiǎn)單的運(yùn)輸問(wèn)題模型就是線性規(guī)劃中的標(biāo)準(zhǔn)運(yùn)輸問(wèn)題，用單純形法求解此類特殊問(wèn)題的具體實(shí)現(xiàn)就是表上作業(yè)法，這個(gè)方法我們已經(jīng)在運(yùn)籌學(xué)課上學(xué)習(xí)過(guò)了，多數(shù)同學(xué)都不會(huì)陌生。運(yùn)輸問(wèn)題模型中最重要的就是運(yùn)輸單位物品的運(yùn)價(jià)，此題中的運(yùn)費(fèi)包括兩部分：由鋼廠到各個(gè)管道結(jié)點(diǎn)的運(yùn)費(fèi)和由各管道結(jié)點(diǎn)運(yùn)到各施工處的費(fèi)用。第二十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期六最簡(jiǎn)單最直觀的想法就是分“兩步走”。第一步：求出各鋼廠到各鋪設(shè)結(jié)點(diǎn)的單位最小運(yùn)費(fèi)；這部分包括鐵路運(yùn)費(fèi)和公路運(yùn)費(fèi)，通過(guò)合理的方式可將鐵路運(yùn)費(fèi)轉(zhuǎn)換成公路運(yùn)費(fèi)（具體后面說(shuō)明），再利用求最短路的方法求出我們需要的單位最小運(yùn)費(fèi)。第二步：沿著鋪設(shè)管道從各結(jié)點(diǎn)到各施工地的單位最小運(yùn)費(fèi)。如果這兩個(gè)運(yùn)費(fèi)都能算出，我們就可以將待鋪設(shè)的主管道全線按照1公里作為一個(gè)單位分割成5171個(gè)點(diǎn)（對(duì)于問(wèn)題三，可以將樹形圖分割成5903個(gè)點(diǎn)）。這樣問(wèn)題就變成了一個(gè)理想的運(yùn)輸問(wèn)題，根據(jù)我們所學(xué)的知識(shí)，求解是不難的。簡(jiǎn)單的初始思路第二十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期六初始思路的考慮不周或未盡之處我們對(duì)各鋼廠的出廠銷價(jià)未做考慮，即我們已經(jīng)默認(rèn)各鋼廠的出廠銷價(jià)是相同的或此銷價(jià)的不同不影響鋼管的訂購(gòu)和運(yùn)輸，但這是不符合題意的；鐵路和公路的運(yùn)費(fèi)轉(zhuǎn)換未明確；我們把各鋼廠的出廠銷價(jià)、鋼廠到鋪設(shè)結(jié)點(diǎn)的最小運(yùn)費(fèi)和鋪設(shè)結(jié)點(diǎn)到各施工處的最小費(fèi)用分離開來(lái)考慮，實(shí)際上它們是不能完全分開的。第二十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期六對(duì)于每一段待鋪設(shè)的管線中的任一鋪設(shè)點(diǎn)p而言，從某一鋼廠將鋼管運(yùn)到p點(diǎn)無(wú)外乎有通過(guò)和通過(guò)兩種可能，顯然，這兩種走法的運(yùn)費(fèi)是不同的。為此要計(jì)算到p點(diǎn)的費(fèi)用，還應(yīng)該比較這兩種走法的大小，對(duì)于每一段管線都會(huì)有一個(gè)平衡點(diǎn)，即兩種走法運(yùn)價(jià)相同的點(diǎn)，在該平衡點(diǎn)的兩側(cè)應(yīng)該分別采用兩種走法。而且對(duì)于同一段管線，這種運(yùn)價(jià)的平衡點(diǎn)又會(huì)因運(yùn)出鋼廠的不同而異，因此絕不可以將運(yùn)到樞紐點(diǎn)（鋪設(shè)結(jié)點(diǎn)）和運(yùn)到具體的鋪設(shè)點(diǎn)割裂開來(lái)考慮。注由此注解我們很容易知道，前面看似是三個(gè)方面的不足實(shí)際上可歸結(jié)為兩點(diǎn)：1，那就是鋼管的出廠銷價(jià)、鐵路運(yùn)費(fèi)與公路運(yùn)費(fèi)需統(tǒng)一；2，結(jié)點(diǎn)到施工處的最小運(yùn)價(jià)通過(guò)鋼廠運(yùn)送到結(jié)點(diǎn)的運(yùn)量與鋼廠到結(jié)點(diǎn)的最小運(yùn)價(jià)發(fā)生關(guān)系，它們是不可分離的，是密切相關(guān)的。第二十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期六如果假設(shè)已經(jīng)找到了較好的運(yùn)費(fèi)、銷價(jià)的轉(zhuǎn)換方法，問(wèn)題的模型就可以給出了。方法一的數(shù)學(xué)模型第二十五頁(yè)，共三十七頁(yè)，編輯于2023年，星期六這種模型與普通運(yùn)輸問(wèn)題模型的區(qū)別在于約束條件（2），因?yàn)轭}目給出要求是一個(gè)鋼廠如果承擔(dān)制造這種鋼管，則至少需要生產(chǎn)500個(gè)單位。而普通的運(yùn)輸問(wèn)題相應(yīng)的條件則是模型說(shuō)明此模型的最大優(yōu)點(diǎn)是其目標(biāo)函數(shù)為線性函數(shù)，處理起來(lái)比較簡(jiǎn)單，而且這種模型對(duì)題目的第一問(wèn)和第三問(wèn)的情況都適用它的最大缺點(diǎn)是規(guī)模太大，決策變量太多，一般的求解線性規(guī)劃的軟件會(huì)因?yàn)樽兞刻蠖鵁o(wú)法工作。為此，在后續(xù)的求解中要采取各種手段，盡可能減少?zèng)Q策變量數(shù)。（如，先期比較運(yùn)費(fèi)將S4從供應(yīng)商中刪除，根據(jù)圖形特點(diǎn)將供需點(diǎn)歸類等手段

），但這種分析手段只能針對(duì)本題的具體情況而不具有一般性，而且，采用這種方法將很難證明所得的結(jié)果一定是最優(yōu)的。第二十六頁(yè)，共三十七頁(yè)，編輯于2023年，星期六法二：二次規(guī)劃方法此處含訂購(gòu)費(fèi)用由Aj向左，需運(yùn)輸?shù)匿摴芰浚篫j+Zj-1+Zj-2+…+1(邊運(yùn)輸邊放下)第二十七頁(yè)，共三十七頁(yè)，編輯于2023年，星期六其它模型以上，我們介紹了兩種最普遍使用的模型，求解此問(wèn)題的方法很多，獲獎(jiǎng)?wù)撐闹幸采婕案鞣N不同的做法，但多數(shù)做法都可大致歸為這兩種之一，比如其中的最小費(fèi)用網(wǎng)絡(luò)流模型或者二分圖的模型就其本質(zhì)來(lái)講就屬于第一種。第二十八頁(yè)，共三十七頁(yè)，編輯于2023年，星期六模型求解1.統(tǒng)一在一起的運(yùn)費(fèi)模型一和模型二的求解難點(diǎn)都是類似的，主要有如下兩點(diǎn)：2.約束條件2的處理下面依次解決。第二十九頁(yè)，共三十七頁(yè)，編輯于2023年，星期六出廠銷價(jià)、鐵路運(yùn)費(fèi)向公路運(yùn)費(fèi)的轉(zhuǎn)換轉(zhuǎn)換方法一：第三十頁(yè)，共三十七頁(yè)，編輯于2023年，星期六轉(zhuǎn)換方法二：第三十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期六特殊約束條件的處理第三十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期六根據(jù)這種思想，運(yùn)用二次規(guī)劃軟件得到的最優(yōu)解中于是將S4從供應(yīng)名單中刪除，再將第7家工廠的供貨量改為0和不小于500兩種情況重做。相比之下，取0的情況總費(fèi)用較小，從而也應(yīng)把S7刪去，得到問(wèn)題的最優(yōu)解為第三十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期六題目要求中第二問(wèn)問(wèn)題中的第二問(wèn)就是靈敏度分析的內(nèi)容，可以使用軟件結(jié)合適當(dāng)?shù)挠懻?，不難作出。第三十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期六第三十五頁(yè)，共三十七頁(yè)，編輯于2