1、第三章 線性規(guī)劃問題的 計算機求解,如何求解？,“管理運籌學”的軟件包,本章將介紹如何使用計算機軟件包求解線性規(guī)劃問題。 解決線性規(guī)劃問題的軟件包分兩種，一種是大規(guī)模的軟件包，它可以用來解決復雜的包含數(shù)千個決策變量和數(shù)千個約束條件的大型的線性規(guī)劃的問題，重點掌握國內外常用軟件：由芝加哥大學LinusESchrage開發(fā)的lindo6.1軟件，此軟件包可解決32000個變量(3200整型變量）16000個約束方程的運籌學問題。 另一種是用于微機的軟件包，它們有很好的界面，使用方便，由科研機構和小軟件公司為解決包含數(shù)百個決策變量的線性規(guī)劃問題而開發(fā)的。本章介紹的是與本書配套的名為“管理運籌學”2.

2、0軟件包就是屬于這種軟件，此軟件包可解決100個變量50個約束方程的管理運籌學問題。 本章的重點放在如何讀懂“管理運籌學”軟件包的計算機輸出結果關于線性規(guī)劃問題的求解和靈敏度分析的信息，解決工商管理中的實際問題。,3.1“管理運籌學”軟件的操作方法下面用運籌學軟件2.0來解決例1的線性規(guī)劃問題。,從開始程序管理運籌學2.0，這樣就打開此軟件，如下圖：,然后就根據(jù)需要選擇運籌學的各個分枝,1輸入的系數(shù)可以是整數(shù)、小數(shù)， 但不能是分數(shù)，要把分數(shù)先化為小數(shù)再輸入。 2輸入前先要合并同類項。 3、此軟件的一個最大缺點是變量只有一組X，不能有Y和Z等，而且下標不能是二維下標如：X12是錯的（看作是一維）

3、。還有X1A等也是錯誤的，其次模型的修改比較麻煩。,注,意！,下面以第二章的例1為例說明此軟件的用法,max Z=50 x1+100 x2， 約束條件：x1+x2300， 2 x1+x2400， x2250, x10, x20. 選擇了線性規(guī)劃后，就出現(xiàn)的界面，然后點新建。得到如下對話框：,然后新建清零，下面就可以輸入模型了。,先輸入變量個數(shù)、約束個數(shù)和MAX或Min，然后點確定后，才能輸入模型。,輸入目標函數(shù)系數(shù),一般地變量的非負性不必修改。,在這輸入約束條件，在輸入約束條件時注意清0，還要注意不等號的方向。,輸完模型后就可以選擇要進行的操作，如：保存、解決（求解）等。下面是例1的輸入結果。

4、,輸完模型后，苦要修改模型點這里,樣？,就,這,解決后得到如下結果。,如果選擇保存，就彈出保存路徑的對話框。,輸入文件名，然后點保存即可，以后可以點打開調出模型。,從上面變量、最優(yōu)解、相差值一欄中，知道例1的最優(yōu)解為生產(chǎn)產(chǎn)品50單位；生產(chǎn)產(chǎn)品250單位。相差值的數(shù)值表示相應的決策變量的目標系數(shù)需要改進的數(shù)量，使得該決策變量有可能取正數(shù)值，一般地，當決策變量已取正數(shù)值時則相差值為零。如果決策變量取0值，則相差值可能不為0。對例1來說由于x1=50，x2=250，都是正值，所以它們的相差值都為零。如果x1的值為0；x1 的相差值為20；則就知道，只有當產(chǎn)品I 的利潤再提高20元，即達到50+20=

5、70元時（這里的50是表示X1的利潤，不是X1的最優(yōu)解）， 產(chǎn)品I 才可能生產(chǎn)，即x1才可能大于零。對于目標函數(shù)求最小值的線性規(guī)劃問題，那么所謂的改進就應該使其對應的決策變量的系數(shù)減少其相差值。這在以后還要說明。,如何讀懂輸出結果？,3.2軟件輸出信息分析,喂！相差值是什么意思？,我知道：如果決策變量取正數(shù)值，則相差值一般為零。則此時目標函數(shù)的系數(shù)無法再改變使目標函數(shù)值變得更好。 如果決策變量取0值，則相差值可能不為0（比如說相差值為正a，也有可能為0)。則此時目標函數(shù)的系數(shù)可以在原來基礎上增加a（而當目標函數(shù)是求最小值時，減少a)，則可能才能使此決策變量變?yōu)榉橇悖瓷a(chǎn)該種產(chǎn)品），才有可能使

6、目標函數(shù)值變得更好。 也可以這樣理解：在相差值內,價值系數(shù)增加就不會影響原來的最優(yōu)基，但當價值系數(shù)增加大于等于相差值時,最優(yōu)基就會發(fā)生變化。,滿足約束條件：x1+x2300，（臺時數(shù)） 2 x1+x2400，（原料A） x2250, （原料B） 在約束條件、松弛剩余變量、對偶價格這欄中，可知設備的臺時數(shù)全部使用完，每個設備臺時的對偶價格為50元，即增加了一個臺時數(shù)就可使總利潤增加50元；原料A還有50千克沒有使用，原料A的對偶價格當然為零，即增加1千克A原料不會使總利潤有所增加；原料B全部使用完，原料B的對偶價格為50元，即增加一千克原料B就可使總利潤增加50元。,設備 原料A 原料B,在目標

