韓伯棠管理運籌學(xué)(第三版)-第三章-線性規(guī)劃問題的計算機(jī)求解

第三章線性規(guī)劃問題的

計算機(jī)求解如何求解？“管理運籌學(xué)”的軟件包

本章將介紹如何使用計算機(jī)軟件包求解線性規(guī)劃問題。本章介紹的是與本書配套的名為“管理運籌學(xué)”的軟件包(國外常用是lindo軟件），此軟件包可解決100個變量50個約束方程的管理運籌學(xué)問題。本章的重點放在如何讀懂“管理運籌學(xué)”軟件包的計算機(jī)輸出結(jié)果——關(guān)于線性規(guī)劃問題的求解和靈敏度分析的信息，解決工商管理中的實際問題。解決線性規(guī)劃問題的軟件包分兩種，一種是大規(guī)模的軟件包，它可以用來解決復(fù)雜的包含數(shù)千個決策變量和數(shù)千個約束條件的大型的線性規(guī)劃的問題，這些用手工的方式幾年幾十年都解決不了的問題，用這種軟件包，只需要幾分鐘就可以解決了。另一種是用于微機(jī)的軟件包，它們有很好的界面，使用方便，由科研機(jī)構(gòu)和小軟件公司為解決包含數(shù)百個決策變量的線性規(guī)劃問題而開發(fā)的。管理運籌學(xué)軟件就是屬于這種軟件，它可以解決工商管理中大量的線性規(guī)劃問題。此軟件可以解決本書中的絕大多數(shù)問題。§3.1“管理運籌學(xué)”軟件的操作方法

下面用運籌學(xué)軟件2.5來解決例1的線性規(guī)劃問題。從開始→程序→管理運籌學(xué)2.5，這樣就打開此軟件，如下圖：然后就根據(jù)需要選擇運籌學(xué)的各個分枝

1．輸入的系數(shù)可以是整數(shù)、小數(shù)，但不能是分?jǐn)?shù)，要把分?jǐn)?shù)先化為小數(shù)再輸入。2．輸入前先要合并同類項。3．由于計算機(jī)鍵盤沒有“≤”“≥”的符號，我們約定用“>”代替“≥”，用“<”代替“≤”。4、所有變量≥0不必輸入。默認(rèn)的。5、此軟件的一個最大缺點是變量只有一組X，不能有Y和Z等，而且下標(biāo)不能是二維下標(biāo)如：X12是錯的（看作是一維）。還有X1A等也是錯誤的，其次模型的修改比較麻煩。注意！下面以第二章的例1為例說明此軟件的用法

maxZ=50x1+100x2，

約束條件：x1+x2≤300，2x1+x2≤400，x2≤250,x1≥0,x2≥0.選擇了線性規(guī)劃后，就出現(xiàn)的界面，然后點新建。得到如下對話框：然后新建清零，下面就可以輸入模型了。先輸入變量個數(shù)、約束個數(shù)和MAX或Min，然后點確定后，才能輸入模型。輸入目標(biāo)函數(shù)系數(shù)一般地變量的非負(fù)性不必修改。在這輸入約束條件，在輸入約束條件時注意清0，還要注意不等號的方向。輸完模型后就可以選擇要進(jìn)行的操作，如：保存、解決（求解）等。下面是例1的輸入結(jié)果。輸完模型后，苦要修改模型點這里樣？就這解決后得到如下結(jié)果。如果選擇保存，就彈出保存路徑的對話框。輸入文件名，然后點保存即可，以后可以點打開調(diào)出模型。從上面變量、最優(yōu)解、相差值一欄中，知道例1的最優(yōu)解為生產(chǎn)Ⅰ產(chǎn)品50單位；生產(chǎn)Ⅱ產(chǎn)品250單位。相差值提供的數(shù)值表示相應(yīng)的決策變量的目標(biāo)系數(shù)需要改進(jìn)的數(shù)量，使得該決策變量有可能取正數(shù)值，一般地，當(dāng)決策變量已取正數(shù)值時則相差值為零。如果決策變量取0值，則相差值可能不為0。對例1來說由于x1=50，x2=250，都是正值，所以它們的相差值都為零。如果x1的值為0；x1的相差值為20；則就知道，只有當(dāng)產(chǎn)品I的利潤再提高20元，即達(dá)到50+20=70元時（這里的50是表示X1的利潤，不是X1的最優(yōu)解），產(chǎn)品I才可能生產(chǎn)，即x1才可能大于零。對于目標(biāo)函數(shù)求最小值的線性規(guī)劃問題，那么所謂的改進(jìn)就應(yīng)該使其對應(yīng)的決策變量的系數(shù)減少其相差值。這在以后還要說明。如何讀懂輸出結(jié)果？§3.2軟件輸出信息分析喂！你知道什么叫相差值嗎？

