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

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

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

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ī)劃的特征是目標(biāo)函數(shù)線性規(guī)劃的特征是目標(biāo)函數(shù)和約束條件中的函數(shù)都是決策變量的線性函數(shù)，和約束條件中的函數(shù)都是決策變量的線性函數(shù)，并且約束是必不可少的（否則不存在有實(shí)際意并且約束是必不可少的（否則不存在有實(shí)際意義的解）義的解）三要素：三要素：決策變量決策變量；目標(biāo)函數(shù)目標(biāo)函數(shù)；約束條件約束條件約約束束條

4、條件件決策變量決策變量數(shù)學(xué)規(guī)劃模型的一般形式數(shù)學(xué)規(guī)劃模型的一般形式njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min規(guī)劃問題：求目標(biāo)函數(shù)在約束條件下的最值規(guī)劃問題：求目標(biāo)函數(shù)在約束條件下的最值可行解（只滿足約束）與最優(yōu)解可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值取到最優(yōu)值)目標(biāo)函數(shù)目標(biāo)函數(shù)數(shù)學(xué)規(guī)劃模型的數(shù)學(xué)規(guī)劃模型的簡(jiǎn)單分類簡(jiǎn)單分類 線性規(guī)劃線性規(guī)劃(LP) 目標(biāo)和約束均為線性函數(shù)目標(biāo)和約束均為線性函數(shù) 非線性規(guī)劃非線性規(guī)劃(NLP) 目標(biāo)或約束中存在非線性函數(shù)目標(biāo)或約束中存在非線性函數(shù) 二次規(guī)劃二次規(guī)劃(QP) 目標(biāo)為二次函數(shù)、約束為線性目標(biāo)為二次函數(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ù)學(xué)規(guī)劃數(shù)學(xué)規(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)化無(wú)

6、約束優(yōu)化無(wú)約束優(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軟件的求解過(guò)程軟件的求解過(guò)程 LINGO預(yù)處理程序預(yù)處理程序線性優(yōu)化求解程序線性優(yōu)化求解程序非線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序分枝定界管理程序1. 確定常數(shù)確定常數(shù)2. 識(shí)別類型識(shí)別類型1. 單純形算法單純形算法2. 內(nèi)點(diǎn)算法內(nèi)點(diǎn)算法(選選)1、順序線性規(guī)劃法、順序線

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

9、行速度較快運(yùn)行速度較快LINDO LINDO 公司軟件產(chǎn)品簡(jiǎn)要介紹公司軟件產(chǎn)品簡(jiǎn)要介紹 美國(guó)芝加哥美國(guó)芝加哥(Chicago)大學(xué)的大學(xué)的Linus Schrage教授于教授于1980年前后開發(fā)年前后開發(fā), 后來(lái)成立后來(lái)成立 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)演示演示(試用試用)版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版 （求解（求解問題規(guī)模問題規(guī)模和和選件選件不同）不同）歷史悠久，理論成熟，應(yīng)用廣泛運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。 線性規(guī)劃模型線性規(guī)劃模型1939年前蘇聯(lián)康托洛維奇（年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ） 生產(chǎn)組織與計(jì)劃中的生產(chǎn)組織與計(jì)劃中

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

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

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

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

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

16、農(nóng)場(chǎng)有一個(gè)農(nóng)場(chǎng)有50畝土地畝土地, 20個(gè)勞動(dòng)力個(gè)勞動(dòng)力, 計(jì)劃種蔬菜計(jì)劃種蔬菜,棉花和水棉花和水稻稻. 種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力 1/2 1/3 1/4, 預(yù)計(jì)每畝產(chǎn)值分別為預(yù)計(jì)每畝產(chǎn)值分別為 110元元, 75元元, 60元元. 如何規(guī)劃經(jīng)營(yíng)使如何規(guī)劃經(jīng)營(yíng)使經(jīng)濟(jì)效益最大經(jīng)濟(jì)效益最大. 種植蔬菜 x1 畝, 棉花 x2 畝, 水稻 x3 畝(決策變量)以取得最高的產(chǎn)值的方式達(dá)到收益最大的目標(biāo). 求f=110 x1+75x2+60 x3的最大值(目標(biāo)函數(shù)、優(yōu)劣標(biāo)準(zhǔn)) 約束條件 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目標(biāo)函數(shù)和約束條件是線性的，是線性規(guī)劃目標(biāo)函數(shù)和約束條件是線性的，是線性規(guī)劃如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型。 實(shí)際問題中線性的含義：一是嚴(yán)格的比例性二是可疊加性關(guān)于線性的界定關(guān)于線性的界定比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比；可加性：每個(gè)決

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