7、函數(shù)系數(shù)范圍一欄中，所謂的當前值是指在目標函數(shù)中決策變量的當前系數(shù)值。如x1的系數(shù)值為50，x2的系數(shù)值為100。所謂的上限與下限值是指目標函數(shù)的決策變量的系數(shù)（其它決策變量的系數(shù)固定在當前值）在此范圍內變化時，其線性規(guī)劃的最優(yōu)解不變。例如當c1= 80時，因為080100，在x1的系數(shù)變化范圍內，所以其最優(yōu)解不變（此時要固定c2=100)，也即當x1=50，x2=250時，有最大利潤。當然由于產(chǎn)品的單位利潤由50變?yōu)?0了，其最大利潤也增加了(最優(yōu)值變了)， 變?yōu)?050 +100250 =29000(元)。 但是如果c1=110元時，由于110100，所以原來的最優(yōu)解就可能不再是最優(yōu)解了。

8、 同樣從上圖可知，當c2 在50與之間變化時（此時要固定c1=50) ，原來的最優(yōu)解依然是其最優(yōu)解。,所謂當前值是指約束條件右邊值的現(xiàn)在值，可知b1=300；b2=400，b3=250。所謂上限值與下限值是指當約束條件的右邊值在此范圍內變化時，則與其對應的約束條件的對偶價格不變，不能保證最優(yōu)解不變。從可由對偶價格判斷增加某約束條件的常數(shù)項值是否能使目標函數(shù)值變得更好（前提條件是其它常數(shù)項保持不變）。 當設備臺時數(shù)在250325的范圍內，其對偶價格都為50元，說明增加設備臺時數(shù)可使目標函數(shù)值變大，每增加1個臺時數(shù)可增加利潤50元。當原料A的公斤數(shù)在350到+范圍內，其對偶價格都為零；增加原料A對

9、目標函數(shù)值無影響。當原料B的千克數(shù)在200到300的范圍內，其對偶價格都為50元。例如設備臺時數(shù)和原料A的數(shù)量不變，即b1=300；b2=400，原料B變?yōu)?80千克，由于200280300，原料B的對偶價格仍為50元，故新的最大利潤值應為： 27500+(280-250)50=29000元。這里50是對偶價格。,設備 原料A 原料B,如果所有的右端常數(shù)項同時在變，對偶價格是否變啊？,以上關于目標函數(shù)系數(shù)及約束條件右邊值的靈敏度分析都是基于這樣一個重要假設：只有一個系數(shù)在變化，而其他的系數(shù)值保持不變。所有以上的目標函數(shù)系數(shù)及約束條件右邊值的變化范圍只適合于單個系數(shù)變化的情況。如果兩個或更多或者

10、說所有約束條件右邊常數(shù)項同時變動，就不能用上面方法來判斷對偶價格是否變了。要用下面方法來判斷。,百分之一百法則：,先以例1為例看一看如何用百分之一百法則對兩個目標函數(shù)系數(shù)同時變化進行靈敏度分析。例1中原來每件產(chǎn)品和產(chǎn)品的利潤分別為50元和100元，現(xiàn)在由于市場情況的變化每件產(chǎn)品和產(chǎn)品的利潤分別變?yōu)?4元和78元，最優(yōu)解發(fā)生變化嗎? 為了解決這個問題我們首先來定義“允許增加值”和“允許減少值”這兩個術語，對一個目標函數(shù)的決策變量系數(shù)，所謂允許增加值是該系數(shù)在上限范圍內的最大增加量，所謂的允許減少量是該系數(shù)在下限范圍內的最大的減少量。,這樣可以計算出C1的允許增加量百分比為： (74-50)50=

11、48；C2 的允許減少百分比為 (100-78)50=44，C1允許增加百分比與C2的允許減 少百分比之和為：48+44=92。,變量 下限 當前值 上限 x1 0 50 100 x2 50 100 無上限 從上面可知目標函數(shù)中X1的系數(shù)的上限為100，故C1允許增加量為： 上限-現(xiàn)在值=100-50=50；而X2的下限為50，故C2的允許減少量為： 現(xiàn)在值-下限=100-50=50。 定義Ci 的允許增加(減少)百分比為：Ci 的增加量(減少量)除以Ci 的允許增加量(允許減少量)的值。,目標函數(shù)決策變量系數(shù)的百分之一百法則：對于所有變化的目標函數(shù)決策變量系數(shù)，當其所有允許增加百分比和允許減

