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

數(shù)學(xué)規(guī)劃概述第一頁，共九十一頁，編輯于2023年，星期三

假期你想去旅游。假如你只去一個(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è)基本要素：

決策變量（decisionvariables）

約束條件(constraints)

目標(biāo)函數(shù)(objectivefunction)第二頁，共九十一頁，編輯于2023年，星期三決策變量(decisionvariables):它們是決策者所控制的那些數(shù)量，它們?nèi)∈裁磾?shù)值需要決策者來決策，最優(yōu)化問題的求解就是找出決策變量的最優(yōu)取值．約束條件(constraints)：它們是決策變量在現(xiàn)實(shí)世界中所受到的限制，或者說決策變量在這些限制范圍之內(nèi)取值才有實(shí)際意義．目標(biāo)函數(shù)(objectivefunction):它代表決策者希望對其進(jìn)行優(yōu)化的那個(gè)指標(biāo)。目標(biāo)函數(shù)是決策變量的函數(shù)．第三頁，共九十一頁，編輯于2023年，星期三如果一個(gè)最優(yōu)化問題的決策變量不是時(shí)間的函數(shù)，則屬于靜態(tài)優(yōu)化(staticoptimization)或有限維優(yōu)化(finitedimensionaloptimization)的范疇．按照靜態(tài)優(yōu)化問題的結(jié)構(gòu)是否線性分為線性規(guī)劃和非線性規(guī)劃．線性規(guī)劃的特征是目標(biāo)函數(shù)和約束條件中的函數(shù)都是決策變量的線性函數(shù)，并且約束是必不可少的（否則不存在有實(shí)際意義的解）第四頁，共九十一頁，編輯于2023年，星期三三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量數(shù)學(xué)規(guī)劃模型的一般形式規(guī)劃問題：求目標(biāo)函數(shù)在約束條件下的最值可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值)目標(biāo)函數(shù)第五頁，共九十一頁，編輯于2023年，星期三數(shù)學(xué)規(guī)劃模型的簡單分類

線性規(guī)劃(LP)目標(biāo)和約束均為線性函數(shù)

非線性規(guī)劃(NLP)目標(biāo)或約束中存在非線性函數(shù)

二次規(guī)劃(QP)目標(biāo)為二次函數(shù)、約束為線性

整數(shù)規(guī)劃(IP)決策變量(全部或部分)為整數(shù)整數(shù)線性規(guī)劃(ILP)，整數(shù)非線性規(guī)劃(INLP)純整數(shù)規(guī)劃(PIP),混合整數(shù)規(guī)劃(MIP)一般整數(shù)規(guī)劃，0-1（整數(shù)）規(guī)劃連續(xù)優(yōu)化離散優(yōu)化數(shù)學(xué)規(guī)劃第六頁，共九十一頁，編輯于2023年，星期三MATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無約束優(yōu)化非線性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線性方程(組)fzerofsolve全局優(yōu)化暫缺非線性最小二乘lsqnonlinlsqcurvefit線性規(guī)劃linprog純0-1規(guī)劃bintprog一般IP(暫缺)非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprog第七頁，共九十一頁，編輯于2023年，星期三優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃LINDOLINGOLINDO/LINGO軟件能求解的模型第八頁，共九十一頁，編輯于2023年，星期三LPQPNLPIP全局優(yōu)化(選)

ILPIQPINLP

LINGO軟件的求解過程LINGO預(yù)處理程序線性優(yōu)化求解程序非線性優(yōu)化求解程序分枝定界管理程序1.確定常數(shù)2.識別類型1.單純形算法2.內(nèi)點(diǎn)算法(選)1、順序線性規(guī)劃法(SLP)2、廣義既約梯度法(GRG)(選)

3、多點(diǎn)搜索(Multistart)(選)第九頁，共九十一頁，編輯于2023年，星期三LINGO軟件的功能與特點(diǎn)LINGO模型的優(yōu)點(diǎn)集成了線性(非線性)/連續(xù)(整數(shù))優(yōu)化功能具有多點(diǎn)搜索/全局優(yōu)化功能提供了靈活的編程語言(矩陣生成器)，可方便地輸入模型提供與其他數(shù)據(jù)文件的接口提供與其他編程語言的接口LINDOAPI可用于自主開發(fā)運(yùn)行速度較快第十頁，共九十一頁，編輯于2023年，星期三LINDO公司軟件產(chǎn)品簡要介紹

美國芝加哥(Chicago)大學(xué)的LinusSchrage教授于1980年前后開發(fā),后來成立LINDO系統(tǒng)公司（LINDOSystemsInc.），網(wǎng)址：

LINDO:

LinearINteractiveandDiscreteOptimizer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)What’sBest!:(SpreadSheete.g.EXCEL)(V8.0)演示(試用)版、高級版、超級版、工業(yè)版、擴(kuò)展版…（求解問題規(guī)模和選件不同）第十一頁，共九十一頁，編輯于2023年，星期三歷史悠久，理論成熟，應(yīng)用廣泛運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。

線性規(guī)劃模型第十二頁，共九十一頁，編輯于2023年，星期三1939年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ）《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》提出“解乘數(shù)法”。列奧尼德·康托羅維奇，前蘇聯(lián)人，由于在1939年創(chuàng)立了享譽(yù)全球的線性規(guī)劃要點(diǎn)，對資源最優(yōu)分配理論做出了貢獻(xiàn)，而獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。線性規(guī)劃理論的發(fā)展第十三頁，共九十一頁，編輯于2023年，星期三美國科學(xué)院院士DANTZIG（丹齊克），1948年在研究美國空軍資源的優(yōu)化配置時(shí)提出線性規(guī)劃及其通用解法“單純形法”。被稱為線性規(guī)劃之父。

