線性規(guī)劃問題的求解

線性規(guī)劃問題的求解第1頁，共68頁，2023年，2月20日，星期六5.1一般線性規(guī)劃模型的建立與求解5.1.1基本理論線性規(guī)劃問題的標(biāo)準(zhǔn)形式是等約束的，用矩陣表示如下：一般線性規(guī)劃問題都可以通過引入松弛變量與剩余變量的方法化成標(biāo)準(zhǔn)形式。線性規(guī)劃模型的一般性質(zhì)：(1)比例性，每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻(xiàn)與該決策變量的取值成正比。(2)可加性，每個決策變量對目標(biāo)函數(shù)以及右端項的貢獻(xiàn)與其他決策變量的取值無關(guān)。(3)連續(xù)性，每個決策變量的取值都是連續(xù)的。比例性和可加性保證了目標(biāo)函數(shù)和約束條件對于決策變量的線性性質(zhì)，連續(xù)性則允許得到?jīng)Q策變量的實數(shù)最優(yōu)解。單純形算法的實質(zhì)：在保證可行(最小比值法則)的前提下，先在可行解上取一個頂點(diǎn)，判斷是否達(dá)到最優(yōu)解，如果沒有，則通過一定的規(guī)則(入基，旋轉(zhuǎn)等)到另一個更優(yōu)第2頁，共68頁，2023年，2月20日，星期六的頂點(diǎn)，如此迭代下去直到最優(yōu)，或者判斷不可行或者判斷無界為止。5.1.2應(yīng)用舉例例5-1(運(yùn)輸問題)兩個糧庫A1,A2,向三個糧站B1,B2,B3調(diào)運(yùn)大米，兩個糧庫現(xiàn)存大米分別為4t，8t，三個兩站至少需要大米分別為2t,4t,5t，兩個糧庫到三個糧站的距離(km)如下表，求使運(yùn)費(fèi)最低。B1B2B3庫存A1122484A23012248需求245解：(1)問題分析：總需求量為11t，小于總庫存量12t，所以問題可行。(2)從線性規(guī)劃的三個要素出發(fā)，決策變量：問題是各個糧倉向糧站調(diào)運(yùn)了多少大米，此調(diào)運(yùn)量就是決策變量。目標(biāo)函數(shù)：運(yùn)費(fèi)和運(yùn)量和距離有關(guān)系，即t*km最小，所以要將運(yùn)量與相應(yīng)的距離相乘然后使總和最小。約束條件：兩個糧庫的庫存量限制和三個糧站需求量的限制。第3頁，共68頁，2023年，2月20日，星期六(3)建立模型，設(shè)A1,A2分別向B1,B2,B3運(yùn)送大米x11,x12,x13,x21,x22,x23，則有：minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13<=4x21+x22+x23<=8x11+x21>=2x12+x22>=4x13+x23>=5x11,x12,x13,x21,x22,x23>=0(4)轉(zhuǎn)化成對應(yīng)的Lingo建模語言程序1，求解模型，結(jié)果如下頁圖示：第4頁，共68頁，2023年，2月20日，星期六第5頁，共68頁，2023年，2月20日，星期六通過選擇Lingo|Generate|Displaymodel將模型展開，方便查看求解報告的第三部分。相應(yīng)的添加的剩余變量或者松弛變量。第6頁，共68頁，2023年，2月20日，星期六程序改進(jìn)一、上面解法是一種傻瓜式的直接輸入法，適用于程序規(guī)模不大的問題，如果問題規(guī)模很大的話用這種方式很費(fèi)力，可以使用矩陣生成器來編寫程序2minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13+y1=4x21+x22+x23+y2=8x11+x21-y3=2x12+x22-y4=4x13+x23-y5=5x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5>=0轉(zhuǎn)換成Lingo語言如下所示：第7頁，共68頁，2023年，2月20日，星期六第8頁，共68頁，2023年，2月20日，星期六注：1、寫程序要習(xí)慣給程序用title命名2、為了方便查看報告，用行號區(qū)分約束3、此程序的格式可以固定為標(biāo)準(zhǔn)形式的求解模式。程序改進(jìn)三：可以減少引入的變量個數(shù)，將模型修改為下面的形式minf=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t.x11+x12+x13<=4x21+x22+x23<=8-x11-x21<=-2-x12-x22<=-4-x13-x23<=-5x11,x12,x13,x21,x22,x23>=0寫成lingo語言如下所示：第9頁，共68頁，2023年，2月20日，星期六第10頁，共68頁，2023年，2月20日，星期六注：1、改程序把不等式約束全部轉(zhuǎn)化為小于等于約束，是為了將約束可以寫到一個循環(huán)語句中實現(xiàn)，如果還有等是約束的話，則要在寫一個循環(huán)語句來控制約束。2、當(dāng)程序比較大的時候，一般將約束按性質(zhì)進(jìn)行分類程序改進(jìn)四：將約束進(jìn)行分類，代碼如下：第11頁，共68頁，2023年，2月20日，星期六注：1、在進(jìn)行調(diào)試程序時，可以用!號某些語句屏蔽，縮小尋找出錯的范圍。2、可以編寫程序邊運(yùn)行，保證每行書寫都是正確的3、常見的出錯情況有：(1)定義了多個長度一樣的集合，而在使用中區(qū)分不明確；(2)定義了同名的屬性；(3)漏掉了括號；(4)分號不是英文半角；(5)使用的字母沒有定義；(6)循環(huán)語句中元素下標(biāo)顛倒或者不明；(7)約束錯誤變成不可行或者無界；(8)關(guān)系運(yùn)算符誤用成邏輯運(yùn)算符；(9)函數(shù)調(diào)用錯誤等等…第12頁，共68頁，2023年，2月20日，星期六例5-2（階段生產(chǎn)問題）某公司產(chǎn)品最大生產(chǎn)能力為10000單位，每單位存儲費(fèi)2元，預(yù)定的銷售量與單位成本如下表所示：月份單位成本銷售量17060002717000380120004766000求一生產(chǎn)計劃，使(1)滿足需求；(2)不超過生產(chǎn)能力；(3)成本(生產(chǎn)成本與存儲費(fèi)之和最低)問題分析：這是一個多階段生產(chǎn)計劃問題，設(shè)計多階段存儲，只需要制定1~4月份的生產(chǎn)計劃，不妨假定1月初無庫存，4月底賣完，當(dāng)月生產(chǎn)的不作為當(dāng)月的庫存，庫存量無限制。模型建立（1）：設(shè)xi為第i月產(chǎn)量，di為銷售量，ei為存儲費(fèi)，ci為單位成本，則目標(biāo)生產(chǎn)成本為:第13頁，共68頁，2023年，2月20日，星期六第j月到j(luò)+1月的庫存量(記作第j+1月的庫存量)應(yīng)該是1月到j(luò)月的總產(chǎn)量減去1月到j(luò)月的總銷售量，即：總的庫存費(fèi)用為：總成本為：即求總成本的最小值。約束條件1：如果每個月都有非負(fù)的存儲量，顯然滿足要求，可用約束：第14頁，共68頁，2023年，2月20日，星期六約束條件3：產(chǎn)量限制，0<=xi<=10000。綜上，建立如下數(shù)學(xué)模型：約束條件2：4個月的總產(chǎn)量等于總需求量即：轉(zhuǎn)成相應(yīng)的Lingo語言如下：第15頁，共68頁，2023年，2月20日，星期六第16頁，共68頁，2023年，2月20日，星期六模型改進(jìn)(2)：引入庫存變量，再利用庫存平衡方程使模型更加流暢簡潔。設(shè)xi為第i個月的產(chǎn)量，di為銷售量，ei為存儲費(fèi)，ci為單位成本，設(shè)第i個月的庫存為si,則：程序編寫如下：第17頁，共68頁，2023年，2月20日，星期六模型改進(jìn)(3)：將該模型轉(zhuǎn)化成運(yùn)輸問題。設(shè)xij表示第i個月生產(chǎn)的產(chǎn)品在第j個月賣出去的數(shù)量，cij表示第i個月生產(chǎn)的產(chǎn)品在第j月賣出去時的生產(chǎn)成本與存儲成本之和，第18頁，共68頁，2023年，2月20日，星期六dj表示第j月的銷售量，則生產(chǎn)月生產(chǎn)的產(chǎn)品在需求月賣出時單位總成本如下表所示：需求月1需求月2需求月3需求月4產(chǎn)量生產(chǎn)月17072747610000生產(chǎn)月271737510000生產(chǎn)月3808210000生產(chǎn)月47610000銷量60007000120006000建立模型如下：第19頁，共68頁，2023年，2月20日，星期六相應(yīng)的Lingo程序如下：第20頁，共68頁，2023年，2月20日，星期六例5-3（連續(xù)投資問題）某部門在今后5年內(nèi)考慮給下列項目投資，已知：(1)項目A，從第1年到第4年每年初要投資，次年末回收本利1.15；(2)項目B，第3年初投資，到第5年末回收本利1.25，最大投資4萬元;(3)項目C，第2年初投資，到第5年末回收本利1.40，最大投資3萬元；(4)項目D，每年初購買國債，當(dāng)年末回收本利1.06;該部門現(xiàn)有資金10萬元，問應(yīng)如何投資到第5年末總資本最大。問題分析：將可能的投資情況設(shè)為變量，如下表所示第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx3CDx1Dx2Dx3Dx4Dx5D因為具有項目D，所以可以認(rèn)為該部門每年都把自己全部投出去，而且年末的總資本等于第二年初的總投資額。由此可建立模型如下：第21頁，共68頁，2023年，2月20日，星期六轉(zhuǎn)換成Lingo程序如下所示：第22頁，共68頁，2023年，2月20日，星期六第23頁，共68頁，2023年，2月20日，星期六5.2靈敏性分析與影子價格5.2.1靈敏性分析例5-4(生產(chǎn)計劃問題)某工廠計劃安排生產(chǎn)III兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備臺時及A,B兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的定額見下表所示：產(chǎn)品I產(chǎn)品II最大資源量設(shè)備128臺原材料A4016kg原材料B0412kg單位產(chǎn)品利潤23求：(1)怎么樣安排生產(chǎn)使得工廠利潤最大？(2)產(chǎn)品I的單位利潤降低到1.8萬元，要不要改變生產(chǎn)計劃，如果降低到1萬元呢？(3)產(chǎn)品II的單位利潤增大到5萬元，要不要改變生產(chǎn)計劃？(4)如果產(chǎn)品I,II的單位利潤同時降低了1萬元，要不要改變生產(chǎn)計劃？第24頁，共68頁，2023年，2月20日，星期六建立模型：用x1,x2分別表示計劃生產(chǎn)產(chǎn)品III的數(shù)量，可建立如下模型編寫lingo程序如下：第25頁，共68頁，2023年，2月20日，星期六程序執(zhí)行結(jié)果：通過執(zhí)行結(jié)果對問題進(jìn)行分析：問題1：安排生產(chǎn)產(chǎn)品I為4個單位，II為2個單位，最大利潤為14萬元。靈敏性分析：打開LINGO中的靈敏性分析開關(guān)，LINGO|Options|GeneralSolver|DualComputations|PricesandRanges分析結(jié)果通過點(diǎn)擊Lingo|Range命令獲得第26頁，共68頁，2023年，2月20日，星期六說明1、(1)紅框內(nèi)的部分是對目標(biāo)函數(shù)進(jìn)行的靈敏性分析，第一列是變量，第二列是對應(yīng)的系數(shù)，第三列是允許增加量，第四列是允許減少量，允許增加和允許減少都是在當(dāng)前系數(shù)基礎(chǔ)上改變的。在其他變量系數(shù)都不變的情況下有：當(dāng)x1在(2-0.5,2+∞)=(1.5,∞)之間變化時,最優(yōu)解不變；當(dāng)x2在(3-3,3+1)=(0,4)之間變化時，最優(yōu)解不變。第27頁，共68頁，2023年，2月20日，星期六問題2：

