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

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

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

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

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

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

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

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

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

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

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

獲利24×3x1

獲利16×4x2

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

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

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料無(wú)剩余時(shí)間無(wú)剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源“資源”剩余為零的約束為緊約束（有效約束）結(jié)果解釋第44頁(yè)，共68頁(yè)，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單位時(shí)“效益”的增量時(shí)間加1單位,利潤(rùn)增2影子價(jià)格35元可買(mǎi)到1桶牛奶，要買(mǎi)嗎？35<48,應(yīng)該買(mǎi)！

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

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時(shí)目標(biāo)系數(shù)允許變化范圍DORANGE(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é)果解釋第46頁(yè)，共68頁(yè)，2023年，2月20日，星期六結(jié)果解釋RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

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

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

4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)14003231013201341203511116030170023下料問(wèn)題1兩種標(biāo)準(zhǔn)1.原料鋼管剩余總余量最小第52頁(yè)，共68頁(yè)，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頁(yè)，共68頁(yè)，2023年，2月20日，星期六當(dāng)余料沒(méi)有用處時(shí)，通常以總根數(shù)最少為目標(biāo)目標(biāo)2（總根數(shù)）下料問(wèn)題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頁(yè)，共68頁(yè)，2023年，2月20日，星期六下料問(wèn)題2對(duì)大規(guī)模問(wèn)題，用模型的約束條件界定合理模式增加一種需求：5米10根；切割模式不超過(guò)3種。現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，過(guò)于復(fù)雜。決策變量xi~按第i種模式切割的原料鋼管根數(shù)(i=1,2,3)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長(zhǎng)的鋼管的數(shù)量第55頁(yè)，共68頁(yè)，2023年，2月20日，星期六滿足需求模式合理：每根余料不超過(guò)3米整數(shù)非線性規(guī)劃模型下料問(wèn)題2目標(biāo)函數(shù)（總根數(shù)）約束條件整數(shù)約束：xi,r1i,r2i,r3i,r4i(i=1,2,3)為整數(shù)第56頁(yè)，共68頁(yè)，2023年，2月20日，星期六增加約束，縮小可行域，便于求解原料鋼管總根數(shù)下界：

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

下料問(wèn)題2需求：4米50根，5米10根，6米20根，8米15根每根原料鋼管長(zhǎng)19米第57頁(yè)，共68頁(yè)，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頁(yè)，共68頁(yè)，2023年，2月20日，星期六例5-8(選址問(wèn)題)A，B，