線性規(guī)劃及其對(duì)偶問題-課件

線性規(guī)劃及其對(duì)偶問題1線性規(guī)劃問題及其數(shù)學(xué)模型2線性規(guī)劃問題的圖解法3單純形法4對(duì)偶問題5EXCEL求解線性規(guī)劃6靈敏度分析線性規(guī)劃及其對(duì)偶問題1線性規(guī)劃問題及其數(shù)學(xué)模型11線性規(guī)劃問題及其數(shù)學(xué)模型(1)線性規(guī)劃問題例、生產(chǎn)組織與計(jì)劃問題A,B各生產(chǎn)多少,可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉庫AB123202單位利潤(rùn)40503060241線性規(guī)劃問題及其數(shù)學(xué)模型(1)線性規(guī)劃問題例、生產(chǎn)組織2解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1，x2可以建立如下的數(shù)學(xué)模型：Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件可用資源煤勞動(dòng)力倉庫AB123202單位利潤(rùn)4050306024解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1，x2Max3

例某建筑設(shè)計(jì)院設(shè)計(jì)每萬ｍ２辦公建筑和工業(yè)廠房需要的建筑師、結(jié)構(gòu)工程師、設(shè)備工程師和電氣工程師的平均人數(shù)列在表。問該院應(yīng)如何安排設(shè)計(jì)任務(wù)，才能使設(shè)計(jì)費(fèi)收入最大?專業(yè)建筑物建筑結(jié)構(gòu)設(shè)備電器設(shè)計(jì)費(fèi)收入（萬元/萬ｍ２

）辦公建筑532136工業(yè)廠房121220全院現(xiàn)有專業(yè)人數(shù)28261210解設(shè)辦公建筑和工業(yè)廠房各承攬ｘ１、ｘ２萬ｍ２。根據(jù)題意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥0例某建筑設(shè)計(jì)院設(shè)計(jì)每萬ｍ２辦公建筑和工業(yè)廠房需要的建筑42.9m鋼筋架子100個(gè)，每個(gè)需用2.1m各1，原料長(zhǎng)7.4m1.5m求：如何下料，使得殘余料頭最少。解：首先列出各種可能的下料方案；計(jì)算出每個(gè)方案可得到的不同長(zhǎng)度鋼筋的數(shù)量及殘余料頭長(zhǎng)度；確定決策變量；根據(jù)下料目標(biāo)確定目標(biāo)函數(shù)；根據(jù)不同長(zhǎng)度鋼筋的需要量確定約束方程。例、合理下料問題2.9m例5設(shè)按第i種方案下料的原材料為xi根組合方案123456782.9m211100002.1m021032101.5m10130234合計(jì)7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料長(zhǎng)7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料頭0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m設(shè)按第i種方案下料的原材料為xi根組合方案16例、運(yùn)輸問題工廠123庫存?zhèn)}121350222430庫334210需求401535運(yùn)輸單價(jià)求：運(yùn)輸費(fèi)用最小的運(yùn)輸方案。例、運(yùn)輸問題7解：設(shè)xij為i倉庫運(yùn)到j(luò)工廠的產(chǎn)品數(shù)量其中：i

＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13=

50x21+x22+x23=

30x31+x32+x33=

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0s.t解：設(shè)xij為i倉庫運(yùn)到j(luò)工廠的產(chǎn)品數(shù)量MinZ=28(2)線性規(guī)劃問題的特點(diǎn)決策變量：(x1…xn)T代表某一方案，

決策者要考慮和控制的因素非負(fù)；目標(biāo)函數(shù)：Z=?(x1

…xn)為線性函數(shù)，求Z極大或極小;約束條件：可用線性等式或不等式表示.具備以上三個(gè)要素的問題就稱為線性規(guī)劃問題。(2)線性規(guī)劃問題的特點(diǎn)決策變量：(x1…xn)T9目標(biāo)函數(shù)約束條件(3)線性規(guī)劃模型一般形式目標(biāo)函數(shù)約束條件(3)線性規(guī)劃模型一般形式10隱含的假設(shè)比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個(gè)決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij,bi,cj為確定值隱含的假設(shè)112線性規(guī)劃問題的圖解法定義1：滿足約束(2)的X=(X1…Xn)T稱為線性規(guī)劃問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(1)的可行解稱為線性規(guī)劃問題的最優(yōu)解。2線性規(guī)劃問題的圖解法定義1：滿足約束(2)的X=(X112例1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t例1X1+2X230s.t13解：(1)、確定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域解：(1)、確定可行域2030100102030X2D14(2)、求最優(yōu)解最優(yōu)解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C點(diǎn)：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC最優(yōu)解Z=975可行解Z=0等值線(2)、求最優(yōu)解最優(yōu)解：Z=40X1+50X2020301015例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20s.t例2、MaxZ=40X1+80X2X1+2X216解：(1)、確定可行域與上例完全相同。(2)、求最優(yōu)解0203010102030DABC最優(yōu)解Z=1200最優(yōu)解：BC線段解：(1)、確定可行域與上例完全相同。0203010117最優(yōu)解：BC線段B點(diǎn)：X(1)=(6,12)C點(diǎn)：X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)MaxZ=1200

X1615

