線性、整數(shù)規(guī)劃模型

優(yōu)化建模與計(jì)算

參考書(shū)《優(yōu)化建模與LINDO/LINGO軟件》謝金星,薛毅編著,

清華大學(xué)出版社,2005年7月第1版./~jxie/lindo內(nèi)容提要1.優(yōu)化模型的基本概念2.優(yōu)化問(wèn)題的建模實(shí)例3.LINDO/LINGO軟件簡(jiǎn)介1.優(yōu)化模型的基本概念

最優(yōu)化是工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究、社會(huì)生活中經(jīng)常遇到的問(wèn)題,如:優(yōu)化模型和算法的重要意義結(jié)構(gòu)設(shè)計(jì)資源分配生產(chǎn)計(jì)劃運(yùn)輸方案解決優(yōu)化問(wèn)題的手段

經(jīng)驗(yàn)積累，主觀判斷

作試驗(yàn)，比優(yōu)劣

建立數(shù)學(xué)模型，求解最優(yōu)策略最優(yōu)化:在一定條件下，尋求使目標(biāo)最大(小)的決策

優(yōu)化問(wèn)題三要素：決策變量；目標(biāo)函數(shù)；約束條件約束條件決策變量?jī)?yōu)化問(wèn)題的一般形式

無(wú)約束優(yōu)化(沒(méi)有約束)與約束優(yōu)化(有約束)

可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值)目標(biāo)函數(shù)局部最優(yōu)解與整體最優(yōu)解

局部最優(yōu)解(LocalOptimalSolution,如x1)

整體最優(yōu)解(GlobalOptimalSolution,如x2)x*f(x)x1x2o優(yōu)化模型的簡(jiǎn)單分類

線性規(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ī)劃優(yōu)化模型的簡(jiǎn)單分類和求解難度優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃問(wèn)題求解的難度增加

2.優(yōu)化模型實(shí)例目標(biāo)函數(shù)約束條件例2.1線性規(guī)劃模型(LP)模型求解

圖解法

x1x20ABCDl1l2l3l4l5約束條件目標(biāo)函數(shù)

Z=0Z=2400Z=3600z=c(常數(shù))~等值線c在B(20,30)點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)可行域?yàn)橹本€段圍成的凸多邊形目標(biāo)函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。求解LP的基本思想思路：從可行域的某一頂點(diǎn)開(kāi)始，只需在有限多個(gè)頂點(diǎn)中一個(gè)一個(gè)找下去，一定能得到最優(yōu)解。LP的約束和目標(biāo)函數(shù)均為線性函數(shù)2維可行域

線段組成的凸多邊形目標(biāo)函數(shù)等值線為直線最優(yōu)解凸多邊形的某個(gè)頂點(diǎn)n維超平面組成的凸多面體等值線是超平面凸多面體的某個(gè)頂點(diǎn)LP的通常解法是單純形法(G.B.Dantzig,1947)線性規(guī)劃模型的解的幾種情況線性規(guī)劃問(wèn)題有可行解(Feasible)無(wú)可行解（Infeasible）有最優(yōu)解（Optimal）無(wú)最優(yōu)解(Unbounded)目標(biāo)98x1+277x2

－x12

－0.3x1x2

－2x22約束x1+x2

≤100x1

≤2x2x1,x2

≥0二次規(guī)劃模型(QP)若還要求

變量為整數(shù)，則是整數(shù)二次規(guī)劃模型(IQP)二次規(guī)劃模型(QP)-例1.2決策變量：cij，(xj,yj)~16維非線性規(guī)劃模型(NLP)非線性規(guī)劃模型(NLP)－例1.3：整數(shù)規(guī)劃問(wèn)題一般形式

整數(shù)線性規(guī)劃(ILP)

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

目標(biāo)或約束中存在非線性函數(shù)整數(shù)規(guī)劃問(wèn)題的分類

純(全)整數(shù)規(guī)劃(PIP)

決策變量均為整數(shù)混合整數(shù)規(guī)劃(MIP)

