數(shù)學(xué)規(guī)劃及軟件

數(shù)學(xué)規(guī)劃及軟件2023/4/21第1頁，共160頁，2023年，2月20日，星期六一.數(shù)學(xué)規(guī)劃模型與優(yōu)化軟件簡(jiǎn)介二.LINDO/LINGO軟件Outline四.LINGO建模語言

三.建模實(shí)例2023/4/21第2頁，共160頁，2023年，2月20日，星期六

?數(shù)學(xué)規(guī)劃是優(yōu)化問題的一個(gè)分支，起始于20世紀(jì)30年代末，50年代與60年代發(fā)展成為一個(gè)完整的分支并受到數(shù)學(xué)界和社會(huì)各界的重視。七八十年代是數(shù)學(xué)規(guī)劃飛速發(fā)展時(shí)期，無論是從理論上還是算法方面都得到了進(jìn)一步完善。時(shí)至今日數(shù)學(xué)規(guī)劃仍然是運(yùn)籌學(xué)領(lǐng)域中熱點(diǎn)研究問題。從國內(nèi)外的數(shù)學(xué)建模競(jìng)賽的試題中看，有一半以上的問題可用數(shù)學(xué)規(guī)劃進(jìn)行求解。

一.數(shù)學(xué)規(guī)劃模型與優(yōu)化軟件簡(jiǎn)介2023/4/21第3頁，共160頁，2023年，2月20日，星期六約束條件決策變量數(shù)學(xué)規(guī)劃模型的一般形式目標(biāo)函數(shù)可行域

三要素：決策變量；目標(biāo)函數(shù)；約束條件可行解（只滿足約束）與最優(yōu)解(取到最優(yōu)值)“受約束于”之意．2023/4/21第4頁，共160頁，2023年，2月20日，星期六數(shù)學(xué)規(guī)劃類型連續(xù)規(guī)劃:全部決策變量取值均為連續(xù)數(shù)值(實(shí)數(shù))離散規(guī)劃:部分或全部決策變量只取離散數(shù)值2023/4/21第5頁，共160頁，2023年，2月20日，星期六

線性規(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ù)規(guī)劃離散規(guī)劃數(shù)學(xué)規(guī)劃(MathematicalProgramming)2023/4/21第6頁，共160頁，2023年，2月20日，星期六常用優(yōu)化軟件

LINDO/LINGO軟件MATLAB優(yōu)化工具箱/mathematica優(yōu)化程序包EXCEL軟件的優(yōu)化功能SAS(統(tǒng)計(jì)分析)軟件的優(yōu)化功能2023/4/21第7頁，共160頁，2023年，2月20日，星期六LINDO公司軟件產(chǎn)品簡(jiǎn)要介紹

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

LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer2023/4/21第8頁，共160頁，2023年，2月20日，星期六LINDO和LINGO能求解的數(shù)學(xué)規(guī)劃模型LINGOLINDO數(shù)學(xué)規(guī)劃模型線性規(guī)劃(LP)非線性規(guī)劃(NLP)二次規(guī)劃(QP)連續(xù)規(guī)劃整數(shù)規(guī)劃(IP)2023/4/21第9頁，共160頁，2023年，2月20日，星期六LINDO是專門用于求解數(shù)學(xué)規(guī)劃的軟件包。LINDO執(zhí)行速度很快、易于方便輸入，因此在數(shù)學(xué)、科研和工業(yè)界得到廣泛應(yīng)用。LINDO主要用于解線性規(guī)劃、二次規(guī)劃。也可以用于線性方程組的求解以及代數(shù)方程求根等。LINDO中包含了建模語言和許多常用的數(shù)學(xué)函數(shù)（包括大量概論函數(shù)），可供使用者建立規(guī)劃問題時(shí)調(diào)用。一般用LINDO（LinearInteractiveandDiscreteOptimizer）解決線性規(guī)劃二.LINDO/LINGO軟件簡(jiǎn)介2023/4/21第10頁，共160頁，2023年，2月20日，星期六最大規(guī)模的模型的非零系數(shù)可以達(dá)到1,000,000個(gè)最大變量個(gè)數(shù)可以達(dá)到100,000個(gè)，最大目標(biāo)函數(shù)和約束條件個(gè)數(shù)可以達(dá)到32000個(gè)最大整數(shù)變量個(gè)數(shù)可以達(dá)到100,000個(gè)