線性規(guī)劃之父的Dantzig(丹齊克)。據(jù)說，一次上課，Dantzig遲到了，仰頭看去，黑板上留了幾個(gè)題目，他就抄了一下，回家后埋頭苦做。幾個(gè)星期之后，疲憊的去找老師說，這件事情真的對不起，作業(yè)好像太難了，我所以現(xiàn)在才交，言下很是慚愧。幾天之后，他的老師就把他召了過去，興奮的告訴他說他太興奮了。Dantzig很不解,后來才知道原來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解決的問題，他給出的那個(gè)解法也就是單純形法。這個(gè)方法是上個(gè)世紀(jì)前十位的算法。第十四頁，共九十一頁，編輯于2023年，星期三

1960年，“最佳資源利用的經(jīng)濟(jì)計(jì)算”康托洛維奇和庫伯曼斯(Koopmans)。兩人因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)

佳林·庫普曼斯，美國人，他將數(shù)理統(tǒng)計(jì)學(xué)成功運(yùn)用于經(jīng)濟(jì)計(jì)量學(xué)，對資源最優(yōu)分配理論做出了貢獻(xiàn)。第十五頁，共九十一頁，編輯于2023年，星期三1961年，查恩斯與庫伯提出了目標(biāo)規(guī)劃，艾吉利提出了用優(yōu)先因子來處理多目標(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ān)的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。保羅-薩繆爾遜（PAULASAMUELSON）,他發(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)。華西里·列昂惕夫（WASSILYLEONTIEF），美國人，他發(fā)展了投入產(chǎn)出方法，該方法在許多重要的經(jīng)濟(jì)問題中得到運(yùn)用。曾獲1973年諾貝爾經(jīng)濟(jì)科學(xué)獎(jiǎng)。肯尼斯-J-阿羅（KENNETHJ.ARROW）,美國人，因與約翰-?？怂梗↗OHNR.HICKS）共同深入研究了經(jīng)濟(jì)均衡理論和福利理論獲得1972年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。牟頓-米勒（MERTONM.MILLER）,1923-2000,美國人,由于他在金融經(jīng)濟(jì)學(xué)方面做出了開創(chuàng)性工作，于1990年獲得諾貝爾經(jīng)濟(jì)獎(jiǎng)。第十六頁，共九十一頁，編輯于2023年，星期三一個(gè)農(nóng)場有50畝土地,20個(gè)勞動(dòng)力,計(jì)劃種蔬菜,棉花和水稻.種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力1/21/31/4,預(yù)計(jì)每畝產(chǎn)值分別為110元,75元,60元.如何規(guī)劃經(jīng)營使經(jīng)濟(jì)效益最大.種植蔬菜x1畝,棉花x2畝,水稻x3畝(決策變量)以取得最高的產(chǎn)值的方式達(dá)到收益最大的目標(biāo).求f=110x1+75x2+60x3的最大值(目標(biāo)函數(shù)、優(yōu)劣標(biāo)準(zhǔn))約束條件

x1+x2+x3

501/2x1+1/3x2+1/4x320

例1農(nóng)作物種植

max:Z=110x1+75x2+60x3s.t.x1+x2+x3

501/2x1+1/3x2+1/4x320

x1，x2，x3≥0目標(biāo)函數(shù)和約束條件是線性的，是線性規(guī)劃第十七頁，共九十一頁，編輯于2023年，星期三如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。實(shí)際問題中線性的含義：一是嚴(yán)格的比例性二是可疊加性關(guān)于線性的界定第十八頁，共九十一頁，編輯于2023年，星期三比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比；可加性：每個(gè)決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌兞浚贿B續(xù)性：每個(gè)決策變量取連續(xù)值；確定性：線性規(guī)劃中的參數(shù)aij,bi,ci為確定值。第十九頁，共九十一頁，編輯于2023年，星期三

正則模型

決策變量:x1,x2,…,xn.目標(biāo)函數(shù):Z=c1x1+c2x2+…+cnxn.求目標(biāo)函數(shù)的最小或最大約束條件:a11x1+…+a1nxn≤b1,

…

…am1x1+…+amnxn≤bm線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)化第二十頁，共九十一頁，編輯于2023年，星期三

標(biāo)準(zhǔn)化模型

決策變量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,

……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,第二十一頁，共九十一頁，編輯于2023年，星期三

模型的標(biāo)準(zhǔn)化

10.引入松弛變量將不等式約束變?yōu)榈仁郊s束若有ai1x1+…+ainxn≤bi,則引入xn+i≥0,使得ai1x1+…+ainxn+xn+i=bi

若有aj1x1+…+ajnxn≥bj,則引入xn+j≥0,使得aj1x1+…+ajnxn-xn+j=bj.

且此時(shí)目標(biāo)函數(shù)Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.20.將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化.若求minZ,令Z’=–Z,則問題變?yōu)閙axZ’.30.引入人工變量,使得所有變量均為非負(fù).若xi沒有非負(fù)的條件,則引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,則可使得問題的全部變量均非負(fù).

第二十二頁，共九十一頁，編輯于2023年，星期三線性規(guī)劃的對偶性和影子價(jià)格農(nóng)作物種植（續(xù)）：一個(gè)農(nóng)場有50畝土地,20個(gè)勞動(dòng)力,計(jì)劃種蔬菜,棉花和水稻.種植這三種農(nóng)作物每畝地分別需要?jiǎng)趧?dòng)力1/21/31/4,預(yù)計(jì)每畝產(chǎn)值分別為110元,75元,60元.如果出租土地和勞動(dòng)力如何規(guī)劃經(jīng)營使經(jīng)濟(jì)效益最大.決策變量:對單位土地和單位勞力出租價(jià)格分別為y1y2目標(biāo)函數(shù):g=50y1+20y2優(yōu)劣準(zhǔn)則:應(yīng)求g的最小值.

