運籌學第三章-線性規(guī)劃的應用及計算機求解

第三章線性規(guī)劃的應用及計算機求解主講教師：陳煒一、制造業(yè)中的應用：制定生產(chǎn)計劃

首都汽車制造廠生產(chǎn)５種不同檔次的轎車：豪華型、高中檔、中檔、經(jīng)濟型和微型豪華轎車?，F(xiàn)有以下約束：１每款轎車的利潤分別為：58、43、25、17、28萬元。２每輛轎車的車身必須使用同一種混合材料制造，其庫存總量：50000m2。其中每輛豪華型的車身需用25m2的混合材料，高檔轎車：15m2，中檔：10m2，經(jīng)濟：5m2，微型豪華：1m2.

１、汽車生產(chǎn)計劃

3裝配任一款轎車都要用到兩種配件：A和B，而工廠現(xiàn)有庫存量分別為：10000件和25000件。汽車型號配件A配件B豪華型2852高中檔型2448中檔型1840經(jīng)濟型1260微型豪華575４工廠技術(shù)工人的總工時為：2000小時，而用于豪華型、高中檔、中檔、經(jīng)濟型和微型豪華轎車的工時分別為：1.5、1.25、1、0.75、1.5小時。５工廠已經(jīng)獲得的訂單為：200輛中檔轎車和100輛經(jīng)濟型較車。６歷史訂單數(shù)據(jù)表明：高檔轎車和豪華型轎車通常一起收到訂單－－2輛高檔轎車訂單的同時一定收到1輛豪華型轎車的訂單。７歷史訂單數(shù)據(jù)表明：微型豪華轎車的訂單數(shù)量不會超過其它４款轎車的訂單總量的一半。解：設生產(chǎn)豪華型、高中檔、中檔、經(jīng)濟型和微型豪華轎車的產(chǎn)量分別為：，則可列出如下的線性規(guī)劃模型：為了利用計算機求解上述線性規(guī)劃模型，需要將上述模型的約束條件整理成標準形式，其基本要求如下：

(1)約束條件中所有決策變量都必須出現(xiàn)在不等式的左端。

(2)約束條件中變量順序與其定義順序相一致。

(3)每個變量都有屬于自己的系數(shù)。

(4)如果決策變量在約束條件中不出現(xiàn)，則給它們補系數(shù)0。

則上述汽車生產(chǎn)計劃模型可變?yōu)槿缦碌臉藴矢袷剑?/p>

用Excel求解線性規(guī)劃問題，可以按照如下三個步驟進行：１列出所求問題的標準表格

2把標準表格轉(zhuǎn)換為Excel電子表格。

3利用Excel的“規(guī)劃求解”進行求解。2、Excel求解汽車生產(chǎn)計劃問題

其中：單元格J4(目標函數(shù))的計算公式為：

=SUMPRODUCT(B4:F4,$B$15:$F$15)單元格Jk(約束條件k)的計算公式為：

=SUMPRODUCT(Bk:Fk,$B$15:$F$15)將單元格對應的值相乘再求和

安裝office的時候，系統(tǒng)默認的安裝方式不會安裝宏程序，需要用戶根據(jù)自己的需求選擇安裝。下面是加載“規(guī)劃求解”宏的步驟：如何加載Excel的“規(guī)劃求解”

1)在“工具”菜單上，單擊“加載宏”。

2)在彈出的對話框中的“可用加載宏”列表框中，選定待添加的加載宏“規(guī)劃求解”選項旁的復選框，然后單擊“確定”。單擊“確定”以后，“工具”菜單下就會出現(xiàn)一項“規(guī)劃求解”。如果需要其他功能，也可以用鼠標勾選。提醒一句，加載的宏越多，excel啟動的時候就會越慢，所以請根據(jù)自己的需要選擇。

3)如果要卸載已經(jīng)加載的宏，請在“可用加載宏”列表框中，選定待添加的加載宏選項旁的復選框，然后單擊“確定”。單擊“規(guī)劃求解”按鈕，將會出現(xiàn)以下的規(guī)劃求解參數(shù)的對話框?！耙?guī)劃求解”各參數(shù)解釋和設置

(1)目標單元格：存放目標函數(shù)的計算值的位置。

(2)最大值、最小值：在此指定是否希望目標單元格為最大值、最小值或某一特定數(shù)值。如果需要指定數(shù)，請在右側(cè)編輯框中鍵入該值。

(3)可變單元格：在此指定可變單元格。求解時其中的數(shù)值不斷調(diào)整，直到滿足約束條件并且“設置目標單元格”框中指定的單元格達到目標值。

(4)約束：在此列出了規(guī)劃求解的所有約束條件。

(5)約束：在此列出了規(guī)劃求解的所有約束條件。

