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

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

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

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

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

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

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

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

9、行速度較快運行速度較快LINDO LINDO 公司軟件產品簡要介紹公司軟件產品簡要介紹 美國芝加哥美國芝加哥(Chicago)大學的大學的Linus Schrage教授于教授于1980年前后開發年前后開發, 后來成立后來成立 LINDO系統公司（系統公司（LINDO Systems Inc.），）， 網址：網址：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)演示演示(試用試用)版、高級版、超級版、工業版、擴展版版、高級版、超級版、工業版、擴展版 （求解（求解問題規模問題規模和和選件選件不同）不同）歷史悠久，理論成熟，應用廣泛運籌學的最基本的方法之一，網絡規劃、整數規劃、目標規劃和多目標規劃都是以線性規劃為基礎的。解決稀缺資源最優分配的有效方法，使付出的費用最小或獲得的收益最大。 線性規劃模型線性規劃模型1939年前蘇聯康托洛維奇（年前蘇聯康托洛維奇（KOHTOPOBUZ） 生產組織與計劃中的生產組織與計劃中

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

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

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

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

15、, 他發展了數理和動態經濟理論，將經濟科學提高到新的水平。他的研究涉及經濟學的全部領域。于1970年獲得諾貝爾經濟學獎。華西里列昂惕夫（WASSILY LEONTIEF） ，美國人，他發展了投入產出方法，該方法在許多重要的經濟問題中得到運用。曾獲1973年諾貝爾經濟科學獎。肯尼斯-J-阿羅（KENNETH J. ARROW）,美國人，因與約翰-希克斯（JOHN R. HICKS）共同深入研究了經濟均衡理論和福利理論獲得1972年諾貝爾經濟學獎。牟頓-米勒（MERTON M. MILLER）,1923-2000, 美國人,由于他在金融經濟學方面做出了開創性工作，于1990年獲得諾貝爾經濟獎。一個

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

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

18、策變量對目標和約束的影響獨立于其它變量；連續性：每個決策變量取連續值；確定性：線性規劃中的參數aij , bi , ci為確定值。 正則模型正則模型 決策變量: x1,x2,xn. 目標函數: Z=c1x1+c2x2+cnxn. 求目標函數的最小或最大 約束條件: a11x1+a1nxnb1, am1x1+amnxnbm線性規劃的數學模型及其標準化線性規劃的數學模型及其標準化 標準化模型標準化模型 決策變量 x1, x2, xn, max Z = c1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0, 模型的標準化模型

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

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

21、出租價約束條件滿足，決策者關心的是在最低要求達到時出租價格的心理底線是多少？格的心理底線是多少？)約束條件約束條件: y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 (成本成本不小于產值不小于產值)（我出租出去要比自己種植合適。出租底線）（我出租出去要比自己種植合適。出租底線）對偶線性規劃對偶線性規劃 原問題 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對偶定理對偶定理: 互為對偶的兩個線性規劃問題 若其中一個有有窮的最優解,則另一個也有有窮的最優解,且最優值相等. 若兩者之一有無界的最優解,則另一個沒有可行解。模型II 給出了生產中資源的最低估價. 這種價格涉及到資源的有效利用,它不是市場價格,而是根據資源在生產中做出的貢獻確定的估價,被稱為“影子價格影子價格”。 模型I 給出

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

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

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

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

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

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

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

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

31、單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價60單位30單位20單位 若要求桌子的生產量不超過若要求桌子的生產量不超過5件，如何安排三種產品件，如何安排三種產品的生產可使利潤最大？的生產可使利潤最大？解解：用用DESKS、TABLES和和CHAIRS分別表示三種產品的分別表示三種產品的生產量（決策變量），容易建立生產量（決策變量），容易建立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）”按鈕，這表示你需要做靈敏性分析。然后，按鈕，這表示你需要做靈敏性分析。然后，查看輸出結果。查看輸出結果。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輸出結果的前半部分：輸出結果的前半部分：前半部分的輸出結果的解釋前半部分的輸出結果的解釋:“LP OPTIM

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

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

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

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