X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)最優(yōu)解：BC線段MaxZ=1200X118例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域無界無有限最優(yōu)解無有限最優(yōu)解可行域無上界例3、MaxZ=2X1+4X22X1+X28s.19例4、MaxZ=3X1+2X2-X1-X21X1,X20無可行域無可行解-1X2-1X10s.tX20X10-X1-X21例4、MaxZ=3X1+2X2-X1-X21無可20直觀結(jié)論線性規(guī)劃問題的解有四種情況唯一最優(yōu)解無窮多最優(yōu)解無有限最優(yōu)解無可行解若線性規(guī)劃問題有解，則可行域是一個(gè)凸多邊形（或凸多面體）；若線性規(guī)劃問題有最優(yōu)解，則唯一最優(yōu)解對(duì)應(yīng)于可行域的一個(gè)頂點(diǎn)；無窮多個(gè)最優(yōu)解對(duì)應(yīng)于可行域的一條邊；直觀結(jié)論線性規(guī)劃問題的解有四種情況213單純形法3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式3.2線性規(guī)劃問題的基本解3.3單純形法的基本思想3單純形法3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式223.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)約束條件(1)線性規(guī)劃模型一般形式3.1線性規(guī)劃問題的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)約束條件(1)線性規(guī)23價(jià)值系數(shù)決策變量技術(shù)系數(shù)右端常數(shù)(2)線性規(guī)劃模型標(biāo)準(zhǔn)形式價(jià)值系數(shù)決策變量技術(shù)系數(shù)右端常數(shù)(2)線性規(guī)劃模型標(biāo)準(zhǔn)形式24價(jià)值向量決策向量系數(shù)矩陣右端向量(3)線性規(guī)劃模型矩陣形式價(jià)值向量決策向量系數(shù)矩陣右端向量(3)線性規(guī)劃模型矩陣形式25對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式:(4)一般型向標(biāo)準(zhǔn)型的轉(zhuǎn)化目標(biāo)函數(shù)目標(biāo)函數(shù)為極小化約束條件分兩種情況：大于、小于決策變量可能存在小于零的情況對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下變換，將263.2線性規(guī)劃問題的基本解(1)解的基本概念定義在線性規(guī)劃問題中，約束方程組(2)的系數(shù)矩陣A(假定)的任意一個(gè)階的非奇異(可逆)的子方陣B(即)，稱為線性規(guī)劃問題的一個(gè)基陣或基。3.2線性規(guī)劃問題的基本解(1)解的基本概念定義在27基陣非基陣基向量非基向量基變量非基變量基陣非基陣基非基變量非基變量28令則定義在約束方程組(2)中，對(duì)于一個(gè)選定的基B，令所有的非基變量為零得到的解，稱為相應(yīng)于基B的基本解。令則定義在約束方程組(2)中，對(duì)于一個(gè)選定的基B，令29定義在基本解中，若該基本解滿足非負(fù)約束，即，則稱此基本解為基本可行解，簡(jiǎn)稱基可行解；對(duì)應(yīng)的基B稱為可行基?；窘庵凶疃嘤衜個(gè)非零分量?；窘獾臄?shù)目不超過個(gè)。定義在基本解中，若該基本解滿足非負(fù)約束，即30若B滿足下列條件，稱為最優(yōu)基稱為最優(yōu)解若B滿足下列條件，稱為最優(yōu)基31例現(xiàn)有線性規(guī)劃問題試求其基本解、基本可行解。例現(xiàn)有線性規(guī)劃問題試求其基本解、基本可行解。32解:(1)首先將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型引入松弛變量x3和x4(2)求基本解由上式得解:(1)首先將原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型(2)求基本解33可能的基陣由于所有|B|≠0，所以有6個(gè)基陣和6個(gè)基本解。可能的基陣由于所有|B|≠0，所以有6個(gè)基陣和34對(duì)于基陣令則對(duì)于基陣令則為基本可行解，B13為可行基為基本可行解，B12為可行基對(duì)于基陣令則對(duì)于基陣令則為基本可行解，B13為可行基為基本可35對(duì)于基陣令則對(duì)于基陣令則對(duì)于基陣令則對(duì)于基陣令則36對(duì)于基陣令則對(duì)于基陣令則為基本可行解，B24為可行基為基本可行解，B34為可行基對(duì)于基陣令則對(duì)于基陣令則為基本可行解，B24為可行基為基本可370ABCDE所以，本問題存在6個(gè)基本解，其中4個(gè)為基可行解.0ABCDE所以，本問題存在6個(gè)基本解，其中4個(gè)為基可行解.38(2)幾點(diǎn)結(jié)論若線性規(guī)劃問題有可行解,則可行域是一個(gè)凸多邊形或凸多面體(凸集),且僅有有限個(gè)頂點(diǎn)(極點(diǎn));線性規(guī)劃問題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一個(gè)頂點(diǎn)(極點(diǎn));若線性規(guī)劃問題有最優(yōu)解,則最優(yōu)解必可在基可行解(極點(diǎn))上達(dá)到;線性規(guī)劃問題的基可行解(極點(diǎn))的個(gè)數(shù)是有限的,不會(huì)超過個(gè).上述結(jié)論說明:線性規(guī)劃的最優(yōu)解可通過有限次運(yùn)算在基可行解中獲得.(2)幾點(diǎn)結(jié)論若線性規(guī)劃問題有可行解,則可行域是一個(gè)凸多邊393.3單純形法(1)單純形法的引入(2)表格單純形法3.3單純形法(1)單純形法的引入(2)表格單純形40

…n…j…m+1

…

k…

1-CBTb*amn…amj…amm+1

…0…am1bm*xmcm

…

…

…

…

…

…

…

…

…akn…akj…akm+1

…akk…ak1bk*xkck

…

…

…

…

…

…

…

…a1n…a1j…a1m+1…a1k…a11b1*x1c1xn…xj…xm+1xm…xk…x1b*XBCBcn…cj…cm+1cm…ck…c1cj→單純形表ammmmaxZ＝c1x1十c2x2十……十cnxn

a11x1＋a12x2十……十a(chǎn)1nxn＝b1

a21x1＋a22x2十……十a(chǎn)2nxn＝b2……am1x1＋am2x2十……十a(chǎn)mnxn＝bmxj≥0(j＝l、2、……，n)a1m…n…j…m+1…k…1-41x3x5x4000σ10

18000170/2100/3150/5maxZ＝10x1＋18x2（1）5x1＋2x2＋x3＝170s.t2x1＋3x2＋x4＝100（2）x1＋5x2＋x5＝150xj≥0（j＝1，2，3，4，5）主元x3x5x4000σ1018000170/2100/31542x3x400x2100/2x3x5x4000σ10

18000170/2150/3100181/5001/53010σ1＝10－（0×23/5＋0×7/5－18×1/5）＝32/57/50111023/51－3/50－2/5σ32/5000－18/5550/2350/7150maxZ＝10x1＋18x2（1）5x1＋2x2＋x3＝170s.t2x1＋3x2＋x4＝100（2）x1＋5x2＋x5＝150xj≥0（j＝1，2，3，4，5）σ2＝18－－（0×0＋0×0－18×1）＝010＝100－（30×3）7/5＝2－（1/5×3）x3x400x2100/2x3x5x4000σ10180043x3x400x2100/2x3x5x4000σ10