我知道：如果決策變量取正數(shù)值，則相差值一般為零。則此時目標(biāo)函數(shù)的系數(shù)無法再改變使目標(biāo)函數(shù)值變得更好（當(dāng)目標(biāo)函數(shù)是求最大值時，目標(biāo)函數(shù)值變得更大；而當(dāng)目標(biāo)函數(shù)是求最小值時，目標(biāo)函數(shù)值變得更?。Ｈ绻麤Q策變量取0值，則相差值可能不為0（比如說相差值為正a)。則此時目標(biāo)函數(shù)的系數(shù)可以在原來基礎(chǔ)上增加a（而當(dāng)目標(biāo)函數(shù)是求最小值時，減少a)，則可能才能使此決策變量變?yōu)榉橇悖瓷a(chǎn)該種產(chǎn)品），才有可能使目標(biāo)函數(shù)值變得更好。

滿足約束條件：x1+x2≤300，（臺時數(shù)）2x1+x2≤400，（原料A）x2≤250,（原料B）

在約束條件、松弛／剩余變量、對偶價格這欄中，可知設(shè)備的臺時數(shù)全部使用完，每個設(shè)備臺時的對偶價格為50元，即增加了一個臺時數(shù)就可使總利潤增加50元；原料A還有50千克沒有使用，原料A的對偶價格當(dāng)然為零，即增加1千克A原料不會使總利潤有所增加；原料B全部使用完，原料B的對偶價格為50元，即增加一千克原料B就可使總利潤增加50元。設(shè)備原料A原料B

在目標(biāo)函數(shù)系數(shù)范圍一欄中，所謂的當(dāng)前值是指在目標(biāo)函數(shù)中決策變量的當(dāng)前系數(shù)值。如x1的系數(shù)值為50，x2的系數(shù)值為100。所謂的上限與下限值是指目標(biāo)函數(shù)的決策變量的系數(shù)（其它決策變量的系數(shù)固定）在此范圍內(nèi)變化時，其線性規(guī)劃的最優(yōu)解不變。例如當(dāng)c1=

80時，因為0≤80≤100，在x1的系數(shù)變化范圍內(nèi)，所以其最優(yōu)解不變（此時要固定c2=100)，也即當(dāng)x1=50，x2=250時，有最大利潤。當(dāng)然由于產(chǎn)品Ⅰ的單位利潤由50變?yōu)?0了，其最大利潤也增加了(最優(yōu)值變了)，

變?yōu)?0×50+100×250=29000(元)。但是如果c1=110元時，由于110>100，所以原來的最優(yōu)解就可能不再是最優(yōu)解了。同樣從上圖可知，當(dāng)c2在50與＋∞之間變化時（此時要固定c1=50)

，原來的最優(yōu)解依然是其最優(yōu)解。所謂當(dāng)前值是指約束條件右邊值的現(xiàn)在值，可知b1=300；b2=400，b3=250。所謂上限值與下限值是指當(dāng)約束條件的右邊值在此范圍內(nèi)變化時，則與其對應(yīng)的約束條件的對偶價格不變，不能保證最優(yōu)解不變。從而可由對偶價格判斷增加某約束條件的常數(shù)項值是否能使目標(biāo)函數(shù)值變得更好（前提條件是其它常數(shù)項保持不變）。當(dāng)設(shè)備臺時數(shù)在250→325的范圍內(nèi)，其對偶價格都為50元，說明增加設(shè)備臺時數(shù)可使目標(biāo)函數(shù)值變大，每增加1個臺時數(shù)可增加利潤50元。當(dāng)原料A的公斤數(shù)在350到+∞范圍內(nèi)，其對偶價格都為零；增加原料A對目標(biāo)函數(shù)值無影響。當(dāng)原料B的千克數(shù)在200到300的范圍內(nèi)，其對偶價格都為50元。例如設(shè)備臺時數(shù)和原料A的數(shù)量不變，即b1=300；b2=400，原料B變?yōu)?80千克，由于200≤280≤300，原料B的對偶價格仍為50元，故新的最大利潤值應(yīng)為：27500+(280-250)×50=29000元。這里50是對偶價格。設(shè)備原料A原料B如果所有的右端常數(shù)項同時在變，對偶價格是否變啊？

