《數(shù)學(xué)建模與數(shù)據(jù)學(xué)實(shí)驗(yàn)》課件第9章

第9章LINDO軟件簡(jiǎn)介9.1

LINDO軟件的求解過(guò)程9.2一個(gè)簡(jiǎn)單的LINDO程序9.3靈敏度分析9.4整數(shù)線(xiàn)性規(guī)劃的求解9.5二次規(guī)劃求解

9.1

LINDO軟件的求解過(guò)程

LINDO軟件內(nèi)有以下4個(gè)基本的求解程序用于求解不同類(lèi)型的優(yōu)化模型(見(jiàn)圖9.1)：

（1）直接求解程序（DriectSolver）；

（2）線(xiàn)性?xún)?yōu)化求解程序（LinearSolver）；

（3）非線(xiàn)性?xún)?yōu)化求解程序（NonlinearSolver）；

（4）分支定界管理程序（BranchandBoundManager）。圖9.1

LINDO軟件的求解過(guò)程

9.2一個(gè)簡(jiǎn)單的LINDO程序

下面通過(guò)一個(gè)簡(jiǎn)單的例子，說(shuō)明如何編寫(xiě)、運(yùn)行一個(gè)完整的LINDO程序。

啟動(dòng)LINDO程序后，屏幕上首先顯示如圖9.2所示的初始界面。圖9.2

LINDO初始界面在LINDO的初始界面，光標(biāo)所在的子窗口稱(chēng)為模型窗口（modelwindow），是用戶(hù)輸入LINDO程序的地方。一個(gè)LINDO程序就是一個(gè)LINDO優(yōu)化模型，目前這個(gè)模型窗口標(biāo)有“〈untitled〉”字樣，表明用戶(hù)尚未為此程序命名，因此系統(tǒng)采用默認(rèn)的名字“〈untitled〉”，用戶(hù)可在保存程序時(shí)對(duì)它重新命名。圖9.3輸入一個(gè)簡(jiǎn)單的優(yōu)化模型注意:

（1）低版本的LINDO要求變量一律用大寫(xiě)字母表示，高版本則大小寫(xiě)無(wú)區(qū)別。

（2）求解一個(gè)問(wèn)題，送入的程序必須以min或max開(kāi)頭，以end結(jié)束（可省略）；然后按Ctrl+S（或按工具欄中的執(zhí)行快捷鍵）進(jìn)行求解。

（3）目標(biāo)函數(shù)與約束條件之間要用subjectto（或st）分開(kāi)。（4）LINDO已假定所有變量非負(fù)，若某變量，例如x3有可能取負(fù)值，可在end命令下面一行用FREEx3命令取消x3的非負(fù)限制；LINDO要求將取整數(shù)值的變量放在前面（即下標(biāo)取小值），在end下面一行用命令I(lǐng)NTEGERk表示前k個(gè)變量是（0，1）變量；在end下面一行用命令GINh表示前h個(gè)變量是整數(shù)變量。

（5）在LINDO中，“<”等價(jià)于“≤”，“>”等價(jià)于“≥”。

（6）在LINDO命令中，約束條件的右邊只能是常數(shù)，不能有變量，變量名不能超過(guò)8個(gè)字符。

（7）LINDO對(duì)目標(biāo)函數(shù)的要求是每項(xiàng)都要有變量，例如：LINDO不認(rèn)識(shí)min2000-x+y，要改為min-x+y；LINDO不識(shí)別400（x+y）要改為400x+400y?，F(xiàn)在利用LINDO軟件來(lái)求解這個(gè)模型，用鼠標(biāo)單擊LINDO軟件的〖XC9A.TIF,JZ〗按鈕，或從菜單中選擇Solve/Solve（Ctrl+S）命令，則LINDO開(kāi)始編譯這個(gè)模型，編譯沒(méi)有錯(cuò)誤后馬上開(kāi)始求解，求解時(shí)會(huì)顯示如圖9.4所示的LINDO求解器運(yùn)行狀態(tài)窗口。LINDO求解線(xiàn)性規(guī)劃的過(guò)程默認(rèn)采用單純形法，一般先尋找一個(gè)可行解，在有可行解的情況下尋找最優(yōu)解。用LINDO求解一個(gè)LP問(wèn)題會(huì)得到可行解或不可行解；可行解又分為有最優(yōu)解和解無(wú)界兩種情況。因此圖9.4中當(dāng)前狀態(tài)除Optimal（最優(yōu)解）外，還有可能顯示另外三個(gè)：Feasible（可行解）、Infeasible（不可行解）、Unbounded（最優(yōu)值無(wú)界）。圖9.4