19、的標(biāo)準(zhǔn)化 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í)目標(biāo)函數(shù)Z=c1x1+c2x2+cnxn+0 xn+1+0 xn+m. 20. 將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化. 若求 min Z, 令 Z=Z, 則問題變?yōu)?max Z. 30. 引入人工變量,使得所有變量均為非負(fù). 若xi沒有非負(fù)的條件,則引入 xi 0和xi0, 令xi= xi xi,則可使得問題的全部變量

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

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

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

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

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

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

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

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

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

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

31、單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價(jià)60單位30單位20單位 若要求桌子的生產(chǎn)量不超過(guò)若要求桌子的生產(chǎn)量不超過(guò)5件，如何安排三種產(chǎn)品件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤(rùn)最大？的生產(chǎn)可使利潤(rù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解這個(gè)模型，并對(duì)彈出的對(duì)話框解這個(gè)模型，并對(duì)彈出的對(duì)話框 “ 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)解?！癘BJECTIVE FUNCTION VALUE 1）280.000000”表示最優(yōu)目標(biāo)值為表示最優(yōu)目標(biāo)值為280。 “VALUE”給出最優(yōu)解中各變量的值：造給出最優(yōu)解中各變量的值：造2個(gè)書桌（個(gè)書桌（desks）, 0個(gè)餐桌（個(gè)餐桌（tables）, 8個(gè)椅子（個(gè)椅子（chairs）。所以）。所以desks、chairs是基變量（取值非是基變量（取值非0），），tables是非基變量（取值為是非基變量（取值為0）。）。 “SLACK OR SURPLUS”給出松馳變量的值給出松馳

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

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

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

38、也就是）如果在最優(yōu)解處約束正好取等號(hào)（也就是“緊約束緊約束”現(xiàn)有相現(xiàn)有相應(yīng)資源全部使用），該資源的對(duì)偶價(jià)格才可能不是應(yīng)資源全部使用），該資源的對(duì)偶價(jià)格才可能不是0。例如本例。例如本例中：第中：第3行是緊約束，對(duì)應(yīng)的是資源是漆工，其對(duì)偶價(jià)格值為行是緊約束，對(duì)應(yīng)的是資源是漆工，其對(duì)偶價(jià)格值為10，表示當(dāng)緊約束表示當(dāng)緊約束 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個(gè)變量都是一般整數(shù)變量。個(gè)變量都是一般整數(shù)變量。 （仍然默認(rèn)為取值是非負(fù)的）（仍然默認(rèn)為取值是非負(fù)的）求解后狀態(tài)窗口中與整數(shù)相關(guān)的三個(gè)域有了相關(guān)結(jié)果求解后狀態(tài)窗口中與整數(shù)相關(guān)的三個(gè)域有了相關(guān)結(jié)果:“Best IP ：94”表示當(dāng)前表示當(dāng)前得到的最好的整數(shù)解的目得到的最好的整數(shù)解的目標(biāo)函數(shù)值為標(biāo)函數(shù)

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

41、第一條說(shuō)明目前得到的解就是聘用而第一條說(shuō)明目前得到的解就是聘用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é)果的報(bào)告窗口如下：求解結(jié)果的報(bào)告窗口如下： （接下頁(yè)）（接下頁(yè)） 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報(bào)告窗口中前兩行告訴我們：在報(bào)告窗口中前兩行告