18000170/2150/3100181/5001/530107/50111023/51－3/50－2/5σ32/5000－18/5550/2350/7150x3x1x201018150/7005/7－3/7540/7001－23/711/7200/7010－1/72/7X*=(50/7,200/7,540/7,0,0)TZ*=4100/7σ000－32/7－6/7x3x400x2100/2x3x5x4000σ10180044例某房地產(chǎn)公司欲開發(fā)一七通一平空地，總面積2500m2。公司原計(jì)劃開發(fā)商業(yè)樓1000m2，住宅樓5250m2。請(qǐng)根據(jù)下列前提條件，確定其是否最佳開發(fā)方式。(1)根據(jù)規(guī)劃要求：沿馬路建商業(yè)房，為4層樓框架結(jié)構(gòu)，其余為磚混住宅，為6層樓；容積率為2.5，建筑密度≤50%。(2)開發(fā)日期為2003年12月，建筑物完成時(shí)間不超過一年半。(3)根據(jù)預(yù)測(cè)，一年半以后商業(yè)樓平均造價(jià)為1400元/m2，磚混住宅平均造價(jià)為950元/m2，不計(jì)土地成本。(4)預(yù)計(jì)建筑物完成后商業(yè)樓及住宅均可全部售出，商業(yè)樓出售當(dāng)時(shí)的平均售價(jià)為2400元/m2，住宅樓出售當(dāng)時(shí)的平均售價(jià)為1700元/m2。(5)物業(yè)出售時(shí)的稅費(fèi)為總額的5%。(6)公司投入資金不超過650萬元。例某房地產(chǎn)公司欲開發(fā)一七通一平空地，總面積2500m2。公45分析：容積率＝總建筑面積/總占地面積建筑密度＝建筑基地總面積/總占地面積(1)總建筑面積2500×2.5=6250m2(2)建筑基地總面積2500×50%＝1250m2(3)商業(yè)樓每平方米的利潤(rùn):(0.24－0.14一0.24×5%)=0.088(萬元/m2)(4)住宅樓每平方米的利潤(rùn):(0.17一0.095一0.17×5%)=0.0665(萬元/m2)分析：46設(shè)商業(yè)樓建筑面積為x1m2;磚混住宅建筑面積為x2m2求x1、x2目標(biāo)函數(shù)maxZ=0.088x1＋0.0665x2滿足:x1＋x2≤6250x1/4+x2/6≤12500.14x1十0.095x2≤650x1、x2≥0(1)總建筑面積2500×2.5=6250m2(2)建筑基地總面積2500×50%＝1250m2(3)商業(yè)樓每平方米的利潤(rùn):(0.24－0.14一0.24×5%)=0.088(萬元/元m2)(4)住宅樓每平方米的利潤(rùn):(0.17一0.095一0.17×5%)=0.0665(萬元/m2)設(shè)商業(yè)樓建筑面積為x1m2;磚混住宅建筑面積為x2m2(147為了便于計(jì)算，變換一下約束條件及目標(biāo)函數(shù)。（由于在整個(gè)價(jià)值最優(yōu)程序中只是相對(duì)的價(jià)值是重要的，而不是它們絕對(duì)值。絕對(duì)值的值只影響目標(biāo)函數(shù)的最后值，但不影響設(shè)計(jì)變量的最優(yōu)值）因此，我們可以將其變換為:x1/4+x2/6≤1250轉(zhuǎn)變?yōu)?x1十2x2≤150000.14x1十0.095x2≤650轉(zhuǎn)變?yōu)?.4737x1十x2≤6842maxZ=0.088x1＋0.0665x2轉(zhuǎn)變?yōu)閙axZ‘=Z/0.0665＝1.323x1＋x2maxZ=0.088x1＋0.0665x2x1＋x2≤6250x1/4+x2/6≤12500.14x1十0.095x2≤650x1、x2≥0為了便于計(jì)算，變換一下約束條件及目標(biāo)函數(shù)。（由于在整個(gè)價(jià)值最48數(shù)學(xué)模型maxZ‘=1.323x1+x2x1＋x2≤62503x1十2x2≤150001.4737x1十x2≤6842x1、x2≥0x3x4x5000數(shù)學(xué)模型x3x4x500049maxZ=1.323x1+x2x1＋x2≤62503x1十2x2≤150001.4737x1十x2≤6842x1、x2≥01.32310006250/115000/36842/1.4737x11.3230146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000maxZ=1.323x1+x21.3231000625501.3230x1146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000x211500003.111402.11140125000.11141-1.4602012501-2.11140-0.754200-0.318000-1.1136最優(yōu)解:x1=1250,x2=5000,x4=1250,x3=x5＝0Z‘=6654即Z=0.0665×Z‘=442.5（萬）1.3230x1146430.6786000.678610751例某項(xiàng)目經(jīng)理部有三種住宅可以承建。三種住宅每百平方米的利潤(rùn)分別為6000元、8000元和5000元。承建時(shí)主要考慮木工和瓦工工時(shí)的安排。由于現(xiàn)在瓦工空閑，應(yīng)盡量多安排；而可支配的木工工時(shí)雖然僅有26000個(gè)，但不允許有任何空閑。三種住宅每百平方米需用的瓦工和木工工時(shí)列在表中。另外，公司要求至少安排12000瓦工工時(shí)。問三種住宅各承建多少平方米．可使利潤(rùn)最大?