產(chǎn)品I的單位利潤降低到1.8萬元，在(1.5,∞)之間，所以不改變生產(chǎn)計劃；而降低到1萬元，則需要重新制定生產(chǎn)計劃；問題3：5萬不在(0,4)范圍內(nèi)，故要重新制定生產(chǎn)計劃。修改程序之后運(yùn)行結(jié)果如下：問題4：

因為兩個系數(shù)同時發(fā)生變化，所以只能更改程序的數(shù)據(jù)，重新運(yùn)行。運(yùn)行結(jié)果和靈敏性分析結(jié)果如下：第28頁，共68頁，2023年，2月20日，星期六第29頁，共68頁，2023年，2月20日，星期六說明2、

紅框內(nèi)所示為保持最優(yōu)基不變的約束右端項的變化范圍，即原材料A的量在(8-4，8+2)=(4,10)，原材料B的量在(16-8,16+16)=(8,32)，設(shè)備臺時在(12-4,12+∞)=(8,∞)內(nèi)變化時，最優(yōu)基保持不變。第30頁，共68頁，2023年，2月20日，星期六5.2.2對偶問題兩個線性規(guī)劃問題：稱為對稱形式的對偶問題(dualproblem),互為對偶問題的(I)和(II)一個稱為原問題，一個稱為原問題的對偶問題。稱對偶問題的最優(yōu)解為原問題約束條件的影子價格(shadowprice)1、一對對稱形式的對偶問題有如下的對應(yīng)關(guān)系：(1)若一個模型為目標(biāo)求極大，約束為小于等于的不等式，則它的對偶模型為目標(biāo)求極小，約束為大于等于的不等式，即”max<=”對應(yīng)”min>=”第31頁，共68頁，2023年，2月20日，星期六(2)從約束系數(shù)的矩陣看，一個模型為A，一個模型為AT，一個模型為m個約束，n個變量，另一個則為n個約束，m個變量。(3)從數(shù)據(jù)b和c的位置看，在兩個規(guī)劃模型中兩者互換。(4)兩個模型中的變量皆非負(fù)。2、非對稱形式的對偶規(guī)劃一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。對于非對稱形式的規(guī)劃，可以按照下面的對應(yīng)關(guān)系直接給出其對偶規(guī)劃。（1）將模型統(tǒng)一為“max，≤”或“min，≥”的形式，對于其中的等式約束按下面（2）、（3）中的方法處理；（2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負(fù)限制；（3）若原規(guī)劃的某個變量的值沒有非負(fù)限制，則在對偶問題中與此變量對應(yīng)的那個約束為等式。第32頁，共68頁，2023年，2月20日，星期六下面對關(guān)系（2）作一說明。對于關(guān)系（3）可以給出類似的解釋。設(shè)原規(guī)劃中第一個約束為等式：a11x1+…+a1nxn=b1那么，這個等式與下面兩個不等式等價：則原規(guī)劃模型可以寫成如下形式：第33頁，共68頁，2023年，2月20日，星期六此時已轉(zhuǎn)化為對稱形式，可以直接寫出其對偶問題：這里，把y1看作是y1=y1’-y1’’，于是y1沒有非負(fù)限制，關(guān)系（2）的說明完畢。對偶定理：若互為對偶問題的線性規(guī)劃問題(I)和(II)中有一個最優(yōu)解，則另一個必有最優(yōu)解，且目標(biāo)函數(shù)值相同。第34頁，共68頁，2023年，2月20日，星期六例5-5(生產(chǎn)決策問題)某工廠可以用A，B兩種原料生產(chǎn)I,II,III三種產(chǎn)品，每種產(chǎn)品需要同時用兩種原料，有關(guān)數(shù)據(jù)如下表(單位消耗與資源限制)：產(chǎn)品I產(chǎn)品II產(chǎn)品III現(xiàn)有原料/t原料A2127原料B13211單位產(chǎn)品利潤/萬元231求：(1)若目前市場上原料A的實際價格為0.5萬元/t，工廠應(yīng)如何決策？(2)若目前市場上原料B的實際價格為0.8萬元/t，工廠應(yīng)如何決策？解：建立模型，設(shè)x1,x2,x3分別表示I，II，III的生產(chǎn)量，則模型如下：對偶問題第35頁，共68頁，2023年，2月20日，星期六模型討論：若把y1,y2當(dāng)作原料A，B的定價，用兩個單位的A，1個單位的B，若生產(chǎn)產(chǎn)品I只能賺2萬元，現(xiàn)在考慮把資源拿到市場上賣，定價y1,y2,使得2y1+y2≥2,也就是一定比生產(chǎn)產(chǎn)品I賺得多。產(chǎn)品II，III同理。亦即對偶問題的約束條件保證了資源直接在市場上出售一定不會比生產(chǎn)產(chǎn)品獲得的利潤低，另一方面，為了增強(qiáng)出售資源的市場競爭力，定價希望低一些，定價的目標(biāo)是在比生產(chǎn)產(chǎn)品獲得更多利潤的前提下的最小利潤，這個定價模型就是對偶問題。如果把資源A的量由7增加到8，會導(dǎo)致什么結(jié)果呢？影子價格：在最有情況下，y1的值就是資源A的影子價格，所以要把影子價格與資源A的市場價格做比較，如果影子價格大于市場價格，考慮出售部分資源以獲得更大利潤，否則，則從市場買進(jìn)該資源。第36頁，共68頁，2023年，2月20日，星期六影子價格的經(jīng)濟(jì)意義：在資源得到最優(yōu)配置，使總效益最大時，該資源投入量每增加一個單位所帶來總收益的增加量。影子價格是一種靜態(tài)的資源最優(yōu)配置價格，不能表現(xiàn)資源在不同時期動態(tài)配置時的最優(yōu)價格，只反映某種資源的稀缺程度和資源與總體積極效益之間的關(guān)系，不能代替資源本身的價值。程序編寫：執(zhí)行結(jié)果如下：第37頁，共68頁，2023年，2月20日，星期六說明：從紅框部分知道，A的影子的價格為0.6，B的影子價格為0.8，松弛變量的值都是0，說明約束是緊約束(約束取等號)，即資源沒有剩余，影子價格有意義必須是緊約束。影子價格是對應(yīng)最優(yōu)基來說的，如果約束的改變使得最優(yōu)基發(fā)生改變，當(dāng)前的影子價格也就沒有任何意義了。通過對右端項的靈敏性分析：第38頁，共68頁，2023年，2月20日，星期六在最優(yōu)基不變時，A,B的右端項變化范圍分別為(4.67,22)和(3.5,21)對問題(1)0.5<0.6,應(yīng)該購進(jìn)原料A，擴(kuò)大生產(chǎn)能力，最大購進(jìn)15t，利潤增加(0.6-0.50*15=1.5萬元對于問題(2),0.8>0.6，應(yīng)該售出部分原料將使利潤更大，最大售出量為3.33t,利潤將會增加(0.8-0.6)*3.33=0.66萬元第39頁，共68頁，2023年，2月20日，星期六例5-6(奶制品的加工問題)1桶牛奶3公斤A1

12小時8小時4公斤A2

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

制訂生產(chǎn)計劃，使每天獲利最大(1)35元可買到1桶牛奶，買嗎？若買，每天最多買多少?(2)可聘用臨時工人，付出的工資最多是每小時幾元?(3)A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計劃？每天：第40頁，共68頁，2023年，2月20日，星期六1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

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

獲利24×3x1

獲利16×4x2

原料供應(yīng)勞動時間加工能力決策變量目標(biāo)函數(shù)每天獲利約束條件非負(fù)約束線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天第41頁，共68頁，2023年，2月20日，星期六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=220桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。模型求解第42頁，共68頁，2023年，2月20日，星期六模型求解reducedcost值表示當(dāng)該非基變量增加一個單位時（其他非基變量保持不變）目標(biāo)函數(shù)減少的量(對max型問題)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解為：為了使該非基變量變成基變量，目標(biāo)函數(shù)中對應(yīng)系數(shù)應(yīng)增加的量第43頁，共68頁，2023年，2月20日，星期六OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋第44頁，共68頁，2023年，2月20日，星期六OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋最優(yōu)解下“資源”增加1單位時“效益”的增量時間加1單位,利潤增2影子價格35元可買到1桶牛奶，要買嗎？35<48,應(yīng)該買！

聘用臨時工人付出的工資最多每小時幾元？2元！第45頁，共68頁，2023年，2月20日，星期六RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標(biāo)系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

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

x2系數(shù)范圍(48,72)A1獲利增加到30元/千克，應(yīng)否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋第46頁，共68頁，2023年，2月20日，星期六結(jié)果解釋RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加5335元可買到1桶牛奶，每天最多買多少？最多買10桶？(目標(biāo)函數(shù)不變)注意:充分但可能不必要第47頁，共68頁，2023年，2月20日，星期六5.3整數(shù)線性規(guī)劃例5-7(下料問題)做100套鋼架，用長為2.9m,2.1m,1.5m的元鋼各一根，已知原料長為7.4m，問如何下料，所用最?。繂栴}分析：每一種下料方式用了多少根鋼材，合理的下料方式是剩余料頭的長度不能超過最短原料需求(1.5m)，可首先利用lingo搜索出全部的下料方式，然后從中篩選出符合條件的方式：模型建立：設(shè)xi為按第i種方式下料的根數(shù)，i=1,…,8，建立如下模型：x1x8第48頁，共68頁，2023年，2月20日，星期六說明：(1)目標(biāo)函數(shù)有兩種取法，一是剩余的料最少，二是所用原料的根數(shù)最少。(2)決策變量限制取整數(shù)。(3)這種全方式設(shè)變量的模型只適合小型下料問題，大型下料問題或者對下料方式有限制的問題將不再合適。程序編寫：第49頁，共68頁，2023年，2月20日，星期六補(bǔ)充例5-7(下料問題2)問題1.如何下料最節(jié)省?問題2.客戶增加需求：原料鋼管:每根19米4米50根6米20根8米15根客戶需求節(jié)省的標(biāo)準(zhǔn)是什么？由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?米10根第50頁，共68頁，2023年，2月20日，星期六按照客戶需要在一根原料鋼管上安排切割的一種組合。

