數(shù)學規(guī)劃概述

1、數(shù)學規(guī)劃模型概述數(shù)學規(guī)劃模型概述 假期你想去旅游。假如你只去一個地方而且只有一條線路可走，反倒省心一些如果你要去許多地方，又有許多路線，許多交通工具，而你還想盡量節(jié)省路費，那么你就要考慮“最優(yōu)決策”或“最優(yōu)（方案）設(shè)計”的問題了最優(yōu)化(optimization)是企業(yè)運作、科技研發(fā)和工程設(shè)計中常見的問題要表述一個最優(yōu)化問題(即建立數(shù)學模型)，應(yīng)明確三個基本要素： 決策變量（decision variables） 約束條件(constraints) 目標函數(shù)(objective function)決策變量決策變量(decision variables):它們是決策者所控它們是決策者所控制的那些數(shù)

2、量，它們?nèi)∈裁磾?shù)值需要決策者來決制的那些數(shù)量，它們?nèi)∈裁磾?shù)值需要決策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值取值約束條件約束條件(constraints)：它們是決策變量在現(xiàn)實：它們是決策變量在現(xiàn)實世界中所受到的限制，或者說決策變量在這些限世界中所受到的限制，或者說決策變量在這些限制范圍之內(nèi)取值才有實際意義制范圍之內(nèi)取值才有實際意義目標函數(shù)目標函數(shù)(objective function):它代表決策者希望它代表決策者希望對其進行優(yōu)化的那個指標。對其進行優(yōu)化的那個指標。如果一個最優(yōu)化問題的決策變量不是時間的函如果一個最優(yōu)化問題的決策變量不是時

3、間的函數(shù)，則屬于數(shù)，則屬于靜態(tài)優(yōu)化靜態(tài)優(yōu)化(static optimization)或有或有限維優(yōu)化限維優(yōu)化(finite dimensional optimization)的的范疇范疇按照靜態(tài)優(yōu)化問題的結(jié)構(gòu)是否線性分為按照靜態(tài)優(yōu)化問題的結(jié)構(gòu)是否線性分為線性規(guī)線性規(guī)劃劃和和非線性規(guī)劃非線性規(guī)劃線性規(guī)劃的特征是目標函數(shù)線性規(guī)劃的特征是目標函數(shù)和約束條件中的函數(shù)都是決策變量的線性函數(shù)，和約束條件中的函數(shù)都是決策變量的線性函數(shù)，并且約束是必不可少的（否則不存在有實際意并且約束是必不可少的（否則不存在有實際意義的解）義的解）三要素：三要素：決策變量決策變量；目標函數(shù)目標函數(shù)；約束條件約束條件約約束束條

4、條件件決策變量決策變量數(shù)學規(guī)劃模型的一般形式數(shù)學規(guī)劃模型的一般形式njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min規(guī)劃問題：求目標函數(shù)在約束條件下的最值規(guī)劃問題：求目標函數(shù)在約束條件下的最值可行解（只滿足約束）與最優(yōu)解可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值取到最優(yōu)值)目標函數(shù)目標函數(shù)數(shù)學規(guī)劃模型的數(shù)學規(guī)劃模型的簡單分類簡單分類 線性規(guī)劃線性規(guī)劃(LP) 目標和約束均為線性函數(shù)目標和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(NLP) 目標或約束中存在非線性函數(shù)目標或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(QP) 目標為二次函數(shù)、約束為線性目標為二次函數(shù)、約束

5、為線性 整數(shù)規(guī)劃整數(shù)規(guī)劃(IP) 決策變量決策變量(全部或部分全部或部分)為整數(shù)為整數(shù) 整數(shù)整數(shù)線性線性規(guī)劃規(guī)劃(ILP)，整數(shù)，整數(shù)非線性非線性規(guī)劃規(guī)劃(INLP) 純整數(shù)規(guī)劃純整數(shù)規(guī)劃(PIP), 混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃(MIP) 一般整數(shù)規(guī)劃，一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃（整數(shù)）規(guī)劃njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min連連續(xù)續(xù)優(yōu)優(yōu)化化離離散散優(yōu)優(yōu)化化數(shù)學規(guī)劃數(shù)學規(guī)劃MATLABMATLAB優(yōu)化工具箱優(yōu)化工具箱能求解的優(yōu)化模型能求解的優(yōu)化模型優(yōu)化工具箱優(yōu)化工具箱3.0 (MATLAB 7.0 R14)連續(xù)優(yōu)化連續(xù)優(yōu)化離散優(yōu)化離散優(yōu)化無

6、約束優(yōu)化無約束優(yōu)化非線性非線性極小極小fminunc非光滑非光滑(不可不可微微)優(yōu)化優(yōu)化fminsearch非線性非線性方程方程(組組)fzerofsolve全局全局優(yōu)化優(yōu)化暫缺暫缺非線性非線性最小二乘最小二乘lsqnonlinlsqcurvefit線性規(guī)劃線性規(guī)劃linprog純純0-1規(guī)劃規(guī)劃 bintprog一般一般IP(暫缺暫缺)非線性規(guī)劃非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性約束線性最小二乘最小二乘lsqnonneglsqlin約束優(yōu)化約束優(yōu)化二次規(guī)劃