以上關(guān)于目標(biāo)函數(shù)系數(shù)及約束條件右邊值的靈敏度分析都是基于這樣一個重要假設(shè)：只有一個系數(shù)在變化，而其他的系數(shù)值保持不變。所有以上的目標(biāo)函數(shù)系數(shù)及約束條件右邊值的變化范圍只適合于單個系數(shù)變化的情況。如果兩個或更多或者說所有約束條件右邊常數(shù)項同時變動，就不能用上面方法來判斷對偶價格是否變了。要用下面方法來判斷。

百分之一百法則：

先以例1為例看一看如何用百分之一百法則對兩個目標(biāo)函數(shù)系數(shù)同時變化進(jìn)行靈敏度分析。例1中原來每件Ⅰ產(chǎn)品和Ⅱ產(chǎn)品的利潤分別為50元和100元，現(xiàn)在由于市場情況的變化每件Ⅰ產(chǎn)品和Ⅱ產(chǎn)品的利潤分別變?yōu)?4元和78元，最優(yōu)解發(fā)生變化嗎?為了解決這個問題我們首先來定義“允許增加值”和“允許減少值”這兩個術(shù)語，對一個目標(biāo)函數(shù)的決策變量系數(shù)，所謂允許增加值是該系數(shù)在上限范圍內(nèi)的最大增加量，所謂的允許減少量是該系數(shù)在下限范圍內(nèi)的最大的減少量。這樣可以計算出C1的允許增加量百分比為：(74-50)／50=48％；C2的允許減少百分比為(100-78)／50=44％，C1允許增加百分比與C2的允許減少百分比之和為：48％+44％=92％。變量下限當(dāng)前值上限

x1050100

x250100無上限

從上面可知目標(biāo)函數(shù)中X1的系數(shù)的上限為100，故C1允許增加量為：上限-現(xiàn)在值=100-50=50；

而X2的下限為50，故C2的允許減少量為：

現(xiàn)在值-下限=100-50=50。

定義Ci

的允許增加(減少)百分比為：Ci

的增加量(減少量)除以Ci

的允許增加量(允許減少量)的值。

