優(yōu)化問題與Lingo

1、優(yōu)化模型與優(yōu)化模型與LINGO優(yōu)化軟件優(yōu)化軟件玩具、照片、飛機(jī)、火箭模型玩具、照片、飛機(jī)、火箭模型 實(shí)物模型實(shí)物模型地圖、電路圖、分子結(jié)構(gòu)圖地圖、電路圖、分子結(jié)構(gòu)圖 符號模型符號模型模型模型是為了一定目的，對客觀事物的一部分是為了一定目的，對客觀事物的一部分進(jìn)行簡縮、抽象、提煉出來的進(jìn)行簡縮、抽象、提煉出來的原型原型的替代物的替代物模型模型集中反映了集中反映了原型原型中人們需要的那一部分特征中人們需要的那一部分特征從現(xiàn)實(shí)對象到數(shù)學(xué)模型從現(xiàn)實(shí)對象到數(shù)學(xué)模型我們常見的模型我們常見的模型你碰到過的數(shù)學(xué)模型你碰到過的數(shù)學(xué)模型“航行問題航行問題”用用 x 表示船速，表示船速，y 表示水速，列出方程：表示

2、水速，列出方程：75050)(75030)(yxyx答：船速每小時答：船速每小時20千米千米/ /小時小時. .甲乙兩地相距甲乙兩地相距750千米，船從甲到乙順?biāo)叫行枨?，船從甲到乙順?biāo)叫行?0小時，小時，從乙到甲逆水航行需從乙到甲逆水航行需50小時，問船的速度是多少小時，問船的速度是多少?x =20y =5求解求解航行問題航行問題建立數(shù)學(xué)模型的基本步驟建立數(shù)學(xué)模型的基本步驟 作出簡化假設(shè)（船速、水速為常數(shù)）；作出簡化假設(shè)（船速、水速為常數(shù)）； 用符號表示有關(guān)量（用符號表示有關(guān)量（x, y表示船速和水速）；表示船速和水速）； 用物理定律（勻速運(yùn)動的距離等于速度乘以用物理定律（勻速運(yùn)動的距離

3、等于速度乘以 時間）列出數(shù)學(xué)式子（二元一次方程）；時間）列出數(shù)學(xué)式子（二元一次方程）； 求解得到數(shù)學(xué)解答（求解得到數(shù)學(xué)解答（x=20, y=5）；）； 回答原問題（船速每小時回答原問題（船速每小時20千米千米/小時）。小時）。數(shù)學(xué)模型數(shù)學(xué)模型 (Mathematical Model) 和和數(shù)學(xué)建模（數(shù)學(xué)建模（Mathematical Modeling)對于一個對于一個現(xiàn)實(shí)對象現(xiàn)實(shí)對象，為了一個，為了一個特定目的特定目的，根據(jù)其根據(jù)其內(nèi)在規(guī)律內(nèi)在規(guī)律，作出必要的，作出必要的簡化假設(shè)簡化假設(shè)，運(yùn)用適當(dāng)?shù)倪\(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具數(shù)學(xué)工具，得到的一個，得到的一個數(shù)學(xué)結(jié)構(gòu)數(shù)學(xué)結(jié)構(gòu)。建立數(shù)學(xué)模型的全過程建立數(shù)學(xué)

4、模型的全過程（包括表述、求解、解釋、檢驗(yàn)等）（包括表述、求解、解釋、檢驗(yàn)等）數(shù)學(xué)模型數(shù)學(xué)模型數(shù)學(xué)數(shù)學(xué)建模建模數(shù)學(xué)建模的重要意義數(shù)學(xué)建模的重要意義 電子計(jì)算機(jī)的出現(xiàn)及飛速發(fā)展；電子計(jì)算機(jī)的出現(xiàn)及飛速發(fā)展； 數(shù)學(xué)以空前的廣度和深度向一切領(lǐng)域滲透。數(shù)學(xué)以空前的廣度和深度向一切領(lǐng)域滲透。數(shù)學(xué)建模作為用數(shù)學(xué)方法解決實(shí)際問題的第一步，數(shù)學(xué)建模作為用數(shù)學(xué)方法解決實(shí)際問題的第一步，越來越受到人們的重視。越來越受到人們的重視。 在一般工程技術(shù)領(lǐng)域數(shù)學(xué)建模仍然大有用武之地；在一般工程技術(shù)領(lǐng)域數(shù)學(xué)建模仍然大有用武之地； 在高新技術(shù)領(lǐng)域數(shù)學(xué)建模幾乎是必不可少的工具；在高新技術(shù)領(lǐng)域數(shù)學(xué)建模幾乎是必不可少的工具； 數(shù)學(xué)進(jìn)

5、入一些新領(lǐng)域，為數(shù)學(xué)建模開辟了許多處女地。數(shù)學(xué)進(jìn)入一些新領(lǐng)域，為數(shù)學(xué)建模開辟了許多處女地。數(shù)學(xué)建模的具體應(yīng)用數(shù)學(xué)建模的具體應(yīng)用 分析與設(shè)計(jì)分析與設(shè)計(jì) 預(yù)報(bào)與決策預(yù)報(bào)與決策 控制與優(yōu)化控制與優(yōu)化 規(guī)劃與管理規(guī)劃與管理數(shù)學(xué)建模計(jì)算機(jī)技術(shù)知識經(jīng)濟(jì)知識經(jīng)濟(jì)如虎添翼如虎添翼 數(shù)學(xué)建模的基本方法數(shù)學(xué)建模的基本方法機(jī)理分析機(jī)理分析測試分析測試分析根據(jù)對客觀事物特性的認(rèn)識，根據(jù)對客觀事物特性的認(rèn)識，找出反映內(nèi)部機(jī)理的數(shù)量規(guī)律找出反映內(nèi)部機(jī)理的數(shù)量規(guī)律將對象看作將對象看作“黑箱黑箱”,通過對量測數(shù)據(jù)的通過對量測數(shù)據(jù)的統(tǒng)計(jì)分析，找出與數(shù)據(jù)擬合最好的模型統(tǒng)計(jì)分析，找出與數(shù)據(jù)擬合最好的模型機(jī)理分析沒有統(tǒng)一的方法，主要

6、通過實(shí)例研究機(jī)理分析沒有統(tǒng)一的方法，主要通過實(shí)例研究 (Case Studies)來學(xué)習(xí)。以下建模主要指機(jī)理分析。來學(xué)習(xí)。以下建模主要指機(jī)理分析。二者結(jié)合二者結(jié)合用機(jī)理分析建立模型結(jié)構(gòu)用機(jī)理分析建立模型結(jié)構(gòu),用測試分析確定模型參數(shù)用測試分析確定模型參數(shù)數(shù)學(xué)建模的方法和步驟數(shù)學(xué)建模的方法和步驟 數(shù)學(xué)建模的一般步驟數(shù)學(xué)建模的一般步驟模型準(zhǔn)備模型準(zhǔn)備模型假設(shè)模型假設(shè)模型構(gòu)成模型構(gòu)成模型求解模型求解模型分析模型分析模型檢驗(yàn)?zāi)Ｐ蜋z驗(yàn)?zāi)Ｐ蛻?yīng)用模型應(yīng)用模模型型準(zhǔn)準(zhǔn)備備了解實(shí)際背景了解實(shí)際背景明確建模目的明確建模目的搜集有關(guān)信息搜集有關(guān)信息掌握對象特征掌握對象特征形成一個形成一個比較清晰比較清晰的的問題問題模