12、少百分比之和不超過百分之一百時(含百分百），最優(yōu)解不變。,在上題中C1 的允許增加百分比與C2 的允許減少百分比之和為92不超過100，所以當每件產(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=370019500=23200(元)。 注意最大利潤已變。,同樣有約束條件右邊常數(shù)值的百分之一百法則：對于所有變化的約束條件右邊常數(shù)值，當其所有允許增加百分比和允許減少百分比之和不超過百分之一百時，則其對偶價格不變。 其中bj 的允許增加(減少)百分

13、比的定義同Ci 的允許增加(減少)百分比一樣：為bj 的增加量(減少量)除以bj的允許增加量(減少量)的值。,仍以例1為例來說明如何用約束條件右邊常數(shù)值的百分之一百法則進行靈敏度分析。不妨設設備臺時數(shù)從300臺時增加為315臺時，而原料A從400千克減少到390千克，原料B從250千克減少到240千克，這樣可以得到它們的允許增加(減少)百分比。因為： 約束 下限 當前值 上限 1 250 300 325 2 350 400 無上限 3 200 250 300設備臺時數(shù)： (315-300)/(325-300)=15/25=60， 原料A： (400-390)/(400-350)=10/50=2

14、0， 原料B： (250-240)/(250-200)=10/50=20。,所以它們的允許增加百分比與允許減少百分比之和為60+20+20=100，從以上約束條件右邊常數(shù)值的百分之一百法則可知此線性規(guī)劃的對偶價格不變。因為設備臺時數(shù)從300臺時增加為315臺時，而原料A從400千克減少到390千克，原料B從250千克減少到240千克，所以從對偶價格可知5015+0（-10）+50（-10）=250(元)，則最大利潤增加了250元，為27750元。,在使用百分之一百的法則進行靈敏度分析時，要注意以下四點：,1)、當允許增加量(減少量)為無窮大時，則對于任一個增加量(減少量)，其允許增加(減少)百

15、分比都看成零。 例如，在表3- 4中，約束條件2的常數(shù)項變動范圍為350至+, 如果原料A從400增加到410，則相當于 （410- 400）/（無窮大- 400)=0. 2)、當允許增加量(減少量)為0時， 則對于任一個增加量(減少量)，其 允許增加(減少)百分比都看成無窮 大（相當于該變量不能增加或減少）。,3)、百分之一百法則是判斷最優(yōu)解或對偶價格變不變的充分條件，但不是必要條件，也就是說當其允許增加和減少百分比之和不超過100時，其最優(yōu)解或對偶價格不變，但是當其允許增加和減少百分比之和超過100時，我們并不知道其最優(yōu)解或對偶價格變還是不變。 4)、百分之一百法則不能應用于目標函數(shù)決策變

16、量系數(shù)和約束條件右邊常數(shù)值同時變化的情況，在這種情況下，只有重新求解。,下面把例2輸入計算機來分析此線性規(guī)劃的計算機輸出，例2的數(shù)學模型如下：,目標函數(shù)：min 2x1+3x2 約束條件：x1+x2350， x1125， 2x1+x2600 x10， x20 上機計算得到如下結果：,從上面結果知道，當購進A原料250噸(X1=250)，B原料100噸(X2=100)時，使得購進成本最低為800萬元。在松弛剩余欄中，約束條件的值為125，約束條件表示對原料A的最低需求，由于此約束為大于等于，這樣可知原料A的剩余變量值為125（因為x1=250）。同樣可知約束條件（對所有原料的總需要量）的剩余變量

17、值為零，約束條件（加工時數(shù)的限制）的松弛變量值為零。,約束 松弛剩余變量 對偶價格 1 0 - 4 2 125 0 3 0 1,在對偶價格一欄中，可知約束條件的對偶價格為- 4萬元，也就是說如果把購進原料A+原料B的下限從350噸增加到351噸，那么總成本將加大（因為對偶價格為負值），由800萬元增加到800+4=804(萬元)了。當然如果減少對原料A+原料B的下限，如把原料A+原料B的下限從350噸減少到349噸，那么總成本將得到改進，由800萬元減少到800- 4=796萬元了。 可知約束條件（加工時數(shù)）的對偶價格為1萬元，也就是說如果把加工時數(shù)從600小時增加到601小時，則總成本將得到

18、改進(因為對偶價格為正值)，由800萬元減少為800-1=799萬元了。,目標函數(shù)系數(shù)范圍： 變量 下限 當前值 上限 X1 無下限 2 3 X2 2 3 無上限,在目標函數(shù)系數(shù)范圍這一欄中，知道當C2(目標函數(shù)中X2的系數(shù))不變，C1（目標函數(shù)中X1的系數(shù)）在-到3范圍內變化時，最優(yōu)解不變；當C1不變時，C2在2到+范圍內變化時，最優(yōu)解不變。,常數(shù)項范圍： 約束 下限 當前值 上限 1 300 350 475 2 無下限 125 250 3 475 600 700 在約束條件右邊值范圍一欄中，知道當約束條件的右邊值（原料A和原料B的總量的下限）在300到475范圍內變化，而其他約束條件的右邊值不變時，則約束條件的對偶價格不變仍為 - 4。 當約束條件的右邊值（原料A的需求量的下限）在0 到250范圍內變化時，而其他約束條件的右邊值