決策變量有整數(shù)，也有實(shí)數(shù)0-1規(guī)劃決策變量只取0或1取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），對(duì)應(yīng)的連續(xù)優(yōu)化問(wèn)題稱為原問(wèn)題的松弛問(wèn)題整數(shù)規(guī)劃問(wèn)題對(duì)應(yīng)的松弛問(wèn)題松弛問(wèn)題松弛整數(shù)規(guī)劃問(wèn)題最優(yōu)解最優(yōu)解整數(shù)非整數(shù)整數(shù)舍入非最優(yōu)解基本思想：隱式地枚舉一切可行解（“分而治之”）所謂分枝，就是逐次對(duì)解空間（可行域）進(jìn)行劃分；而所謂定界，是指對(duì)于每個(gè)分枝（或稱子域），要計(jì)算原問(wèn)題的最優(yōu)解的下界（對(duì)極小化問(wèn)題）.這些下界用來(lái)在求解過(guò)程中判定是否需要對(duì)目前的分枝進(jìn)一步劃分，也就是盡可能去掉一些明顯的非最優(yōu)點(diǎn)，避免完全枚舉.分枝定界法（B&B:BranchandBound）整數(shù)線性規(guī)劃的分枝定界算法無(wú)約束優(yōu)化更多的優(yōu)化問(wèn)題線性規(guī)劃非線性規(guī)劃網(wǎng)絡(luò)優(yōu)化組合優(yōu)化整數(shù)規(guī)劃不確定規(guī)劃多目標(biāo)規(guī)劃目標(biāo)規(guī)劃動(dòng)態(tài)規(guī)劃連續(xù)優(yōu)化離散優(yōu)化從其他角度分類

應(yīng)用廣泛：生產(chǎn)和運(yùn)作管理、經(jīng)濟(jì)與金融、圖論和網(wǎng)絡(luò)優(yōu)化、目標(biāo)規(guī)劃問(wèn)題、對(duì)策論、排隊(duì)論、存儲(chǔ)論，以及更加綜合、更加復(fù)雜的決策問(wèn)題等實(shí)際問(wèn)題規(guī)模往往較大，用軟件求解比較方便3.LINDO/LINGO軟件簡(jiǎn)介常用優(yōu)化軟件1.LINDO/LINGO軟件2.MATLAB優(yōu)化工具箱/Mathematic的優(yōu)化功能3.SAS(統(tǒng)計(jì)分析)軟件的優(yōu)化功能4.EXCEL軟件的優(yōu)化功能5.其他（如CPLEX等）MATLAB優(yōu)化工具箱能求解的優(yōu)化模型優(yōu)化工具箱3.0(MATLAB7.0R14)連續(xù)優(yōu)化離散優(yōu)化無(wú)約束優(yōu)化非線性極小fminunc非光滑(不可微)優(yōu)化fminsearch非線性方程(組)fzerofsolve全局優(yōu)化暫缺非線性最小二乘lsqnonlinlsqcurvefit線性規(guī)劃linprog純0-1規(guī)劃bintprog一般IP(暫缺)非線性規(guī)劃fminconfminimaxfgoalattainfseminf上下界約束fminbndfminconlsqnonlinlsqcurvefit約束線性最小二乘lsqnonneglsqlin約束優(yōu)化二次規(guī)劃quadprogLINDO公司軟件產(chǎn)品簡(jiǎn)要介紹

美國(guó)芝加哥(Chicago)大學(xué)的LinusSchrage教授于1980年前后開(kāi)發(fā),后來(lái)成立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)演示(試用)版、高級(jí)版、超級(jí)版、工業(yè)版、擴(kuò)展版…（求解問(wèn)題規(guī)模和選件不同）LINGO除了能用于求解線性規(guī)劃和二次規(guī)劃外，還可以用于非線性規(guī)劃求解以及一些線性和非線性方程（組）的求解等。LINGO軟件的最大特色在于它允許優(yōu)化模型中的決策變量為整數(shù)，而且執(zhí)行速度快。LINGO內(nèi)置了一種建立最優(yōu)化模型的語(yǔ)言，可以簡(jiǎn)便地表達(dá)大規(guī)模問(wèn)題，利用LINGO高效的求解器可快速求解并分析結(jié)果。

LINGO可以求解:線性規(guī)劃、二次規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、圖論及網(wǎng)絡(luò)優(yōu)化和排隊(duì)論模型中的最優(yōu)化問(wèn)題等。LINDO/LINGO軟件能求解的模型優(yōu)化線性規(guī)劃非線性規(guī)劃二次規(guī)劃連續(xù)優(yōu)化整數(shù)規(guī)劃LINDOLINGO建模時(shí)需要注意的幾個(gè)基本問(wèn)題