7、模型型假假設(shè)設(shè)針對問題特點(diǎn)和建模目的針對問題特點(diǎn)和建模目的作出合理的、簡化的假設(shè)作出合理的、簡化的假設(shè)在合理與簡化之間作出折中在合理與簡化之間作出折中模模型型構(gòu)構(gòu)成成用數(shù)學(xué)的語言、符號描述問題用數(shù)學(xué)的語言、符號描述問題發(fā)揮想像力發(fā)揮想像力使用類比法使用類比法盡量采用簡單的數(shù)學(xué)工具盡量采用簡單的數(shù)學(xué)工具 數(shù)學(xué)建模的一般步驟數(shù)學(xué)建模的一般步驟模型模型求解求解各種數(shù)學(xué)方法、軟件和計(jì)算機(jī)技術(shù)各種數(shù)學(xué)方法、軟件和計(jì)算機(jī)技術(shù)如結(jié)果的誤差分析、統(tǒng)計(jì)分析、如結(jié)果的誤差分析、統(tǒng)計(jì)分析、模型對數(shù)據(jù)的穩(wěn)定性分析模型對數(shù)據(jù)的穩(wěn)定性分析模型模型分析分析模型模型檢驗(yàn)檢驗(yàn)與實(shí)際現(xiàn)象、數(shù)據(jù)比較，與實(shí)際現(xiàn)象、數(shù)據(jù)比較，檢驗(yàn)?zāi)Ｐ?/p>

8、的合理性、適用性檢驗(yàn)?zāi)Ｐ偷暮侠硇?、適用性模型應(yīng)用模型應(yīng)用 數(shù)學(xué)建模的一般步驟數(shù)學(xué)建模的一般步驟數(shù)學(xué)建模的全過程數(shù)學(xué)建模的全過程現(xiàn)實(shí)對象的信息現(xiàn)實(shí)對象的信息數(shù)學(xué)模型數(shù)學(xué)模型現(xiàn)實(shí)對象的解答現(xiàn)實(shí)對象的解答數(shù)學(xué)模型的解答數(shù)學(xué)模型的解答表述表述求解求解解釋解釋驗(yàn)證驗(yàn)證(歸納)(演繹)表述表述求解求解解釋解釋驗(yàn)證驗(yàn)證根據(jù)建模目的和信息將實(shí)際問題根據(jù)建模目的和信息將實(shí)際問題“翻譯翻譯”成數(shù)學(xué)問成數(shù)學(xué)問題題選擇適當(dāng)?shù)臄?shù)學(xué)方法求得數(shù)學(xué)模型的解答選擇適當(dāng)?shù)臄?shù)學(xué)方法求得數(shù)學(xué)模型的解答將數(shù)學(xué)語言表述的解答將數(shù)學(xué)語言表述的解答“翻譯翻譯”回實(shí)際對象回實(shí)際對象用現(xiàn)實(shí)對象的信息檢驗(yàn)得到的解答用現(xiàn)實(shí)對象的信息檢驗(yàn)得到的解答實(shí)