LINDO6.1學(xué)生版至多可求解多達(dá)300個(gè)變量和150個(gè)約束的規(guī)劃問題2023/4/21第11頁，共160頁，2023年，2月20日，星期六1.求解線性規(guī)劃和非線性規(guī)劃問題2.模型輸入簡(jiǎn)練直觀3.運(yùn)行速度快計(jì)算能力強(qiáng)4.內(nèi)置建模語言提供內(nèi)部函數(shù)較少語句直觀描述大規(guī)模優(yōu)化模型5.引入集合容易建模6.數(shù)據(jù)交換方便(與EXCEL和數(shù)據(jù)庫)

LINGO軟件的主要功能和特點(diǎn)2023/4/21第12頁，共160頁，2023年，2月20日，星期六例1簡(jiǎn)單的線性規(guī)劃（LP）問題：在空白的模型窗口中輸入這個(gè)LP模型：max2x+3yst4x+3y<=103x+5y<12end2023/4/21第13頁，共160頁，2023年，2月20日，星期六如圖：2023/4/21第14頁，共160頁，2023年，2月20日，星期六LINDO程序有以下特點(diǎn)：

★程序以“MAX”（或“MIN”）開始，表示目標(biāo)最大化（或最小化）問題，后面直接寫目標(biāo)函數(shù)表達(dá)式和約束表達(dá)式；★目標(biāo)函數(shù)和約束之間用“ST”分開；（或用“s.t.”）★程序以“END”結(jié)束（“END”也可以省略）?！锵禂?shù)與變量之間的乘號(hào)必須省略?！锵到y(tǒng)對(duì)目標(biāo)函數(shù)所在行自動(dòng)生成行名“1）”,對(duì)約束默認(rèn)的行名分別是“2)”“3)”…，用戶也可以自己輸入行名；行名放在對(duì)應(yīng)的約束之前。★書寫相當(dāng)靈活，不必對(duì)齊，不區(qū)分字符的大小寫。★默認(rèn)所有的變量都是非負(fù)的,所以不必輸入非負(fù)約束。★約束條件中的“<=”及“>=”可分別用“<”及“>”代替?！镆恍兄懈袊@號(hào)“！”后面的文字為是注釋語句，可增強(qiáng)程序的可讀性，不參與模型的建立。2023/4/21第15頁，共160頁，2023年，2月20日，星期六模型求解：用鼠標(biāo)點(diǎn)擊工具欄中的圖標(biāo)，或從菜單中選擇Solve|Solve（Ctrl+S）命令LINDO首先開始編譯這個(gè)模型，編譯沒有錯(cuò)誤則開始求解；求解時(shí)會(huì)首先顯示如右圖所示的LINDO

“求解器運(yùn)行狀態(tài)窗口”。2023/4/21第16頁，共160頁，2023年，2月20日，星期六求解器運(yùn)行狀態(tài)窗口顯示的相應(yīng)信息及含義：

名稱含義Status當(dāng)前狀態(tài)顯示當(dāng)前求解狀態(tài)：“Optimal”表示已達(dá)到最優(yōu)解；其他可能的顯示還有三個(gè)：Feasible(可行解),Infeasible(不可行),Unbounded(最優(yōu)值無界)。Iterations迭代次數(shù)顯示迭代次數(shù)：“2”表示經(jīng)過了2次迭代。

Infeasibility

不可行性約束不滿足的量(即各個(gè)約束條件不滿足的“數(shù)量”的和)：“0”表示解是可行的。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）表示無答案或無意義，因?yàn)檫@個(gè)模型中沒有整數(shù)變量，不是整數(shù)規(guī)劃（IP）。