(6)添加：顯示“添加約束”對話框。

(7)更改：顯示“更改約束”對話框。注意：單擊此按鈕的時候，要先選擇需要更改的約束。

(8)刪除：刪除選定的約束條件。同樣單擊此按鈕前，要先選擇需要刪除的約束。

(9)求解：對定義好的問題進行求解。

(10)選項：顯示“規(guī)劃求解選項”對話框。在其中可加載或保存規(guī)劃求解模型，并對求解過程的高級屬性進行控制。

(1)目標單元格：存放目標函數(shù)的計算值的位置。

(2)最大值、最小值：在此指定是否希望目標單元格為最大值、最小值或某一特定數(shù)值。如果需要指定數(shù)，請在右側(cè)編輯框中鍵入該值。

(3)可變單元格：在此指定可變單元格。求解時其中的數(shù)值不斷調(diào)整，直到滿足約束條件并且“設置目標單元格”框中指定的單元格達到目標值。

(4)約束：在此列出了規(guī)劃求解的所有約束條件。

(5)約束：在此列出了規(guī)劃求解的所有約束條件。

最長運算時間：在此設定求解過程的時間。可輸入的最大值為32767（秒），默認值100（秒）可以滿足大多數(shù)小型規(guī)劃求解要求。

迭代次數(shù)：在此設定求解過程中迭代運算的次數(shù)，限制求解過程的時間?？奢斎氲淖畲笾禐?2767，默認值100次可滿足大多數(shù)小型規(guī)劃求解要求。

精度：在此輸入用于控制求解精度的數(shù)字，以確定約束條件單元格中的數(shù)值是否滿足目標值或上下限。精度值必須表示為小數(shù)（0到1之間），輸入數(shù)字的小數(shù)位越多，精度越高。例如，0.0001比0.01的精度高。

允許誤差：在此輸入滿足整數(shù)約束條件并可被接受的目標單元格求解結(jié)果與真實的最佳結(jié)果間的百分偏差。這個選項只應用于具有整數(shù)約束條件的問題。設置的允許誤差值越大，求解過程就越快。

收斂度：在此輸入收斂度數(shù)值，當最近五次迭代后目標單元格中數(shù)值的變化小于“收斂度”框中設置的數(shù)值時，“規(guī)劃求解”停止運行。收斂度只應用于非線性規(guī)劃求解問題，并且必須表示為小數(shù)（0到1之間）。設置的數(shù)值越小，收斂度就越高。例如，0.0001表示比0.01更小的相對差別。收斂度越小，“規(guī)劃求解”得到結(jié)果所需的時間就越長。

采用線性模型：當模型中的所有關(guān)系都是線性的，并且希望解決線性優(yōu)化問題時，選中此復選框可加速求解進程。

顯示迭代結(jié)果：如果選中此復選框，每進行一次迭代后都將中斷“規(guī)劃求解”，并顯示當前的迭代結(jié)果。

假定非負：如果選中此復選框，則對于在“添加約束”對話框的“約束值”框中沒有設置下限的所有可變單元格，假定其下限為0（零）。

Excel求解汽車生產(chǎn)計劃模型：

點擊《規(guī)劃求解》

運行結(jié)果報告：

簡化計算方法：

例題１：

例題２：

例題3：二、線性規(guī)劃在其它行業(yè)中的應用

例１假設中國投資基金正在發(fā)行一個固定收益的共同基金，基金經(jīng)理預測到發(fā)行結(jié)束后，可以售出1億份基金(1份基金等于人民幣1元)?，F(xiàn)有以下約束：１為分散風險，投資于任何一只債券的資金額不能超過總資金的25%。２至少有一半以上資金投資于長期債券(2009年以后)。

3投資于”一般”債券上的資金額不能超過總資金額的30%。

１、金融行業(yè)：投資組合債券名稱收益率(%)到期年份等級A8.52.10非常好B9.02019很好C10.02006一般D9.52007一般E8.52011非常好F9.02014很好企業(yè)債券基本情況

設投資于A,B,C,D,E,F六只債券上的投資額(萬元)分別為，則可列出如下線性規(guī)劃模型：

例２某部門現(xiàn)有資金200萬元，今后五年內(nèi)考慮給以下項目投資：項目A：從第一年到第五年每年年初都可投資，當年末能收回本利110%。項目B：從第一年到第四年每年年初都可以投資，次年末收回本利125％，但規(guī)定每年最大投資額不能超過30萬元。項目C：第三年初需要投資，到第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元。

項目D：第二年初需要投資，到第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。

據(jù)測定每次投資1萬元的風險指數(shù)如下表所示：項目風險指數(shù)（每次投資1萬元）A１B３C４D5.5

