版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第三章線性規(guī)劃問題的
計(jì)算機(jī)求解如何求解?“管理運(yùn)籌學(xué)”的軟件包
本章將介紹如何使用計(jì)算機(jī)軟件包求解線性規(guī)劃問題。本章介紹的是與本書配套的名為“管理運(yùn)籌學(xué)”的軟件包(國外常用是lindo軟件),此軟件包可解決100個(gè)變量50個(gè)約束方程的管理運(yùn)籌學(xué)問題。本章的重點(diǎn)放在如何讀懂“管理運(yùn)籌學(xué)”軟件包的計(jì)算機(jī)輸出結(jié)果——關(guān)于線性規(guī)劃問題的求解和靈敏度分析的信息,解決工商管理中的實(shí)際問題。解決線性規(guī)劃問題的軟件包分兩種,一種是大規(guī)模的軟件包,它可以用來解決復(fù)雜的包含數(shù)千個(gè)決策變量和數(shù)千個(gè)約束條件的大型的線性規(guī)劃的問題,這些用手工的方式幾年幾十年都解決不了的問題,用這種軟件包,只需要幾分鐘就可以解決了。另一種是用于微機(jī)的軟件包,它們有很好的界面,使用方便,由科研機(jī)構(gòu)和小軟件公司為解決包含數(shù)百個(gè)決策變量的線性規(guī)劃問題而開發(fā)的。管理運(yùn)籌學(xué)軟件就是屬于這種軟件,它可以解決工商管理中大量的線性規(guī)劃問題。此軟件可以解決本書中的絕大多數(shù)問題?!?.1“管理運(yùn)籌學(xué)”軟件的操作方法
下面用運(yùn)籌學(xué)軟件2.5來解決例1的線性規(guī)劃問題。從開始→程序→管理運(yùn)籌學(xué)2.5,這樣就打開此軟件,如下圖:然后就根據(jù)需要選擇運(yùn)籌學(xué)的各個(gè)分枝
1.輸入的系數(shù)可以是整數(shù)、小數(shù),但不能是分?jǐn)?shù),要把分?jǐn)?shù)先化為小數(shù)再輸入。2.輸入前先要合并同類項(xiàng)。3.由于計(jì)算機(jī)鍵盤沒有“≤”“≥”的符號(hào),我們約定用“>”代替“≥”,用“<”代替“≤”。4、所有變量≥0不必輸入。默認(rèn)的。5、此軟件的一個(gè)最大缺點(diǎn)是變量只有一組X,不能有Y和Z等,而且下標(biāo)不能是二維下標(biāo)如:X12是錯(cuò)的(看作是一維)。還有X1A等也是錯(cuò)誤的,其次模型的修改比較麻煩。注意!下面以第二章的例1為例說明此軟件的用法
maxZ=50x1+100x2,
約束條件:x1+x2≤300,2x1+x2≤400,x2≤250,x1≥0,x2≥0.選擇了線性規(guī)劃后,就出現(xiàn)的界面,然后點(diǎn)新建。得到如下對(duì)話框:然后新建清零,下面就可以輸入模型了。先輸入變量個(gè)數(shù)、約束個(gè)數(shù)和MAX或Min,然后點(diǎn)確定后,才能輸入模型。輸入目標(biāo)函數(shù)系數(shù)一般地變量的非負(fù)性不必修改。在這輸入約束條件,在輸入約束條件時(shí)注意清0,還要注意不等號(hào)的方向。輸完模型后就可以選擇要進(jìn)行的操作,如:保存、解決(求解)等。下面是例1的輸入結(jié)果。輸完模型后,苦要修改模型點(diǎn)這里樣?就這解決后得到如下結(jié)果。如果選擇保存,就彈出保存路徑的對(duì)話框。輸入文件名,然后點(diǎn)保存即可,以后可以點(diǎn)打開調(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ù)值時(shí)則相差值為零。如果決策變量取0值,則相差值可能不為0。對(duì)例1來說由于x1=50,x2=250,都是正值,所以它們的相差值都為零。如果x1的值為0;x1的相差值為20;則就知道,只有當(dāng)產(chǎn)品I的利潤再提高20元,即達(dá)到50+20=70元時(shí)(這里的50是表示X1的利潤,不是X1的最優(yōu)解),產(chǎn)品I才可能生產(chǎn),即x1才可能大于零。對(duì)于目標(biāo)函數(shù)求最小值的線性規(guī)劃問題,那么所謂的改進(jìn)就應(yīng)該使其對(duì)應(yīng)的決策變量的系數(shù)減少其相差值。這在以后還要說明。如何讀懂輸出結(jié)果?§3.2軟件輸出信息分析喂!你知道什么叫相差值嗎?
我知道:如果決策變量取正數(shù)值,則相差值一般為零。則此時(shí)目標(biāo)函數(shù)的系數(shù)無法再改變使目標(biāo)函數(shù)值變得更好(當(dāng)目標(biāo)函數(shù)是求最大值時(shí),目標(biāo)函數(shù)值變得更大;而當(dāng)目標(biāo)函數(shù)是求最小值時(shí),目標(biāo)函數(shù)值變得更?。?。如果決策變量取0值,則相差值可能不為0(比如說相差值為正a)。則此時(shí)目標(biāo)函數(shù)的系數(shù)可以在原來基礎(chǔ)上增加a(而當(dāng)目標(biāo)函數(shù)是求最小值時(shí),減少a),則可能才能使此決策變量變?yōu)榉橇悖瓷a(chǎn)該種產(chǎn)品),才有可能使目標(biāo)函數(shù)值變得更好。
滿足約束條件:x1+x2≤300,(臺(tái)時(shí)數(shù))2x1+x2≤400,(原料A)x2≤250,(原料B)
在約束條件、松弛/剩余變量、對(duì)偶價(jià)格這欄中,可知設(shè)備的臺(tái)時(shí)數(shù)全部使用完,每個(gè)設(shè)備臺(tái)時(shí)的對(duì)偶價(jià)格為50元,即增加了一個(gè)臺(tái)時(shí)數(shù)就可使總利潤增加50元;原料A還有50千克沒有使用,原料A的對(duì)偶價(jià)格當(dāng)然為零,即增加1千克A原料不會(huì)使總利潤有所增加;原料B全部使用完,原料B的對(duì)偶價(jià)格為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)變化時(shí),其線性規(guī)劃的最優(yōu)解不變。例如當(dāng)c1=
80時(shí),因?yàn)?≤80≤100,在x1的系數(shù)變化范圍內(nèi),所以其最優(yōu)解不變(此時(shí)要固定c2=100),也即當(dāng)x1=50,x2=250時(shí),有最大利潤。當(dāng)然由于產(chǎn)品Ⅰ的單位利潤由50變?yōu)?0了,其最大利潤也增加了(最優(yōu)值變了),
變?yōu)?0×50+100×250=29000(元)。但是如果c1=110元時(shí),由于110>100,所以原來的最優(yōu)解就可能不再是最優(yōu)解了。同樣從上圖可知,當(dāng)c2在50與+∞之間變化時(shí)(此時(shí)要固定c1=50)
,原來的最優(yōu)解依然是其最優(yōu)解。所謂當(dāng)前值是指約束條件右邊值的現(xiàn)在值,可知b1=300;b2=400,b3=250。所謂上限值與下限值是指當(dāng)約束條件的右邊值在此范圍內(nèi)變化時(shí),則與其對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格不變,不能保證最優(yōu)解不變。從而可由對(duì)偶價(jià)格判斷增加某約束條件的常數(shù)項(xiàng)值是否能使目標(biāo)函數(shù)值變得更好(前提條件是其它常數(shù)項(xiàng)保持不變)。當(dāng)設(shè)備臺(tái)時(shí)數(shù)在250→325的范圍內(nèi),其對(duì)偶價(jià)格都為50元,說明增加設(shè)備臺(tái)時(shí)數(shù)可使目標(biāo)函數(shù)值變大,每增加1個(gè)臺(tái)時(shí)數(shù)可增加利潤50元。當(dāng)原料A的公斤數(shù)在350到+∞范圍內(nèi),其對(duì)偶價(jià)格都為零;增加原料A對(duì)目標(biāo)函數(shù)值無影響。當(dāng)原料B的千克數(shù)在200到300的范圍內(nèi),其對(duì)偶價(jià)格都為50元。例如設(shè)備臺(tái)時(shí)數(shù)和原料A的數(shù)量不變,即b1=300;b2=400,原料B變?yōu)?80千克,由于200≤280≤300,原料B的對(duì)偶價(jià)格仍為50元,故新的最大利潤值應(yīng)為:27500+(280-250)×50=29000元。這里50是對(duì)偶價(jià)格。設(shè)備原料A原料B如果所有的右端常數(shù)項(xiàng)同時(shí)在變,對(duì)偶價(jià)格是否變?。?/p>
以上關(guān)于目標(biāo)函數(shù)系數(shù)及約束條件右邊值的靈敏度分析都是基于這樣一個(gè)重要假設(shè):只有一個(gè)系數(shù)在變化,而其他的系數(shù)值保持不變。所有以上的目標(biāo)函數(shù)系數(shù)及約束條件右邊值的變化范圍只適合于單個(gè)系數(shù)變化的情況。如果兩個(gè)或更多或者說所有約束條件右邊常數(shù)項(xiàng)同時(shí)變動(dòng),就不能用上面方法來判斷對(duì)偶價(jià)格是否變了。要用下面方法來判斷。
百分之一百法則:
先以例1為例看一看如何用百分之一百法則對(duì)兩個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化進(jìn)行靈敏度分析。例1中原來每件Ⅰ產(chǎn)品和Ⅱ產(chǎn)品的利潤分別為50元和100元,現(xiàn)在由于市場(chǎng)情況的變化每件Ⅰ產(chǎn)品和Ⅱ產(chǎn)品的利潤分別變?yōu)?4元和78元,最優(yōu)解發(fā)生變化嗎?為了解決這個(gè)問題我們首先來定義“允許增加值”和“允許減少值”這兩個(gè)術(shù)語,對(duì)一個(gè)目標(biāo)函數(shù)的決策變量系數(shù),所謂允許增加值是該系數(shù)在上限范圍內(nèi)的最大增加量,所謂的允許減少量是該系數(shù)在下限范圍內(nèi)的最大的減少量。這樣可以計(jì)算出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ù)的百分之一百法則:對(duì)于所有變化的目標(biāo)函數(shù)決策變量系數(shù),當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之一百時(shí)(含百分百),最優(yōu)解不變。在上題中C1的允許增加百分比與C2的允許減少百分比之和為92%不超過100%,所以當(dāng)每件產(chǎn)品Ⅰ利潤從50元增加到74元,每件產(chǎn)品Ⅱ利潤從100元減少到78元時(shí),此線性規(guī)劃最優(yōu)解仍然為Ⅰ產(chǎn)品生產(chǎn)50件,Ⅱ產(chǎn)品生產(chǎn)250件(即x1=50,x2=250),此時(shí)有最大利潤為:74×50+78×250=3700+19500=23200(元)。注意最大利潤已變。
同樣有約束條件右邊常數(shù)值的百分之一百法則:對(duì)于所有變化的約束條件右邊常數(shù)值,當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之一百時(shí),則其對(duì)偶價(jià)格不變。其中bj
的
允許增加(減少)百分比的
定義同Ci
的允許增加(減少)
百分比一樣:為bj
的增加
量(減少量)除以bj的允許
增加量(減少量)的值。并不難
仍以例1為例來說明如何用約束條件右邊常數(shù)值的百分之一百法則進(jìn)行靈敏度分析。不妨設(shè)設(shè)備臺(tái)時(shí)數(shù)從300臺(tái)時(shí)增加為315臺(tái)時(shí),而原料A從400千克減少到390千克,原料B從250千克減少到240千克,這樣可以得到它們的允許增加(減少)百分比。因?yàn)椋杭s束下限當(dāng)前值上限
1250300325
2350400無上限
3200250300
設(shè)備臺(tái)時(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ī)劃的對(duì)偶價(jià)格不變。因?yàn)樵O(shè)備臺(tái)時(shí)數(shù)從300臺(tái)時(shí)增加為315臺(tái)時(shí),而原料A從400千克減少到390千克,原料B從250千克減少到240千克,所以從對(duì)偶價(jià)格可知50×15-0×10-50×10=250(元),則最大利潤增加了250元,為27750元。在使用百分之一百的法則進(jìn)行靈敏度分析時(shí),要注意以下四點(diǎn):1)、當(dāng)允許增加量(減少量)為無窮大時(shí),則對(duì)于任一個(gè)增加量(減少量),其允許增加(減少)百分比都看成零。例如,在表3-4中,約束條件2的常數(shù)項(xiàng)變動(dòng)范圍為350至+∞,如果原料A從400增加到410,則相當(dāng)于(410-400)/(無窮大-400)=0.2)、當(dāng)允許增加量(減少量)為0時(shí),則對(duì)于任一個(gè)增加量(減少量),其允許增加(減少)百分比都看成無窮大(相當(dāng)于該變量不能增加或減少)。
要打開思路!3)、百分之一百法則是判斷最優(yōu)解或?qū)ε純r(jià)格變不變的充分條件,但不是必要條件,也就是說當(dāng)其允許增加和減少百分比之和不超過100%時(shí),其最優(yōu)解或?qū)ε純r(jià)格不變,但是當(dāng)其允許增加和減少百分比之和超過100%時(shí),我們并不知道其最優(yōu)解或?qū)ε純r(jià)格變還是不變。4)、百分之一百法則不能應(yīng)用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時(shí)變化的情況,在這種情況下,只有重新求解。下面把例2輸入計(jì)算機(jī)來分析此線性規(guī)劃的計(jì)算機(jī)輸出,例2的數(shù)學(xué)模型如下:
目標(biāo)函數(shù):min2x1+3x2約束條件:x1+x2≥350,①x1≥125,②2x1+x2≤600③x1≥0,x2≥0上機(jī)計(jì)算得到如下結(jié)果:
從上面結(jié)果知道,當(dāng)購進(jìn)A原料250噸(X1=250),B原料100噸(X2=100)時(shí),使得購進(jìn)成本最低為800萬元。在松弛/剩余欄中,約束條件②的值為125,約束條件②表示對(duì)原料A的最低需求,由于此約束為大于等于,這樣可知原料A的剩余變量值為125(因?yàn)閤1=250)。同樣可知約束條件①(對(duì)所有原料的總需要量)的剩余變量值為零,約束條件③(加工時(shí)數(shù)的限制)的松弛變量值為零。
約束松弛/剩余變量對(duì)偶價(jià)格
10-4
21250
301
在對(duì)偶價(jià)格一欄中,可知約束條件①的對(duì)偶價(jià)格為-4萬元,也就是說如果把購進(jìn)原料A+原料B的下限從350噸增加到351噸,那么總成本將加大(因?yàn)閷?duì)偶價(jià)格為負(fù)值),由800萬元增加到800+4=804(萬元)了。當(dāng)然如果減少對(duì)原料A+原料B的下限,如把原料A+原料B的下限從350噸減少到349噸,那么總成本將得到改進(jìn),由800萬元減少到800-4=796萬元了??芍s束條件③(加工時(shí)數(shù))的對(duì)偶價(jià)格為1萬元,也就是說如果把加工時(shí)數(shù)從600小時(shí)增加到601小時(shí),則總成本將得到改進(jìn)(因?yàn)閷?duì)偶價(jià)格為正值),由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)變化時(shí),最優(yōu)解不變;當(dāng)C1不變時(shí),C2在2到+∞范圍內(nèi)變化時(shí),最優(yōu)解不變。常數(shù)項(xiàng)范圍:約束下限當(dāng)前值
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 執(zhí)業(yè)中藥西藥師課程設(shè)計(jì)
- 《堆垛機(jī)的機(jī)械結(jié)構(gòu)及控制系統(tǒng)設(shè)計(jì)研究》
- 《國有土地上房屋征收與補(bǔ)償制度法律問題研究》
- 產(chǎn)品設(shè)計(jì)的品牌價(jià)值體現(xiàn)
- 旅游安全須知匯報(bào)
- 《1980年代“現(xiàn)代派”論爭(zhēng)研究》
- 《從漫畫到真人-電影中“超級(jí)英雄”角色造型設(shè)計(jì)路徑研究》
- 幼兒教學(xué)的課程設(shè)計(jì)
- 兒童成長(zhǎng)環(huán)境對(duì)健康的影響
- 《城市二孩家庭長(zhǎng)子女教育的個(gè)案研究》
- 消防技術(shù)服務(wù)機(jī)構(gòu)培訓(xùn)課件
- 《音樂治療》課件
- (完整版)鏈傳動(dòng)習(xí)題
- 2024年華潤燃?xì)饧瘓F(tuán)招聘筆試參考題庫含答案解析
- 岸基維修協(xié)議
- 幼兒園家訪培訓(xùn)課件
- 住培學(xué)生教學(xué)查房課件
- (完整版)翻譯技巧翻譯方法
- 中醫(yī)護(hù)理技術(shù)操作平衡火罐技術(shù)操作流程與考核評(píng)分標(biāo)準(zhǔn)
- 2018變電站規(guī)范化建設(shè)可視化手冊(cè)
- 河北事業(yè)單位改革方案
評(píng)論
0/150
提交評(píng)論