(因?yàn)橐_(dá)到的要求已經(jīng)通過約束條件滿足，決策者關(guān)心的是在最低要求達(dá)到時(shí)出租價(jià)格的心理底線是多少？)約束條件:y1+1/2y2

110y1+1/3y2

75y1+1/4y2

60(成本不小于產(chǎn)值)（我出租出去要比自己種植合適。出租底線）第二十三頁，共九十一頁，編輯于2023年，星期三對偶線性規(guī)劃

原問題maxf=cTxs.t.Ax

b

xi0,i=1,2,,n.對偶問題minf=bTys.t.ATy

cyi0,i=1,2,,m.

max:Z=110x1+75x2+60x3s.t.x1+x2+x3

501/2x1+1/3x2+1/4x320

x1，x2，x3≥0

A是mn矩陣，

c是n1向量，b是m1向量

x是n1向量,y是m1向量min：g=50y1+20y2s.t.y1+1/2y2

110y1+1/3y2

75y1+1/4y2

60

y1，y2≥0第二十四頁，共九十一頁，編輯于2023年，星期三對偶定理:互為對偶的兩個(gè)線性規(guī)劃問題

若其中一個(gè)有有窮的最優(yōu)解,則另一個(gè)也有有窮的最優(yōu)解,且最優(yōu)值相等.若兩者之一有無界的最優(yōu)解,則另一個(gè)沒有可行解。模型II給出了生產(chǎn)中資源的最低估價(jià).這種價(jià)格涉及到資源的有效利用,它不是市場價(jià)格,而是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)確定的估價(jià),被稱為“影子價(jià)格”。

模型I給出了生產(chǎn)中的資源最優(yōu)分配方案。第二十五頁，共九十一頁，編輯于2023年，星期三

靈敏度分析主要包括下面幾個(gè)內(nèi)容：1：當(dāng)約束條件的右邊常數(shù)項(xiàng)變化的影響；2：約束條件的系數(shù)變化的影響；3：目標(biāo)函數(shù)的系數(shù)變化的影響。

可能的影響結(jié)果：1：最優(yōu)解保持不變；2：基變量保持不變，但值變了；3：基本解變化。線性規(guī)劃的靈敏度分析第二十六頁，共九十一頁，編輯于2023年，星期三例：簡單的線性規(guī)劃（LP）問題在空白的模型窗口中輸入這個(gè)LP模型：max2x+3yst4x+3y<=103x+5y<12end附錄1：用Lindo(Lingo)解線性規(guī)劃第二十七頁，共九十一頁，編輯于2023年，星期三如圖：第二十八頁，共九十一頁，編輯于2023年，星期三模型求解用鼠標(biāo)點(diǎn)擊工具欄中的圖標(biāo)，或從菜單中選擇Solve|Solve（Ctrl+S）命令LINDO首先開始編譯這個(gè)模型，編譯沒有錯(cuò)誤則開始求解；求解時(shí)會(huì)首先顯示如右圖所示的LINDO

“求解器運(yùn)行狀態(tài)窗口”。第二十九頁，共九十一頁，編輯于2023年，星期三名稱含義Status（當(dāng)前狀態(tài)）顯示當(dāng)前求解狀態(tài)：“Optimal”表示已經(jīng)達(dá)到最優(yōu)解；其他可能的顯示還有三個(gè)：Feasible(可行解),Infeasible(不可行),Unbounded(最優(yōu)值無界)。Iterations（迭代次數(shù)）顯示迭代次數(shù)：“2”表示經(jīng)過了2次迭代。

Infeasibility（不可行性）約束不滿足的量(即各個(gè)約束條件不滿足的“數(shù)量”的和；特別注意不是“不滿足的約束個(gè)數(shù)”)：“0”表示這個(gè)解是可行的。Objective（當(dāng)前的目標(biāo)值）顯示目標(biāo)函數(shù)當(dāng)前的值：7.45455。BestIP（整數(shù)規(guī)劃當(dāng)前的最佳目標(biāo)值）顯示整數(shù)規(guī)劃當(dāng)前的最佳目標(biāo)值：“N/A”

（NoAnswer或NotApplicable）表示無答案或無意義，因?yàn)檫@個(gè)模型中沒有整數(shù)變量，不是整數(shù)規(guī)劃（IP）。

求解器運(yùn)行狀態(tài)窗口顯示的相應(yīng)信息及含義第三十頁，共九十一頁，編輯于2023年，星期三名稱含義IPBound（整數(shù)規(guī)劃的界）顯示整數(shù)規(guī)劃的界（對最大化問題顯示上界；對最小化問題，顯示下界）：“N/A”含義同上。

Branches（分枝數(shù)）顯示分枝定界算法已經(jīng)計(jì)算的分枝數(shù)：