LINDO求解器運(yùn)行狀態(tài)窗口由于例9.1中的LP模型規(guī)模太小，與圖9.4同時(shí)彈出來(lái)的還有一個(gè)如圖9.5的對(duì)話(huà)框。這個(gè)對(duì)話(huà)框詢(xún)問(wèn)用戶(hù)是否需要作靈敏度分析(DORANGE（SENSITIVITY)ANALYSIS?)，我們先選擇“否（N）”按鈕，這個(gè)窗口就會(huì)關(guān)閉。然后把圖9.4的窗口也關(guān)閉（點(diǎn)擊圖9.4右下角的“Close”按鈕即可）。圖9.5靈敏度分析對(duì)話(huà)框目前這個(gè)模型就解完了，最優(yōu)解顯示為一個(gè)報(bào)告窗口（若未直接顯示出來(lái)，可在LINDO主菜單“Window”中找到子菜單選項(xiàng)“ReportWindow（報(bào)告窗口）”，選擇后可查看窗口的內(nèi)容（見(jiàn)圖9.6）。這些輸出結(jié)果的含義為：

“LPOPTIMUMFOUNDATSTEP1”表示單純形法在1次迭代后得到最優(yōu)解?！癘BJECTIVEFUNCTIONVALUE1)20.00000”表示最優(yōu)目標(biāo)值為20（在LINDO中目標(biāo)函數(shù)所在的行總被認(rèn)為是第1行，此處“1）”即指目標(biāo)函數(shù)）。

“VALUE”給出了最優(yōu)解各變量（VARIABLE）的值，即x1=4，x2=2（這與我們?cè)诘?章中使用圖解法得到的結(jié)果是一致的）。

“REDUCEDCOST”給出了最優(yōu)的單純形表中目標(biāo)函數(shù)行中變量對(duì)應(yīng)的系數(shù)，其中基變量的REDUCEDCOST值一定為0，而非基變量（其取值一定為0）相應(yīng)的REDUCEDCOST值表示該非基變量增加一個(gè)單位時(shí)對(duì)目標(biāo)函數(shù)減少的量（對(duì)max型問(wèn)題）?！癝LACKORSURPLUS（松弛或剩余）”給出了約束對(duì)應(yīng)的松弛變量的值，即第2、3行松弛變量均為0，說(shuō)明對(duì)于最優(yōu)解來(lái)講，2個(gè)約束（第2、3行）均取等號(hào)。

“DUALPRICES（對(duì)偶價(jià)格）”表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率。

“NO.ITERATIONS=1”表示用單純形法進(jìn)行了兩次

迭代。圖9.6報(bào)告窗口現(xiàn)在可以把結(jié)果保存在一個(gè)文件中（默認(rèn)后綴為.ltx，即LINDO文本文件），以便以后調(diào)出來(lái)查看。

【例9.2】求解下列線(xiàn)性規(guī)劃問(wèn)題：在LINDO中輸入如圖9.7所示的命令。圖9.7線(xiàn)性規(guī)劃的輸入模型得到的結(jié)果如圖9.8所示。圖9.8〓線(xiàn)性規(guī)劃的輸出結(jié)果

9.3靈敏度分析

下面先對(duì)一個(gè)簡(jiǎn)單的例子進(jìn)行分析。