解設(shè)甲、乙、丙三種住宅各承建x1、、x2平方米，根據(jù)問題的要求，可得下列線性規(guī)劃模型例某項(xiàng)目經(jīng)理部有三種住宅可以承建。三種住宅每百平方米的52線性規(guī)劃及其對(duì)偶問題_課件53線性規(guī)劃及其對(duì)偶問題_課件54線性規(guī)劃及其對(duì)偶問題_課件55例某工程的混凝土量總計(jì)1500m3；分三種標(biāo)號(hào)C20，C25，C30，其需要量為400m3、600m3、500m3。今供應(yīng)32.5#水泥250t、42.5#水泥200t、，水泥單價(jià)及用量見表。試選擇合理的配制方案，使水泥費(fèi)用最省。例某工程的混凝土量總計(jì)1500m3；分三種標(biāo)號(hào)C20，C256設(shè)：由32.5#水泥配制的C20，C25，C30混凝土各為x1、x2、x3，由42.5#水泥配制的C20，C25，C30混凝土各為x4、x5、x6則32.5#水泥的總耗量為253x1＋302x2＋362x342.5#水泥的總耗量為211x4＋257x5＋302x6目標(biāo)函數(shù)：minz＝2065（253x1＋302x2＋362x3）＋2192（211x4＋257x5＋302x6）253x1＋302x2＋362x3≤250211x4＋257x5＋302x6≤200x1＋x4≥400x2＋x5≥600x3＋x6≥500xi≥0解得：x1＝48x2＝600x3＝44x4＝252x5＝0x6＝486z＝28337.416（元）設(shè)：由32.5#水泥配制的C20，C25，C30混凝土各為x57案例:建設(shè)監(jiān)理公司監(jiān)理工程師配置問題某建設(shè)監(jiān)理公司(國(guó)家甲級(jí))，側(cè)重國(guó)家大中型項(xiàng)目的監(jiān)理，僅在武漢市就正在監(jiān)理七項(xiàng)工程，總投資均在5000萬元以上。由于工程開工的時(shí)間不同，多工程工期之間相互搭接，具有較長(zhǎng)的連續(xù)性，2002年監(jiān)理的工程量與2003年監(jiān)理的工程量大致相同。每項(xiàng)工程安排多少監(jiān)理工程師進(jìn)駐工地，一般是根據(jù)工程的投資，建筑規(guī)模，使用功能，施工的形象進(jìn)度，施工階段來決定的。監(jiān)理工程師的配置數(shù)量是隨之而變化的。由于監(jiān)理工程師從事的專業(yè)不同，他們每人承擔(dān)的工作量也是不等的。有的專業(yè)一個(gè)工地就需要三人以上，而有的專業(yè)一人則可以兼管三個(gè)以上的工地。案例:建設(shè)監(jiān)理公司監(jiān)理工程師配置問題58因?yàn)閺氖卤O(jiān)理業(yè)的專業(yè)多達(dá)幾十個(gè)，僅以高層民用建筑為例就涉及到建筑學(xué)專業(yè)、工民建(結(jié)構(gòu))專業(yè)、給水排水專業(yè)、采暖通風(fēng)專業(yè)、強(qiáng)電專業(yè)、弱電專業(yè)、自動(dòng)控制專業(yè)、技術(shù)經(jīng)濟(jì)專業(yè)、總圖專業(yè)、合同和信息管理人員等，這就需要我們合理配置這些人力資源。為了方便計(jì)算，我們把所涉及的專業(yè)技術(shù)人員按總平均人數(shù)來計(jì)算，工程的施工形象進(jìn)度，按標(biāo)準(zhǔn)施工期和高峰施工期來劃分。通常標(biāo)準(zhǔn)施工期需求的人數(shù)較容易確定。但高峰施工期比較難確定了。原因有兩點(diǎn):(1)高峰施工期各工地不是同時(shí)來到，是可以事先預(yù)測(cè)的，在同一個(gè)城市里相距不遠(yuǎn)的工地，就存在著各工地的監(jiān)理工程師如何交錯(cuò)使用的運(yùn)籌問題。因?yàn)閺氖卤O(jiān)理業(yè)的專業(yè)多達(dá)幾十個(gè)，僅以高層民用建筑為例就涉及到59(2)各工地總監(jiān)在高峰施工期到來的時(shí)候要向公司要人，如果每個(gè)工地都按高峰施工期配置監(jiān)理工程師的數(shù)量，將造成極大的人力資源浪費(fèi)，這一點(diǎn)應(yīng)該說主要是人為因素所造成的。因此，為了達(dá)到高峰施工期監(jiān)理工程師配置數(shù)量最優(yōu)，人員合理地交錯(cuò)使用，扼制人為因素，根據(jù)歷年來的經(jīng)驗(yàn)對(duì)高峰施工期的監(jiān)理工程師數(shù)量在合理交錯(cuò)發(fā)揮作用的前提下限定了范圍。另經(jīng)統(tǒng)計(jì)測(cè)算得知，全年平均標(biāo)準(zhǔn)施工期占7個(gè)月，人年成本4萬元;高峰施工期占5個(gè)月，人年成本7萬元。(2)各工地總監(jiān)在高峰施工期到來的時(shí)候要向公司要人，如果每個(gè)60另外在高峰施工期各工地所需監(jiān)理工程師的數(shù)量要求第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第5工地的總?cè)藬?shù)不少于10人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的總?cè)藬?shù)不少于7人;第7和第1工地的總?cè)藬?shù)不少于14人。求2003年:1．高峰施工期公司最少配置多少個(gè)監(jiān)理工程師?2．監(jiān)理工程師年耗費(fèi)的總成本是多少?線性規(guī)劃及其對(duì)偶問題_課件61已知條件匯總：為了達(dá)到高峰施工期監(jiān)理工程師配置數(shù)量最優(yōu)，人員合理地交錯(cuò)使用，扼制人為因素，根據(jù)歷年來的經(jīng)驗(yàn)對(duì)高峰施工期的監(jiān)理工程師數(shù)量在合理交錯(cuò)發(fā)揮作用的前提下限定了范圍。另經(jīng)統(tǒng)計(jì)測(cè)算得知，全年平均標(biāo)準(zhǔn)施工期占7個(gè)月，人年成本4萬元;高峰施工期占5個(gè)月，人年成本7萬元。另外在高峰施工期各工地所需監(jiān)理工程師的數(shù)量要求第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第5工地的總?cè)藬?shù)不少于10人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的總?cè)藬?shù)不少于7人;第7和第1工地的總?cè)藬?shù)不少于14人。求2003年:1．高峰施工期公司最少配置多少個(gè)監(jiān)理工程師?2．監(jiān)理工程師年耗費(fèi)的總成本是多少?已知條件匯總：為了達(dá)到高峰施工期監(jiān)理工程師配置數(shù)量最優(yōu)，人員62設(shè)xi為第i工地最少配置監(jiān)理工程師人數(shù)約束條件:第1和第2工地的總?cè)藬?shù)不少于14人;第2和第3工地的總?cè)藬?shù)不少于13人;第3和第4工地的總?cè)藬?shù)不少于11人;第4和第5工地的總?cè)藬?shù)不少于10人;第5和第6工地的總?cè)藬?shù)不少于9人;第6和第7工地的總?cè)藬?shù)不少于7人;第7和第1工地的總?cè)藬?shù)不少于14人。x1≥5x2≥4x3≥4x4≥3x5≥3x6≥2x7≥2

