運(yùn)籌學(xué)第三章-線性規(guī)劃的應(yīng)用及計(jì)算機(jī)求解

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

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

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

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

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

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

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

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

則上述汽車生產(chǎn)計(jì)劃模型可變?yōu)槿缦碌臉?biāo)準(zhǔn)格式：

用Excel求解線性規(guī)劃問題，可以按照如下三個(gè)步驟進(jìn)行：１列出所求問題的標(biāo)準(zhǔn)表格

2把標(biāo)準(zhǔn)表格轉(zhuǎn)換為Excel電子表格。

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

其中：?jiǎn)卧馢4(目標(biāo)函數(shù))的計(jì)算公式為：

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

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

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

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

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

3)如果要卸載已經(jīng)加載的宏，請(qǐng)?jiān)凇翱捎眉虞d宏”列表框中，選定待添加的加載宏選項(xiàng)旁的復(fù)選框，然后單擊“確定”。單擊“規(guī)劃求解”按鈕，將會(huì)出現(xiàn)以下的規(guī)劃求解參數(shù)的對(duì)話框?！耙?guī)劃求解”各參數(shù)解釋和設(shè)置

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

(2)最大值、最小值：在此指定是否希望目標(biāo)單元格為最大值、最小值或某一特定數(shù)值。如果需要指定數(shù)，請(qǐng)?jiān)谟覀?cè)編輯框中鍵入該值。

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

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

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

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

(7)更改：顯示“更改約束”對(duì)話框。注意：?jiǎn)螕舸税粹o的時(shí)候，要先選擇需要更改的約束。

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

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

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

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

(2)最大值、最小值：在此指定是否希望目標(biāo)單元格為最大值、最小值或某一特定數(shù)值。如果需要指定數(shù)，請(qǐng)?jiān)谟覀?cè)編輯框中鍵入該值。

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

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

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

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

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

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

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

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

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

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

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

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

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

運(yùn)行結(jié)果報(bào)告：

簡(jiǎn)化計(jì)算方法：

例題１：

例題２：

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

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

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

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

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

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

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

據(jù)測(cè)定每次投資1萬(wàn)元的風(fēng)險(xiǎn)指數(shù)如下表所示：項(xiàng)目風(fēng)險(xiǎn)指數(shù)（每次投資1萬(wàn)元）A１B３C４D5.5

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

(2)應(yīng)如何確定這些項(xiàng)目每年的投資額，從而使得第五年末擁有資金的本利在330萬(wàn)的基礎(chǔ)上總的風(fēng)險(xiǎn)系數(shù)最??？（１）確定變量第一個(gè)問題的求解如下：設(shè)xij

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

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

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

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

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

設(shè)表示從制造廠

到倉(cāng)庫(kù)

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

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

設(shè)表示工人

從事工作，表示工人

不從事工作。

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

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

設(shè)表示生產(chǎn)

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

總銷售收入為：

總成本為：

總利潤(rùn)為：

原料的庫(kù)存約束條件為：

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

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

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

“END”后對(duì)0-1變量說明：INTn

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

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

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

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

Sub

x10

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

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

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

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

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

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

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

12小時(shí)8小時(shí)4公斤A2

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

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

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

獲利24×3x1

獲利16×4x2

決策變量

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

每天獲利約束條件原料供應(yīng)

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

加工能力

非負(fù)約束

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

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工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，利潤(rùn)3360元。OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋

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

35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？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元/千克，應(yīng)否改變生產(chǎn)計(jì)劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！結(jié)果解釋

輸入模型

LinDo模式

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