9、踐現(xiàn)現(xiàn)實(shí)實(shí)世世界界數(shù)數(shù)學(xué)學(xué)世世界界理論實(shí)踐數(shù)學(xué)模型的特點(diǎn)和分類數(shù)學(xué)模型的特點(diǎn)和分類模型的逼真性和可行性模型的逼真性和可行性模型的漸進(jìn)性模型的漸進(jìn)性模型的穩(wěn)定性模型的穩(wěn)定性模型的可轉(zhuǎn)移性模型的可轉(zhuǎn)移性模型的非預(yù)制性模型的非預(yù)制性模型的條理性模型的條理性模型的技藝性模型的技藝性模型的局限性模型的局限性 數(shù)學(xué)模型的特點(diǎn)數(shù)學(xué)模型的特點(diǎn)數(shù)學(xué)模型的分類數(shù)學(xué)模型的分類應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域人口、交通、經(jīng)濟(jì)、生態(tài)人口、交通、經(jīng)濟(jì)、生態(tài) 數(shù)學(xué)方法數(shù)學(xué)方法初等數(shù)學(xué)、微分方程、規(guī)劃、統(tǒng)計(jì)初等數(shù)學(xué)、微分方程、規(guī)劃、統(tǒng)計(jì) 表現(xiàn)特性表現(xiàn)特性描述、優(yōu)化、預(yù)報(bào)、決策描述、優(yōu)化、預(yù)報(bào)、決策 建模目的建模目的了解程度了解程度白箱白箱灰

10、箱灰箱黑箱黑箱確定和隨機(jī)確定和隨機(jī)靜態(tài)和動態(tài)靜態(tài)和動態(tài)線性和非線性線性和非線性離散和連續(xù)離散和連續(xù)怎樣學(xué)習(xí)數(shù)學(xué)建模與競賽組隊(duì)怎樣學(xué)習(xí)數(shù)學(xué)建模與競賽組隊(duì)數(shù)學(xué)建模與其說是一門技術(shù)，不如說是一門藝術(shù)數(shù)學(xué)建模與其說是一門技術(shù)，不如說是一門藝術(shù)技術(shù)大致有章可循技術(shù)大致有章可循藝術(shù)無法歸納成普遍適用的準(zhǔn)則藝術(shù)無法歸納成普遍適用的準(zhǔn)則想像力想像力洞察力洞察力判斷力判斷力 學(xué)習(xí)、分析、評價、改進(jìn)別人作過的模型學(xué)習(xí)、分析、評價、改進(jìn)別人作過的模型 親自動手，認(rèn)真作幾個實(shí)際題目親自動手，認(rèn)真作幾個實(shí)際題目根據(jù)數(shù)學(xué)建模競賽章程，三人組成一隊(duì)。根據(jù)數(shù)學(xué)建模競賽章程，三人組成一隊(duì)。 這三人中必須一人數(shù)學(xué)基礎(chǔ)較好這三人中

11、必須一人數(shù)學(xué)基礎(chǔ)較好， 一人應(yīng)用數(shù)學(xué)軟件（如一人應(yīng)用數(shù)學(xué)軟件（如Matlab,lindo,maple等）等） 和編程（如和編程（如c,Matlab,vc+等）的能力較強(qiáng)，等）的能力較強(qiáng)， 一人科技論文寫作的水平較好。一人科技論文寫作的水平較好。 科技論文的寫作要求整篇論文的結(jié)構(gòu)嚴(yán)謹(jǐn)，語言要科技論文的寫作要求整篇論文的結(jié)構(gòu)嚴(yán)謹(jǐn)，語言要有邏輯性，用詞要準(zhǔn)確。有邏輯性，用詞要準(zhǔn)確。 三人之間要能夠配合得起來。若三人之間配合不好，三人之間要能夠配合得起來。若三人之間配合不好， 會降低效率，導(dǎo)致整個建模的失敗。會降低效率，導(dǎo)致整個建模的失敗。 如果可能的話，最好是數(shù)學(xué)好的懂得編程的一些知如果可能的話，最

12、好是數(shù)學(xué)好的懂得編程的一些知識，編程好的了解建模，搞論文寫作也要了解建模，識，編程好的了解建模，搞論文寫作也要了解建模，這樣會合作得更好。因?yàn)閿?shù)學(xué)好的在建立模型方案這樣會合作得更好。因?yàn)閿?shù)學(xué)好的在建立模型方案時會考慮到編程的便利性，以利于編程；編程好的時會考慮到編程的便利性，以利于編程；編程好的能夠很好地理解模型，論文寫作的能夠更好、更完能夠很好地理解模型，論文寫作的能夠更好、更完全地闡述模型。否則會出現(xiàn)建立的模型不利于編程，全地闡述模型。否則會出現(xiàn)建立的模型不利于編程，程序不能完全概括模型，論文寫作時會漏掉一些不程序不能完全概括模型，論文寫作時會漏掉一些不經(jīng)意的東西。經(jīng)意的東西。在合作的過程

13、中，最好是能夠在三人中找出一個所謂在合作的過程中，最好是能夠在三人中找出一個所謂的組長，即要能夠總攬全局，包括任務(wù)的分配，相互的組長，即要能夠總攬全局，包括任務(wù)的分配，相互間的合作和進(jìn)度的安排。間的合作和進(jìn)度的安排。在建模過程中出現(xiàn)意見不統(tǒng)一在建模過程中出現(xiàn)意見不統(tǒng)一如何處理？僅我如何處理？僅我個人的經(jīng)驗(yàn)而言，除了一般的理解與尊重外，我覺個人的經(jīng)驗(yàn)而言，除了一般的理解與尊重外，我覺得最重要的一點(diǎn)就是得最重要的一點(diǎn)就是“給我一個相信你的理由給我一個相信你的理由”和和“相信我，我的理由是相信我，我的理由是”，不要作無謂的爭論。，不要作無謂的爭論。 撰寫數(shù)學(xué)建模論文撰寫數(shù)學(xué)建模論文1 1、摘要、摘要