“N/A”含義同上。ElapsedTime（所用時(shí)間）顯示計(jì)算所用時(shí)間（秒）：“0.00”說明計(jì)算太快了，用時(shí)還不到0.005秒。UpdateInterval（刷新本界面的時(shí)間間隔）顯示和控制刷新本界面的時(shí)間間隔：“1”表示1秒；用戶可以直接在界面上修改這個(gè)時(shí)間間隔。InterruptSolver（中斷求解程序）當(dāng)模型規(guī)模比較大時(shí)（尤其對整數(shù)規(guī)劃），可能求解時(shí)間會(huì)很長，如果不想再等待下去時(shí)，可以在程序運(yùn)行過程中用鼠標(biāo)點(diǎn)擊該按鈕終止計(jì)算。求解結(jié)束后這個(gè)按鈕變成了灰色，再點(diǎn)擊就不起作用了。Close（關(guān)閉）該按鈕只是關(guān)閉狀態(tài)窗口，并不終止計(jì)算。如果你關(guān)閉了狀態(tài)窗口，將來隨時(shí)可以選擇WINDOW|OPENSTATUSWINDOW菜單命令來再次打開這個(gè)窗口。第三十一頁，共九十一頁，編輯于2023年，星期三緊接著彈出一對話框，詢問你是否需要做靈敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先選擇“否（N）”按鈕，這個(gè)窗口就會(huì)關(guān)閉。然后，再把狀態(tài)窗口也關(guān)閉。第三十二頁，共九十一頁，編輯于2023年，星期三報(bào)告窗口

用鼠標(biāo)選擇“Window|ReportsWindow”（報(bào)告窗口），就可以查看該窗口的內(nèi)容第三十三頁，共九十一頁，編輯于2023年，星期三保存文件選擇File|Save（F5）命令把“結(jié)果報(bào)告”保存在一個(gè)文件中（缺省的后綴名為LTX,即LINDO文本文件）類似地，回到模型窗口，可以把輸入的模型保存在一個(gè)文件中。保存的文件將來可以用File|Open（F3）和File|View（F4）重新打開，用前者打開的程序可以進(jìn)行修改，而后者只能瀏覽。如果模型有錯(cuò)誤,運(yùn)行時(shí)會(huì)彈出出錯(cuò)信息報(bào)告窗口(LINDOErrorMessage)，則需要修改模型。第三十四頁，共九十一頁，編輯于2023年，星期三例：某家具公司制造書桌、餐桌和椅子，所用的資源有三種：木料、木工和漆工。生產(chǎn)數(shù)據(jù)如下表所示。每個(gè)書桌每個(gè)餐桌每個(gè)椅子現(xiàn)有資源總數(shù)木料8單位6單位1單位48單位漆工4單位2單位1.5單位20單位木工2單位1.5單位0.5單位8單位成品單價(jià)60單位30單位20單位若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大？第三十五頁，共九十一頁，編輯于2023年，星期三解：用DESKS、TABLES和CHAIRS分別表示三種產(chǎn)品的生產(chǎn)量（決策變量），容易建立LP模型。在LINDO模型窗口中輸入模型：MAX60DESKS+30TABLES+20CHAIRSSUBJECTTO2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)DESKS+15TABLES+O5CHAIRS<=85)TABLES<=5END解這個(gè)模型，并對彈出的對話框

“DORANGE(SENSITIVITY)ANALYSIS?”

選擇“是（Y）”按鈕，這表示你需要做靈敏性分析。然后，查看輸出結(jié)果。第三十六頁，共九十一頁，編輯于2023年，星期三LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)280.0000VARIABLEVALUEREDUCEDCOSTDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)24.0000000.0000003)0.00000010.0000004)0.00000010.0000005)5.0000000.000000NO.ITERATIONS=1輸出結(jié)果的前半部分：第三十七頁，共九十一頁，編輯于2023年，星期三前半部分的輸出結(jié)果的解釋:“LPOPTIMUMFOUNDATSTEP2”

表示兩次迭代（旋轉(zhuǎn)變換）后得到最優(yōu)解?！癘BJECTIVEFUNCTIONVALUE1）280.000000”

表示最優(yōu)目標(biāo)值為280。

“VALUE”

給出最優(yōu)解中各變量的值：造2個(gè)書桌（desks）,0個(gè)餐桌（tables）,8個(gè)椅子（chairs）。所以desks、chairs是基變量（取值非0），tables是非基變量（取值為0）?！癝LACKORSURPLUS”

給出松馳變量的值。（在最優(yōu)的情況下資源的剩余量）第2行松馳變量=24（第1行表示目標(biāo)函數(shù)，第2行對應(yīng)第1個(gè)約束）第3行松馳變量=0第4行松馳變量=0第5行松馳變量=5第三十八頁，共九十一頁，編輯于2023年，星期三“REDUCEDCOST”