7、二次規(guī)劃quadprog優(yōu)化優(yōu)化線性規(guī)劃線性規(guī)劃非線性規(guī)劃非線性規(guī)劃二次規(guī)劃二次規(guī)劃連續(xù)優(yōu)化連續(xù)優(yōu)化整數(shù)規(guī)劃整數(shù)規(guī)劃 LINDOLINGOLINDO/LINGOLINDO/LINGO軟件能求解的模型軟件能求解的模型 LP QP NLP IP 全局優(yōu)化全局優(yōu)化(選選) ILP IQP INLP LINGOLINGO軟件的求解過程軟件的求解過程 LINGO預(yù)處理程序預(yù)處理程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識別類型識別類型1. 單純形算法單純形算法2. 內(nèi)點算法內(nèi)點算法(選選)1、順序線性規(guī)劃法、順序線

8、性規(guī)劃法(SLP) 2、廣義既約梯度法、廣義既約梯度法(GRG) (選選) 3、多點搜索、多點搜索(Multistart) (選選) LINGO軟件的功能與特點軟件的功能與特點LINGO模型的優(yōu)點模型的優(yōu)點 集成了線性集成了線性(非線性非線性) / 連續(xù)連續(xù)(整數(shù)整數(shù)) 優(yōu)化功能優(yōu)化功能 具有多點搜索具有多點搜索 / 全局優(yōu)化功能全局優(yōu)化功能 提供了靈活的編程語言提供了靈活的編程語言(矩陣生成器矩陣生成器)，可方便地，可方便地輸入模型輸入模型 提供與其他數(shù)據(jù)文件的接口提供與其他數(shù)據(jù)文件的接口 提供與其他編程語言的接口提供與其他編程語言的接口 LINDO API 可用于自主開發(fā)可用于自主開發(fā) 運

9、行速度較快運行速度較快LINDO LINDO 公司軟件產(chǎn)品簡要介紹公司軟件產(chǎn)品簡要介紹 美國芝加哥美國芝加哥(Chicago)大學的大學的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)LINDO API: LINDO Application Programming Interface (V4.1)LINGO: Linear INteractiv

10、e General Optimizer (V10.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0)演示演示(試用試用)版、高級版、超級版、工業(yè)版、擴展版版、高級版、超級版、工業(yè)版、擴展版 （求解（求解問題規(guī)模問題規(guī)模和和選件選件不同）不同）歷史悠久，理論成熟，應(yīng)用廣泛運籌學的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃和多目標規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費用最小或獲得的收益最大。 線性規(guī)劃模型線性規(guī)劃模型1939年前蘇聯(lián)康托洛維奇（年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ） 生產(chǎn)組織與計劃中的生產(chǎn)組織與計劃中

11、的 數(shù)學方法數(shù)學方法提出提出 “解乘數(shù)法解乘數(shù)法”。列奧尼德列奧尼德康托羅維奇，前蘇聯(lián)人，由于在康托羅維奇，前蘇聯(lián)人，由于在1939年創(chuàng)立年創(chuàng)立了享譽全球的線性規(guī)劃要點，對資源最優(yōu)分配理論做了享譽全球的線性規(guī)劃要點，對資源最優(yōu)分配理論做出了貢獻，而獲得諾貝爾經(jīng)濟學獎。出了貢獻，而獲得諾貝爾經(jīng)濟學獎。 線性規(guī)劃理論的發(fā)展線性規(guī)劃理論的發(fā)展美國科學院院士美國科學院院士DANTZIG（丹齊克），（丹齊克），1948年在年在研究美國空軍資源的優(yōu)化配置時提出線性規(guī)劃及其通用研究美國空軍資源的優(yōu)化配置時提出線性規(guī)劃及其通用解法解法 “單純形法單純形法”。被稱為線性規(guī)劃之父。被稱為線性規(guī)劃之父。 線性規(guī)劃之

12、父的線性規(guī)劃之父的Dantzig (Dantzig (丹齊克丹齊克) )。據(jù)說，一次上課，。據(jù)說，一次上課，DantzigDantzig遲到遲到 了，仰頭看去，黑板上留了幾個題目，他就抄了一下，回家后埋頭苦做。了，仰頭看去，黑板上留了幾個題目，他就抄了一下，回家后埋頭苦做。幾個星期之后，疲憊的去找老師說，這件事情真的對不起，作業(yè)好像太幾個星期之后，疲憊的去找老師說，這件事情真的對不起，作業(yè)好像太難了，我所以現(xiàn)在才交，言下很是慚愧。幾天之后，他的老師就把他召難了，我所以現(xiàn)在才交，言下很是慚愧。幾天之后，他的老師就把他召了過去，興奮的告訴他說他太興奮了。了過去，興奮的告訴他說他太興奮了。Dantz

