《數(shù)學建模與數(shù)據(jù)學實驗》課件第9章

第9章LINDO軟件簡介9.1

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

9.1

LINDO軟件的求解過程

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

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

（2）線性優(yōu)化求解程序（LinearSolver）；

（3）非線性優(yōu)化求解程序（NonlinearSolver）；

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

LINDO軟件的求解過程

9.2一個簡單的LINDO程序

下面通過一個簡單的例子，說明如何編寫、運行一個完整的LINDO程序。

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

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

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

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

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

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

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

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

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

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

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

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

“DUALPRICES（對偶價格）”表示當對應(yīng)約束有微小變動時，目標函數(shù)的變化率。

“NO.ITERATIONS=1”表示用單純形法進行了兩次

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

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

9.3靈敏度分析

下面先對一個簡單的例子進行分析。

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

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

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

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

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

第3）、4）行松弛變量均為0，說明對于最優(yōu)解來講，2個約束（第3）、4）行）均取等號。

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

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

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

（2）約束右端項變化的范圍（RIGHTHANDSIDERANGES）。

本例中第2）行約束中當前右端項（CURRENTRHS）為180、允許增加（ALLOWABLE

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

LINDO輸出的單純形表

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

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

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

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

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

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

若將問題變?yōu)?×5的問題，就能求出解來。

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

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

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

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

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

9.5二次規(guī)劃求解

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

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

3x2+y2－xy－RT(1.2x