列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù)，表示當(dāng)變量有微小變動(dòng)時(shí),目標(biāo)函數(shù)的變化率.其中基變量的reducedcost值應(yīng)為0;非基變量Xj，相應(yīng)的reducedcost值1）表示當(dāng)非基變量Xj增加一個(gè)單位時(shí)，目標(biāo)函數(shù)相應(yīng)減少的量(max型問題)。2）理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中該變量前對應(yīng)系數(shù)應(yīng)增加的量。本例中：變量TABLES對應(yīng)的reducedcost值為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元偏低，不值得生產(chǎn)，如果生產(chǎn)的話至少35元。第三十九頁，共九十一頁，編輯于2023年，星期三“DUALPRICE”（對偶價(jià)格）表示當(dāng)對應(yīng)約束有微小變動(dòng)時(shí),目標(biāo)函數(shù)的變化率.輸出結(jié)果中對應(yīng)于每一個(gè)約束有一個(gè)對偶價(jià)格.若其數(shù)值為p,表示對應(yīng)約束中不等式右端項(xiàng)若增加1個(gè)單位,目標(biāo)函數(shù)將增加p個(gè)單位（max型問題)。也就是相應(yīng)的一個(gè)單位的該資源在生產(chǎn)過程中產(chǎn)生的效益，即其價(jià)值。1）如果在最優(yōu)解處約束正好取等號（也就是“緊約束”現(xiàn)有相應(yīng)資源全部使用），該資源的對偶價(jià)格才可能不是0。例如本例中：第3行是緊約束，對應(yīng)的是資源是漆工，其對偶價(jià)格值為10，表示當(dāng)緊約束4DESKS+2TABLES+1.5CHAIRS<=20變?yōu)?DESKS+2TABLES+1.5CHAIRS<=21時(shí)，目標(biāo)函數(shù)值是280+10=290。即若再增加一名漆工的話，可增加10的利潤。2）對于非緊約束（如本例中第2行木料是非緊約束），DUALPRICE的值為0,表示對應(yīng)約束中不等式右端項(xiàng)的微小擾動(dòng)不影響目標(biāo)函數(shù)。因?yàn)樽顑?yōu)的時(shí)候還有剩余。第四十頁，共九十一頁，編輯于2023年，星期三輸出結(jié)果的后半部分：RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEDESKS60.00000020.0000004.000000TABLES30.0000005.000000INFINITYCHAIRS20.0000002.5000005.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE248.000000INFINITY24.000000320.0000004.0000004.00000048.0000002.0000001.33333355.000000INFINITY5.000000（報(bào)告中INFINITY表示正無窮）第四十一頁，共九十一頁，編輯于2023年，星期三1.目標(biāo)函數(shù)中系數(shù)變化的范圍（OBJCOEFFICIENTRANGES）如本例中：目標(biāo)函數(shù)中DESKS變量當(dāng)前的系數(shù)(CURRENTCOEF)=60，允許增加(AllowableIncrease)=4、允許減少(AllowableDecrease)=2，說明當(dāng)這個(gè)系數(shù)在[60-4，60+20]=[56，80]范圍變化時(shí)，最優(yōu)基保持不變。對TABLES、CHAIRS變量，可以類似解釋。由于此時(shí)約束沒有變化（只是目標(biāo)函數(shù)中某個(gè)系數(shù)發(fā)生變化），所以最優(yōu)基保持不變的意思也就是最優(yōu)解不變（當(dāng)然，由于目標(biāo)函數(shù)中系數(shù)發(fā)生了變化，所以最優(yōu)值會(huì)變化）。

這個(gè)部分包括兩方面的敏感性分析內(nèi)容：第四十二頁，共九十一頁，編輯于2023年，星期三2.約束右端項(xiàng)變化的范圍（RightHandSideRANGES）如本例中：第2行約束中當(dāng)前右端項(xiàng)(CURRENTRHS）=48，允許增加（AllowableIncrease）=INFINITY（無窮）、允許減少（AllowableDecrease）=24，說明當(dāng)它在[48-24，48+)=[24，）范圍變化時(shí)，最優(yōu)基保持不變。第3、4、5行可以類似解釋。不過由于此時(shí)約束發(fā)生變化，最優(yōu)基即使不變，最優(yōu)解、最優(yōu)值也會(huì)發(fā)生變化。第四十三頁，共九十一頁，編輯于2023年，星期三1.變量名由字母和數(shù)字組成，但必須以字母開頭，且長度不能超過8個(gè)字符，不區(qū)分大小寫字母，包括關(guān)鍵字（如MAX、MIN等）也不區(qū)分大小寫字母。2.對目標(biāo)函數(shù)和約束用行號（行名）進(jìn)行標(biāo)識，這些標(biāo)識會(huì)在將來的求解結(jié)果報(bào)告中用到。行名可以和變量名一樣命名，也可以只用數(shù)字命名，還可以含有中文字符，但長度同樣不能超過8個(gè)字符。為了方便將來閱讀求解結(jié)果報(bào)告，建議用戶總是自覺地對每個(gè)約束進(jìn)行命名。行名結(jié)束標(biāo)志符號、即右括號“）”必須是英文字符，否則會(huì)出現(xiàn)錯(cuò)誤。LINDO模型的一些注意事項(xiàng)第四十四頁，共九十一頁，編輯于2023年，星期三3.可以用“TITLE”語句對輸入的模型命名，用法是在TITLE后面寫出其名字（最多72個(gè)字符，可以有漢字），在程序中單獨(dú)占一行，可以在模型的任何地方。模型命名的第一個(gè)作用類似于對模型的注釋和說明。模型命名的另一個(gè)目的，是為了方便將來閱讀求解結(jié)果報(bào)告。因?yàn)橛脩粲锌赡芡瑫r(shí)處理多個(gè)模型，很容易混淆模型與求解結(jié)果的對應(yīng)關(guān)系。這時(shí)如果對不同模型分別進(jìn)行了命名，就可以隨時(shí)（例如在求解當(dāng)前模型前）使用菜單命令“FILE|TITLE”將當(dāng)前模型的名字顯示在求解結(jié)果報(bào)告窗口中，這樣就容易判別每個(gè)求解結(jié)果與每個(gè)模型的對應(yīng)關(guān)系。4.模型中以感嘆號“!”開頭的是注釋行（注釋語句，或稱為說明語句），可以幫助他人或以后自己理解這個(gè)模型。實(shí)際上，每行中“!”符號后面的都是注釋或說明。注釋語句中可以使用漢字字符。第四十五頁，共九十一頁，編輯于2023年，星期三5.變量不能出現(xiàn)在一個(gè)約束條件的右端（即約束條件的右端只能是常數(shù)）；變量與其系數(shù)間可以有空格（甚至回車），但不能有任何運(yùn)算符號（包括乘號“*”等）。6.模型中不接受括號“()”和逗號“,”等符號（除非在注釋語句中）。例如:4(X1+X2)需寫為4X1+4X2；“10,000”需寫為10000。7.表達(dá)式應(yīng)當(dāng)已經(jīng)經(jīng)過化簡。如不能出現(xiàn)2X1+3X2-4X1，而應(yīng)寫成-2X1+3X2等。8.LINDO中已假定所有變量非負(fù)。若要取消變量的非負(fù)假定，可在模型的“END”語句后面用命令“FREE”。例如，在“END”語句后輸入FREEvname，可將變量vname的非負(fù)假定取消。第四十六頁，共九十一頁，編輯于2023年，星期三9.可以在模型的“END”語句后面用命令“SUB”（即設(shè)置上界（SETUPPERBOUND）的英文縮寫）設(shè)定變量的上界，用命令“SLB”（即設(shè)置下界（SETLOWERBOUND）的英文縮寫）設(shè)定變量的上下界。其用法是：“SUBvnamevalue”將變量vname的上限設(shè)定為value；“SLB”的用法類似。用“SUB”和“SLB”表示的上下界約束不計(jì)入模型的約束，因此LINDO也不能給出其松緊判斷和敏感性分析。10.數(shù)值均衡化考慮：如果約束系數(shù)矩陣中各非零元的絕對值的數(shù)量級差別很大（相差1000倍以上），則稱其為數(shù)值不均衡的。為了避免數(shù)值不均衡引起的計(jì)算問題,使用者應(yīng)盡可能自己對矩陣的行列進(jìn)行均衡化。此時(shí)還有一個(gè)原則,即系數(shù)中非零元的絕對值不能大于100000或者小于.0001。LINDO不能對LP中的系數(shù)自動(dòng)進(jìn)行數(shù)值均衡化，但如果LINDO覺得矩陣元素之間很不均衡,將會(huì)給出警告。第四十七頁，共九十一頁，編輯于2023年，星期三11.簡單錯(cuò)誤的檢查和避免：輸入模型時(shí)可能會(huì)有某些輸入錯(cuò)誤.當(dāng)問題規(guī)模較大時(shí),要查找錯(cuò)誤是比較困難的。在LINDO中有一些可幫助尋找錯(cuò)誤的功能，其中之一就是菜單命令“Report|Picture（Alt+5）”,它的功能是可以將目標(biāo)函數(shù)和約束表達(dá)式中的非零系數(shù)通過列表（或圖形）顯示出來。第四十八頁，共九十一頁，編輯于2023年，星期三附錄2：用MATLAB優(yōu)化工具箱解線性規(guī)劃minz=cX

1.模型：命令：x=linprog（c,A,b）

2.模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若沒有不等式，則令A(yù)=[]，b=[].第四十九頁，共九十一頁，編輯于2023年，星期三3.模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]