2023/4/21第17頁，共160頁，2023年，2月20日，星期六名稱含義IPBound整數(shù)規(guī)劃的界顯示整數(shù)規(guī)劃的界（對(duì)最大化問題顯示上界；對(duì)最小化問題，顯示下界）Branches分枝數(shù)顯示分枝定界算法已經(jīng)計(jì)算的分枝數(shù)：ElapsedTime所用時(shí)間顯示計(jì)算所用時(shí)間（秒）：“0.00”說明計(jì)算太快了，用時(shí)還不到0.005秒。UpdateInterval刷新本界面時(shí)間間隔顯示和控制刷新本界面的時(shí)間間隔：“1”表示1秒；用戶可以直接在界面上修改這個(gè)時(shí)間間隔。InterruptSolver中斷求解程序當(dāng)模型規(guī)模比較大時(shí)，求解時(shí)間會(huì)很長(zhǎng)，可以在程序運(yùn)行過程中用鼠標(biāo)點(diǎn)擊該按鈕終止計(jì)算。Close關(guān)閉該按鈕是關(guān)閉狀態(tài)窗口，并不終止計(jì)算2023/4/21第18頁，共160頁，2023年，2月20日，星期六緊接著彈出一對(duì)話框，詢問你是否需要做靈敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先選擇“否（N）”按鈕，這個(gè)窗口就會(huì)關(guān)閉。然后，再把狀態(tài)窗口也關(guān)閉。2023/4/21第19頁，共160頁，2023年，2月20日，星期六報(bào)告窗口用鼠標(biāo)選擇“Window|ReportsWindow”（報(bào)告窗口），就可以查看該窗口的內(nèi)容2023/4/21第20頁，共160頁，2023年，2月20日，星期六輸出結(jié)果表示的意思是：“LPOPTIMUMFOUNDATSTEP2”表示單純形法在兩次迭代（旋轉(zhuǎn)）后得到最優(yōu)解?！癘BJECTIVEFUNCTIONVALUE1)7.454545”

表示最優(yōu)目標(biāo)值為7.454545.（注意：在LINDO中目標(biāo)函數(shù)所在的行總是被認(rèn)為是第1行，這就是這里“1）”的含義）。2023/4/21第21頁，共160頁，2023年，2月20日，星期六“VALUE”給出最優(yōu)解中各變量(VARIABLE)的值:X=1.272727,Y=1.636364.“REDUCEDCOST”給出最優(yōu)的單純形表中目標(biāo)函數(shù)行（第1行）中變量對(duì)應(yīng)的系數(shù).“SLACKORSURPLUS（松馳或剩余）”給出約束對(duì)應(yīng)的松馳變量的值:第2、3行松馳變量均為0,說明對(duì)于最優(yōu)解來講，兩個(gè)約束（第2、3行）均取等號(hào)，即都是緊約束。2023/4/21第22頁，共160頁，2023年，2月20日，星期六“DUALPRICES”給出對(duì)偶價(jià)格（或影子價(jià)格）的值:表示最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量。

第2、3行對(duì)偶價(jià)格分別為.090909，.545455。

“NO.ITERATIONS=2”表示用單純形法進(jìn)行了兩次迭代。2023/4/21第23頁，共160頁，2023年，2月20日，星期六使用LINDO的一些注意事項(xiàng)“>”（或“<”）號(hào)與“>=”（或“<=”）功能相同變量與系數(shù)間可有空格(甚至回車),但無運(yùn)算符變量名以字母開頭，不能超過8個(gè)字符變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）目標(biāo)函數(shù)所在行是第一行，第二行起為約束條件行號(hào)(行名)自動(dòng)產(chǎn)生或人為定義。行名以“）”結(jié)束行中注有“!”符號(hào)的后面部分為注釋。如:

!It’sComment.在模型的任何地方都可以用“TITLE”對(duì)模型命名（最多72個(gè)字符），如： TITLEThisModelisonlyanExample2023/4/21第24頁，共160頁，2023年，2月20日，星期六變量不能出現(xiàn)在一個(gè)約束條件的右端表達(dá)式中不接受括號(hào)“()”和逗號(hào)“,”等任何符號(hào),例:400(X1+X2)需寫為400X1+400X2表達(dá)式應(yīng)化簡(jiǎn)，如2X1+3X2-4X1應(yīng)寫成-2X1+3X2缺省假定所有變量非負(fù)；可在模型的“END”語句后用“FREEname”將變量name的非負(fù)假定取消可在“END”后用“SUB”或“SLB”設(shè)定變量上下界例如：“subx110”的作用等價(jià)于“x1<=10”但用“SUB”和“SLB”表示的上下界約束不計(jì)入模型的約束，也不能給出其松緊判斷和敏感性分析。使用LINDO的一些注意事項(xiàng)2023/4/21第25頁，共160頁，2023年，2月20日，星期六14.“END”后對(duì)0-1變量說明：INTn或INTname15.“END”后對(duì)整數(shù)變量說明：GINn或GINname使用LINDO的一些注意事項(xiàng)16.

簡(jiǎn)單錯(cuò)誤的檢查和避免：輸入模型時(shí)可能會(huì)有某些輸入錯(cuò)誤.當(dāng)問題規(guī)模較大時(shí),要查找錯(cuò)誤是比較困難的。在LINDO中有一些可幫助尋找錯(cuò)誤的功能，其中之一就是菜單命令“Report|Picture（Alt+5）”,它的功能是可以將目標(biāo)函數(shù)和約束表達(dá)式中的非零系數(shù)通過列表（或圖形）顯示出來。2023/4/21第26頁，共160頁，2023年，2月20日，星期六三個(gè)變量范圍限定命令(FREE、SUB、SLB)的作用

求解如下的LP問題：這個(gè)模型中對(duì)變量x沒有非負(fù)限制，對(duì)y有上限限制，對(duì)z有下限限制。用FREE、SUB、SLB三個(gè)命令可以實(shí)現(xiàn)這些功能。2023/4/21第27頁，共160頁，2023年，2月20日，星期六MAX2x–3y+4zS.T.con2)4x+3y+2z<=10con3)-3x+5y-z<12con4)x+y+5z>8con5)-5x-y-z>2ENDfreex!說明：變量x沒有非負(fù)限制suby20!說明：變量y的上界為20slbz30!說明：變量z的下界為30具體輸入如下：求解得到的結(jié)果：最大值為122，最優(yōu)解為x=-17，y=0，z=39。可以看出y的上界（20）在最優(yōu)解中并沒有達(dá)到，z的下界（30）也沒有達(dá)到，因此模型中去掉“suby20”和“slbz30”兩個(gè)語句，得到的結(jié)不變。但由于最優(yōu)解中x的取值為負(fù)值，所以“freex”這個(gè)語句確實(shí)是不能少的。不妨試一下，去掉這個(gè)語句后效果會(huì)怎樣？2023/4/21第28頁，共160頁，2023年，2月20日，星期六

LINGO入門設(shè)有線性規(guī)劃模型如下：2023/4/21第29頁，共160頁，2023年，2月20日，星期六LP問題在lindo和lingo中不同的輸入形式Lindo:max2x+3yst4x+3y<103x+5y<12endLingo:max=2*x+3*y;4*x+3*y<10;3*x+5*y<12;（1）將目標(biāo)函數(shù)的表示方式從“MAX”變成了“MAX=”（2）“ST”在LINGO模型中不再需要，所以被刪除了

（3）每個(gè)系數(shù)與變量間增加了運(yùn)算符“*”（即乘號(hào)不能省略）

（4）每行（目標(biāo)、約束和說明語句）后面均增加了一個(gè)分號(hào)“;”（5）模型結(jié)束標(biāo)志“END”也被刪除了（LINGO中只有當(dāng)模型以“MODEL:”開始時(shí)才能以“END”結(jié)束）。