x1、x2、x3、x4、x5、x6、x7≥0x1＋x2≥14x2＋x3≥13x3＋x4≥11x4＋x5≥10x5＋x6≥9x6＋x7≥7x7＋x1≥7Minz=x1+x2+x3+x4+x5+x6+x7設(shè)xi為第i工地最少配置監(jiān)理工程師人數(shù)第1和第2工地的總?cè)藬?shù)632．監(jiān)理工程師年耗費(fèi)的總成本(4×7/12+7×5/12）×min（x1+x2+x3+x4+x5+x6+x7）2．監(jiān)理工程師年耗費(fèi)的總成本644線性規(guī)劃的對(duì)偶理論4.1對(duì)偶問題4.2對(duì)偶問題的基本性質(zhì)4.3影子價(jià)格4.4對(duì)偶單純形法4線性規(guī)劃的對(duì)偶理論4.1對(duì)偶問題654.1對(duì)偶問題(1)對(duì)偶問題的提出例1、生產(chǎn)組織與計(jì)劃問題A,B各生產(chǎn)多少,可獲最大利潤(rùn)?可用資源煤勞動(dòng)力倉庫AB123202單位利潤(rùn)40503060244.1對(duì)偶問題(1)對(duì)偶問題的提出例1、生產(chǎn)組織與計(jì)劃問66Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件如果因?yàn)槟撤N原因，不愿意自己生產(chǎn)，而希望通過將現(xiàn)有資源承接對(duì)外加工來獲得收益，那么應(yīng)如何確定各資源的使用價(jià)格？MaxZ=40x1+50x2x1+2x267Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目標(biāo)函數(shù)約束條件兩個(gè)原則所得不得低于生產(chǎn)的獲利要使對(duì)方能夠接受設(shè)三種資源的使用單價(jià)分別為y1,y2,y3y1y2y3生產(chǎn)單位產(chǎn)品A的資源消耗所得不少于單位產(chǎn)品A的獲利生產(chǎn)單位產(chǎn)品B的資源消耗所得不少于單位產(chǎn)品B的獲利y1+3y240

2y1+2y2+2y350MaxZ=40x1+50x2x1+2x268通過使用所有資源對(duì)外加工所獲得的收益W=30y1+60y2+24y3根據(jù)原則2，對(duì)方能夠接受的價(jià)格顯然是越低越好，因此此問題可歸結(jié)為以下數(shù)學(xué)模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目標(biāo)函數(shù)約束條件原線性規(guī)劃問題稱為原問題，此問題為對(duì)偶問題，y1,y2,y3稱為影子價(jià)格通過使用所有資源對(duì)外加工所獲得的收益W=30y1+669(2)對(duì)偶問題的形式定義設(shè)原線性規(guī)劃問題為則稱下列線性規(guī)劃問題為其對(duì)偶問題，其中yi(i=1,2,…,m)稱為對(duì)偶變量。上述對(duì)偶問題稱為對(duì)稱型對(duì)偶問題。原問題簡(jiǎn)記為(P)，對(duì)偶問題簡(jiǎn)記為(D)(2)對(duì)偶問題的形式定義設(shè)原線性規(guī)劃問題為則稱70對(duì)偶關(guān)系對(duì)應(yīng)表原問題對(duì)偶問題目標(biāo)函數(shù)類型MaxMin目標(biāo)函數(shù)系數(shù)目標(biāo)函數(shù)系數(shù)右邊項(xiàng)系數(shù)與右邊項(xiàng)的對(duì)應(yīng)關(guān)系右邊項(xiàng)系數(shù)目標(biāo)函數(shù)系數(shù)變量數(shù)與約束數(shù)變量數(shù)n約束數(shù)n的對(duì)應(yīng)關(guān)系約束數(shù)m變量數(shù)m原問題變量類型與

0

對(duì)偶問題約束類型變量

0約束

的對(duì)應(yīng)關(guān)系無限制＝原問題約束類型與

0對(duì)偶問題變量類型約束

變量

0的對(duì)應(yīng)關(guān)系＝無限制對(duì)偶關(guān)系對(duì)應(yīng)表714.2對(duì)偶問題的基本性質(zhì)定理1對(duì)偶問題的對(duì)偶就是原問題MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0對(duì)偶的定義對(duì)偶的定義4.2對(duì)偶問題的基本性質(zhì)定理1對(duì)偶問題的對(duì)偶就是原問題M72定理2(弱對(duì)偶定理)分別為(P),(D)的可行解，則有CbX，yXy證明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb定理2(弱對(duì)偶定理)分別為(P),(D)的可行解，則有C73推論2、(P)有可行解,但無有限最優(yōu)解，則(D)無可行解。定理3、yX,分別為(P),(D)的可行解，且XyC=b,則它們是(P),(D)

的最優(yōu)解。證明：對(duì)任X，有CXby=CXX最優(yōu)推論1、(P),(D)都有可行解，則必都有最優(yōu)解。推論2、(P)有可行解,但無有限最優(yōu)解，則(D)無可行解。74定理4(主對(duì)偶定理)若一對(duì)對(duì)偶問題(P)和(D)都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。證明：(1)當(dāng)X*和Y*為原問題和對(duì)偶問題的一個(gè)可行解有原問題目標(biāo)函數(shù)值對(duì)偶問題目標(biāo)函數(shù)值所以原問題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問題有下界，也存在有限最優(yōu)解。定理4(主對(duì)偶定理)證明：(1)當(dāng)X*和Y*為原問題和對(duì)偶75(2)當(dāng)X*為原問題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過引入松弛變量Xs,將問題(P)轉(zhuǎn)化為標(biāo)準(zhǔn)型令令所以Y*是對(duì)偶問題的可行解，對(duì)偶問題的目標(biāo)函數(shù)值為X*是原問題的最優(yōu)解，原問題的目標(biāo)函數(shù)值為(2)當(dāng)X*為原問題的一個(gè)最優(yōu)解，B為相應(yīng)的最優(yōu)基,通過引76推論：若一對(duì)對(duì)偶問題中的任意一個(gè)有最優(yōu)解，則另一個(gè)也有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等。一對(duì)對(duì)偶問題的關(guān)系，有且僅有下列三種：都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等；兩個(gè)都無可行解；一個(gè)問題無界，則另一問題無可行解。推論：一對(duì)對(duì)偶問題的關(guān)系，有且僅有下列三種：77從兩圖對(duì)比可明顯看到原問題無界，

其對(duì)偶問題無可行解y1y2從兩圖對(duì)比可明顯看到原問題無界，