目標(biāo)函數(shù)決策變量系數(shù)的百分之一百法則：對于所有變化的目標(biāo)函數(shù)決策變量系數(shù)，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之一百時(含百分百），最優(yōu)解不變。在上題中C1的允許增加百分比與C2的允許減少百分比之和為92％不超過100％，所以當(dāng)每件產(chǎn)品Ⅰ利潤從50元增加到74元，每件產(chǎn)品Ⅱ利潤從100元減少到78元時，此線性規(guī)劃最優(yōu)解仍然為Ⅰ產(chǎn)品生產(chǎn)50件，Ⅱ產(chǎn)品生產(chǎn)250件(即x1=50，x2=250)，此時有最大利潤為:74×50+78×250=3700＋19500=23200(元)。注意最大利潤已變。

同樣有約束條件右邊常數(shù)值的百分之一百法則：對于所有變化的約束條件右邊常數(shù)值，當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之一百時，則其對偶價格不變。其中bj

的

允許增加(減少)百分比的

定義同Ci

的允許增加(減少)

百分比一樣：為bj

的增加

量(減少量)除以bj的允許

增加量(減少量)的值。并不難

仍以例1為例來說明如何用約束條件右邊常數(shù)值的百分之一百法則進(jìn)行靈敏度分析。不妨設(shè)設(shè)備臺時數(shù)從300臺時增加為315臺時，而原料A從400千克減少到390千克，原料B從250千克減少到240千克，這樣可以得到它們的允許增加(減少)百分比。因為：約束下限當(dāng)前值上限

1250300325

2350400無上限

3200250300

設(shè)備臺時數(shù)：(315-300)/(325-300)=15/25=60％，原料A：(400-390)/(400-350)=10/50=20％，原料B：(250-240)/(250-200)=10/50=20％。

所以它們的允許增加百分比與允許減少百分比之和為60％+20％+20％=100％，從以上約束條件右邊常數(shù)值的百分之一百法則可知此線性規(guī)劃的對偶價格不變。因為設(shè)備臺時數(shù)從300臺時增加為315臺時，而原料A從400千克減少到390千克，原料B從250千克減少到240千克，所以從對偶價格可知50×15-0×10-50×10=250(元)，則最大利潤增加了250元，為27750元。在使用百分之一百的法則進(jìn)行靈敏度分析時，要注意以下四點：1)、當(dāng)允許增加量(減少量)為無窮大時，則對于任一個增加量(減少量)，其允許增加(減少)百分比都看成零。例如，在表3-4中，約束條件2的常數(shù)項變動范圍為350至+∞,如果原料A從400增加到410，則相當(dāng)于（410-400）/（無窮大-400)=0.2)、當(dāng)允許增加量(減少量)為0時，則對于任一個增加量(減少量)，其允許增加(減少)百分比都看成無窮大（相當(dāng)于該變量不能增加或減少）。

要打開思路!3)、百分之一百法則是判斷最優(yōu)解或?qū)ε純r格變不變的充分條件，但不是必要條件，也就是說當(dāng)其允許增加和減少百分比之和不超過100％時，其最優(yōu)解或?qū)ε純r格不變，但是當(dāng)其允許增加和減少百分比之和超過100％時，我們并不知道其最優(yōu)解或?qū)ε純r格變還是不變。4)、百分之一百法則不能應(yīng)用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況，在這種情況下，只有重新求解。下面把例2輸入計算機(jī)來分析此線性規(guī)劃的計算機(jī)輸出，例2的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：min2x1+3x2約束條件：x1+x2≥350，①x1≥125，②2x1+x2≤600③x1≥0，x2≥0上機(jī)計算得到如下結(jié)果：

從上面結(jié)果知道，當(dāng)購進(jìn)A原料250噸(X1=250)，B原料100噸(X2=100)時，使得購進(jìn)成本最低為800萬元。在松弛／剩余欄中，約束條件②的值為125，約束條件②表示對原料A的最低需求，由于此約束為大于等于，這樣可知原料A的剩余變量值為125（因為x1=250）。同樣可知約束條件①（對所有原料的總需要量）的剩余變量值為零，約束條件③（加工時數(shù)的限制）的松弛變量值為零。

約束松弛／剩余變量對偶價格

10-4

21250

301

在對偶價格一欄中，可知約束條件①的對偶價格為-4萬元，也就是說如果把購進(jìn)原料A+原料B的下限從350噸增加到351噸，那么總成本將加大（因為對偶價格為負(fù)值），由800萬元增加到800+4=804(萬元)了。當(dāng)然如果減少對原料A+原料B的下限，如把原料A+原料B的下限從350噸減少到349噸，那么總成本將得到改進(jìn)，由800萬元減少到800-4=796萬元了?？芍s束條件③（加工時數(shù)）的對偶價格為1萬元，也就是說如果把加工時數(shù)從600小時增加到601小時，則總成本將得到改進(jìn)(因為對偶價格為正值)，由800萬元減少為800-1=799萬元了。目標(biāo)函數(shù)系數(shù)范圍：

變量下限當(dāng)前值上限

X1

無下限23

X223無上限

在目標(biāo)函數(shù)系數(shù)范圍這一欄中，知道當(dāng)C2(目標(biāo)函數(shù)中X2的系數(shù))不變，C1（目標(biāo)函數(shù)中X1的系數(shù)）在-∞到3范圍內(nèi)變化時，最優(yōu)解不變；當(dāng)C1不變時，C2在2到+∞范圍內(nèi)變化時，最優(yōu)解不變。常數(shù)項范圍：約束下限當(dāng)前值