同濟(jì)大學(xué)線性規(guī)劃教案

線性規(guī)劃標(biāo)準(zhǔn)型線性規(guī)劃(LP):minf=c1X1+……cjXj……+cnXn=ΣcjXjs.ta11x1+…+a1jxj+……+a1nxn=b1…ai1x1+…+aijxj+……+ainxn=bi…………am1x1+…+amjxj+……+amnxn=bmxj≥0,j=1,……,n.C=X=b=A=minf=Xs.tAX=bx≥0minf=c1X1+……cjXj……+cnXn=ΣcjXjs.tai1x1+…+aijxj+……+ainxn=bii=1,……,mxj≥0,j=1,……,n.在幾何直觀上告訴我們，若兩個(gè)變量的線性規(guī)劃問(wèn)題的最優(yōu)解存在且唯一，則最優(yōu)解必為可行域K的一個(gè)頂點(diǎn)，而K為凸多邊形．對(duì)于目標(biāo)函數(shù)求min的兩個(gè)變量的線性規(guī)劃，根據(jù)目標(biāo)函數(shù)的等值線與可行域K的各種關(guān)系，我們可以得知它的解可能會(huì)出現(xiàn)以下幾種情況．最優(yōu)解存在且唯一．這時(shí)，K是一個(gè)非空的、有界或無(wú)界的凸多邊形，最優(yōu)解X*必為K的一個(gè)頂點(diǎn)，最優(yōu)值f*為一個(gè)有限值。(2)最優(yōu)解x*存往但不唯一．這時(shí)，K是一個(gè)非空、有界或無(wú)界的凸多邊形，最優(yōu)值f*是一個(gè)有限值，f的等值線c1x1+c2x2=f*與K之交是K的一個(gè)邊界，網(wǎng)此該邊界上的點(diǎn)都為最優(yōu)解；但是，我們至少可以取到K的一個(gè)頂點(diǎn)為最優(yōu)解。(3)可行解存在但目標(biāo)函數(shù)值在K內(nèi)無(wú)下界(簡(jiǎn)稱線性規(guī)劃無(wú)下界)．這時(shí)，K必是一個(gè)非空無(wú)界的凸多邊形，最優(yōu)解不存在，minf→∞(4)可行解不存在(或稱線性規(guī)劃不可行)．這時(shí)，K為空集。通過(guò)以上各種情況的分析，關(guān)于2個(gè)變量的線性規(guī)劃的解，我們可以得到以下兩點(diǎn)結(jié)論：①如果K≠(空集)，則K必是x1ox2坐標(biāo)平面第一象限內(nèi)的一個(gè)凸多邊形(今后，在線性規(guī)劃理論中，稱為凸集)，K的頂點(diǎn)一定存在．②如果最優(yōu)解X*存在，則最優(yōu)解中至少有一個(gè)為K的頂點(diǎn)．（請(qǐng)學(xué)生看書(shū)第9頁(yè)，請(qǐng)教師朗讀書(shū)上這些結(jié)論）§1．3基本可行解非基本變量（獨(dú)立變量）基本變量（非獨(dú)立變量）基本解基本可行解基B—若│B│≠O，稱B為（LP）的一個(gè)基。Minf=c1X1+……cjXj……+cnXn=ΣcjXjs.tai1x1+…+aijxj+……+ainxn=biI=1,……,mxj≥0,j=1,……,n.令=b=X=A=B=minf=Xs.tAX=bx≥0A=IB對(duì)應(yīng)的基本矩陣B：B=矩陣B為基本變量xB,…，xBm在A矩陣中的系數(shù)列向量。ai1x1+…+aijxj+……+ainxn=biI=1,……,mw+c1X1+……cjXj……+cnXn=0當(dāng)IB給定時(shí)，將上述方程組變換為典型方程組：xBi+0?w+……+yijXj+……=,i=1,……,mw+……+rjXj+……=–f。 +=i,w+rjXj=–f。-f（X）+rjXj=–f。=f（X。）f（X）=f（X。）+rjxj§1．4單純形法單純形法的基本步驟是：求(LP)的初始基本可行解X。，并將(LP)的有關(guān)信息制成表格(稱為單純形表)。、判別X。是否為最優(yōu)解?為此，需要給出一個(gè)基本可行解是否為最優(yōu)解的判別準(zhǔn)則。3、若X。不是最優(yōu)解，則應(yīng)另求基本可行解xˊ，且使CTXˊCTX。(至少CTXˊ≤CTX。)。同時(shí)，我們由X。相應(yīng)的單純形表給出xˊ相應(yīng)的單純形表。（該步驟稱為轉(zhuǎn)軸）(4)當(dāng)xˊ不是最優(yōu)解時(shí)，視xˊX。，重復(fù)上述步驟，直至(LP)求得最優(yōu)解或判定f在K內(nèi)無(wú)下界。定理1-2（3）如果T（B）中存在rt<0（t∈ID），且對(duì)于i=1，…，m均有yit≤0，則（LP）的目標(biāo)函數(shù)在可行域上無(wú)下界?！?．5單純形表的矩陣描述我們前面已經(jīng)說(shuō)明過(guò)：ai1x1+…+aijxj+……+ainxn=bii=1,……,mw+c1x1+……cjxj……+cnxn=0當(dāng)IB給定時(shí)，將上述方程組變換為典型方程組：xBi+0?w+……+yijxj+……=,i=1,……,mw+……+rjxj+……=–f。這些信息就構(gòu)成了單純形表。即 +=w+rjXj=–f。若是記：yj=(y1j,…,yij,…ymj)T，=(由掛圖的單純形表中得到， XB+=,下面我們來(lái)推導(dǎo)和yj以及rj的公式。給定IB和基本矩陣B（│B│≠O），假設(shè)：A=[B，D]AX=b化成[B，D]=bBXB+DXD=b，兩邊左乘B-1XB+B-1DXD=B-1bXB+B-1[…，A.j,…]=B-1bXB+=B-1b進(jìn)行比較可得：yj=B-1A.j,=B-1b由w+……+rjXj+……=–f。得：w+rjXj=–f。現(xiàn)在我們來(lái)推導(dǎo)rj的公式。得到由w+c1x1+……+cjxj……+cnxn=0即w+CTX=0，（結(jié)合掛圖講解CBT和CDT）w+[CBT，CDT]=0，即w+CBTXB+CDTXD=0由XB+=，得XB=-代入：得到rj=cj-CBTyj=cj-CBTB-1A.jf。=CBT=CBTB-1b請(qǐng)同學(xué)看書(shū)27頁(yè)………………yj=B-1A.j=B-1brj=cj-CBTyj=cj-CBTB-1A.jf。=CBT=CBTB-1b§1．7大M法和兩階段法1．7．1大M法minf=s.t.i=1,…,m,xj≥0,j=1,…,n.引進(jìn)松弛變量xn+1,…,xn+m,minf=s.t.i=1,…,m,xj≥0,j=1,…,n我們?nèi)B={n+1，…，n+m}，由于b≥0,可以很方便地取得一個(gè)初始基本可行解。如果我們的規(guī)劃是下列形式，問(wèn)題就變得復(fù)雜：minf=s.t.≥（=，≤）bi，i=1,…,m,xj≥（=，≤）0,j=1,…,n.將它標(biāo)準(zhǔn)化后，不能夠很快地觀察出一個(gè)初始基本可行解。例1-14minf=-x1-3x2+x3s.t.x1+x2+2x3=4-x1+2x2+x3=4xj≥0,j=1,2，3.人工變量x4和x5x1+x2+2x3+x4=4-x1+2x2+x3+x5=4minf=-x1-3x2+x3+Mx4+Mx5s.t.x1+x2+2x3+x4=4-x1+2x2+x3+x5=4xj≥0,j=1，…，5.（LPM）C-1-31MMCBXBx1x2x3x4x5Mx4x511210-1210144Mr-1-3-3M1-3M00-8MC-1-31MMCBXBx1x2x3x4x5Mx4x511210-1210144Mr-1-3-3M1-3M00-8MXBx1x2x3x4x5x4x23/203/21-1/2-1/211/201/222r-1.5M-2.50-1.5M+2.501.5M+1.5-2M+6Y11=3/2作為轉(zhuǎn)軸元素，帶上括弧，得下表：XBx1x2x3x4x5X1X21012/3-1/30111/31/34/38/3r005M+（5/3）M+（2/3）28/3最優(yōu)解X*=（4/3，8/3，0）T最優(yōu)值f*=-28/3。15minf=-3x1-2x2s.t.2x1+x2≤23x1+4x2≥12xj≥0,j=1,2.其（LPM）為：minf=-3x1-2x2+Mx5s.t.2x1+x2+x3=23x1+4x2–x4+x5=12xj≥0,j=1,…，5.解：C-3-200MCBXBx1x2x3x4x50Mx3x52（1）100340-11212r-3M-3–4M-20M0-12MCBXBx1x2x3x4x5-2MX2x521100-50-4-1124r5M+104M+2M0-4M+4線性規(guī)劃不可行。例1-16minf=2x1-x2s.t.2x1+3x2≥6x1-x2≤6xj≥0,j=1,2.其（LPM）為：minf=2x1-x2+Mx5s.t.2x1+3x2-x3+x5=6x1-x2+x4=6xj≥0,j=1,…，5.解：C2-100MCBXBx1x2x3x4x5M0X5X42（3）-1011-101066r2-2M–1-3MM00-6MCBXBx1x2x3x4x5-10X2X42/31-1/301/35/30-1/311/328r8/30-1/30M+1/32R3=-1/3<0，最小比值準(zhǔn)則失效可知（LPM）無(wú)下界,又人工變量x5=0，因此原線性規(guī)劃無(wú)下界。例1-17minf=-x1+x2+x3-x4s.t.x1-x2-3x3-2x4=2x1+x2-2x4=1xj≥0,j=1,…,4.minf=-x1+x2+x3-x4+Mx5+Mx6s.t.x1-x2-3x3-2x4+x5=2x1+x2-2x4+x6=1xj≥0,j=1,…,6.C-111-1MMCBXBx1x2x3x4x5x6MMx5x61-1-3-210110-20121r-2M-113M+14M-100-3MC-111-1MMCBXBx1x2x3x4x5x6M-1X5X10-2-301-1110-20111r02M+23M+1-302M+1-M+1r4=-3<0，最小比值準(zhǔn)則失效可知（LPM）無(wú)下界。又由于x5>0，（LP）無(wú)可行解。標(biāo)準(zhǔn)型線性規(guī)劃：minf=s.t.=bi，i=1,…,m,xj≥0,j=1,…,n.引進(jìn)m個(gè)人工變量xn+1,…,xn+m：minf=+s.t.i=1,…,m,xj≥0,j=1,…,nxn+i≥0,i=1,…,m我們?nèi)B={n+1，…，n+m}，由于b≥0,可以很方便地取得一個(gè)初始基本可行解：XB=b，XD=0。記XN=（x1，……，n）T，XM=（xn+1，……，xn+m）T，我們得下述定理。(結(jié)合書(shū)來(lái)進(jìn)行總結(jié))§1．8線性規(guī)劃應(yīng)用舉例某工廠車(chē)間有30個(gè)工人，每人每周工作5天，車(chē)間每天開(kāi)工，每天需要的人數(shù)是波動(dòng)的。周i需要人數(shù)為ai（i=1，2，3，4，5，6），周日需要人數(shù)為a7。現(xiàn)車(chē)間調(diào)度科希望制定一個(gè)計(jì)劃，以確保休息日不連續(xù)的工人數(shù)最少，為此，準(zhǔn)備建立一個(gè)線性規(guī)劃模型。請(qǐng)你回答下列三個(gè)問(wèn)題：你準(zhǔn)備設(shè)多少個(gè)變量？請(qǐng)列出。列出目標(biāo)函數(shù)。在周一至周日所需人數(shù)的七個(gè)約束條件中，請(qǐng)列出周一所需人數(shù)18人這個(gè)約束條件。設(shè)xij（共21個(gè)）為在第i天、第j天休息的工人數(shù)。x13x14x15x16x12x17x24x25x26x27x21x23x35x36x37x31x32x34x41x42x46x47x43x45x51x52x53x57x56x54x61x62x63x64x65x67x72x73x74x75x76x71Minf=x13+x14+x15+x16+x24+x25+x26+x27x35+x36+x37+x46+x47+x57s．t．x24+x25+x26+x27+x23+x34+x35+x36+x37+x45+x46+x47+x57+x56+x67≥18例1—23(生產(chǎn)計(jì)劃問(wèn)題)某工廠明年根據(jù)合同，每個(gè)季度末向銷售公司提供產(chǎn)品，有關(guān)信息如表。若當(dāng)季生產(chǎn)的產(chǎn)品過(guò)多，季末有積余，則一個(gè)季度每積壓一噸產(chǎn)品需支付存貯費(fèi)0．2萬(wàn)元?，F(xiàn)該廠考慮明年的最佳生產(chǎn)方案，使該廠在完成合同的情況下，全年的生產(chǎn)費(fèi)用最低。試建立線性規(guī)劃模型。季度j生產(chǎn)能力aj(噸)生產(chǎn)成本dj（萬(wàn)元/噸）需求量bj(噸)13015.02024014.02032015.33041014.810(1)設(shè)工廠第j季度生產(chǎn)產(chǎn)品xj噸。(2)設(shè)第j季度工廠生產(chǎn)的產(chǎn)品為xj噸，第j季度初存貯的產(chǎn)品為yj噸(顯然y1=0)。(3)設(shè)第i季度生產(chǎn)而用于第j季度末交貨的產(chǎn)品數(shù)量為xij噸。例1—24(多階段投資問(wèn)題)某公司現(xiàn)有資金30萬(wàn)元可用于投資，5年內(nèi)有下列方案可供采納：1#方案在年初投資1元，2年后可收回1．3元；2#方案在年初投資1元，3年后可收回1．45元；3#方案：僅在第1年年初有一次投資機(jī)會(huì)。每投資1元，4年后可收回1．65元；4#方案：僅在第2年年初有一次投資機(jī)會(huì)。每投資1元，4年后可收回1．7元；5#方案：在年初貸給其他企業(yè)，年息為10%，第二年初可收回。每年年初投資所得收益及貸款本金利息也可用作安排。問(wèn)該公司在5年內(nèi)怎樣使用資金，才能在第6年年初擁有最多資金?解：設(shè)Xij為i#方案在第j年年初所使用的資金數(shù)。年份（年初）1234561.31.451.651.11.31.451.71.11.31.451.11.31.11.1設(shè)Xij為i#方案在第j年年初所使用的資金數(shù)。年份（年初）123456x111.3x11x121.45x12x131.65x13x151.1x15x211.3x21x221.45x22x241.7x24x251.1x25x311.3x31x321.45x32x351.1x35x411.3x41x251.1x25X551.1X55x11+x12+x13+x15=300000x21+x22+x24+x25=1.1x15例1-22（混料問(wèn)題）某糖果廠用原料A、B和C按不同比率混合加工而成甲、乙、丙三種糖果(假設(shè)混合加工中不損耗原料)。原料A、B、C在糖果甲、乙、丙中的含量、原料成本、加工成本、原料限量及糖果售價(jià)如表所示。問(wèn)該廠對(duì)這三種糖果各生產(chǎn)多少公斤，使得到的利潤(rùn)最大?含量j#糖果原料供應(yīng)量（公斤）成本(元/公斤)甲（1#）乙（2#）丙（3#）i#原料A≥60%≥15%20002.50B25002.00C≤20%≤60%≤70%22001.70加工成本(元/公斤)2.001.801.60售價(jià)(元/公斤)12108設(shè)i#原料在j#糖果中的用量為Xij公斤。23（下料問(wèn)題）用長(zhǎng)度為7.4米的圓鋼截?cái)喑芍圃炷撤N機(jī)床所以需要的3個(gè)軸坯，長(zhǎng)度分別為2.9米、2.1米和1.5米?，F(xiàn)在要制造100臺(tái)機(jī)床，問(wèn)最少要圓鋼多少根？軸坯長(zhǎng)度截取方法需要量（米）x1x2x3x4x5x6x72.92.11.5211001002023111032013100100100剩余料頭長(zhǎng)度（米）0.10.300.21.10.90.8習(xí)題一第7題課堂練習(xí)某企業(yè)年初有現(xiàn)金30萬(wàn)元。該企業(yè)有兩個(gè)方案可供選擇：年初貸給其他企業(yè)，年息18%，第二年年初可收回；本企業(yè)投資擴(kuò)大再生產(chǎn)，若年初投資一定金額，則第二年還需繼續(xù)投資金額的60%，而第三年可有等于兩年投資額的1。4倍收益。為使第五年年初企業(yè)對(duì)使用這部分資金有最大的收益，試確定企業(yè)每年資金的使用方案。請(qǐng)建立數(shù)學(xué)模型。習(xí)題討論課討論第一章習(xí)題一第20題（請(qǐng)同學(xué)上黑板逐個(gè)小問(wèn)題回答）：XBX1X2X3X4X5X6X5X2X300001β1β310-1/203/21/201β40-1/2β221/21/2rβ500β601/2習(xí)題一第六題6．某廠月底安排某一產(chǎn)品在下個(gè)月四周的生產(chǎn)計(jì)劃。估計(jì)每件產(chǎn)品在第一周和第二周的生產(chǎn)成本150元，后兩周為170元，各周產(chǎn)品需求量分別為700，800，1000，1200件，工廠每周至多生產(chǎn)產(chǎn)品900件，在第二周和第三周可加班，加班生產(chǎn)時(shí)每周增產(chǎn)300件，但生產(chǎn)成本每件增加30元，過(guò)剩的產(chǎn)品存貯費(fèi)為每件每周15元，問(wèn)如何安排生產(chǎn)，使總成本最??？解：(1)設(shè)4周生產(chǎn)的產(chǎn)品件數(shù)分別為；第2，3周加班生產(chǎn)的件數(shù)為：=195x1+180x2+185x3+170x4+210y2+215y3-70500s.t.;;(2)設(shè)4周生產(chǎn)的產(chǎn)品件數(shù)分別為；第2，3周加班生產(chǎn)的件數(shù)為;第2，3，4周初存儲(chǔ)量為z2、z3、z4。Minf=150x1+150x2+180y2+15z2+170x3+200y3+15z3+170x4+15z4S．t．x1=700+z2x2+y2+z2=800+z3x3+y3+z3=1000+z4x4+z4=1200；；；習(xí)題一、第7題7.某企業(yè)年出有現(xiàn)金30萬(wàn)元，該企業(yè)有兩個(gè)方案選擇年初貸給其它企業(yè)，年息18%，第二年初可以收回本企業(yè)投資擴(kuò)大生產(chǎn)。若年初投資一定金額，則第二年還需要繼續(xù)投資第一年的60%，而第三年可有等于第二年投資額的1.4倍收益為使第五年年初企業(yè)對(duì)這部分資金的最大收益，試確定企業(yè)每年資金的使用方案，列出數(shù)學(xué)模型。解：設(shè)為該企業(yè)在第j年初采用第一方案所使用的資金，為該企業(yè)在第j年初采用第二方案所使用的資金年份j(年初)12345