其對(duì)偶問題無可行解y1y278例4已知線性規(guī)劃問題maxz=x1+x2-x1+x2+x3≤2-2x1+x2-x3≤1x1,x2,x3≥0試用對(duì)偶理論證明上述線性規(guī)劃問題無最優(yōu)解。例4已知線性規(guī)劃問題maxz=x1+x279上述問題的對(duì)偶問題為minw=2y1+y2-y1-2y2≥1y1+y2≥1y1-y2≥0y1，y2≥0由第1約束條件，可知對(duì)偶問題無可行解；原問題雖然有可行解，但無最優(yōu)解。上述問題的對(duì)偶問題為minw=2y1+y280例5已知線性規(guī)劃問題minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其對(duì)偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試用對(duì)偶理論找出原問題的最優(yōu)解。例5已知線性規(guī)劃問題minw=2x1+3x2+5x3+81例5已知線性規(guī)劃問題解：先寫出它的對(duì)偶問題maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0例5已知線性規(guī)劃問題maxz=4y1+3y282例5已知線性規(guī)劃問題將y1*=4/5,y2*=3/5的值代入約束條件，得②=1/5<3，③=17/5<5，④=7/5<2它們?yōu)閲?yán)格不等式；由互補(bǔ)松弛性得x2*=x3*=x4*=0。因y1，y2≥0；原問題的兩個(gè)約束條件應(yīng)取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原問題的最優(yōu)解為X*=(1，0，0，0，1)T；w*=5例5已知線性規(guī)劃問題得②=1/5<3，③=17/5<5，83定理5

若X,Y分別為(P),(D)的可行解，則X,Y為最優(yōu)解的充要條件是同時(shí)成立證:(必要性）原問題對(duì)偶問題定理5若X,Y分別為(P),(D)的可行解，則84y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

對(duì)偶問題的變量對(duì)偶問題的松弛變量原始問題的變量原始問題的松弛變量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一對(duì)變量中，其中一個(gè)大于0，另一個(gè)一定等于0y1yiymym+185影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于04.3影子價(jià)格變量yi*的經(jīng)濟(jì)意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函的最優(yōu)值的變化。影子價(jià)格越大，說明這種資源越是相對(duì)緊缺4.3影子價(jià)格變量y86第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。由表1-5可知cj23000θCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。cj23000θC87第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。

這說明是其他條件不變的情況下，若設(shè)備增加一臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元；原材料A增加1kg，可多獲利0.125元；原材料B增加1kg，對(duì)獲利無影響。從圖2-1可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線由①移至①′，相應(yīng)的最優(yōu)解由(4，2)變?yōu)?4，2.5)，目標(biāo)函數(shù)z=2×4+3×2.5=15.5，即比原來的增大1.5。又若原材料A增加1kg時(shí)，代表該約束方程的直線由②移至②′，相應(yīng)的最優(yōu)解從(4，2)變?yōu)?4.25，1.875)，目標(biāo)函數(shù)z=２×4.25+3×1.875=14.125。比原來的增加0.125。原材料B增加1kg時(shí)，該約束方程的直線由③移至③′，這時(shí)的最優(yōu)解不變。第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。這說明是其他條件不變88第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。

第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。89yi*的值代表對(duì)第i種資源的估價(jià)——影子價(jià)格。

這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為“影子價(jià)格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原材料A的出讓費(fèi)為除成本外再附加0.125元，1kg原材料B可按原成本出讓，這時(shí)該廠的收入與自己組織生產(chǎn)時(shí)獲利相等。影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣掉?？梢娪白觾r(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。yi*的值代表對(duì)第i種資源的估價(jià)——影子價(jià)格。這種估價(jià)902.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用很多（1）影子價(jià)格能指示企業(yè)內(nèi)部挖潛的方向1）影子價(jià)格越高的資源，表明它對(duì)目標(biāo)增益影響越大，同時(shí)也表明這種資源對(duì)該企業(yè)來說越稀缺和越貴重，企業(yè)的管理者就應(yīng)該重視對(duì)這種資源的管理，通過挖潛革新、降低消耗或及時(shí)補(bǔ)充該種資源，以保證給企業(yè)帶來較大的收益。即對(duì)影子價(jià)格大于零的資源都應(yīng)采取措施，增加投入，以保證生產(chǎn)正常進(jìn)行，實(shí)現(xiàn)利潤(rùn)最大化。2）對(duì)影子價(jià)格為零的資源，企業(yè)的管理者也不應(yīng)忽視，這種資源對(duì)該企業(yè)來說是相對(duì)富裕的。一方面，可以向別的企業(yè)轉(zhuǎn)讓這種資源或者以市場(chǎng)價(jià)出售，以免形成積壓浪費(fèi)；另一方面，通過企業(yè)內(nèi)部的改造、挖潛和增加對(duì)影子價(jià)格大于零的資源的投入后，使原有的剩余資源又可以得到充分利用，而變?yōu)樾碌木o缺資源（變?yōu)橛白觾r(jià)格大于零）。這樣不斷調(diào)整、補(bǔ)充，真正實(shí)現(xiàn)資源的合理利用。2.影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用91（2）影子價(jià)格在企業(yè)經(jīng)營(yíng)決策中的作用因?yàn)橛白觾r(jià)格不是市場(chǎng)價(jià)格，它是根據(jù)企業(yè)本身的資源情況bi、消耗系數(shù)aij和產(chǎn)品的利潤(rùn)cj計(jì)算出來的一種價(jià)格，是新增資源所創(chuàng)造的價(jià)值，是邊際價(jià)格。不同的企業(yè)，即使是相同的資源（例如鋼材），其影子價(jià)格也不一定相同。就是同一企業(yè)，在不同的生產(chǎn)周期，資源的影子價(jià)格也不完全一樣。因此，企業(yè)的決策者可以把本企業(yè)資源的影子價(jià)格與當(dāng)時(shí)的市場(chǎng)價(jià)格進(jìn)行比較。1）當(dāng)i種資源的影子價(jià)格高于市場(chǎng)價(jià)格時(shí)，則企業(yè)可以買進(jìn)該種資源；2）當(dāng)某種資源的影子價(jià)格低于市場(chǎng)價(jià)格時(shí)（特別是當(dāng)影子價(jià)格為零時(shí)），則企業(yè)可以賣出該種資源，以獲得較大的利潤(rùn)。3）隨著資源的買進(jìn)和賣出，它的影子價(jià)格也將發(fā)生變化，直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。所以我們說影子價(jià)格又是一種機(jī)會(huì)成本，它在決定企業(yè)的經(jīng)常策略中起著十分重要的作用。（2）影子價(jià)格在企業(yè)經(jīng)營(yíng)決策中的作用92

式中：cj表示單位j種產(chǎn)品的價(jià)值（或利潤(rùn)）m∑aijyii=1表示生產(chǎn)第j種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和，它可以稱為第j種產(chǎn)品的隱含成本，檢驗(yàn)數(shù)бj稱作是第j種產(chǎn)品的相對(duì)價(jià)值系數(shù)。