x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若沒有等式約束:,則令 Aeq=[],beq=[].[2]其中X0表示初始點(diǎn)4.命令：[x,fval]=linprog(…)返回最優(yōu)解ｘ及ｘ處的目標(biāo)函數(shù)值fval.第五十頁，共九十一頁，編輯于2023年，星期三問題一:任務(wù)分配問題：某車間有甲、乙兩臺(tái)機(jī)床，可用于加工三種工件.假定這兩臺(tái)車床的可用臺(tái)時(shí)數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種不同車床加工單位數(shù)量不同工件所需的臺(tái)時(shí)數(shù)和加工費(fèi)用如下表.問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費(fèi)用最低？第五十一頁，共九十一頁，編輯于2023年，星期三解設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,可建立以下線性規(guī)劃模型：第五十二頁，共九十一頁，編輯于2023年，星期三s.t.改寫為：第五十三頁，共九十一頁，編輯于2023年，星期三編寫M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)第五十四頁，共九十一頁，編輯于2023年，星期三結(jié)果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲機(jī)床上加工600個(gè)工件2,在乙機(jī)床上加工400個(gè)工件1、500個(gè)工件3，可在滿足條件的情況下使總加工費(fèi)最小為13800.第五十五頁，共九十一頁，編輯于2023年，星期三問題二：某廠每日8小時(shí)的產(chǎn)量不低于1800件.為了進(jìn)行質(zhì)量控制，計(jì)劃聘請兩種不同水平的檢驗(yàn)員.一級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度25件/小時(shí)，正確率98%，計(jì)時(shí)工資4元/小時(shí)；二級檢驗(yàn)員的標(biāo)準(zhǔn)為：速度15件/小時(shí)，正確率95%，計(jì)時(shí)工資3元/小時(shí).檢驗(yàn)員每錯(cuò)檢一次，工廠要損失2元.為使總檢驗(yàn)費(fèi)用最省，該工廠應(yīng)聘一級、二級檢驗(yàn)員各幾名？解設(shè)需要一級和二級檢驗(yàn)員的人數(shù)分別為x1、x2人,則應(yīng)付檢驗(yàn)員的工資為：因檢驗(yàn)員錯(cuò)檢而造成的損失為：第五十六頁，共九十一頁，編輯于2023年，星期三故目標(biāo)函數(shù)為：約束條件為：第五十七頁，共九十一頁，編輯于2023年，星期三線性規(guī)劃模型：改寫為：第五十八頁，共九十一頁，編輯于2023年，星期三編寫M文件xxgh4.m如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%調(diào)用linprog函數(shù)：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)第五十九頁，共九十一頁，編輯于2023年，星期三結(jié)果為：x=9.00000.0000fval=360即只需聘用9個(gè)一級檢驗(yàn)員.