1、盡量使用實(shí)數(shù)優(yōu)化，減少整數(shù)約束和整數(shù)變量2、盡量使用光滑優(yōu)化，減少非光滑約束的個(gè)數(shù)如：盡量少使用絕對(duì)值、符號(hào)函數(shù)、多個(gè)變量求最大/最小值、四舍五入、取整函數(shù)等3、盡量使用線性模型，減少非線性約束和非線性變量的個(gè)數(shù)（如x/y<5改為x<5y）4、合理設(shè)定變量上下界，盡可能給出變量初始值5、模型中使用的參數(shù)數(shù)量級(jí)要適當(dāng)(如小于103)需要掌握的幾個(gè)重要方面LINGO：

正確閱讀求解報(bào)告；掌握集合(SETS)的應(yīng)用； 正確理解求解狀態(tài)窗口； 學(xué)會(huì)設(shè)置基本的求解選項(xiàng)(OPTIONS)； 掌握與外部文件的基本接口方法§1.2

了解LINGO的菜單新建打開(kāi)保存打印剪切復(fù)制粘貼取消重做查找定位匹配括號(hào)求解顯示答案模型圖示選項(xiàng)設(shè)置窗口后置關(guān)閉所有窗口平鋪窗口在線幫助上下文相關(guān)幫助文件菜單編輯菜單LINGO菜單窗口菜單幫助菜單[變量][約束][非零系數(shù)][內(nèi)存使用量][已運(yùn)行時(shí)間][求解器狀態(tài)][擴(kuò)展求解器狀態(tài)]例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶

3kgA1

12h

8h

4kgA2

或獲利24元/kg獲利16元/kg50桶牛奶時(shí)間480h至多加工100kgA1

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?

可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/kg，應(yīng)否改變生產(chǎn)計(jì)劃？每天：?jiǎn)栴}1桶牛奶3kgA1

12h8h4kgA2

或獲利24元/kg獲利16元/kgx1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時(shí)間480h至多加工100kgA1

50桶牛奶每天基本模型模型求解

軟件實(shí)現(xiàn)

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元.LINGO的語(yǔ)法規(guī)定：（1）求目標(biāo)函數(shù)的最大值或最小值分別用MAX=…或MIN=…來(lái)表示；（2）每個(gè)語(yǔ)句必須以分號(hào)“；”結(jié)束，每行可以有許多語(yǔ)句，語(yǔ)句可以跨行；（3）變量名稱必須以字母(A~Z)開(kāi)頭，由字母、數(shù)字(0~9)和下劃線所組成，長(zhǎng)度不超過(guò)32個(gè)字符，不區(qū)分大小寫；（4）可以給語(yǔ)句加上標(biāo)號(hào)，例如[OBJ]MAX=200*X1+300*X2；LINGO的語(yǔ)法規(guī)定：（5）以驚嘆號(hào)“！”開(kāi)頭，以分號(hào)“；”結(jié)束的語(yǔ)句是注釋語(yǔ)句;（6）如果對(duì)變量的取值范圍沒(méi)有作特殊說(shuō)明，則默認(rèn)所有決策變量都非負(fù)；（7）乘號(hào)“*”必須輸入，不能省略。（8）LINGO模型以語(yǔ)句“MODEL：”開(kāi)頭，以“END”結(jié)束，對(duì)于比較簡(jiǎn)單的模型，這兩個(gè)語(yǔ)句可以省略。模型求解

軟件實(shí)現(xiàn)

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元.模型求解

reducedcost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對(duì)max型問(wèn)題)

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對(duì)應(yīng)系數(shù)應(yīng)增加的量結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000

MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三種資源“資源”剩余為零的約束為緊約束（有效約束）原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40結(jié)果解釋

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量影子價(jià)格35元可買到1桶牛奶，要買嗎?35<48,應(yīng)該買！

聘用臨時(shí)工人付出的工資最多每小時(shí)幾元?2元！原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)該命令產(chǎn)生當(dāng)前模型的靈敏度分析報(bào)告（需要通過(guò)Lingo菜單設(shè)置激活）(1)最優(yōu)解保持不變的情況下,目標(biāo)函數(shù)的系數(shù)變化范圍;(2)在影子價(jià)格和縮減成本系數(shù)都不變的前提下,約束條件右邊的常數(shù)變化范圍;敏感性分析(“LINGO|Ranges”)注意：靈敏性分析耗費(fèi)相當(dāng)多的求解時(shí)間，因此當(dāng)速度很關(guān)鍵時(shí),就沒(méi)有必要激活它Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000

最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍敏感性分析