13、igDantzig很不解很不解, , 后來才知道原后來才知道原來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解決的問題，他給出的那個解法也就是單純形法。這個方法是上個世紀前決的問題，他給出的那個解法也就是單純形法。這個方法是上個世紀前十位的算法。十位的算法。 19601960年，年，“最佳資源利用的經(jīng)濟計算最佳資源利用的經(jīng)濟計算” ” 康托洛維奇康托洛維奇和庫伯曼斯和庫伯曼斯(Koopmans) (Koopmans) 。兩人。兩人因?qū)Y源最優(yōu)分配理論的因?qū)Y源最優(yōu)分配理論的貢獻而獲貢獻而獲19751975年諾貝爾經(jīng)濟學

14、獎年諾貝爾經(jīng)濟學獎 佳林佳林庫普曼斯，美國人，他將數(shù)理統(tǒng)計學成功運用庫普曼斯，美國人，他將數(shù)理統(tǒng)計學成功運用于經(jīng)濟計量學，對資源最優(yōu)分配理論做出了貢獻。于經(jīng)濟計量學，對資源最優(yōu)分配理論做出了貢獻。1961年，查恩斯與庫伯提出了目標規(guī)劃，艾吉利提出了用優(yōu)先因子來處理多目標問題。20世紀70年代，斯姆李與杰斯開萊尼應(yīng)用計算機處理目標規(guī)劃問題從1964年諾貝爾獎設(shè)經(jīng)濟學獎后，到1992年28年間的32名獲獎?wù)咧杏?3人(40%)從事過與線性規(guī)劃有關(guān)的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。保羅-薩繆爾遜（PAUL A SAMUELSON ）

15、, 他發(fā)展了數(shù)理和動態(tài)經(jīng)濟理論，將經(jīng)濟科學提高到新的水平。他的研究涉及經(jīng)濟學的全部領(lǐng)域。于1970年獲得諾貝爾經(jīng)濟學獎。華西里列昂惕夫（WASSILY LEONTIEF） ，美國人，他發(fā)展了投入產(chǎn)出方法，該方法在許多重要的經(jīng)濟問題中得到運用。曾獲1973年諾貝爾經(jīng)濟科學獎?？夏崴?J-阿羅（KENNETH J. ARROW）,美國人，因與約翰-?？怂梗↗OHN R. HICKS）共同深入研究了經(jīng)濟均衡理論和福利理論獲得1972年諾貝爾經(jīng)濟學獎。牟頓-米勒（MERTON M. MILLER）,1923-2000, 美國人,由于他在金融經(jīng)濟學方面做出了開創(chuàng)性工作，于1990年獲得諾貝爾經(jīng)濟獎。一個

16、農(nóng)場有一個農(nóng)場有50畝土地畝土地, 20個勞動力個勞動力, 計劃種蔬菜計劃種蔬菜,棉花和水棉花和水稻稻. 種植這三種農(nóng)作物每畝地分別需要勞動力種植這三種農(nóng)作物每畝地分別需要勞動力 1/2 1/3 1/4, 預(yù)計每畝產(chǎn)值分別為預(yù)計每畝產(chǎn)值分別為 110元元, 75元元, 60元元. 如何規(guī)劃經(jīng)營使如何規(guī)劃經(jīng)營使經(jīng)濟效益最大經(jīng)濟效益最大. 種植蔬菜 x1 畝, 棉花 x2 畝, 水稻 x3 畝(決策變量)以取得最高的產(chǎn)值的方式達到收益最大的目標. 求f=110 x1+75x2+60 x3的最大值(目標函數(shù)、優(yōu)劣標準) 約束條件 x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 例例

17、1 1 農(nóng)作物種植農(nóng)作物種植 max : Z =110 x1+75x2+60 x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 x1，x2，x3 0目標函數(shù)和約束條件是線性的，是線性規(guī)劃目標函數(shù)和約束條件是線性的，是線性規(guī)劃如果規(guī)劃問題的數(shù)學模型中，決策變量的取值可以是連續(xù)的，目標函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學模型稱為線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型。 實際問題中線性的含義：一是嚴格的比例性二是可疊加性關(guān)于線性的界定關(guān)于線性的界定比例性：決策變量變化引起目標的改變量與決策變量改變量成正比；可加性：每個決

18、策變量對目標和約束的影響?yīng)毩⒂谄渌兞浚贿B續(xù)性：每個決策變量取連續(xù)值；確定性：線性規(guī)劃中的參數(shù)aij , bi , ci為確定值。 正則模型正則模型 決策變量: x1,x2,xn. 目標函數(shù): Z=c1x1+c2x2+cnxn. 求目標函數(shù)的最小或最大 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm線性規(guī)劃的數(shù)學模型及其標準化線性規(guī)劃的數(shù)學模型及其標準化 標準化模型標準化模型 決策變量 x1, x2, xn, max Z = c1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0, 模型的標準化模型