【例9.3】某公司制造了三種新產(chǎn)品A、B、C，所用原料分別為a、b、c，產(chǎn)品的基本數(shù)據(jù)如表9.1所示。若要求B產(chǎn)品的數(shù)量不超過(guò)50件，如何安排三種產(chǎn)品的生產(chǎn)使利潤(rùn)最大？容易建立LP模型，首先在LINDO模型窗口中輸入模型,如圖9.9所示。圖9.9產(chǎn)品生產(chǎn)問(wèn)題的輸入模型求解這個(gè)模型，并在圖9.5的對(duì)話(huà)框（DORANGE（SENSITIVITY）ANALYSIS？）中選擇“是（Y）”按鈕，這表示需要作靈敏度分析，這時(shí)從報(bào)告窗口（ReportsWindow）可以看到結(jié)果（見(jiàn)圖9.10）。圖9.10產(chǎn)品生產(chǎn)問(wèn)題的輸出結(jié)果圖9.10中前半部分的輸出結(jié)果的解釋與9.2節(jié)例9.1的結(jié)果（見(jiàn)圖9.6）類(lèi)似：

“LPOPTIMUMFOUNDATSTEP2”表示單純形法在兩次迭代后得到最優(yōu)解。

“OBJECTIVEFUNCTIONVALUE1)1175.000”表示最優(yōu)目標(biāo)值為1175.000。

“VALUE”給出了最優(yōu)解各變量的值，生產(chǎn)5個(gè)A、50個(gè)B、0個(gè)C，即A、B是基變量（取值非0），C是非基變量（取值為0）?！癝LACKORSURPLUS”給出了松弛變量的值，

第2）行松弛變量=10（第2）行對(duì)應(yīng)的是第一個(gè)約束）；

第3）、4）行松弛變量均為0，說(shuō)明對(duì)于最優(yōu)解來(lái)講，2個(gè)約束（第3）、4）行）均取等號(hào)。

“REDUCEDCOST”給出了最優(yōu)的單純形表中目標(biāo)函數(shù)行中變量對(duì)應(yīng)的系數(shù)，表示當(dāng)變量有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率。本例中，變量C對(duì)應(yīng)的REDUCEDCOST為3.750000，表示當(dāng)非基變量C的值從0變?yōu)?時(shí)（假設(shè)此時(shí)其他非基變量保持不變，但為了滿(mǎn)足約束條件，基變量顯然會(huì)發(fā)生變化），最優(yōu)目標(biāo)函數(shù)值=1175-3.75=1171.25。“DUALPRICES（對(duì)偶價(jià)格）”表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率。輸出結(jié)果中對(duì)應(yīng)于每一個(gè)約束有一個(gè)對(duì)偶價(jià)格，若其值為p，表示對(duì)應(yīng)約束中不等式右端項(xiàng)若增加1個(gè)，目標(biāo)函數(shù)將增加p個(gè)（對(duì)max型問(wèn)題）。顯然對(duì)于在最優(yōu)解處約束正好取等號(hào)（“緊約束”，即起作用約束）時(shí)，對(duì)偶價(jià)格值才可能不是0。本例中第3）行對(duì)偶價(jià)格值為2.5，表示當(dāng)緊約束2A+2B+1.5C<=110變?yōu)?A+2B+1.5C<=111時(shí)，目標(biāo)函數(shù)值=1175+2.5=1177.5。對(duì)第4）行也可作類(lèi)似解釋。對(duì)于非緊約束（本例中的第2）行），DUALPRICES的值為0，表示對(duì)應(yīng)約束中不等式右端項(xiàng)的微小變動(dòng)不影響目標(biāo)函數(shù)。有時(shí)，通過(guò)分析DUALPRICES，可以對(duì)產(chǎn)生不可行問(wèn)題的原因有所了解。

圖9.10后半部分的輸出結(jié)果是敏感性分析結(jié)果（若在原來(lái)求解時(shí)沒(méi)有要求LINDO作敏感性分析，可直接用菜單命令“Reports/Range”）。敏感性分析的作用是給出“RANGESINWHICHTHEBASISISUNCHANGED”，即研究當(dāng)目標(biāo)函數(shù)的系數(shù)和約束右端項(xiàng)在什么范圍變化時(shí)（此時(shí)假定其他系數(shù)保持不變），最優(yōu)基（矩陣）保持不變（報(bào)告中的INFINITY表示正無(wú)窮），這包括兩方面的敏感性分析內(nèi)容：（1）目標(biāo)函數(shù)中系數(shù)變化的范圍（OBJCOEFFICIENTRANGES）。