(“LINGO|Ranges”)

x1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/kg，應(yīng)否改變生產(chǎn)計(jì)劃?x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶,每天最多買多少?最多買10桶!(目標(biāo)函數(shù)不變)充分條件!奶制品的生產(chǎn)與銷售

由于產(chǎn)品利潤(rùn)、加工時(shí)間等均為常數(shù)，可建立線性規(guī)劃模型.

線性規(guī)劃模型的三要素：決策變量、目標(biāo)函數(shù)、約束條件.

用LINGO求解，輸出豐富，利用影子價(jià)格和靈敏性分析可對(duì)結(jié)果做進(jìn)一步研究.

建模時(shí)盡可能利用原始的數(shù)據(jù)信息，把盡量多的計(jì)算留給計(jì)算機(jī)去做.主要內(nèi)容整數(shù)規(guī)劃方法432023年5月18日整數(shù)規(guī)劃的一般模型；整數(shù)規(guī)劃解的求解方法；整數(shù)規(guī)劃的軟件求解方法；

0-1規(guī)劃的模型與求解方法；整數(shù)規(guī)劃的應(yīng)用案例分析。

如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量.

小型中型大型現(xiàn)有量鋼材（t）1.535600勞動(dòng)時(shí)間（h）28025040060000利潤(rùn)（萬(wàn)元）234

制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大.引例汽車生產(chǎn)計(jì)劃設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)模型求解

3）模型中增加條件：x1,x2,x3

均為整數(shù)，重新求解.

ObjectiveValue:632.2581VariableValueReducedCost

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226結(jié)果為小數(shù)，怎么辦？1）舍去小數(shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值z(mì)=629，與LP最優(yōu)值632.2581相差不大.2）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值z(mì)，通過(guò)比較可能得到更優(yōu)的解.

但必須檢驗(yàn)它們是否滿足約束條件.為什么？IP可用LINGO直接求解整數(shù)規(guī)劃(IntegerProgramming,簡(jiǎn)記IP)IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000模型求解

IP結(jié)果輸出IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);end其中3個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：方法1：分解為8個(gè)LP子模型汽車廠生產(chǎn)計(jì)劃

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最優(yōu)值z(mì)=610LINGO中對(duì)0-1變量的限定：@bin(y1);@bin(y2);@bin(y3);方法2：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù),本例可取1000ObjectiveValue:610.0000VariableValueReducedCost

X180.000000-2.000000

X2150.000000-3.000000

X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前

IP模型LINGO求解Model：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1<1000*y1;x1>80*y1;%取M=1000x2<1000*y2;x2>80*y2;x2<1000*y2;x2>80*y2;@gin(x1);@gin(x2);@gin(x3);%整數(shù)約束@bin(y1);@bin(y2);@bin(y3);%0-1變量endmax=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;x1*(x1-80)>0;x2*(x2-80)>0;x3*(x3-80)>0;@gin(x1);@gin(x2);@gin(x3);方法3：化為非線性規(guī)劃

非線性規(guī)劃（Non-LinearProgramming，簡(jiǎn)記NLP）

若生產(chǎn)某類汽車，則至少生產(chǎn)80輛，求生產(chǎn)計(jì)劃.x1=0或

80x2=0或

80x3=0或

80最優(yōu)解同前.一般地，整數(shù)規(guī)劃和非線性規(guī)劃的求解比線性規(guī)劃困難得多，特別是問(wèn)題規(guī)模較大或者要求得到全局最優(yōu)解時(shí).532023年5月18日2.整數(shù)規(guī)劃模型的一般形式

一、整數(shù)規(guī)劃的一般模型問(wèn)題是如何求解整數(shù)規(guī)劃問(wèn)題呢？能否設(shè)想先略去決策變量整數(shù)約束，即變?yōu)榫€性規(guī)劃問(wèn)題求解，再對(duì)其最優(yōu)解進(jìn)行取整處理呢？實(shí)際上，可借鑒這種思想來(lái)解決整數(shù)規(guī)劃問(wèn)題．整數(shù)規(guī)劃模型示例542023年5月18日固定資源分配問(wèn)題問(wèn)題分析與準(zhǔn)備

固定資源分配問(wèn)題資源B1…Bj…Bm車間A1利潤(rùn)：r11……………Ai……rij………An…………rnm價(jià)格a1…aj…am總量X1…Xj…Xm

目標(biāo)總利潤(rùn)各車間、各資源利潤(rùn)資源分配量決策變量562023年5月18日