19、的標準化 10. 引入松弛變量將不等式約束變?yōu)榈仁郊s束 若有 ai1x1+ainxnbi, 則引入xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 則引入xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj. 且此時目標函數(shù)Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m. 20. 將目標函數(shù)的優(yōu)化變?yōu)槟繕撕瘮?shù)的極大化. 若求 min Z, 令 Z=Z, 則問題變?yōu)?max Z. 30. 引入人工變量,使得所有變量均為非負. 若xi沒有非負的條件,則引入 xi 0和xi0, 令xi= xi xi,則可使得問題的全部變量

20、均非負. 線性規(guī)劃的對偶性和影子價格線性規(guī)劃的對偶性和影子價格農(nóng)作物種植（續(xù)）：農(nóng)作物種植（續(xù)）：一個農(nóng)場有50畝土地,20個勞動力, 計劃種蔬菜,棉花和水稻. 種植這三種農(nóng)作物每畝地分別需要勞動力1/2 1/3 1/4,預(yù)計每畝產(chǎn)值分別為110元,75元,60元. 如果土地和勞動力如何規(guī)劃經(jīng)營使經(jīng)濟效益最大. 決策變量決策變量: 對單位土地和單位勞力出租價格分別為對單位土地和單位勞力出租價格分別為 y1 y2目標函數(shù)目標函數(shù): g=50y1+20y2優(yōu)劣準則優(yōu)劣準則: 應(yīng)求應(yīng)求g的最小值的最小值. (因為要達到的要求已經(jīng)通過因為要達到的要求已經(jīng)通過約束條件滿足，決策者關(guān)心的是在最低要求達到時

21、出租價約束條件滿足，決策者關(guān)心的是在最低要求達到時出租價格的心理底線是多少？格的心理底線是多少？)約束條件約束條件: y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 (成本成本不小于產(chǎn)值不小于產(chǎn)值)（我出租出去要比自己種植合適。出租底線）（我出租出去要比自己種植合適。出租底線）對偶線性規(guī)劃對偶線性規(guī)劃 原問題 max f=cTx s.t. Ax b xi 0,i=1,2,n.對偶問題 min f=bTy s.t. ATy c yi 0, i=1,2,m. max : Z =110 x1+75x2+60 x3 s.t. x1+x2+x3 50 1/2x1+1/3x2+1

22、/4x3 20 x1，x2，x3 0 A 是m n 矩陣， c 是 n 1向量，b 是 m 1向量 x 是 n 1向量, y 是 m 1向量min：g=50y1+20y2s.t. y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 y1，y2 0對偶定理對偶定理: 互為對偶的兩個線性規(guī)劃問題 若其中一個有有窮的最優(yōu)解,則另一個也有有窮的最優(yōu)解,且最優(yōu)值相等. 若兩者之一有無界的最優(yōu)解,則另一個沒有可行解。模型II 給出了生產(chǎn)中資源的最低估價. 這種價格涉及到資源的有效利用,它不是市場價格,而是根據(jù)資源在生產(chǎn)中做出的貢獻確定的估價,被稱為“影子價格影子價格”。 模型I 給出

23、了生產(chǎn)中的資源最優(yōu)分配方案。 靈敏度分析主要包括下面幾個內(nèi)容：1：當約束條件的右邊常數(shù)項變化的影響；2：約束條件的系數(shù)變化的影響；3：目標函數(shù)的系數(shù)變化的影響。 可能的影響結(jié)果：1：最優(yōu)解保持不變；2：基變量保持不變，但值變了；3：基本解變化。線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析例：簡單的線性規(guī)劃（例：簡單的線性規(guī)劃（LP）問題）問題 0,12531034.32 yxyxyxtsyxzMax在在空白的模型窗口中輸入這個空白的模型窗口中輸入這個LP模型模型：max 2x+3yst 4x+3y=10 3x+5y12end附錄附錄1：用：用Lindo(Lingo)解線性規(guī)劃解線性規(guī)劃如圖：如圖：

24、 模型求解用鼠標點擊工具欄中的圖標用鼠標點擊工具欄中的圖標 ，或從菜單中選擇或從菜單中選擇Solve|Solve（Ctrl+S）命令命令LINDO首先開始編譯這個首先開始編譯這個模型，編譯沒有錯誤則開模型，編譯沒有錯誤則開始求解；始求解；求解時會首先顯示如右圖求解時會首先顯示如右圖所示的所示的LINDO“求解器運行狀態(tài)窗口求解器運行狀態(tài)窗口 ”。名稱名稱含義含義Status（當前狀態(tài)）顯示當前求解狀態(tài)：顯示當前求解狀態(tài)：“Optimal”表示已經(jīng)達到最優(yōu)解；表示已經(jīng)達到最優(yōu)解；其他可能的顯示還有三個：其他可能的顯示還有三個：Feasible(可行解可行解), Infeasible(不可行不可行

25、), Unbounded(最優(yōu)值無界最優(yōu)值無界)。Iterations（迭代次數(shù)）顯示迭代次數(shù)：顯示迭代次數(shù)：“2”表示經(jīng)過了表示經(jīng)過了2次迭代。次迭代。 Infeasibility （不可行性）約束不滿足的量約束不滿足的量(即各個約束條件不滿足的即各個約束條件不滿足的“數(shù)量數(shù)量”的和；特別注意不是的和；特別注意不是“不滿足的約束個數(shù)不滿足的約束個數(shù)”)：“0”表示這個解是可行的。表示這個解是可行的。Objective （當前的目標值）顯示目標函數(shù)當前的值：顯示目標函數(shù)當前的值：7.45455。Best IP（整數(shù)規(guī)劃當前的最佳目標值）顯示整數(shù)規(guī)劃當前的最佳目標值：顯示整數(shù)規(guī)劃當前的最佳目標值