2023/4/21第30頁，共160頁，2023年，2月20日，星期六LINGO的語法規(guī)則1.最大值MAX=…,最小值MIN=…2.語句必須以分號(hào)”;”結(jié)束每行可多個(gè)語句語句可跨行3.變量名由字母、數(shù)字和下劃線組成以字母開頭長(zhǎng)度不超32個(gè)字符不區(qū)分大小寫4.默認(rèn)決策變量非負(fù)其他要求可做說明5.模型以MODEL：開頭，以END結(jié)束(此結(jié)構(gòu)也可省略）6.注釋以！開始，以;結(jié)束；7.可以用<表示<=；用>表示>=2023/4/21第31頁，共160頁，2023年，2月20日，星期六程序語句輸入的備注：LINGO總是根據(jù)“MAX=”或“MIN=”尋找目標(biāo)函數(shù)，而除注釋語句和TITLE語句外的其他語句都是約束條件，因此語句的順序并不重要。限定變量取整數(shù)值的語句為“@GIN(X1)”和“@GIN(X2)”，不可以寫成“@GIN(2)”，否則LINGO將把這個(gè)模型看成沒有整數(shù)變量。LINGO中函數(shù)一律需要以“@”開頭，其中整型變量函數(shù)（@BIN、@GIN）和上下界限定函數(shù)（@FREE、@SUB、@SLB）與LINDO中的命令類似。而且0/1變量函數(shù)是@BIN函數(shù)。2023/4/21第32頁，共160頁，2023年，2月20日，星期六一個(gè)簡(jiǎn)單的LINGO程序例直接用LINGO來解如下二次規(guī)劃問題：輸入窗口如下：2023/4/21第33頁，共160頁，2023年，2月20日，星期六輸出結(jié)果：運(yùn)行菜單命令“LINGO|Solve”最優(yōu)整數(shù)解X=(35，65)最大利潤(rùn)=11077.52023/4/21第34頁，共160頁，2023年，2月20日，星期六LINGO求解實(shí)例例1model:max=2*x1-3*x2-2*x3+x4;x1-2*x2-3*x3-2*x4=5;x1-x2+2*x3+x4=10;End2023/4/21第35頁，共160頁，2023年，2月20日，星期六Globaloptimalsolutionfoundatiteration:2

Objectivevalue:18.33333VariableValueReducedCostX18.3333330.000000X20.0000000.6666667X30.0000004.333333X41.6666670.000000RowSlackorSurplusDualPrice118.333331.00000020.0000000.333333330.0000001.666667運(yùn)行結(jié)果如下:2023/4/21第36頁，共160頁，2023年，2月20日，星期六看完例1后,能解下面這個(gè)問題嗎?例22023/4/21第37頁，共160頁，2023年，2月20日，星期六例3model:!thisisanintegerprogrammingproblem;max=4*x1+3*x2;4*x1+x2<=10;2*x1+3*x2<=8;@gin(x1);@gin(x2);end2023/4/21第38頁，共160頁，2023年，2月20日，星期六Globaloptimalsolutionfoundatiteration:0

Objectivevalue:11.00000VariableValueReducedCostX12.000000-4.000000X21.000000-3.000000RowSlackorSurplusDualPrice111.000001.00000021.0000000.00000031.0000000.000000運(yùn)行結(jié)果如下:2023/4/21第39頁，共160頁，2023年，2月20日，星期六例4model:!thisisanuncontrainedoptimalproblem;min=3/2*x1^2+1/2*x2^2-x1*x2-2*x1;@free(x1);@free(x2);end2023/4/21第40頁，共160頁，2023年，2月20日，星期六Localoptimalsolutionfoundatiteration:73

Objectivevalue:-1.000000VariableValueReducedCostX10.99999950.000000X20.99999920.000000RowSlackorSurplusDualPrice1-1.000000-1.000000運(yùn)行結(jié)果如下:2023/4/21第41頁，共160頁，2023年，2月20日，星期六例5model:min=-3*x1^2-x2^2-2*x3^2;x1^2+x2^2+x3^2-3=0;-x1+x2>=0;end2023/4/21第42頁，共160頁，2023年，2月20日，星期六

Localoptimalsolutionfoundatiteration:37

Objectivevalue:-6.000000VariableValueReducedCostX11.2128090.000000X21.2128090.000000X30.24122010.000000RowSlackorSurplusDualPrice1-6.000000-1.00000020.0000002.00000030.000000-2.425619運(yùn)行結(jié)果如下:2023/4/21第43頁，共160頁，2023年，2月20日，星期六例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3千克A1

12小時(shí)8小時(shí)4千克A2

或獲利24元/千克獲利16元/千克50桶牛奶時(shí)間480小時(shí)至多加工100千克A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃？每天：三、建模實(shí)例2023/4/21第44頁，共160頁，2023年，2月20日，星期六1桶牛奶3千克A1

12小時(shí)8小時(shí)4千克A2

或獲利24元/千克獲利16元/千克x1桶牛奶生產(chǎn)A1

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

原料供應(yīng)

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

加工能力

決策變量

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

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

線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100千克A1

50桶牛奶每天2023/4/21第45頁，共160頁，2023年，2月20日，星期六模型求解

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

LINDOmax72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤(rùn)3360元。2023/4/21第46頁，共160頁，2023年，2月20日，星期六結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料無剩余時(shí)間無剩余加工能力剩余40max72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）2023/4/21第47頁，共160頁，2023年，2月20日，星期六結(jié)果解釋

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最優(yōu)解下“資源”增加1單位時(shí)“效益”的增量原料增加1單位,利潤(rùn)增長(zhǎng)48時(shí)間增加1單位,利潤(rùn)增長(zhǎng)2加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？2元！2023/4/21第48頁，共160頁，2023年，2月20日，星期六RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

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

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計(jì)劃

x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)2023/4/21第49頁，共160頁，2023年，2月20日，星期六結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價(jià)格有意義時(shí)約束右端的允許變化范圍原料最多增加10時(shí)間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶(目標(biāo)函數(shù)不變)2023/4/21第50頁，共160頁，2023年，2月20日，星期六如果生產(chǎn)某一類型汽車，則至少要生產(chǎn)80輛，那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？例2汽車廠生產(chǎn)計(jì)劃