固定資源分配問(wèn)題

3、整數(shù)規(guī)劃的LINGO解法二、整數(shù)規(guī)劃的求解方法572023年5月18日582023年5月18日

1、0-1整數(shù)規(guī)劃的模型三、0-1整數(shù)規(guī)劃592023年5月18日

2、指派（或分配）問(wèn)題三、0-1整數(shù)規(guī)劃

在生產(chǎn)管理上，總希望把人員最佳分派，以發(fā)揮其最大工作效率，創(chuàng)造最大的價(jià)值。例如：某部門有n項(xiàng)任務(wù)，正好需要n個(gè)人去完成，由于任務(wù)的性質(zhì)和各人的專長(zhǎng)不同，如果分配每個(gè)人僅能完成一項(xiàng)任務(wù)。如何分派使完成n項(xiàng)任務(wù)的總效益為最高（效益量化），這是典型的分配問(wèn)題。2.指派（或分配）問(wèn)題602023年5月18日

現(xiàn)在不妨設(shè)有4個(gè)人，各有能力去完成4項(xiàng)科研任務(wù)中的任一項(xiàng)，由于4個(gè)人的能力和經(jīng)驗(yàn)不同，所需完成各項(xiàng)任務(wù)的時(shí)間如右表：?jiǎn)柸绾畏峙浜稳巳ネ瓿珊雾?xiàng)目使完成4項(xiàng)任務(wù)所需總時(shí)間最少？612023年5月18日2.指派（或分配）問(wèn)題622023年5月18日2.指派（或分配）問(wèn)題632023年5月18日2.指派（或分配）問(wèn)題642023年5月18日2.指派（或分配）問(wèn)題指派問(wèn)題的一般模型：652023年5月18日2.指派（或分配）問(wèn)題指派問(wèn)題的一般模型：662023年5月18日

匈牙利算法的基本思想

因?yàn)槊總€(gè)指派問(wèn)題都有一個(gè)相應(yīng)的效益矩陣，通過(guò)初等變換修改效益矩陣的行或列，使得在每一行或列中至少有一個(gè)零元素，直到在不同行不同列中都至少有一個(gè)零元素為止。從而得到與這些零元素相對(duì)應(yīng)的一個(gè)完全分配方案，這個(gè)方案對(duì)原問(wèn)題而言是一個(gè)最優(yōu)的分配方案。3.指派問(wèn)題的匈牙利算法672023年5月18日

用LINGO求解0-1規(guī)劃模型4、0-1規(guī)劃的LINGO解法如何選拔隊(duì)員組成4100m混合泳接力隊(duì)?例1混合泳接力隊(duì)的選拔5名候選人的百米成績(jī)窮舉法：組成接力隊(duì)的方案共有5!=120種.甲乙丙丁戊蝶泳仰泳蛙泳自由泳討論:丁的蛙泳成績(jī)退步到；戊的自由泳成績(jī)進(jìn)步到,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(s)~隊(duì)員i第j種泳姿的百米成績(jī)約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人模型求解MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata輸入LINGO求解

min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END模型求解最優(yōu)解：x14=x21=x32=x43=1,其他變量為0;輸入LINGO求解

甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.成績(jī)?yōu)?53.2(s)=甲乙丙丁戊蝶泳仰泳蛙泳自由泳丁蛙泳c43

=69.675.2(s)，戊自由泳c54=62.4

57.5(s),方案是否調(diào)整？

敏感性分析？新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般沒(méi)有與LP相類似的理論，LINGO輸出的敏感性分析結(jié)果通常是沒(méi)有意義的.c43,c54

的新數(shù)據(jù)重新輸入模型，用LINGO求解

原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.討論最優(yōu)解：x21=x32=x43=x51=1,成績(jī)?yōu)榛旌嫌窘恿﹃?duì)的選拔指派(Assignment)問(wèn)題：有若干項(xiàng)任務(wù),

每項(xiàng)任務(wù)必有且只能有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，不同人員承擔(dān)不同任務(wù)的效益(或成本)不同，怎樣分派各項(xiàng)任務(wù)使總效益最大(或總成本最小)?

人員數(shù)量與任務(wù)數(shù)量相等

人員數(shù)量大于任務(wù)數(shù)量(本例)

人員數(shù)量小于任務(wù)數(shù)量

?建立0-1規(guī)劃模型是常用方法為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

例

選課策略要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課課號(hào)課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)