26、：“N/A” （No Answer或或Not Applicable）表示無答案或無意義，因）表示無答案或無意義，因為這個模型中沒有整數(shù)變量，不是整數(shù)規(guī)劃（為這個模型中沒有整數(shù)變量，不是整數(shù)規(guī)劃（IP）。）。 求解器運行狀態(tài)窗口顯示的相應(yīng)信息及含義名稱名稱含義含義IP Bound（整數(shù)規(guī)劃的界）顯示整數(shù)規(guī)劃的界（對最大化問題顯示上界；對最小化顯示整數(shù)規(guī)劃的界（對最大化問題顯示上界；對最小化問題，顯示下界）：問題，顯示下界）：“N/A”含義同上。含義同上。 Branches（分枝數(shù)）顯示分枝定界算法已經(jīng)計算的分枝數(shù)：顯示分枝定界算法已經(jīng)計算的分枝數(shù)： “N/A”含義同含義同上。上。Elapsed

27、Time（所用時間）顯示計算所用時間（秒）：顯示計算所用時間（秒）：“0.00”說明計算太快了，說明計算太快了，用時還不到用時還不到0.005秒。秒。Update Interval（刷新本界面的時間間隔）顯示和控制刷新本界面的時間間隔：顯示和控制刷新本界面的時間間隔：“1”表示表示1秒；用秒；用戶可以直接在界面上修改這個時間間隔。戶可以直接在界面上修改這個時間間隔。Interrupt Solver（中斷求解程序）當模型規(guī)模比較大時（尤其對整數(shù)規(guī)劃），可能求解時當模型規(guī)模比較大時（尤其對整數(shù)規(guī)劃），可能求解時間會很長，如果不想再等待下去時，可以在程序運行過間會很長，如果不想再等待下去時，可以在程

28、序運行過程中用鼠標點擊該按鈕終止計算。求解結(jié)束后這個按鈕程中用鼠標點擊該按鈕終止計算。求解結(jié)束后這個按鈕變成了灰色，再點擊就不起作用了。變成了灰色，再點擊就不起作用了。Close（關(guān)閉）該按鈕只是關(guān)閉狀態(tài)窗口，并不終止計算。如果你關(guān)閉該按鈕只是關(guān)閉狀態(tài)窗口，并不終止計算。如果你關(guān)閉了狀態(tài)窗口，將來隨時可以選擇了狀態(tài)窗口，將來隨時可以選擇WINDOW | OPEN STATUS WINDOW 菜單命令來再次打開這個窗口。菜單命令來再次打開這個窗口。緊接著彈出一對話框，詢問你是否需要做靈敏性分析緊接著彈出一對話框，詢問你是否需要做靈敏性分析（DO RANGE (SENSITIVITY) ANALY

29、SIS? ）先選擇）先選擇“否（否（N）”按鈕，這個窗口就會關(guān)閉。然后，再把狀態(tài)按鈕，這個窗口就會關(guān)閉。然后，再把狀態(tài)窗口也關(guān)閉。窗口也關(guān)閉。 報告窗口 用鼠標選擇用鼠標選擇“Window | Reports Window”（報告窗口），（報告窗口），就可以查看該窗口的內(nèi)容就可以查看該窗口的內(nèi)容 保存文件選擇選擇File|Save（F5）命令把命令把“結(jié)果報告結(jié)果報告”保存在一個文件中保存在一個文件中（缺省的后綴名為（缺省的后綴名為LTX,即即LINDO文本文件）文本文件）類似地，回到模型窗口，可以把輸入的模型保存在一個文件類似地，回到模型窗口，可以把輸入的模型保存在一個文件中。保存的文件將來

30、可以用中。保存的文件將來可以用File | Open（F3）和）和File | View（F4）重新打開，用前者打開的程序可以進行修改，而后者）重新打開，用前者打開的程序可以進行修改，而后者只能瀏覽。只能瀏覽。如果模型有錯誤如果模型有錯誤,運行時會彈出出錯信息報告窗口運行時會彈出出錯信息報告窗口(LINDO Error Message)，則需要修改模型。，則需要修改模型。例：某家具公司制造書桌、餐桌和椅子，所用的資源有例：某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示。三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示。每個書桌每個餐桌每個椅子現(xiàn)有資源總數(shù)木料8