如本例中，目標(biāo)函數(shù)中A變量當(dāng)前的系數(shù)（CURRENTCOEF）為35、允許增加（ALLOWABLEINCREASE）為5、允許減少（ALLOWABLEDECREASE）為15，說(shuō)明當(dāng)這個(gè)系數(shù)在［35-15，35+5］=［20，40］范圍變化時(shí)，最優(yōu)基保持不變。對(duì)B、C變量，可以作類(lèi)似解釋。由于此時(shí)約束沒(méi)有變化(只是目標(biāo)函數(shù)中某個(gè)系數(shù)發(fā)生了變化)，所以最優(yōu)基保持不變的意思也就是最優(yōu)解不變（由于目標(biāo)函數(shù)中的系數(shù)發(fā)生了變化，所以最優(yōu)值也會(huì)發(fā)生變化）。

（2）約束右端項(xiàng)變化的范圍（RIGHTHANDSIDERANGES）。

本例中第2）行約束中當(dāng)前右端項(xiàng)（CURRENTRHS）為180、允許增加（ALLOWABLE

INCREASE）為INFINITY、允許減少（ALLOWABLEDECREASE）為10，說(shuō)明當(dāng)它在［180-10，180+∞］=［170，∞］范圍變化時(shí)，最優(yōu)基保持不變。第3）、4）行也可以作類(lèi)似解釋。由于此時(shí)約束發(fā)生變化，最優(yōu)基即使保持不變，最優(yōu)解、最優(yōu)值也會(huì)發(fā)生變化。至于如何變化，我們將在本節(jié)后面結(jié)合第5章中例5.1的實(shí)際問(wèn)題來(lái)進(jìn)行繼續(xù)說(shuō)明。若讀者對(duì)于單純形法比較熟悉，則可以直接查看最優(yōu)解時(shí)的單純形表（選擇菜單命令Reports/Tableau（Alt+7）執(zhí)行即可），輸出結(jié)果見(jiàn)圖9.11。在圖9.11中，基變量為BV={SLK2，B，A}，ART是人工變量（artificialvariable），即相應(yīng)的目標(biāo)值z(mì)，則z=3.75C+2.5SLK3=1175。敏感性分析結(jié)果表示的是最優(yōu)基保持不變的系數(shù)范圍，由此也可以進(jìn)一步確定當(dāng)目標(biāo)函數(shù)的系數(shù)和約束右端項(xiàng)發(fā)生小的變化時(shí)，最優(yōu)解、最優(yōu)值如何變化。圖9.11

LINDO輸出的單純形表

【例9.4】繼續(xù)討論例9.1，其模型為關(guān)于模型,前面已經(jīng)討論過(guò)了，下面對(duì)其作靈敏度分析。查看報(bào)告窗口可看到關(guān)于靈敏度分析的一些信息，如圖9.12所示。

3個(gè)約束條件的右端分別為A、B、C三種設(shè)備的“工時(shí)限額”，輸出中的SLACKORSURPLUS給出三種設(shè)備工時(shí)在最優(yōu)解下是否有剩余：A、B設(shè)備所剩工時(shí)均為0（約束為緊約束），C設(shè)備尚余2單位工時(shí)（不是緊約束）。目標(biāo)函數(shù)看做“效益”，成為緊約束的“工時(shí)限額”一旦增加，“效益”必然跟著增長(zhǎng)。輸出中DUALPRICES給出這三種設(shè)備在最優(yōu)解下“工時(shí)限額”增加1單位時(shí)“效益”的增量：A設(shè)備增加1單位工時(shí)利潤(rùn)增長(zhǎng)2，B設(shè)備增加1單位工時(shí)利潤(rùn)增長(zhǎng)1，而增加非緊約束設(shè)備C的工時(shí)顯然不會(huì)使利潤(rùn)增長(zhǎng)。這里“效益”的增量可以看做“工時(shí)限額”的潛在價(jià)值，經(jīng)濟(jì)學(xué)上稱(chēng)為影子價(jià)格（shadowprice），即1單位工時(shí)A設(shè)備的價(jià)格為2單位利潤(rùn)，1單位工時(shí)B設(shè)備的價(jià)格為1單位利潤(rùn)，C設(shè)備的影子價(jià)格為0。讀者可以用直接求解的辦法驗(yàn)證以上結(jié)論，即將輸入文件中約束條件1的右端6改為7，看得到的最優(yōu)值（利潤(rùn)）是否恰好增長(zhǎng)2。根據(jù)此處影子價(jià)格的概念，可以考慮在投資時(shí)增加哪種設(shè)備的工時(shí)限額以獲得最優(yōu)效益。圖9.12產(chǎn)品生產(chǎn)問(wèn)題的靈敏度分析結(jié)果目標(biāo)函數(shù)的系數(shù)發(fā)生變化時(shí)（假定約束條件不變），最優(yōu)解和最優(yōu)值會(huì)變嗎？圖9.12中的輸出結(jié)果給出了最優(yōu)基不變條件下目標(biāo)函數(shù)系數(shù)的允許變化范圍：x1的系數(shù)范圍為［3－1，3+1］=［2，4］；x2的系數(shù)范圍為［4－1，4+2］=［3，6］。注意,x1