切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸余料3米8米1根8米1根下料問題第51頁，共68頁，2023年，2月20日，星期六為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)?。亢侠砬懈钅Ｊ?.所用原料鋼管總根數(shù)最少模式

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023下料問題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小第52頁，共68頁，2023年，2月20日，星期六xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,…7)約束滿足需求決策變量

目標(biāo)1（總余量）按模式2切割12根,按模式5切割15根，余料27米

模式4米根數(shù)6米根數(shù)8米根數(shù)余料14003231013201341203511116030170023需求502015最優(yōu)解：x2=12,x5=15,

其余為0；最優(yōu)值：27整數(shù)約束：xi為整數(shù)第53頁，共68頁，2023年，2月20日，星期六當(dāng)余料沒有用處時，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）下料問題1約束條件不變最優(yōu)解：x2=15,x5=5,x7=5,其余為0；最優(yōu)值：25。xi為整數(shù)按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米雖余料增加8米，但減少了2根與目標(biāo)1的結(jié)果“共切割27根，余料27米”相比第54頁，共68頁，2023年，2月20日，星期六下料問題2對大規(guī)模問題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過3種?，F(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過于復(fù)雜。決策變量xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量第55頁，共68頁，2023年，2月20日，星期六滿足需求模式合理：每根余料不超過3米整數(shù)非線性規(guī)劃模型下料問題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)第56頁，共68頁，2023年，2月20日，星期六增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

特殊生產(chǎn)計劃：對每根原料鋼管模式1：切割成4根4米鋼管，需13根；模式2：切割成1根5米和2根6米鋼管，需10根；模式3：切割成2根8米鋼管，需8根。原料鋼管總根數(shù)上界：31模式排列順序可任定

下料問題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長19米第57頁，共68頁，2023年，2月20日，星期六LINGO求解整數(shù)非線性規(guī)劃模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式1：每根原料鋼管切割成3根4米和1根6米鋼管，共10根；模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根；模式3：每根原料鋼管切割成2根8米鋼管，共8根。原料鋼管總根數(shù)為28根。第58頁，共68頁，2023年，2月20日，星期六例5-8(選址問題)A，B，