38、也就是）如果在最優解處約束正好取等號（也就是“緊約束緊約束”現有相現有相應資源全部使用），該資源的對偶價格才可能不是應資源全部使用），該資源的對偶價格才可能不是0。例如本例。例如本例中：第中：第3行是緊約束，對應的是資源是漆工，其對偶價格值為行是緊約束，對應的是資源是漆工，其對偶價格值為10，表示當緊約束表示當緊約束 4 DESKS + 2 TABLES + 1.5 CHAIRS = 20變變為為 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個變量都是一般整數變量。個變量都是一般整數變量。 （仍然默認為取值是非負的）（仍然默認為取值是非負的）求解后狀態窗口中與整數相關的三個域有了相關結果求解后狀態窗口中與整數相關的三個域有了相關結果:“Best IP ：94”表示當前表示當前得到的最好的整數解的目得到的最好的整數解的目標函數值為標函數

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

41、第一條說明目前得到的解就是聘用而第一條說明目前得到的解就是聘用94（人），所以已經是最優的了。（人），所以已經是最優的了。 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. 求解結果的報告窗口如下：求解結果的報告窗口如下： （接下頁）（接下頁） 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次迭代后找到對應的線次迭代后找到對應的線性規劃（性規劃（LP）問題的最優解，最優值）問題的最優解，最優值=93.3333359。 LINDO求解求解IP用的是分枝定界法，緊接著幾行顯示的是分用的是分枝定界法，緊接著幾行顯示的是分枝定界的信息，在第枝定界的信息，在第1個分枝中設定個分枝中設定x2=4,并在該分枝中并在該分枝中找到了整數解，而且就是全局整數最優解，所以算法停止。找到了整數解，而且就是全局整數最優解，所以算法停止。旋轉迭代（旋轉迭代（PIVOT）共）共18次。次。 后面顯示的是最后的最優解：后面顯示的是最后的最優解：x=(0,4,40,2,34,10,4).松弛和剩余變量

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

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

47、5x6x7x1)4 (y4y5y6y7y1) =8a1 半時雇員的限制半時雇員的限制 45yi=0.258(ai)一個旅行者的背包最多只能裝 6 kg 物品. 現有4 件物品 重量為 2 kg , 3 kg, 3 kg, 4 kg, 價值為 1 元, 1.2元, 0.9元, 1.1元. 應攜帶那些物品使得攜帶物品的價值最大?0-1規劃規劃 背包問題背包問題 決策變量： xj 旅行者是否攜帶第 j 件物品, xj = 0, 1.約束條件 2x1+3x 2+3x 3+4x 4 6目標函數 f=x1+1.2x2+0.9x3+1.1x4 優劣標準： 最大.用Lingo 軟件求解0-1規劃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種不同的工藝生產n種產品，每種產品的利潤已知。在各種工藝條件下每種產品所消耗的資源是確定的，并且，工廠的總資源有一定限制。問應選擇哪種工藝，每種產品各生產多少，使總利潤最大 混合混合0-1規劃規劃 生產工藝問題生產工藝問題分析分析 有關參量：用有關參量：用A1,A2,Ak表示表示k種工藝；用種工藝；用B1,B2,Bn表示表示n種產品；單件

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

50、，所以在k個資源限制約束中只有個資源限制約束中只有yj0的有的有效。）效。）牌牌號號產量成本價格甲甲x1q1p1乙乙x2q2p2假設假設A產銷平衡產銷平衡假設假設Bp隨隨x (兩種牌號兩種牌號)增加而減小，呈線性關系增加而減小，呈線性關系12111211121211111, 0,aaaabxaxabp某廠生產兩個牌號的同一種產品，如何確定產量使利潤最大某廠生產兩個牌號的同一種產品，如何確定產量使利潤最大21222221222212122, 0,aaaabxaxabp二次規劃模型產銷計劃問題二次規劃模型產銷計劃問題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 二次規劃模型二次