(1)應如何確定這些項目每年的投資額，從而使得第五年末擁有資金的本利金額最大？

(2)應如何確定這些項目每年的投資額，從而使得第五年末擁有資金的本利在330萬的基礎上總的風險系數(shù)最小？（１）確定變量第一個問題的求解如下：設xij

為第i年初投資于項目j的金額（單位：萬元），根據(jù)給定的條件，將變量列于下表中：年份項目１２３４５Ax1AX2AX3AX4AX5ABx1BX2BX3BX4BCX3CDX2D（2）約束條件第一年：該部門年初有資金200萬元，故有第二年：因第一年給項目B的投資要到第二年末才能收回，所以該部門在第二年所擁有的資金僅為項目A在第一年投資額所收回的本息110%，故有年份項目１２３４５Ax1AX2AX3AX4AX5ABx1BX2BX3BX4BCX3CDX2D備注１項目A第一到第五年年初均可投資，每年年末均能收回本利110%２項目B第一到第四年年初均可投資，次年末收回本利125%３項目C第三年年初投資，第五年末收回本利140%４項目D第二年年初投資，第五年末收回本利155%。第三年：第三年年初的資金額是從項目A第二年投資和項目B第一年投資所收回的本息和，故有第四年：類似上面分析可以得到第五年：年份項目１２３４５Ax1AX2AX3AX4AX5ABx1BX2BX3BX4BCX3CDX2D備注１項目A第一到第五年年初均可投資，每年年末均能收回本利110%２項目B第一到第四年年初均可投資，次年末收回本利125%３項目C第三年年初投資，第五年末收回本利140%４項目D第二年年初投資，第五年末收回本利155%。對項目B,C,D的投資額的限制有：（3）目標函數(shù)此題要求在第五年末該部門所擁有的資金額達到最大，即目標函數(shù)可以表示為：從而，該問題的數(shù)學模型為：Excel求解該問題結(jié)果：第二個問題的求解如下：解：所設變量與第一問題相同，其目標為風險系數(shù)最小，即在約束條件中還需加入第五年末資金本利在330萬元之上的約束條件從而，該問題的數(shù)學模型為：Excel求解該問題結(jié)果：

某企業(yè)年度廣告總預算是100萬元人民幣，選擇《大眾體育》、《體育世界》和《人民體育》三種雜志作為投放對象，廣告投放形式是1/4的廣告雜志頁。現(xiàn)有以下約束：１投放在《體育世界》的廣告不能超過５次。２至少在《大眾體育》和《人民體育》上刊登２次以上。

２、市場營銷：廣告投放大眾體育體育世界人民體育讀者數(shù)量(百萬)1000600400有效顧客10%15％7％廣告價格(萬元)1056廣告效果1009028雜志基本信息

設投放在《大眾體育》、《體育世界》和《人民體育》三種雜志中1/4的廣告頁的數(shù)量分別為：廣告效果最大資金約束

如何安排從制造中心（通常是工廠）到銷售中心（通常是倉庫）之間的運量，使得整體運輸費用最小。３、運輸行業(yè)：生產(chǎn)調(diào)度工廠年產(chǎn)量（百萬臺）鄭州100南昌300深圳200總產(chǎn)量600倉庫年需量（百萬臺）北京150上海100廣州200武漢150總需求量600北京上海廣州武漢鄭州197321南昌1521186深圳11141522北京上海廣州武漢產(chǎn)量鄭州x11x12x13x14100南昌x21x22x23x24300深圳x31x32x33x34200需求量150100200150

設表示從制造廠

到倉庫

的數(shù)量。注：對于該問題（運輸問題）用前面的方法求得的結(jié)果不是最優(yōu)解注：正確的求解方法將在第六章節(jié)講授

某廠有３位工人，老張，老王和老李，加工１把剪刀需要經(jīng)過鉆具、磨具和切割３道工序，相關(guān)信息見下表。４、人力資源管理：人力分配工人鉆具磨具切割工具老張51010老王10515老李151510

設表示工人

從事工作，表示工人

不從事工作。

第六章方法求解結(jié)果