汽車廠生產(chǎn)三種類型的汽車，已知各類型每輛車對(duì)鋼材、勞動(dòng)時(shí)間的需求，利潤(rùn)及工廠每月的現(xiàn)有量。小型中型大型現(xiàn)有量鋼材（噸）1.535600勞動(dòng)時(shí)間（小時(shí)）28025040060000利潤(rùn)（萬元）234制訂月生產(chǎn)計(jì)劃，使工廠的利潤(rùn)最大。2023/4/21第51頁，共160頁，2023年，2月20日，星期六設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為x1,x2,x3汽車廠生產(chǎn)計(jì)劃模型建立

小型中型大型現(xiàn)有量鋼材1.535600時(shí)間28025040060000利潤(rùn)234線性規(guī)劃模型(LP)2023/4/21第52頁，共160頁，2023年，2月20日，星期六模型求解

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

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

OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOST

X164.5161290.000000

X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.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ì)，通過比較可能得到更優(yōu)的解。但必須檢驗(yàn)它們是否滿足約束條件。為什么？2023/4/21第53頁，共160頁，2023年，2月20日，星期六IP可用LINDO直接求解整數(shù)規(guī)劃(IP)“gin3”表示“前3個(gè)變量為整數(shù)”，等價(jià)于：ginx1ginx2ginx3IP的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值z(mì)=632max2x1+3x2+4x3st1.5x1+3x2+5x3<600280x1+250x2+400x3<60000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解

IP結(jié)果輸出2023/4/21第54頁，共160頁，2023年，2月20日，星期六LINDO中對(duì)0-1變量的限定：inty1inty2inty3方法：引入0-1變量，化為整數(shù)規(guī)劃

M為大的正數(shù)，可取1000OBJECTIVEFUNCTIONVALUE1)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或

802023/4/21第55頁，共160頁，2023年，2月20日，星期六應(yīng)如何安排原油的采購和加工

？

例3原油采購與加工

市場(chǎng)上可買到不超過1500噸的原油A：購買量不超過500噸時(shí)的單價(jià)為10000元/噸；購買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購買量超過1000噸時(shí)，超過1000噸的部分6000元/噸。售價(jià)4800元/噸售價(jià)5600元/噸庫存500噸