14、: :問題、模型、方法、結(jié)果問題、模型、方法、結(jié)果2 2、問題重述、問題重述3 3、模型假設(shè)與記號、模型假設(shè)與記號4 4、分析與建立模型、分析與建立模型5 5、模型求解、模型求解6 6、模型檢驗(yàn)、模型檢驗(yàn)7 7、模型推廣、模型推廣8 8、參考文獻(xiàn)、參考文獻(xiàn)9 9、附錄、附錄優(yōu)化模型優(yōu)化模型 實(shí)際問題中實(shí)際問題中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策變量決策變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃線性規(guī)劃線性規(guī)劃(LP)二次規(guī)劃二次規(guī)劃(QP)非線性規(guī)劃非線性規(guī)劃(NLP)純整數(shù)規(guī)劃

15、純整數(shù)規(guī)劃(PIP)混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP)整數(shù)規(guī)劃整數(shù)規(guī)劃(IP)0-1整數(shù)規(guī)劃整數(shù)規(guī)劃一般整數(shù)規(guī)劃一般整數(shù)規(guī)劃連續(xù)規(guī)劃連續(xù)規(guī)劃美國芝加哥美國芝加哥(Chicago)大學(xué)的大學(xué)的Linus Schrage教授于教授于1980年前后開發(fā)年前后開發(fā), 后來成立后來成立 LINDO系統(tǒng)公司（系統(tǒng)公司（LINDO Systems Inc.），）， 網(wǎng)址：網(wǎng)址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO

16、 API: LINDO Application Programming Interface (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示演示(試用試用)版、學(xué)生版、高級版、超級版、工業(yè)版、版、學(xué)生版、高級版、超級版、工業(yè)版、擴(kuò)展版擴(kuò)展版 （求解（求解問題規(guī)模問題規(guī)模和和選件選件不同）不同） LINGO LINDO優(yōu)化模型優(yōu)化模型線性規(guī)劃線性規(guī)劃(LP)非線性規(guī)劃非線性規(guī)劃(NLP)二次規(guī)劃二次規(guī)劃(QP)連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) LP QP NLP IP 全局優(yōu)化全局優(yōu)化(選選) ILP IQP INLP LINDO/

17、LINGO預(yù)處理程序預(yù)處理程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法(選選)1、順序線性規(guī)劃法、順序線性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點(diǎn)搜索、多點(diǎn)搜索(Multistart) (選選) 1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù)盡量使用光滑優(yōu)化，減少非光滑約束的個數(shù) 如：盡量少使用絕對值、符號函數(shù)、多個變量求如

18、：盡量少使用絕對值、符號函數(shù)、多個變量求最大最大/最小值、四舍五入、取整函數(shù)等最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變盡量使用線性模型，減少非線性約束和非線性變量的個數(shù)量的個數(shù) （如（如x/y 5 改為改為x5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值合理設(shè)定變量上下界，盡可能給出變量初始值 5、模型中使用的參數(shù)數(shù)量級要適當(dāng)模型中使用的參數(shù)數(shù)量級要適當(dāng) (如小于如小于103)1、LINDO: 正確閱讀求解報(bào)告（尤其要掌握敏感性分析）正確閱讀求解報(bào)告（尤其要掌握敏感性分析）2、LINGO： 掌握集合掌握集合(SETS)的應(yīng)用；的應(yīng)用；正確閱讀求解報(bào)告；正確

19、閱讀求解報(bào)告；正確理解求解狀態(tài)窗口；正確理解求解狀態(tài)窗口； 學(xué)會設(shè)置基本的求解選項(xiàng)學(xué)會設(shè)置基本的求解選項(xiàng)(OPTIONS) ； 掌握與外部文件的基本接口方法掌握與外部文件的基本接口方法例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶 時間時間480小時小時 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時工人，付出的工資最多是每小時幾元可聘用

20、臨時工人，付出的工資最多是每小時幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：1桶牛奶 3公斤A1 12小時 8小時 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時

21、間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型求解模型求解 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.00

22、0000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）目標(biāo)保持不變）目標(biāo)函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.00

23、0000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2也可理解為：也可理解為：為了使該非基變?yōu)榱耸乖摲腔兞孔兂苫兞?，量變成基變量，目?biāo)函數(shù)中對應(yīng)目標(biāo)函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量系數(shù)應(yīng)增加的量 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.

24、000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE RED

25、UCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時單位時“效益效益”的的增量增量 原料增原料增1單位單位, 利潤增利潤增48 時間加時間加1單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 ”

26、（或“=”（或“=”）功能相同變量與系數(shù)間可有空格(甚至回車), 但無運(yùn)算符變量名以字母開頭，不能超過8個字符變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(行名)自動產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號的后面部分為注釋。如: ! Its Comment.在模型的任何地方都可以用“TITLE” 對模型命名（最多72個字符），如： TITLE This Model is only an Example變量不能出現(xiàn)在一個約束條件的右端表達(dá)式中不接受括號“( )”和逗號“,”等任何符號, 例: 400(X1+X2)需寫為400X1+400X