注：本問題應(yīng)還有一個(gè)約束條件：x1、x2取整數(shù).故它是一個(gè)整數(shù)線性規(guī)劃問題.這里把它當(dāng)成一個(gè)線性規(guī)劃來解，求得其最優(yōu)解剛好是整數(shù)：x1=9，x2=0，故它就是該整數(shù)規(guī)劃的最優(yōu)解.若用線性規(guī)劃解法求得的最優(yōu)解不是整數(shù)，將其取整后不一定是相應(yīng)整數(shù)規(guī)劃的最優(yōu)解，這樣的整數(shù)規(guī)劃應(yīng)用專門的方法求解.第六十頁，共九十一頁，編輯于2023年，星期三整數(shù)規(guī)劃、0-1規(guī)劃如果要求決策變量取整數(shù),或部分取整數(shù)的數(shù)學(xué)規(guī)劃問題,稱為整數(shù)規(guī)劃.如果要求決策變量只取0或1的線性規(guī)劃問題,稱為0-1規(guī)劃.0-1約束不一定是由變量的性質(zhì)決定的,更多地是由于邏輯關(guān)系引進(jìn)問題的.整數(shù)規(guī)劃、0－1規(guī)劃模型第六十一頁，共九十一頁，編輯于2023年，星期三整數(shù)規(guī)劃問題一般形式整數(shù)線性規(guī)劃(ILP)目標(biāo)和約束均為線性函數(shù)整數(shù)非線性規(guī)劃(NLP)目標(biāo)或約束中存在非線性函數(shù)整數(shù)規(guī)劃問題的分類純(全)整數(shù)規(guī)劃(PIP)決策變量均為整數(shù)混合整數(shù)規(guī)劃(MIP)

決策變量有整數(shù)，也有實(shí)數(shù)0-1規(guī)劃決策變量只取0或1第六十二頁，共九十一頁，編輯于2023年，星期三取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對應(yīng)的連續(xù)優(yōu)化問題稱為原問題的松弛問題整數(shù)規(guī)劃問題對應(yīng)的松弛問題松弛問題松弛整數(shù)規(guī)劃問題最優(yōu)解最優(yōu)解整數(shù)非整數(shù)整數(shù)舍入下界（對Min問題）上界（對Max問題）非最優(yōu)解第六十三頁，共九十一頁，編輯于2023年，星期三用連續(xù)優(yōu)化方法求解松弛問題，如果松弛問題最優(yōu)解（分量）全為整數(shù)，則也是原整數(shù)規(guī)劃問題的最優(yōu)解（見例1）對松弛問題的最優(yōu)解（分量）舍入為整數(shù)，得到的往往不是原整數(shù)規(guī)劃問題的最優(yōu)解（甚至不是可行解）第六十四頁，共九十一頁，編輯于2023年，星期三．．．．．．．．．．．．．．．．．．．x1x20Po69Zmax56去掉整數(shù)限制后，可行域?yàn)辄c(diǎn)（0,0),(6,0),(0,5),P(2.25,3.75)圍成的4邊形從LP最優(yōu)解經(jīng)過簡單的“移動(dòng)”不一定能得到IP最優(yōu)解例第六十五頁，共九十一頁，編輯于2023年，星期三LINDO可用于求解線性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃(IP)，模型的輸入與LP問題類似,但需在END標(biāo)志后定義整型變量。0/1型的變量可由INTEGER（可簡寫為INT）命令來標(biāo)識，有以下兩種可能的用法：

INTvname

INTn前者只將決策變量vname標(biāo)識為0/1型,后者將當(dāng)前模型中前n個(gè)變量標(biāo)識為0/1型（模型中變量順序由模型中輸入時(shí)出現(xiàn)的先后順序決定,該順序可由輸出結(jié)果中的變量順序查證是否一致）。一般的整數(shù)變量可用命令GIN（是GENERALINTEGER的意思）,其使用方式及格式與INT命令相似。LINDO求解整數(shù)線性規(guī)劃概述第六十六頁，共九十一頁，編輯于2023年，星期三純整數(shù)規(guī)劃-聘用方案決策變量：周一至周日每天(新)聘用人數(shù)x1,x2,x7目標(biāo)函數(shù)：7天(新)聘用人數(shù)之和約束條件：周一至周日每天需要人數(shù)第六十七頁，共九十一頁，編輯于2023年，星期三連續(xù)工作5天周一工作的應(yīng)是(上)周四至周一聘用的設(shè)系統(tǒng)已進(jìn)入穩(wěn)態(tài)（不是開始的幾周）聘用方案整數(shù)規(guī)劃模型(IP)第六十八頁，共九十一頁，編輯于2023年，星期三首先在LINDO模型窗口輸入模型:MINX1+X2+X3+X4+X5+X6+X7SUBJECTTOMON)X1+X4+X5+X6+X7>=50TUE)X1+X2+X5+X6+X7>=50WED)X1+X2+X3+X6+X7>=50THU)X1+X2+X3+X4+X7>=50FRI)X1+X2+X3+X4-X5>=80SAT)X2+X3+X4-X5+X6>=90SUN)X3+X4-X5+X6+X7>=90ENDGIN7其中“GIN7”表示7個(gè)變量都是一般整數(shù)變量。

（仍然默認(rèn)為取值是非負(fù)的）第六十九頁，共九十一頁，編輯于2023年，星期三求解后狀態(tài)窗口中與整數(shù)相關(guān)的三個(gè)域有了相關(guān)結(jié)果:“BestIP：94”表示當(dāng)前得到的最好的整數(shù)解的目標(biāo)函數(shù)值為94（人）?！癐PBound：93.5”表示該整數(shù)規(guī)劃目標(biāo)值的下界為93.5（人）?！癇ranches：1”表示分枝數(shù)為1（即在第1個(gè)分枝中就找到了最優(yōu)解）。我們前面說過，LINDO求解IP用的是分枝定界法。顯然，上面第二條“整數(shù)規(guī)劃目標(biāo)值的下界為93.5（人）”表明至少要聘用93.5名員工，由于員工人數(shù)只能是整數(shù)，所以至少要聘用94（人）。而第一條說明目前得到的解就是聘用94（人），所以已經(jīng)是最優(yōu)的了。第七十頁，共九十一頁，編輯于2023年，星期三LPOPTIMUMFOUNDATSTEP8OBJECTIVEVALUE=93.3333359SETX2TO>=4AT1,BND=-94.00TWIN=-93.5018