庫存1000噸汽油甲(A50%)原油A原油B汽油乙(A60%)2023/4/21第56頁，共160頁，2023年，2月20日，星期六決策變量

目標(biāo)函數(shù)問題分析利潤(rùn)：銷售汽油的收入-購買原油A的支出難點(diǎn)：原油A的購價(jià)與購買量的關(guān)系較復(fù)雜甲(A50%)AB乙(A60%)購買xx11x12x21x224.8千元/噸5.6千元/噸原油A的購買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購買原油A的支出利潤(rùn)(千元)c(x)如何表述？2023/4/21第57頁，共160頁，2023年，2月20日，星期六原油供應(yīng)

約束條件x

500噸單價(jià)為10千元/噸；500噸x1000噸，超過500噸的8千元/噸；1000噸x1500噸，超過1000噸的6千元/噸。目標(biāo)函數(shù)購買xABx11x12x21x22庫存500噸庫存1000噸2023/4/21第58頁，共160頁，2023年，2月20日，星期六目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡(jiǎn)，用現(xiàn)成的軟件求解。

汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x222023/4/21第59頁，共160頁，2023年，2月20日，星期六y1,y2,y3=1~以價(jià)格10,8,6(千元/噸)采購A增加約束0-1線性規(guī)劃模型，可用LINDO求解y1,y2,y3=0或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000購買1000噸原油A，與庫存的500噸原油A和1000噸原油B一起，生產(chǎn)汽油乙，利潤(rùn)為5,000千元。x1,x2,x3~以價(jià)格10,8,6(千元/噸)采購A的噸數(shù)y=0x=0x>0y=12023/4/21第60頁，共160頁，2023年，2月20日，星期六例4:員工聘用方案決策變量：周一至周日每天(新)聘用人數(shù)x1,x2,x7目標(biāo)函數(shù)：7天(新)聘用人數(shù)之和約束條件：周一至周日每天需要人數(shù)2023/4/21第61頁，共160頁，2023年，2月20日，星期六連續(xù)工作5天周一工作的應(yīng)是(上)周四至周一聘用的設(shè)系統(tǒng)已進(jìn)入穩(wěn)態(tài)聘用方案整數(shù)規(guī)劃模型(IP)2023/4/21第62頁，共160頁，2023年，2月20日，星期六首先在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/4/21第63頁，共160頁，2023年，2月20日，星期六求解后狀態(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)解）。2023/4/21第64頁，共160頁，2023年，2月20日，星期六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求解結(jié)果的報(bào)告窗口如下：2023/4/21第65頁，共160頁，2023年，2月20日，星期六生產(chǎn)中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小例5鋼管和易拉罐下料原料下料問題按照工藝要求，確定下料方案，使所用材料最省，或利潤(rùn)最大2023/4/21第66頁，共160頁，2023年，2月20日，星期六某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19米長(zhǎng)。1) 現(xiàn)有一客戶需要50根4米長(zhǎng)、20根6米長(zhǎng)和15根8米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)??？2) 零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要1）中的三種鋼管外，還需要10根5米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)??？1、鋼管下料2023/4/21第67頁，共160頁，2023年，2月20日，星期六問題1）的求解

問題分析首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將19米長(zhǎng)的鋼管切割成3根4米長(zhǎng)的鋼管，余料為7米顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有7種，如表所示。2023/4/21第68頁，共160頁，2023年，2月20日，星期六為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ?.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023鋼管下料問題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小2023/4/21第69頁，共160頁，2023年，2月20日，星期六xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015整數(shù)約束：xi為整數(shù)2023/4/21第70頁，共160頁，2023年，2月20日，星期六模型求解將整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下：

Title鋼管下料-最小化余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7 2023/4/21第71頁，共160頁，2023年，2月20日，星期六求解可以得到最優(yōu)解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000

按模式2切割12根,按模式5切割15根，余料27米