31、單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位 若要求桌子的生產(chǎn)量不超過若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？的生產(chǎn)可使利潤最大？解解：用用DESKS、TABLES和和CHAIRS分別表示三種產(chǎn)品的分別表示三種產(chǎn)品的生產(chǎn)量（決策變量），容易建立生產(chǎn)量（決策變量），容易建立LP模型。模型。在在LINDO模型窗口中輸入模型：模型窗口中輸入模型：MAX 60 DESKS + 30 TABLES + 20 CHAIRSSUBJECT TO 2) 8 DESKS + 6 TAB

32、LES + CHAIRS = 48 3) 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20 4) DESKS + 1 5 TABLES + O 5 CHAIRS = 8 5) TABLES = 5END解這個模型，并對彈出的對話框解這個模型，并對彈出的對話框 “ DO RANGE (SENSITIVITY) ANALYSIS? ” 選擇選擇“是（是（Y）”按鈕，這表示你需要做靈敏性分析。然后，按鈕，這表示你需要做靈敏性分析。然后，查看輸出結(jié)果。查看輸出結(jié)果。LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 28

33、0.0000 VARIABLE VALUE REDUCED COST DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 24.000000 0.000000 3) 0.000000 10.000000 4) 0.000000 10.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1輸出結(jié)果的前半部分：輸出結(jié)果的前半部分：前半部分的輸出結(jié)果的解釋前半部分的輸出結(jié)果的解釋:“LP OPTIM

34、UM FOUND AT STEP2”表示兩次迭代（旋轉(zhuǎn)變換）后得到最優(yōu)解。表示兩次迭代（旋轉(zhuǎn)變換）后得到最優(yōu)解。“OBJECTIVE FUNCTION VALUE 1）280.000000”表示最優(yōu)目標值為表示最優(yōu)目標值為280。 “VALUE”給出最優(yōu)解中各變量的值：造給出最優(yōu)解中各變量的值：造2個書桌（個書桌（desks）, 0個餐桌（個餐桌（tables）, 8個椅子（個椅子（chairs）。所以）。所以desks、chairs是基變量（取值非是基變量（取值非0），），tables是非基變量（取值為是非基變量（取值為0）。）。 “SLACK OR SURPLUS”給出松馳變量的值給出松馳

35、變量的值。（在最優(yōu)的情況下資源的剩余量）。（在最優(yōu)的情況下資源的剩余量） 第第2行松馳變量行松馳變量 =24 （第（第1行表示目標函數(shù)，第行表示目標函數(shù)，第2行對應(yīng)第行對應(yīng)第1個約束）個約束） 第第3行松馳變量行松馳變量 =0 第第4行松馳變量行松馳變量 =0 第第5行松馳變量行松馳變量 =5“REDUCED COST”列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當變列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當變量有微小變動時量有微小變動時, 目標函數(shù)的變化率目標函數(shù)的變化率. 其中其中 基變量的基變量的reduced cost值應(yīng)為值應(yīng)為0; 非基變量非基變量 Xj，相應(yīng)的，相應(yīng)的

36、 reduced cost值值1）表示當非基變量）表示當非基變量Xj 增加一個單位時，目標函數(shù)相應(yīng)減少的增加一個單位時，目標函數(shù)相應(yīng)減少的量量( max型問題型問題)。2）理解為：為了使該非基變量變成基變量，目標函數(shù)中該變）理解為：為了使該非基變量變成基變量，目標函數(shù)中該變量前對應(yīng)系數(shù)應(yīng)增加的量。量前對應(yīng)系數(shù)應(yīng)增加的量。本例中：變量TABLES對應(yīng)的reduced cost值為5。 1）表示當非基變量TABLES 的值從0變?yōu)?時（此時假定其它非基變量保持不變,但為了滿足約束條件，基變量顯然會發(fā)生變化），此時的最優(yōu)的目標函數(shù)值為280 - 5=275。 2）理解為目前table的單價30元偏低

37、，不值得生產(chǎn)，如果生產(chǎn)的話至少35元。“DUAL PRICE” （對偶價格）表示當對應(yīng)約束有微小變動時（對偶價格）表示當對應(yīng)約束有微小變動時, 目標函數(shù)的變化率目標函數(shù)的變化率. 輸出結(jié)果中對應(yīng)于每一個約束有一個對偶價輸出結(jié)果中對應(yīng)于每一個約束有一個對偶價格格. 若其數(shù)值為若其數(shù)值為p, 表示對應(yīng)約束中不等式右端項若增加表示對應(yīng)約束中不等式右端項若增加1個單位個單位, 目標函數(shù)將增加目標函數(shù)將增加p個單位（個單位（max型問題型問題)。也就是相應(yīng)的一個單。也就是相應(yīng)的一個單位的該資源在生產(chǎn)過程中產(chǎn)生的效益，即其價值。位的該資源在生產(chǎn)過程中產(chǎn)生的效益，即其價值。1）如果在最優(yōu)解處約束正好取等號（