27、2表達(dá)式應(yīng)化簡，如2X1+3X2- 4X1應(yīng)寫成 -2X1+3X2缺省假定所有變量非負(fù)；可在模型的“END”語句后用“FREE name”將變量name的非負(fù)假定取消可在 “END”后用“SUB” 或“SLB” 設(shè)定變量上下界 例如： “sub x1 10”的作用等價于“x1=10” 但用“SUB”和“SLB”表示的上下界約束不計(jì)入模型的約束，也不能給出其松緊判斷和敏感性分析。14. “END”后對0-1變量說明：INT n 或 INT name15. “END”后對整數(shù)變量說明：GIN n 或 GIN nameQLINDO可求解二次規(guī)劃(QP)問題，但輸入方式較復(fù)雜，因?yàn)樵贚INDO中不許出

28、現(xiàn)非線性表達(dá)式Q需要為每一個實(shí)際約束增加一個對偶變量（LAGRANGE乘子），在實(shí)際約束前增加有關(guān)變量的一階最優(yōu)條件，轉(zhuǎn)化為互補(bǔ)問題Q“END”后面使用QCP命令指明實(shí)際約束開始的行號，然后才能求解Q建議總是用LINGO解QP注意對QP和IP: 敏感性分析意義不大Q當(dāng)前狀態(tài)：已達(dá)最優(yōu)解Q迭代次數(shù)：18次Q約束不滿足的“量”(不是“約束個數(shù)”)：0Q當(dāng)前的目標(biāo)值：94Q最好的整數(shù)解：94Q整數(shù)規(guī)劃的界：93.5Q分枝數(shù)：1Q所用時間：0.00秒（太快了，還不到0.005秒）Q刷新本界面的間隔:1(秒) Preprocess：預(yù)處理：預(yù)處理(生成割平面生成割平面)； Preferred Branc

29、h：優(yōu)先的分枝方式：優(yōu)先的分枝方式： “Default”（缺省方式）、（缺省方式）、“Up”（向上取整優(yōu)先）、（向上取整優(yōu)先）、“Down”（向下取整優(yōu)先）；（向下取整優(yōu)先）； IP Optimality Tol：IP最優(yōu)值允許的誤最優(yōu)值允許的誤差上限（一個百分?jǐn)?shù)，如差上限（一個百分?jǐn)?shù)，如5%即即0.05）；）； IP Objective Hurdle：IP目標(biāo)函數(shù)的籬目標(biāo)函數(shù)的籬笆值，即只尋找比這個值更優(yōu)最優(yōu)解笆值，即只尋找比這個值更優(yōu)最優(yōu)解（如當(dāng)知道當(dāng)前模型的某個整數(shù)可行解（如當(dāng)知道當(dāng)前模型的某個整數(shù)可行解時，就可以設(shè)置這個值）；時，就可以設(shè)置這個值）； IP Var Fixing Tol

30、：固定一個整數(shù)變量：固定一個整數(shù)變量取值所依據(jù)的一個上限（如果一個整數(shù)取值所依據(jù)的一個上限（如果一個整數(shù)變量的判別數(shù)（變量的判別數(shù)（REDUCED COST）的）的值很大，超過該上限，則以后求解中把值很大，超過該上限，則以后求解中把該整數(shù)變量固定下來）。該整數(shù)變量固定下來）。Nonzero Limit：非零系數(shù)的個數(shù)上限；非零系數(shù)的個數(shù)上限；Iteration Limit：最大迭代步數(shù)；最大迭代步數(shù)；Initial Contraint Tol：約束的初始誤差上限；約束的初始誤差上限；Final Contraint Tol：約束的最后誤差上限；約束的最后誤差上限；Entering Var Tol

31、：進(jìn)基變量的進(jìn)基變量的REDUCED COST的誤差限；的誤差限；Pivot Size Tol：旋轉(zhuǎn)元的誤差限旋轉(zhuǎn)元的誤差限第一行：模型有第一行：模型有5行（約束行（約束4行），行），4個變量，兩個整數(shù)變量（沒有個變量，兩個整數(shù)變量（沒有0-1變量），從第變量），從第4行開始是二次規(guī)劃的實(shí)際約束。行開始是二次規(guī)劃的實(shí)際約束。第二行：非零系數(shù)第二行：非零系數(shù)19個，約束中非零系數(shù)個，約束中非零系數(shù)12個個(其中其中6個為個為1或或-1)，模型密度為模型密度為0.760(密度密度=非零系數(shù)非零系數(shù)/行數(shù)行數(shù)(變量數(shù)變量數(shù)) 。第三行的意思：按絕對值看，系數(shù)最小、最大分別為第三行的意思：按絕對值看，

32、系數(shù)最小、最大分別為0.3和和277。第四行的意思：模型目標(biāo)為極小化；小于等于、等于、大于等于約第四行的意思：模型目標(biāo)為極小化；小于等于、等于、大于等于約束分別有、個；廣義上界約束（束分別有、個；廣義上界約束（GUBS）不超過個；）不超過個；變量上界約束（變量上界約束（VUBS）不少于個。所謂）不少于個。所謂GUBS，是指一組不，是指一組不含有相同變量的約束；所謂含有相同變量的約束；所謂VUBS，是指一個蘊(yùn)涵變量上界的約，是指一個蘊(yùn)涵變量上界的約束，如從約束束，如從約束X1+X2-X3=0可以看出，若可以看出，若X3=0，則，則X1=0，X2=0（因?yàn)橛蟹秦?fù)限制），因此（因?yàn)橛蟹秦?fù)限制），因此