2023/4/21第72頁，共160頁，2023年，2月20日，星期六目標(biāo)2（總根數(shù)）鋼管下料問題1約束條件不變xi為整數(shù)2023/4/21第73頁，共160頁，2023年，2月20日，星期六將整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO：Title鋼管下料-最小化鋼管根數(shù)Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7模型求解2023/4/21第74頁，共160頁，2023年，2月20日，星期六求解，可以得到最優(yōu)解如下：OBJECTIVEFUNCTIONVALUE1)25.00000 VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.0000002023/4/21第75頁，共160頁，2023年，2月20日，星期六當(dāng)余料沒有用處時(shí)，通常以總根數(shù)最少為目標(biāo)最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比2023/4/21第76頁，共160頁，2023年，2月20日，星期六鋼管下料問題2對(duì)大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量

xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量2023/4/21第77頁，共160頁，2023年，2月20日，星期六滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型鋼管下料問題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)2023/4/21第78頁，共160頁，2023年，2月20日，星期六增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計(jì)劃：對(duì)每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：13+10+8=31模式排列順序可任定

需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米2023/4/21第79頁，共160頁，2023年，2月20日，星期六將模型輸入LINGO如下：model:Title鋼管下料-最小化鋼管根數(shù)的LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13>=50;x1*r21+x2*r22+x3*r23>=10;x1*r31+x2*r32+x3*r33>=20;x1*r41+x2*r42+x3*r43>=15;4*r11+5*r21+6*r31+8*r41<=19;4*r12+5*r22+6*r32+8*r42<=19;4*r13+5*r23+6*r33+8*r43<=19;4*r11+5*r21+6*r31+8*r41>=16;4*r12+5*r22+6*r32+8*r42>=16;4*r13+5*r23+6*r33+8*r43>=16;x1+x2+x3>=26;x1+x2+x3<=31;x1>=x2;x2>=x3;@gin(x1);@gin(x2);@gin(x3);@gin(r11);@gin(r12);@gin(r13);@gin(r21);@gin(r22);@gin(r23);@gin(r31);@gin(r32);@gin(r33);@gin(r41);@gin(r42);@gin(r43);end

2023/4/21第80頁，共160頁，2023年，2月20日，星期六LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。2023/4/21第81頁，共160頁，2023年，2月20日，星期六

問題某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高10cm，上蓋和下底的直徑均為5cm。該公司使用兩種不同規(guī)格的鍍錫板原料：規(guī)格1的鍍錫板為正方形，邊長(zhǎng)24cm；規(guī)格2的鍍錫板為長(zhǎng)方形，長(zhǎng)、寬分別為32cm和28cm。由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制，對(duì)于規(guī)格1的鍍錫板原料，只可以按照模式1、模式2或模式3進(jìn)行沖壓；對(duì)于規(guī)格2的鍍錫板原料只能按照模式4進(jìn)行沖壓。使用模式1、模式2、模式3、模式4進(jìn)行每次沖壓所需要的時(shí)間分別為1.5s、2s、1s、3s。2、易拉罐下料2023/4/21第82頁，共160頁，2023年，2月20日，星期六

該工廠每周工作40小時(shí)，每周可供使用的規(guī)格1、規(guī)格2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤(rùn)為0.10元，原料余料損失為0.001元/平方厘米（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。問工廠應(yīng)如何安排每周的生產(chǎn)？2023/4/21第83頁，共160頁，2023年，2月20日，星期六板材規(guī)格2：長(zhǎng)方形，3228cm，2萬張。問題分析模式1：1.5秒模式2：2秒模式3：1秒模式4：3秒上蓋下底罐身罐身高10cm，上蓋、下底直徑均5cm。

板材規(guī)格1：正方形，邊長(zhǎng)24cm，5萬張。2023/4/21第84頁，共160頁，2023年，2月20日，星期六

罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53模式1:正方形邊長(zhǎng)24cm問題分析計(jì)算各種模式下的余料損失上、下底直徑d=5cm，罐身高h(yuǎn)=10cm。模式1余料損失242-10d2/4-dh=222.6cm22023/4/21第85頁，共160頁，2023年，2月20日，星期六問題分析目標(biāo):易拉