mбj=cj—CBB-1Pj=cj—∑aijyi(j=1,2,…,n).i=1由于（3）影子價(jià)格在新產(chǎn)品開發(fā)決策中的應(yīng)用企業(yè)在新產(chǎn)品投產(chǎn)之前，可以用影子價(jià)格，通過分析產(chǎn)品使用資源的經(jīng)濟(jì)效果，以決定新產(chǎn)品是否應(yīng)該投產(chǎn)。б<0，產(chǎn)品所能提供的單件利潤(rùn)小于其隱含成本，產(chǎn)品不值得投產(chǎn)；б>0，產(chǎn)品B所能提供的單件利潤(rùn)大于其隱含成本，產(chǎn)品值得投產(chǎn)

93例MaxZ=10x1+18x2;5x1+2x2≤170;2x1+3x2≤100;s.t.x1+5x2≤150;x1、x2≥0.計(jì)算產(chǎn)品A和B的相對(duì)價(jià)值系數(shù)：mбA=CA—∑aijyii=1=10—(1×0+2×32/7＋3×6/7)=—12/7<0;解說明產(chǎn)品A所能提供的單件利潤(rùn)小于其隱含成本，相對(duì)價(jià)值系數(shù)бA<0，故產(chǎn)品A不值得投產(chǎn)。例計(jì)算產(chǎn)品A和B的相對(duì)價(jià)值系數(shù)：94mбB=CB—∑aijyi=18－(2×0+1×32/7+4×6/7)=10>0.i=1說明產(chǎn)品B所能提供的單件利潤(rùn)大于其隱含成本，相對(duì)價(jià)值系數(shù)бB>0，故產(chǎn)品B值得投產(chǎn)。m說明95

（4）利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)對(duì)資源緊缺情況的影響前例中，當(dāng)產(chǎn)品的利潤(rùn)不是（10，18），而是（15，18），則從最優(yōu)單純形表可以重新算影子價(jià)格為

Y*=CBB-1=（0，15，18）

=（0，57/7，—9/7）由于y3*=-9/7<0，說明現(xiàn)有的解不是最優(yōu)解，還須繼續(xù)迭代求新的最優(yōu)解。而y2*=57/7比原來增大了，說明第二種資源更緊缺了。1-23/711/7

05/7-3/70-1/72/7

maxZ=10x1+18x2;5x1+2x2+x3=170;2x1-3x2+x4=100;s.t.x1+5x2+x5=150;x1,x2≥0;（4）利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)對(duì)資源緊缺情況的影響96（5）利用影子價(jià)格分析工藝改變后對(duì)資源的影響前例中，使煤炭節(jié)約2%，則帶來的收益為y2*b2·2%=32/7×100×2%=64/7（萬元）

值得指出的是，以上的分析都是在最優(yōu)基不變的條件下進(jìn)行的如果最優(yōu)基有變化，則應(yīng)結(jié)合下一章將要討論的靈敏度分析方法來進(jìn)行分析。

maxZ=10x1+18x2;5x1+2x2+x3=170;2x1-3x2+x4=100;s.t.x1+5x2+x5=150;x1,x2≥0;（5）利用影子價(jià)格分析工藝改變后對(duì)資源的影響maxZ=97

例已知某工廠計(jì)劃生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，各產(chǎn)品需要在A,B,C設(shè)備上加工，有關(guān)數(shù)據(jù)見表．

試回答:(1)如何充分發(fā)揮設(shè)備能力，使生產(chǎn)盈利最大?(2)若為了增加產(chǎn)量，可借用別的工廠的設(shè)備B，每月可借用60臺(tái)時(shí)，借金1.8萬元，問借用B設(shè)備是否合算?(3)若另有兩種新產(chǎn)品Ⅳ、V，其中Ⅳ需用設(shè)備A一l2臺(tái)時(shí)，B一5臺(tái)時(shí)，C一l0臺(tái)時(shí)，單位產(chǎn)品盈利2.1千元;新產(chǎn)品V需用設(shè)備A一4臺(tái)時(shí)，B一4臺(tái)時(shí)，C一l2臺(tái)時(shí)，單位產(chǎn)品盈利1.87千元，如A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否合算?(4）對(duì)產(chǎn)品工藝重新迸行設(shè)計(jì)，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品I，需用設(shè)備A一9臺(tái)時(shí)，設(shè)備B一12臺(tái)時(shí)，設(shè)備C一4臺(tái)時(shí)，單位產(chǎn)品盈利4.5千元，問這對(duì)原計(jì)劃有何影響?Ⅰ

Ⅱ

Ⅲ

設(shè)備有效臺(tái)時(shí)（每月）ABC8102251310810300400420單位產(chǎn)品利潤(rùn)（千元）322.9例已知某工廠計(jì)劃生產(chǎn)Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，各產(chǎn)品需要在A98解設(shè)產(chǎn)品Ⅰ、Ⅱ、Ⅲ的產(chǎn)量分別為x1，x2，x3，其數(shù)學(xué)模型為maxZ=3x1十2x2十2.9x38x1十2x2十10x3≤30010x1十5x2十8x3≤400，s·t2x1十13x2十10x3≤300，x1、x2、x3≥0在上述線性規(guī)劃問題的約束條件中加入松變量x4，x5，x6。得maxZ=3x1十2x2十2.9x38x1十2x2十10x3＋x4＝30010x1十5x2十8x3＋x5＝400，s·t2x1十13x2十10x3＋x6＝300，x1、x2、x3、x4，x5，x6≥0列出初始單純形表，并求解解設(shè)產(chǎn)品Ⅰ、Ⅱ、Ⅲ的產(chǎn)量分別為x1，x2，x3，其數(shù)99線性規(guī)劃及其對(duì)偶問題_課件100故原線性規(guī)劃問題的最優(yōu)解X*=（338/15，116/5,22/3,0,0，0)，目標(biāo)函數(shù)最優(yōu)值(1)由單純形表知:設(shè)備B的影子價(jià)格為：4/15(千元/臺(tái)時(shí))18（千元）/60（臺(tái)時(shí)）=0.3＞4/15，故借用B設(shè)備并不合算借用別的工廠的設(shè)備B，每月可借用60臺(tái)時(shí)，借金1.8萬元?jiǎng)t借用設(shè)備的租金為:故原線性規(guī)劃問題的最優(yōu)解X*=（338/15，116/101(2)設(shè)Ⅳ及V生產(chǎn)的產(chǎn)量分別為x7，x8，則其各自在最終單純形表對(duì)應(yīng)的列向量故生產(chǎn)產(chǎn)品Ⅳ在經(jīng)濟(jì)上不合算故生產(chǎn)產(chǎn)品Ⅳ在經(jīng)濟(jì)上不合算102所以生產(chǎn)產(chǎn)品V在經(jīng)濟(jì)上合算·由單純性表知:所以生產(chǎn)產(chǎn)品V在經(jīng)濟(jì)上合算·103故線性規(guī)劃最優(yōu)解X*=（107/4,31/2,0,0,0,0，55/4)T目標(biāo)函數(shù)最優(yōu)值Z*=136.9625故線性規(guī)劃最優(yōu)解X*=（107/4,31/2,0,0,0,104對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行(正則解)，但它對(duì)應(yīng)著一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正），所以也可以說是從一個(gè)對(duì)偶基可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的正則解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)正則解，此正則解對(duì)應(yīng)著另一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正）。如果得到的正則解的分量皆非負(fù)則該正則解為最優(yōu)解。也就是說，對(duì)偶單純形法在迭代過程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的正則解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。4.4對(duì)偶單純形法對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一105前節(jié)講到原問題與對(duì)偶問題的解之間的對(duì)應(yīng)關(guān)系時(shí)指出：在單純形表中進(jìn)行迭代時(shí)，在b列中得到的是原問題的基可行解，而在檢驗(yàn)數(shù)行得到的是對(duì)偶問題的基解。通過逐步迭代，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問題的解也是基可行解時(shí)，根據(jù)性質(zhì)(2)、(3)可知，已得到最優(yōu)解。即原問題與對(duì)偶問題都是最優(yōu)解。根據(jù)對(duì)偶問題的對(duì)稱性，可以這樣考慮：若保持對(duì)偶問題的解是基可行解，即cj?CBB-1Pj≤0，而原問題在非可行解的基礎(chǔ)上，通過逐步迭代達(dá)到基可行解，這樣也得到了最優(yōu)解。其優(yōu)點(diǎn)是原問題的初始解不一定是基可行解，可從非基可行解開始迭代。前節(jié)講到原問題與對(duì)偶問題的解之間的對(duì)應(yīng)關(guān)系時(shí)指出：在單純形表1064.4