38、也就是）如果在最優(yōu)解處約束正好取等號（也就是“緊約束緊約束”現(xiàn)有相現(xiàn)有相應(yīng)資源全部使用），該資源的對偶價格才可能不是應(yīng)資源全部使用），該資源的對偶價格才可能不是0。例如本例。例如本例中：第中：第3行是緊約束，對應(yīng)的是資源是漆工，其對偶價格值為行是緊約束，對應(yīng)的是資源是漆工，其對偶價格值為10，表示當緊約束表示當緊約束 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20變變?yōu)闉?4 DESKS + 2 TABLES + 1.5 CHAIRS = 50TUE) X1 + X2 + X5 + X6 + X7 = 50WED) X1 + X2 + X3 + X6 + X7 = 5

39、0THU) X1+ X2 + X3 + X4 +X7 = 50FRI) X1 + X2 + X3 + X4 - X5 = 80SAT) X2 + X3 + X4 - X5 + X6 = 90SUN) X3 + X4 - X5 + X6 + X7 = 90ENDGIN 7其中其中“GIN 7”表示表示7個變量都是一般整數(shù)變量。個變量都是一般整數(shù)變量。 （仍然默認為取值是非負的）（仍然默認為取值是非負的）求解后狀態(tài)窗口中與整數(shù)相關(guān)的三個域有了相關(guān)結(jié)果求解后狀態(tài)窗口中與整數(shù)相關(guān)的三個域有了相關(guān)結(jié)果:“Best IP ：94”表示當前表示當前得到的最好的整數(shù)解的目得到的最好的整數(shù)解的目標函數(shù)值為標函數(shù)

40、值為94（人）。（人）?！癐P Bound ：93.5” 表示表示該整數(shù)規(guī)劃目標值的下界該整數(shù)規(guī)劃目標值的下界為為93.5 （人）。（人）?！癇ranches ：1”表示分表示分枝數(shù)為枝數(shù)為1（即在第（即在第1個分枝個分枝中就找到了最優(yōu)解）。中就找到了最優(yōu)解）。我們前面說過，我們前面說過，LINDO求解求解IP用的是分枝定界法。用的是分枝定界法。顯然，上面第二條顯然，上面第二條“整數(shù)規(guī)劃目標值的下界為整數(shù)規(guī)劃目標值的下界為93.5 （人）（人）”表明至少要表明至少要聘用聘用93.5名員工，由于員工人數(shù)只能是整數(shù)，所以至少要聘用名員工，由于員工人數(shù)只能是整數(shù)，所以至少要聘用94（人）。（人）。而

41、第一條說明目前得到的解就是聘用而第一條說明目前得到的解就是聘用94（人），所以已經(jīng)是最優(yōu)的了。（人），所以已經(jīng)是最優(yōu)的了。 LP OPTIMUM FOUND AT STEP 8 OBJECTIVE VALUE = 93.3333359 SET X2 TO = 4 AT 1, BND= -94.00 TWIN= -93.50 18 NEW INTEGER SOLUTION OF 94.0000000 AT BRANCH 1 PIVOT 18 BOUND ON OPTIMUM: 93.50000 DELETE X2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES

42、= 1 PIVOTS= 18 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. 求解結(jié)果的報告窗口如下：求解結(jié)果的報告窗口如下： （接下頁）（接下頁） OBJECTIVE FUNCTION VALUE 1) 94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.00

43、0000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON) 0.000000 0.000000 TUE) 2.000000 0.000000 WED) 8.000000 0.000000 THU) 0.000000 0.000000 FRI) 0.000000 0.000000 SAT) 0.000000 0.000000 SUN) 0.000000 0.000000 NO. ITERATIONS= 18 BRANCHES= 1 DETERM.= 1.000E 0報告窗口中前兩行告訴我們：在報告窗口中前兩行告

44、訴我們：在8次迭代后找到對應(yīng)的線次迭代后找到對應(yīng)的線性規(guī)劃（性規(guī)劃（LP）問題的最優(yōu)解，最優(yōu)值）問題的最優(yōu)解，最優(yōu)值=93.3333359。 LINDO求解求解IP用的是分枝定界法，緊接著幾行顯示的是分用的是分枝定界法，緊接著幾行顯示的是分枝定界的信息，在第枝定界的信息，在第1個分枝中設(shè)定個分枝中設(shè)定x2=4,并在該分枝中并在該分枝中找到了整數(shù)解，而且就是全局整數(shù)最優(yōu)解，所以算法停止。找到了整數(shù)解，而且就是全局整數(shù)最優(yōu)解，所以算法停止。旋轉(zhuǎn)迭代（旋轉(zhuǎn)迭代（PIVOT）共）共18次。次。 后面顯示的是最后的最優(yōu)解：后面顯示的是最后的最優(yōu)解：x=(0,4,40,2,34,10,4).松弛和剩余變量