33、X1+X2-X3=0是一個是一個VUBS約束。約束。第五行的意思：只含個變量的約束個數(shù)第五行的意思：只含個變量的約束個數(shù)=個；冗余的列數(shù)個；冗余的列數(shù)=個個ROWS= 5 VARS= 4 INTEGER VARS= 2( 0 = 0/1) QCP= 4NONZEROS= 19 CONSTRAINT NONZ= 12( 6 = +-1) DENSITY=0.760SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE= 0.300000 277.000OBJ=MIN, NO. : 2 0 2, GUBS = 0SINGLE COLS= 0 REDUNDAN

34、T COLS= 0LINGO軟件簡介軟件簡介目標(biāo)與約束段目標(biāo)與約束段 集合段（集合段（SETS ENDSETS） 數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA）初始段（初始段（INIT ENDINIT）LINGO模型的構(gòu)成：模型的構(gòu)成：4個段個段LINGO模型的優(yōu)點(diǎn)模型的優(yōu)點(diǎn)包含了包含了LINDO的全部功能的全部功能提供了靈活的編程語言（矩陣生成器）提供了靈活的編程語言（矩陣生成器）某公司有某公司有6個建筑工地，位置坐標(biāo)為個建筑工地，位置坐標(biāo)為(ai, bi) (單位：公里單位：公里),水泥日用量水泥日用量di (單位：噸）單位：噸）ia1.258.750.55.7537.25b1.250.754

35、.7556.57.75d35476111)現(xiàn)有 2 料場，位于 A (5, 1), B (2, 7),記(xj,yj),j=1,2, 日儲量 ej各有 20 噸。假設(shè)：假設(shè)：料場料場和工地之間和工地之間有直線道路有直線道路目標(biāo)：制定每天的供應(yīng)計(jì)劃，即從 A, B 兩料場分別向各工地運(yùn)送多少噸水泥，使總的噸公里數(shù)最小。用例中數(shù)據(jù)計(jì)算，最優(yōu)解為i1234561ic（料料場場 A）3507012ic（料料場場 B）00406102 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij線性規(guī)劃模型線性規(guī)劃模型決策變量：決策變量：c

36、i j (料場料場j到到工地工地i的的運(yùn)量）運(yùn)量）12維維2）改建兩個新料場，需要確定新料場位置）改建兩個新料場，需要確定新料場位置(xj,yj)和和運(yùn)量運(yùn)量cij ，在其它條件不變下使總噸公里數(shù)最小。，在其它條件不變下使總噸公里數(shù)最小。2 , 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjijiiijjjiijijij決策變量：決策變量：ci j，(xj,yj)16維維非線性規(guī)劃模型非線性規(guī)劃模型LINGO模型的構(gòu)成：模型的構(gòu)成：4個段個段集合段（集合段（SETS ENDSETS）數(shù)據(jù)段（數(shù)據(jù)段（DATA ENDDATA）初始段（初始段（INIT

37、ENDINIT） 目標(biāo)與目標(biāo)與約束段約束段 局部最優(yōu)：局部最優(yōu)：89.8835(噸公里噸公里 ) LP：移到數(shù)據(jù)段：移到數(shù)據(jù)段 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密集合 元素列表法元素列表法 元素過濾法元素過濾法 直接列舉法直接列舉法 隱式列舉法隱式列舉法setname /member_list/ : attribute_list;setname(parent_set_list) /member_list/ : attribute_list;SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,

38、B1 A1,B2 A2,B1 A3,B2/:D; ENDSETSSETS: STUDENTS /S1.S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH;ENDSETS類型隱式列舉格式示例示例集合的元素?cái)?shù)字型 1.n1.51, 2, 3, 4, 5字符-數(shù)字型stringM.stringNCar101.car208Car101, car102, , car208星期型 dayM.dayNMON.FRIMON, TUE, WED, THU, FRI月份型 monthM.monthNOCT.JANOCT, NOV

39、, DEC, JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001, NOV2001, DEC2001, JAN2002優(yōu)先級運(yùn)算符最高#NOT# （負(fù)號）* /+ （減法）#EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低(=)三類運(yùn)算符：三類運(yùn)算符： 算術(shù)運(yùn)算符算術(shù)運(yùn)算符 邏輯運(yùn)算符邏輯運(yùn)算符 關(guān)系運(yùn)算符關(guān)系運(yùn)算符四個集合循環(huán)函數(shù)：四個集合循環(huán)函數(shù)：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_l