對(duì)偶單純形法設(shè)原問題為

maxz=CX

AX=b

X≥0又設(shè)B是一個(gè)基。不失一般性，令B=(P1，P2，…，Pm)，它對(duì)應(yīng)的變量為XB=(x1，x2，…,xm)。當(dāng)非基變量都為零時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，設(shè)(B-1b)i＜0，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問題保持可行解，它的各分量是(1)對(duì)應(yīng)基變量x1，x2，…,xm的檢驗(yàn)數(shù)是σi=ci?zi=ci

?

CBB-1Pj=0，i=1,2,…,m(2)對(duì)應(yīng)非基變量xm+1，…，xn的檢驗(yàn)數(shù)是σj=cj?

zj=cj?CBB-1Pj≤0，j=m+1,…,n4.4

對(duì)偶單純形法設(shè)原問題為

max1074.4

對(duì)偶單純形法每次迭代是將基變量中的負(fù)分量xl取出，去替換非基變量中的xk，經(jīng)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問題來看，經(jīng)過每次迭代，原問題由非可行解往可行解靠近。當(dāng)原問題得到可行解時(shí)，便得到了最優(yōu)解。4.4

對(duì)偶單純形法每次迭代是將基變量中的負(fù)分量xl取出，1084.4

對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：(1)根據(jù)線性規(guī)劃問題，列出初始單純形表。檢查b列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。(2)確定換出變量。按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量(3)確定換入變量。在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無可行解，停止計(jì)算。若存在αlj＜0(j=1,2,…，n),計(jì)算4.4

對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：1094.4

對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：按θ規(guī)則所對(duì)應(yīng)的列的非基變量xk為換入變量，這樣才能保持得到的對(duì)偶問題解仍為可行解。(4)以αlk為主元素，按原單純形法在表中進(jìn)行迭代運(yùn)算，得到新的計(jì)算表。重復(fù)步驟(1)～(4)。4.4

對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：1104.4

對(duì)偶單純形法例6用對(duì)偶單純形法求解minw=2x1+3x2+4x3x1+2x2+x3≥32x1?x2+3x3≥4x1，x2，x3≥0解：先將此問題化成下列形式，以便得到對(duì)偶問題的初始可行基maxz=?2x1?

3x2?

4x3?x1?

2x2?

x3+x4=?3?2x1+x2?

3x3+x5=?4xj≥0，j=1,2,…,54.4

對(duì)偶單純形法例6用對(duì)偶單純形法求解minw1114.4

對(duì)偶單純形法例6的初始單純形表，見表2-6。從表2-6看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。

4.4

對(duì)偶單純形法例6的初始單純形表，見表2-6。1124.4

對(duì)偶單純形法換出變量的確定：換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟(3)，即在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無可行解，停止計(jì)算。按上述對(duì)偶單純形法計(jì)算步驟(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量。計(jì)算min(?3,?4)=?4故x5為換出變量。故x1為換入變量。換入、換出變量的所在列、行的交叉處“?2”為主元素。按單純形法計(jì)算步驟進(jìn)行迭代，得表2-7。4.4

對(duì)偶單純形法換出變量的確定：按上述對(duì)偶單純形法計(jì)算1134.4

對(duì)偶單純形法4.4

對(duì)偶單純形法1144.4

對(duì)偶單純形法表2-8中，b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，故問題的最優(yōu)解為X*=(11/5，2/5，0，0，0)T若對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為y1和y2，則對(duì)偶問題的最優(yōu)解為Y*=(y1*,y2*)=(8/5,1/5)4.4

對(duì)偶單純形法表2-8中，b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全1154.4

對(duì)偶單純形法從以上求解過程可以看到對(duì)偶單純形法有以下優(yōu)點(diǎn)：(1)初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。(2)當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對(duì)偶問題，然后用對(duì)偶單純形法求解。(3)在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時(shí)需要用對(duì)偶單純形法，這樣可使問題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問題，很難找到一個(gè)初始可行基，因而這種方法在求解線性規(guī)劃問題時(shí)很少單獨(dú)應(yīng)用。4.4

對(duì)偶單純形法從以上求解過程可以看到對(duì)偶單純形法有以1165EXCEL求解線性規(guī)劃5EXCEL求解線性規(guī)劃1176線性規(guī)劃靈敏度分析6.1目標(biāo)函數(shù)系數(shù)的靈敏度分析6.2右端項(xiàng)的靈敏度分析6線性規(guī)劃靈敏度分析6.1目標(biāo)