44、訴我們：在8次迭代后找到對(duì)應(yīng)的線次迭代后找到對(duì)應(yīng)的線性規(guī)劃（性規(guī)劃（LP）問題的最優(yōu)解，最優(yōu)值）問題的最優(yōu)解，最優(yōu)值=93.3333359。 LINDO求解求解IP用的是分枝定界法，緊接著幾行顯示的是分用的是分枝定界法，緊接著幾行顯示的是分枝定界的信息，在第枝定界的信息，在第1個(gè)分枝中設(shè)定個(gè)分枝中設(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尚無(wú)相應(yīng)完善的敏感性分析理尚無(wú)相應(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ù)最少。 進(jìn)一步考慮，上述指全時(shí)雇員（每天工作8小時(shí)）。如果郵局也可聘用半天雇員（每天工作

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

47、5x6x7x1)4 (y4y5y6y7y1) =8a1 半時(shí)雇員的限制半時(shí)雇員的限制 45yi=0.258(ai)一個(gè)旅行者的背包最多只能裝 6 kg 物品. 現(xiàn)有4 件物品 重量為 2 kg , 3 kg, 3 kg, 4 kg, 價(jià)值為 1 元, 1.2元, 0.9元, 1.1元. 應(yīng)攜帶那些物品使得攜帶物品的價(jià)值最大?0-1規(guī)劃規(guī)劃 背包問題背包問題 決策變量： xj 旅行者是否攜帶第 j 件物品, xj = 0, 1.約束條件 2x1+3x 2+3x 3+4x 4 6目標(biāo)函數(shù) f=x1+1.2x2+0.9x3+1.1x4 優(yōu)劣標(biāo)準(zhǔn)： 最大.用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)品的利潤(rùn)已知。在各種工藝條件下每種產(chǎn)品所消耗的資源是確定的，并且，工廠的總資源有一定限制。問應(yīng)選擇哪種工藝，每種產(chǎn)品各生產(chǎn)多少，使總利潤(rù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的利潤(rùn)的利潤(rùn)pi；在；在工藝工藝Aj下下,資源限制資源限制Qj，單件，單件Bi的資源消耗的資源消耗cij。決策變量：一是決策變量：一是Bi的產(chǎn)量的產(chǎn)量xi；一是工藝的選擇。；一是工藝的選擇。目標(biāo)函數(shù)目標(biāo)函數(shù): max: Zp1*x1+p2*x2+ +pn*xn資源限制約束：資源限制約束： cij*xi=0 為保證為保證yj1的工藝不被選擇，資源限制條件改的工藝不被選擇，資源限制條件改為為 cij*xi=Qj +yjM j=1,2, ,k 其中其中M充分大的一個(gè)正數(shù)。充分大的一個(gè)正數(shù)。 （當(dāng)（當(dāng)yj1時(shí)，此約束條件對(duì)任何決策變量時(shí)，此約束條件對(duì)任何決策變量xi都都成立，所以在成立

50、，所以在k個(gè)資源限制約束中只有個(gè)資源限制約束中只有yj0的有的有效。）效。）牌牌號(hào)號(hào)產(chǎn)量成本價(jià)格甲甲x1q1p1乙乙x2q2p2假設(shè)假設(shè)A產(chǎn)銷平衡產(chǎn)銷平衡假設(shè)假設(shè)Bp隨隨x (兩種牌號(hào)兩種牌號(hào))增加而減小，呈線性關(guān)系增加而減小，呈線性關(guān)系12111211121211111, 0,aaaabxaxabp某廠生產(chǎn)兩個(gè)牌號(hào)的同一種產(chǎn)品，如何確定產(chǎn)量使利潤(rùn)最大某廠生產(chǎn)兩個(gè)牌號(hào)的同一種產(chǎn)品，如何確定產(chǎn)量使利潤(rùn)最大21222221222212122, 0,aaaabxaxabp二次規(guī)劃模型產(chǎn)銷計(jì)劃問題二次規(guī)劃模型產(chǎn)銷計(jì)劃問題22211121,)()(),(max21xqpxqpxxzxx目標(biāo)目標(biāo)利潤(rùn)最大利潤(rùn)最大=（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ī)劃模型二次