40、ist);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( I): constraints SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1);FOR(PAIRS( I, J): BIN( MATCH( I, J);MAXB=MAX(PAIRS( I, J): BENEFIT( I, J);MINB=MIN(PAIRS( I, J): BENEFIT( I, J);Example:PAIRSJIJIMATCHJIBEN

41、EFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCHSolver Type:B-and-BGlobal MultistartModel Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:Global OptimumLocal OptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7 7個選項(xiàng)卡個選項(xiàng)卡( (可設(shè)置可設(shè)置80-9080-90個控制參數(shù)個控制參數(shù)) ) 程序與數(shù)據(jù)分離程序與數(shù)據(jù)分離文文本本文文件件使用外部數(shù)據(jù)文件使用外部數(shù)據(jù)文件 Cu

42、t (or Copy) Paste 方法方法 FILE 輸入數(shù)據(jù)、輸入數(shù)據(jù)、TEXT輸出數(shù)據(jù)（文本文件）輸出數(shù)據(jù)（文本文件） OLE函數(shù)與電子表格軟件（如函數(shù)與電子表格軟件（如EXCEL）連接）連接 ODBC函數(shù)與數(shù)據(jù)庫連接函數(shù)與數(shù)據(jù)庫連接 LINGO命令腳本文件命令腳本文件 LG4 （LONGO模型文件）模型文件） LNG （LONGO模型文件）模型文件） LTF （LONGO腳本文件）腳本文件） LDT （LONGO數(shù)據(jù)文件）數(shù)據(jù)文件） LRP （LONGO報(bào)告文件）報(bào)告文件）常用文件后綴常用文件后綴FILEFILE和和TEXTTEXT：文本文件輸入輸出：文本文件輸入輸出MODEL:SET

43、S: MYSET / FILE(myfile.txt) / : FILE(myfile.txt);ENDSETSMIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) NEED( I); CON2 SHIP( I) SUPPLY( I);DATA: MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=

44、SHIP; ENDDATAEND mydata.xls文件中必須有下列名稱(及數(shù)據(jù))： CITIES， COST，NEED，SUPPLY，SOLUTION 在在EXCEL中還可以通過中還可以通過“宏宏”自動調(diào)用自動調(diào)用LINGO(略略) 也可以將也可以將EXCEL表格嵌入到表格嵌入到LINGO模型中模型中(略略)演示演示 MydataExample.lg4ODBC ODBC ：與數(shù)據(jù)庫連接：與數(shù)據(jù)庫連接輸入基本集合元素：輸入基本集合元素：setname/ODBC(datasource , tablename , columnname)/輸入派生集合元素：輸入派生集合元素：setname/ODB

45、C(source,table , column1, column2)/目前支持下列目前支持下列DBMS: (如為其他數(shù)據(jù)庫，則需自行安裝驅(qū)動如為其他數(shù)據(jù)庫，則需自行安裝驅(qū)動)ACCESS， DBASE，EXCEL，F(xiàn)OXPRO，ORACLE，PARADOX，SQL SERVER， TEXE FILES使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在使用數(shù)據(jù)庫之前，數(shù)據(jù)源需要在ODBC管理器注冊管理器注冊輸入數(shù)據(jù)：輸入數(shù)據(jù)：Attr_list=ODBC(source,table , column1, column2)輸出數(shù)據(jù)：輸出數(shù)據(jù)：ODBC(source,table , column1, column2)= A

46、ttr_list具體例子略具體例子略建模實(shí)例與求解建模實(shí)例與求解最短路問題最短路問題下料問題下料問題露天礦的運(yùn)輸問題露天礦的運(yùn)輸問題鋼管運(yùn)輸問題鋼管運(yùn)輸問題最短路問題最短路問題求各點(diǎn)到求各點(diǎn)到T的最短路的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4jijAjiiLcL),(min問題問題1. 如何下料最節(jié)省如何下料最節(jié)省 ? 問題問題2. 客戶增加需求：客戶增加需求：原料鋼管原料鋼管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客戶需求客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會增加生

47、產(chǎn)和管理成本，由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過規(guī)定切割模式不能超過3種。如何下料最節(jié)省？種。如何下料最節(jié)??？5米米10根根 按照客戶需要在一根原料鋼管上安排切割的一種組合。按照客戶需要在一根原料鋼管上安排切割的一種組合。 余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸的余料應(yīng)小于客戶需要鋼管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 鋼管下料鋼管下料 為滿足客戶需要，按照哪些種合理模式，每種模式為滿足客戶需要，按照哪些

48、種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。壳懈疃嗌俑箱摴?，最為節(jié)?。?. 所用原料鋼管總根數(shù)最少所用原料鋼管總根數(shù)最少 模式模式 4米鋼管根數(shù)米鋼管根數(shù)6米鋼管根數(shù)米鋼管根數(shù)8米鋼管根數(shù)米鋼管根數(shù)余料余料(米米)14003231013201341203511116030170023鋼管下料問題鋼管下料問題1 1 兩種兩種標(biāo)準(zhǔn)標(biāo)準(zhǔn)1. 原料鋼管剩余總余量最小原料鋼管剩余總余量最小xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,7) ) 約束約束滿足需求滿足需求 決策變量決策變量 目標(biāo)目標(biāo)1（總余量）（總余量）765432113333xxxxxx

49、xZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根數(shù)根數(shù)6米米根數(shù)根數(shù)8米米根數(shù)根數(shù)余余料料14003231013201341203511116030170023需需求求502015最優(yōu)解：最優(yōu)解：x2=12, x5=15, 其余為其余為0；最優(yōu)值：最優(yōu)值：27整數(shù)約束：整數(shù)約束： xi 為整數(shù)為整數(shù)當(dāng)余料沒有用處時，當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)通常以總根數(shù)最少為目標(biāo) 76543212xxxxxxxZMin目標(biāo)目標(biāo)2（總根數(shù)）（總根數(shù)）鋼管下料問題

50、鋼管下料問題1 1 約束條約束條件不變件不變 最優(yōu)解：最優(yōu)解：x2=15, x5=5, x7=5, 其余為其余為0；最優(yōu)值：最優(yōu)值：25。5023454321xxxxx20326542xxxx152753xxxxi 為整數(shù)按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 雖余料增加雖余料增加8米，但減少了米，但減少了2根根 與與目標(biāo)目標(biāo)1的結(jié)果的結(jié)果“共切割共切割27根，余料根，余料27米米” 相比相比 鋼管下料問題鋼管下料問題2 2對大規(guī)模問題，用模型的約束條件界定合理模式對大規(guī)模問題，用模型的約束條件界定合理