系數(shù)的允許范圍需要x2的系數(shù)4不變，反之亦然。由于目標(biāo)函數(shù)的系數(shù)變化并不影響約束條件，因此此時(shí)最優(yōu)基不變可以保證最優(yōu)解也不變，但最優(yōu)值會(huì)發(fā)生變化，即當(dāng)甲、乙兩種產(chǎn)品的單位獲利增加時(shí),在允許范圍內(nèi)，不應(yīng)改變生產(chǎn)計(jì)劃，但最優(yōu)值會(huì)發(fā)生變化。下面對(duì)“工時(shí)限額”的影子價(jià)格作進(jìn)一步的分析，影子價(jià)格的作用是有限制的。從上面輸出的結(jié)果中可以看出：約束的右端項(xiàng)的“允許增加”和“允許減少”給出了影子價(jià)格有意義條件下約束右端的限制范圍。具體對(duì)本例來(lái)說(shuō)，A設(shè)備最多可增加2單位工時(shí)，B設(shè)備最多可增加1單位工時(shí)。需要注意的是：靈敏度分析給出的只是最優(yōu)基保持不變的充分條件，而不一定是必要條件。比如對(duì)于上面的問(wèn)題“A設(shè)備最多可增加2單位工時(shí)”的含義是“A設(shè)備增加2單位工時(shí)”時(shí)最優(yōu)基保持不變，所以影子價(jià)格有意義，即利潤(rùn)的增加大于對(duì)A設(shè)備工時(shí)的投資。反過(guò)來(lái)，A設(shè)備增加的工時(shí)超過(guò)了2單位，最優(yōu)基是否一定改變？影子價(jià)格是否一定沒(méi)有意義？一般來(lái)說(shuō)，這無(wú)法從靈敏度分析報(bào)告中直接得出。此時(shí)，應(yīng)重新用新數(shù)據(jù)求解規(guī)劃模型，才能作出判斷。所以嚴(yán)格來(lái)說(shuō)，上面所論述的“A設(shè)備最多增加2單位工時(shí)”并不是完全科學(xué)的。

9.4整數(shù)線(xiàn)性規(guī)劃的求解

LINDO可用于求解線(xiàn)性純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃（IP），模型的輸入與LP問(wèn)題類(lèi)似，但在end標(biāo)志后需定義整型變量。0/1型的變量可由integer（簡(jiǎn)寫(xiě)為int）命令來(lái)標(biāo)識(shí)，一般用intvname或intn表示，前者只將決策變量vname標(biāo)識(shí)為0/1型，后者將當(dāng)前模型的前n個(gè)變量標(biāo)識(shí)為0/1型（模型中變量順序由輸入時(shí)出現(xiàn)的先后順序決定）。一般的整數(shù)變量可用命令gin（generalinteger），其使用方式與int命令相似。【例9.5】求解下列（0，1）線(xiàn)性規(guī)劃問(wèn)題：在LINDO中輸入如圖9.13所示的命令。圖9.13（0，1）線(xiàn)性規(guī)劃的輸入模型

LINDO運(yùn)算后輸出下列結(jié)果（見(jiàn)圖9.14）：NOFEASIBLESOLUTION（求不出最優(yōu)解）。

若將問(wèn)題變?yōu)?×5的問(wèn)題，就能求出解來(lái)。