45、（松弛和剩余變量（SLACK OR SURPLUS）仍然可以表示）仍然可以表示約束的松緊程度，但目前約束的松緊程度，但目前IP尚無相應(yīng)完善的敏感性分析理尚無相應(yīng)完善的敏感性分析理論，因此論，因此REDUCED COST和和DUAL PRICES的結(jié)果在整數(shù)的結(jié)果在整數(shù)規(guī)劃中意義不大。規(guī)劃中意義不大。 聘用方案（續(xù)）聘用方案（續(xù)） 郵局一周中每天需要不同數(shù)目的雇員，設(shè)周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又規(guī)定應(yīng)聘者需連續(xù)工作5天，問郵局每天聘多少雇員才能既滿足需求，又使聘用總?cè)藬?shù)最少。 進一步考慮，上述指全時雇員（每天工作8小時）。如果郵局也可聘用半天雇員（每天工作

46、4小時，連續(xù)工作5天），設(shè)全時和半時雇員的工資每小時為3元和2元，并且限制半時雇員的工作量不應(yīng)超過總工作量的四分之一，問郵局如何安排聘用方案，使所付工資總額最少？ 分析分析此時決策變量由兩部分構(gòu)成：此時決策變量由兩部分構(gòu)成： 全時雇員全時雇員x1,x2, x3,x4,x5,x6,x7; 半時雇員半時雇員y1,y2, y3,y4,y5,y6,y7.目標值應(yīng)該是雇員的總工資，標準是最少：目標值應(yīng)該是雇員的總工資，標準是最少： min : Z=385xi245yi約束條件：約束條件： 每天的工作量應(yīng)該折合為小時工作量每天的工作量應(yīng)該折合為小時工作量(以周一的工作量為例以周一的工作量為例) 8(x4x

47、5x6x7x1)4 (y4y5y6y7y1) =8a1 半時雇員的限制半時雇員的限制 45yi=0.258(ai)一個旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有4 件物品 重量為 2 kg , 3 kg, 3 kg, 4 kg, 價值為 1 元, 1.2元, 0.9元, 1.1元. 應(yīng)攜帶那些物品使得攜帶物品的價值最大?0-1規(guī)劃規(guī)劃 背包問題背包問題 決策變量： xj 旅行者是否攜帶第 j 件物品, xj = 0, 1.約束條件 2x1+3x 2+3x 3+4x 4 6目標函數(shù) f=x1+1.2x2+0.9x3+1.1x4 優(yōu)劣標準： 最大.用Lingo 軟件求解0-1規(guī)劃Linear

48、Interactive and General OptimizerModel:Max=x1+1.2*x2+0.9*x3+1.1*x4;2*x1+3*x2+3*x3+4*x4=6;bin(x1);bin(x2);bin(x3);bin(x4);end 工廠可用k種不同的工藝生產(chǎn)n種產(chǎn)品，每種產(chǎn)品的利潤已知。在各種工藝條件下每種產(chǎn)品所消耗的資源是確定的，并且，工廠的總資源有一定限制。問應(yīng)選擇哪種工藝，每種產(chǎn)品各生產(chǎn)多少，使總利潤最大 混合混合0-1規(guī)劃規(guī)劃 生產(chǎn)工藝問題生產(chǎn)工藝問題分析分析 有關(guān)參量：用有關(guān)參量：用A1,A2,Ak表示表示k種工藝；用種工藝；用B1,B2,Bn表示表示n種產(chǎn)品；單件

49、種產(chǎn)品；單件Bi的利潤的利潤pi；在；在工藝工藝Aj下下,資源限制資源限制Qj，單件，單件Bi的資源消耗的資源消耗cij。決策變量：一是決策變量：一是Bi的產(chǎn)量的產(chǎn)量xi；一是工藝的選擇。；一是工藝的選擇。目標函數(shù)目標函數(shù): max: Zp1*x1+p2*x2+ +pn*xn資源限制約束：資源限制約束： cij*xi=0 為保證為保證yj1的工藝不被選擇，資源限制條件改的工藝不被選擇，資源限制條件改為為 cij*xi=Qj +yjM j=1,2, ,k 其中其中M充分大的一個正數(shù)。充分大的一個正數(shù)。 （當（當yj1時，此約束條件對任何決策變量時，此約束條件對任何決策變量xi都都成立，所以在成立

50、，所以在k個資源限制約束中只有個資源限制約束中只有yj0的有的有效。）效。）牌牌號號產(chǎn)量成本價格甲甲x1q1p1乙乙x2q2p2假設(shè)假設(shè)A產(chǎn)銷平衡產(chǎn)銷平衡假設(shè)假設(shè)Bp隨隨x (兩種牌號兩種牌號)增加而減小，呈線性關(guān)系增加而減小，呈線性關(guān)系12111211121211111, 0,aaaabxaxabp某廠生產(chǎn)兩個牌號的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大某廠生產(chǎn)兩個牌號的同一種產(chǎn)品，如何確定產(chǎn)量使利潤最大21222221222212122, 0,aaaabxaxabp二次規(guī)劃模型產(chǎn)銷計劃問題二次規(guī)劃模型產(chǎn)銷計劃問題22211121,)()(),(max21xqpxqpxxzxx目標目標利潤最大利潤最大=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1 + 277 x2 x12 0.3 x1 x2 2x22 約束約束x1 + x2 100 x1 2 x2x1 , x2 0 二次規(guī)劃模型二次