51、模式增加一種需求：增加一種需求：5米米10根；切割根；切割模式不超過模式不超過3種。種?，F(xiàn)有現(xiàn)有4種種需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚舉法確定合理切割模式，過于復(fù)雜。根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量決策變量 xi 按第按第i 種模式切割的原料鋼管根數(shù)種模式切割的原料鋼管根數(shù)( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 種切割模式下，每根原料鋼管種切割模式下，每根原料鋼管生產(chǎn)生產(chǎn)4米、米、5米、米、6米和米和8米長的鋼管的數(shù)量米長的鋼管的數(shù)量滿足需求滿足需求50313212111xrxrxr103

52、23222121xrxrxr20333232131xrxrxrxrxr模式合理：每根模式合理：每根余料不超過余料不超過3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整數(shù)非線性規(guī)劃模型整數(shù)非線性規(guī)劃模型鋼管下料問題鋼管下料問題2 2目標(biāo)函數(shù)（目標(biāo)函數(shù)（總根數(shù)）總根數(shù)）321xxxMin約束約束條件條件整數(shù)約束：整數(shù)約束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )為整數(shù)為整數(shù)增加約束，縮小可行域，便于求解增加約束，縮小可行域，便于求解321xxx原料鋼管總根

53、數(shù)下界：原料鋼管總根數(shù)下界： 2619158206105504特殊生產(chǎn)計(jì)劃：對每根原料鋼管特殊生產(chǎn)計(jì)劃：對每根原料鋼管模式模式1：切割成：切割成4根根4米鋼管，需米鋼管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米鋼管，需米鋼管，需10根；根；模式模式3：切割成：切割成2根根8米鋼管，需米鋼管，需8根。根。原料鋼管總根數(shù)上界：原料鋼管總根數(shù)上界：31 3126321xxx模式排列順序可任定模式排列順序可任定 鋼管下料問題鋼管下料問題2 2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料鋼管長每根原料鋼管長19米米LINGOLINGO

54、求解整數(shù)非線性規(guī)劃模型求解整數(shù)非線性規(guī)劃模型Local optimal solution found at iteration: 12211 Objective value: 28.00000Variable Value Reduced CostX1 10.00000 0.000000X2 10.00000 2.000000X3 8.000000 1.000000R11 3.000000 0.000000R12 2.000000 0.000000R13 0.000000 0.000000R21 0.000000 0.000000R22 1.000000 0.000000 R23 0.00000

55、0 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式模式1：每根原料鋼管切割成：每根原料鋼管切割成3根根4米和米和1根根6米鋼管，共米鋼管，共10根；根；模式模式2：每根原料鋼管切割成：每根原料鋼管切割成2根根4米、米、1根根5米和米和1根根6米鋼管，米鋼管，共共10根；根；模式模式3：每根原料鋼管切割成：每根原料鋼管切割成2根根8米鋼管，共米鋼管，共8根。根

56、。原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。根。演示演示cut02a.lg4； cut02b.lg4露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘卡車在等待時所耗費(fèi)的能量也是相當(dāng)可觀的，原則上卡車在等待時所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時在安排時不應(yīng)發(fā)生卡車等待不

57、應(yīng)發(fā)生卡車等待的情況。的情況。 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 礦石卸點(diǎn)需要的鐵含量要求都為礦石卸點(diǎn)需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個班次（制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即小時）內(nèi)滿足品位限制即可。卸點(diǎn)在一個班次內(nèi)不變?？ㄜ囕d重量為可。卸點(diǎn)在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平噸，平均時速均時速28km,平均卸車時間為平均卸車時間為3分鐘。分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運(yùn)輸多少次卡車，分別在哪些路線上各運(yùn)輸多少次

58、?問題數(shù)據(jù)問題數(shù)據(jù) 距離距離鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石漏礦石漏5.202.952.742.461.900.641.27倒裝倒裝1.900.991.901.131.272.251.482.043.093.51巖場巖場5.895.615.614.563.513.652.462.461.060.57巖石漏巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝倒裝4.423.863.710.781.6

59、21.270.50鏟位鏟位1 1鏟位鏟位2 2鏟位鏟位3 3鏟位鏟位4 4鏟位鏟位5 5鏟位鏟位6 6鏟位鏟位7 7鏟位鏟位8 8鏟位鏟位9 9鏟位鏟位1010礦石量礦石量095105100105110125105130135125巖石量巖石量125110135105115135105115135125鐵含量鐵含量30%28%29%32%31%33%32%31%33%31%問題分析問題分析 與典型的運(yùn)輸問題明顯有以下不同：與典型的運(yùn)輸問題明顯有以下不同：這是運(yùn)輸?shù)V石與巖石兩種物資的問題；這是運(yùn)輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問題；為了完

60、成品位約束，礦石要搭配運(yùn)輸；為了完成品位約束，礦石要搭配運(yùn)輸；產(chǎn)地、銷地均有單位時間的流量限制；產(chǎn)地、銷地均有單位時間的流量限制；運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，154噸噸/車次；車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；產(chǎn)地作為最后結(jié)果中的產(chǎn)地；1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。近似處理：近似處理：先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排