某石油化工廠生產(chǎn)和銷售93和97號無鉛汽油?？刂七@兩種汽油質(zhì)量的關(guān)鍵是催化劑EL和EP的使用量。假設企業(yè)最新收到1500萬升93號無鉛汽油和500萬升97號無鉛汽油的訂單，問如何制定最佳混合方案使得利潤最大？5、石油化工行業(yè)：液體混合產(chǎn)品EL(%)EP(%)銷售價格（元）訂貨量(萬升）93汽油(1)－1010150097汽油(2)30－20500汽油質(zhì)量、銷售價格和訂貨信息原料EL(%)EP(%)成本（元）庫存量(萬升）原料O(1)50022000原料R(2)1002530500原料S(3)105041000催化劑EL和EP的用料情況

設表示生產(chǎn)

種汽油需要原料的數(shù)量（萬升），其中

總銷售收入為：

總成本為：

總利潤為：

原料的庫存約束條件為：

汽油的訂貨量約束條件為：

每種汽油中催化劑比例的約束條件為：EL所占比例EP所占比例

整理化簡后所得該問題的線性規(guī)劃模型為：６、食品加工行業(yè)：營養(yǎng)搭配營養(yǎng)成分葡萄干干花生米干核桃仁南瓜子奶粉最低含量卡路里54057206540553049903000蛋白質(zhì)2027015029026056鐵1030201101010維他命A230030070092001000維他命B１0.52.54.82.42.91.4維他命B２0.52.61.31.912.11.6尼亞新31701224718鈣6007208305109120800氨基酸2000103009060價格1.52.5411.5解：設生產(chǎn)1件DS需要的葡萄干用量、干花生米用量、干核桃仁用量、南瓜子用量、奶粉用量分別為三、Lindo/Ligo軟件求解線性規(guī)劃問題１、Lindo輸入模型求解點擊求解按鈕即可結(jié)果汽車生產(chǎn)計劃問題模型窗口ST/st可省略C1)1“>”（或“<”）號與“>=”（或“<=”）功能相同2變量與系數(shù)間可有空格(甚至回車),但無運算符3變量名以字母開頭，不能超過8個字符,只能英文！4變量名不區(qū)分大小寫（包括LINDO中的關(guān)鍵字）5目標函數(shù)所在行是第一行，第二行起為約束條件6行號(行名)自動產(chǎn)生或人為定義。行名可漢字，但不可超過８個體字符，行名以“）”結(jié)束7行中注有“!”符號的后面部分為注釋，可以漢字。8在模型的任何地方都可以用“TITLE”對模型命名（最多72個字符），可以是漢字。使用LINDO的一些注意事項9變量不能出現(xiàn)在一個約束條件的右端表達式中不接受括號“()”和逗號“,”等任何符號,例:400(X1+X2)需寫為400X1+400X210表達式應化簡，如2X1+3X2-4X1應寫成-2X1+3X211缺省假定所有變量非負；可在模型的“End”語句后用“FREEname”將變量name的非負假定取消，必須加End12

“END”后對0-1變量說明：INTn

或INTname13“END”后對整數(shù)變量說明：GINn

或GINname14簡單錯誤的檢查和避免。菜單欄中命令“Report｜Picture(Alt+5),可以將目標函數(shù)和約束表達式中的非零系數(shù)通過列表（或圖形）顯示出來。15可以在模型的“End”后用命令“Sub”

（setupperbound)設置上界，用命令“Slb”

（setlowerbound)設置上界，用法：“Subvnamevalue”將變量vname的上限設定為value,“Slb”類似。例如

Sub

x10

不滿足約束條件的個數(shù)OptimalFeasibleInfeasibleUnboundedreducedcost值表示當非基變量增加一個單位時（其他非基變量保持不變）目標函數(shù)減少的量(對max型問題)

對偶價格－當對應約束有微小變動時，目標函數(shù)的變化率在最優(yōu)解下，“資源”增加１個單位時“效益”的增量。例如，第三個約束為配件B庫存量，其對偶價格為：1.341936。因此，如果庫存增加1個單位，即變?yōu)?5000＋１，則利潤增加1.341936，即變?yōu)?6800.65＋1.34936x1系數(shù)范圍(58-9.005128,58+281.600006)

1庫存可無窮增加，能減少43771.8945312配件A庫存可增可減3配件B庫存可增可減約束條件的右端頂變化范圍

目標函數(shù)中系數(shù)變化的范圍例

加工奶制品的生產(chǎn)計劃制訂生產(chǎn)計劃，使每天獲利最大

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?

A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

每天：x1桶牛奶生產(chǎn)A1

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

獲利24×3x1

獲利16×4x2

決策變量

目標函數(shù)

每天獲利約束條件原料供應

勞動時間

加工能力

非負約束

線性規(guī)劃模型(LP)1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

每天：模型求解

max72x1+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，利潤3360元。OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋

最優(yōu)解下“資源”增加1單位時“效益”的增量原料增1單位,利潤增48時間加1單位,利潤增2能力增減不影響利潤影子價格

35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000DORANGE(SENSITIVITY)ANALYSIS?

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

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

A1獲利增加到30元/千克，應否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！結(jié)果解釋

輸入模型

LinDo模式

LinGo模式求解點擊求解按鈕即可結(jié)果2、LingoLingo軟件的優(yōu)點（1）除具有Lindo