NEWINTEGERSOLUTIONOF94.0000000ATBRANCH1PIVOT18BOUNDONOPTIMUM:93.50000DELETEX2ATLEVEL1ENUMERATIONCOMPLETE.BRANCHES=1PIVOTS=18LASTINTEGERSOLUTIONISTHEBESTFOUNDRE-INSTALLINGBESTSOLUTION...

求解結(jié)果的報(bào)告窗口如下：（接下頁）第七十一頁，共九十一頁，編輯于2023年，星期三OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X24.0000001.000000X340.0000001.000000X42.0000001.000000X534.0000001.000000X610.0000001.000000X74.0000001.000000ROWSLACKORSURPLUSDUALPRICESMON)0.0000000.000000TUE)2.0000000.000000WED)8.0000000.000000THU)0.0000000.000000FRI)0.0000000.000000SAT)0.0000000.000000SUN)0.0000000.000000NO.ITERATIONS=18BRANCHES=1DETERM.=1.000E0第七十二頁，共九十一頁，編輯于2023年，星期三報(bào)告窗口中前兩行告訴我們：在8次迭代后找到對應(yīng)的線性規(guī)劃（LP）問題的最優(yōu)解，最優(yōu)值=93.3333359。LINDO求解IP用的是分枝定界法，緊接著幾行顯示的是分枝定界的信息，在第1個(gè)分枝中設(shè)定x2>=4,并在該分枝中找到了整數(shù)解，而且就是全局整數(shù)最優(yōu)解，所以算法停止。旋轉(zhuǎn)迭代（PIVOT）共18次。后面顯示的是最后的最優(yōu)解：x=(0,4,40,2,34,10,4).松弛和剩余變量（SLACKORSURPLUS）仍然可以表示約束的松緊程度，但目前IP尚無相應(yīng)完善的敏感性分析理論，因此REDUCEDCOST和DUALPRICES的結(jié)果在整數(shù)規(guī)劃中意義不大。第七十三頁，共九十一頁，編輯于2023年，星期三

聘用方案（續(xù)）郵局一周中每天需要不同數(shù)目的雇員，設(shè)周一至少需要a1人，周二至少需要a2人，周三至少需要a3人，等等。又規(guī)定應(yīng)聘者需連續(xù)工作5天，問郵局每天聘多少雇員才能既滿足需求，又使聘用總?cè)藬?shù)最少。進(jìn)一步考慮，上述指全時(shí)雇員（每天工作8小時(shí)）。如果郵局也可聘用半天雇員（每天工作4小時(shí)，連續(xù)工作5天），設(shè)全時(shí)和半時(shí)雇員的工資每小時(shí)為3元和2元，并且限制半時(shí)雇員的工作量不應(yīng)超過總工作量的四分之一，問郵局如何安排聘用方案，使所付工資總額最少？第七十四頁，共九十一頁，編輯于2023年，星期三分析此時(shí)決策變量由兩部分構(gòu)成：全時(shí)雇員x1,x2,x3,x4,x5,x6,x7;半時(shí)雇員y1,y2,y3,y4,y5,y6,y7.目標(biāo)值應(yīng)該是雇員的總工資，標(biāo)準(zhǔn)是最少：min:Z=3×8×5×∑xi＋2×4×5×∑yi約束條件：每天的工作量應(yīng)該折合為小時(shí)工作量(以周一的工作量為例)8×(x4＋x5＋x6＋x7＋x1)＋4×(y4＋y5＋y6＋y7＋y1)>=8a1半時(shí)雇員的限制4×5×∑yi=<0.25×8(∑ai)第七十五頁，共九十一頁，編輯于2023年，星期三一個(gè)旅行者的背包最多只能裝6kg物品.現(xiàn)有4件物品重量為2kg,3kg,3kg,4kg,價(jià)值為1元,1.2元,0.9元,1.1元.應(yīng)攜帶那些物品使得攜帶物品的價(jià)值最大?0-1規(guī)劃－背包問題決策變量：xj旅行者是否攜帶第j件物品,xj={0,1}.約束條件2x1+3x2+3x3+4x4

6目標(biāo)函數(shù)f=x1+1.2x2+0.9x3+1.1x4優(yōu)劣標(biāo)準(zhǔn)：最大.第七十六頁，共九十一頁，編輯于2023年，星期三用Lingo軟件求解0-1規(guī)劃LinearInteractiveandGeneralOptimizerModel: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第七十七頁，共九十一頁，編輯于2023年，星期三工廠可用k種不同的工藝生產(chǎn)n種產(chǎn)品，每種產(chǎn)品的利潤已知。在各種工藝條件下每種產(chǎn)品所消耗的資源是確定的，并且，工廠的總資源有一定限制。問應(yīng)選擇哪種工藝，每種產(chǎn)品各生產(chǎn)多少，使總利潤最大混合0-1規(guī)劃－生產(chǎn)工藝問題第七十八頁，共九十一頁，編輯于2023年，星期三分析有關(guān)參量：用A1,A2,···,Ak表示k種工藝；用B1,B2,···,Bn表示n種產(chǎn)品；單件Bi的利潤pi；在工藝Aj下,資源限制Qj，單件Bi的資源消耗cij。決策變量：一是Bi的產(chǎn)量xi；一是工藝的選擇。目標(biāo)函數(shù):max:Z＝p1*x1+p2*x2+······+pn*xn資源限制約束：∑cij*xi=<Qj