圖9.14（0，1）線(xiàn)性規(guī)劃的輸出結(jié)在LINDO中輸入如圖9.15所示的命令，LINDO運(yùn)算后輸出的結(jié)果如圖9.16所示。圖9.15（0，1）線(xiàn)性規(guī)劃（5×5）的輸入模型圖9.16（0，1）線(xiàn)性規(guī)劃（5×5）的輸出結(jié)果這個(gè)結(jié)果說(shuō)明：LINDO求解此（0，1）整數(shù)線(xiàn)性規(guī)劃問(wèn)題（LP）共用16步迭代得到最優(yōu)解fmax=25，x12=x25=x33=x44=x51=1，其他xij=0。松弛變量都取0值，即這個(gè)最優(yōu)解使得約束條件都取等號(hào)。其對(duì)偶問(wèn)題的最優(yōu)解（影子價(jià)格）DUALPRICES都為0。

【例9.6】求解下列整數(shù)線(xiàn)性規(guī)劃問(wèn)題：在LINDO環(huán)境下，輸入如圖9.17所示的命令。圖9.17整數(shù)線(xiàn)性規(guī)劃（例9.6）的輸入模型LINDO運(yùn)行后，輸出如圖9.18所示的結(jié)果。圖9.18整數(shù)線(xiàn)性規(guī)劃（例9.6）的輸出結(jié)果這個(gè)結(jié)果說(shuō)明：LINDO求解此線(xiàn)性規(guī)劃問(wèn)題（LP）共用8步迭代得到最優(yōu)解fmax=285，x1=11，x2=0，z1=9，y1=2，y2=12，z2=1。前4個(gè)松弛變量取0值，即這個(gè)最優(yōu)解使得前4個(gè)約束條件取等號(hào)；其對(duì)偶問(wèn)題的最優(yōu)解（影子價(jià)格）DUALPRICES都為0。

【例9.7】求解下列整數(shù)線(xiàn)性規(guī)劃問(wèn)題：在LINDO中輸入如圖9.19所示的命令。圖9.19整數(shù)線(xiàn)性規(guī)劃（例9.7）的輸入模型

LINDO運(yùn)行后輸出如圖9.20所示的結(jié)果。

這個(gè)結(jié)果說(shuō)明：LINDO求解此線(xiàn)性規(guī)劃問(wèn)題（LP）共用3步迭代得到最優(yōu)解fmin=5200，x2=4000，x6=1200，其他xj=0。松弛變量都取0值，即這個(gè)最優(yōu)解使得約束條件都取等號(hào)；其對(duì)偶問(wèn)題的最優(yōu)解（影子價(jià)格）DUALPRICES都為0。圖9.20整數(shù)線(xiàn)性規(guī)劃（例9.7）的輸出結(jié)果

9.5二次規(guī)劃求解

LINDO可用于求解二次規(guī)劃（QP）問(wèn)題，但輸入方式比較復(fù)雜，因?yàn)樵贚INDO中不允許出現(xiàn)非線(xiàn)性表達(dá)式。我們需要為每一個(gè)實(shí)際約束增加一個(gè)對(duì)偶變量（或Lagrange乘子），通過(guò)在實(shí)際約束前增加有關(guān)變量的一階最優(yōu)條件，從而轉(zhuǎn)化二次型為線(xiàn)性互補(bǔ)型（對(duì)線(xiàn)性互補(bǔ)型有興趣的讀者，可參閱其他一些相關(guān)書(shū)籍），并要使用QCP命令指明實(shí)際約束開(kāi)始的行號(hào)，然后才能求解。下面通過(guò)兩個(gè)例子進(jìn)行說(shuō)明。

【例9.8】求解如下的二次規(guī)劃問(wèn)題：用RT、ONE和UL作為對(duì)偶變量，問(wèn)題輸入格式參見(jiàn)圖9.21。圖9.21二次規(guī)劃（例9.8）的輸入模型輸入中的第1行（目標(biāo)函數(shù)）只用于給出模型中相應(yīng)變量的出現(xiàn)順序：X、Y、RT、ONE、UL，用加號(hào)連接。輸入中的第2、3行約束是在實(shí)際約束前增加的有關(guān)變量的一階最優(yōu)條件，即Lagrange函數(shù)：

3x2+y2－xy－RT(1.2x