運(yùn)籌學(xué)課程講義

運(yùn)籌學(xué)課程講義第一部分線性規(guī)劃第一章線性規(guī)劃的基本性質(zhì)1.1線性規(guī)劃的數(shù)學(xué)模型一、 線性規(guī)劃問(wèn)題的特點(diǎn)勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子售價(jià)30元/個(gè)。生產(chǎn)桌子和椅子需木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷售收入最大？maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012例：某工廠生產(chǎn)某一種型號(hào)的機(jī)床。每臺(tái)機(jī)床上需要2.9m、2.1m、1.5m的軸，分別為1根、2根和1根。這些軸需用同一種圓鋼制作，圓鋼的長(zhǎng)度為74m。如果要生產(chǎn)100臺(tái)機(jī)床，問(wèn)應(yīng)如何安排下料，才能用料最省？二、 數(shù)學(xué)模型的標(biāo)準(zhǔn)型1.繁寫形式2.縮寫形式向量形式矩陣形式

三、 任一模型如何化為標(biāo)準(zhǔn)型？1.若原模型要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化，如何將其化為最小化問(wèn)1.題？2.若原模型中約束條件為不等式，如何化為等式？2.若原模型中約束條件為不等式，如何化為等式？3.若原模型中變量xk是自由變量，如何化為非負(fù)變量?k4.若原模型中變量X.有上下界，如何化為非負(fù)變量?j3.若原模型中變量xk是自由變量，如何化為非負(fù)變量?k4.若原模型中變量X.有上下界，如何化為非負(fù)變量?jmaxz=一5x一6x一7x123一x+5x一3xn15

123一5x一6x+10x<20< 1 2 3x一x一x=一5

123x<0,x>0,x無(wú)約束123令x'=-x,x=x'-x”，x',x”>0,-Z=Z'1 1 3 3 3 3 3minz'=-5x'+6x+7x'一7x''+0x一Mx一Mx1 2 3 3 5 6 7x'+5x—3x'+3x''—x+x=151 2 3 3 4 65x'一6x+10x'一10x''+x=20< 1 2 3 3 5x'+x+x'—x''+x=—5

12337x',x,x',x'',x,x,x,x>0

123345671.2圖解法該法簡(jiǎn)單直觀，平面作圖適于求解二維問(wèn)題。使用該法求解線性規(guī)劃問(wèn)題時(shí)，不必把原模型化為標(biāo)準(zhǔn)型。、圖解法步驟由全部約束條件作圖求出可行域作出一條目標(biāo)函數(shù)的等值線平移目標(biāo)函數(shù)等值線，作圖求解最優(yōu)點(diǎn)，再算出最優(yōu)值、從圖解法看線性規(guī)劃問(wèn)題解的幾種情況有唯一最優(yōu)解有無(wú)窮多組最優(yōu)解3.有唯一最優(yōu)解有無(wú)窮多組最優(yōu)解3.無(wú)可行解無(wú)有限最優(yōu)解（無(wú)界解）minz=6x+4x122x+x>1123<3x+4x>-122x,x>012最優(yōu)解（丄,0），最優(yōu)值32直觀結(jié)論：1）線性規(guī)劃問(wèn)題的可行域?yàn)橥辜厥馇闆r下為無(wú)界域但有有限個(gè)頂點(diǎn)）或空集；2）線性規(guī)劃問(wèn)題若有最優(yōu)解，一定可以在其可行域的頂點(diǎn)上得到。1.3線性規(guī)劃的基本概念和基本定理一、 線性規(guī)劃問(wèn)題的基與解可行解最優(yōu)解基基向量非基向量基變量非基變量基本解基本可行解最優(yōu)基本可行解退化的基本解二、 幾何意義上的幾個(gè)基本概念凸集凸組合頂點(diǎn)三、 線性規(guī)劃問(wèn)題的基本定理定理1：若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集。引理1：線性規(guī)劃問(wèn)題的可行解X=(x,x,,X)T為基本可行解的充要12n條件是X的正分量對(duì)應(yīng)的系數(shù)列向量是線性無(wú)關(guān)的。定理2：線性規(guī)劃問(wèn)題的基本可行解對(duì)應(yīng)于可行域的頂點(diǎn)。引理2：K是有界凸集，則任何一點(diǎn)XeK可表示為K的頂點(diǎn)的凸組合。定理3：如果線性規(guī)劃問(wèn)題有有限最優(yōu)解，則其目標(biāo)函數(shù)最優(yōu)值一定可以在可行域的頂點(diǎn)上達(dá)到。四、 求解線性規(guī)劃問(wèn)題的基本思路在有限個(gè)基本可行解中尋找最優(yōu)基本可行解。找一個(gè)基本可行解(m個(gè)線性無(wú)關(guān)的系數(shù)列向量)，由其換到另一個(gè)基本可行解。實(shí)質(zhì)即為換基。前提是保證新的基本可行解的目標(biāo)函數(shù)值比原來(lái)的更優(yōu)而不是更劣。第二章單純形法它是求解線性規(guī)劃最為成熟的算法。勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子售價(jià)30元/個(gè)，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷售收入最大？maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012將其變形，得4x+3x+x=1201232x+x+x=50124x,x,x,x>011234將xx對(duì)應(yīng)的單位矩陣作為初始可行基。令xx為基變量，xx為非TOC\o"1-5"\h\zxx xx xx3 4 3 4 1 2基變量。原模型變形為maxz=50x+30x12x=120一4x一3x3 1 2ix=50一2x一x41 2x,x,x,x>01234如果令非基變量「x等于零，得一個(gè)基本可行解（0,0，120,50）,12對(duì)應(yīng)的目標(biāo)函數(shù)值z(mì)=0最優(yōu)性檢驗(yàn)：該解是否最優(yōu)？顯然不是。經(jīng)濟(jì)意義分析：,x等于零12意味著家具廠不開工生產(chǎn),銷售收入為零,資源未得到充分利用。數(shù)學(xué)角度分析：非基變量x,x前的系數(shù)都為正，表明目標(biāo)函數(shù)值有增12

加的可能。只要將系數(shù)為正的非基變量與某一基變量對(duì)換，當(dāng)換入變量的值增加時(shí)，目標(biāo)函數(shù)值就可能增加。換基迭代：尋找下一個(gè)可行解需要進(jìn)行換基迭代。換基后需滿足：（1）新的解仍是基本可行解；（2）目標(biāo)函數(shù)得到改善。選擇入基變量：x,x系數(shù)均為正。對(duì)求目標(biāo)函數(shù)極大化的問(wèn)題，我們12希望目標(biāo)值增加得越快越好，因此應(yīng)選系數(shù)最大的,入基。1選擇出基變量：x入基后，其值從零增加并引起其他變量取值的變化。1由問(wèn)題的典則表達(dá)式和變量必須取正值的條件，得下列不等式關(guān)系：x=120-4x-3x>03 1 2x=50-2x-x>04 1 2因迭代后x仍為取零值的非基變量，上式可簡(jiǎn)化為2120-4x>0150-2x>01很明顯，只有選x=min（120/4,50/2）=25時(shí)，才能使上述不等式成立，1并使基變量x變?yōu)榱悖脻M足非基變量必須為零的條件，所以可令4x出基，新的典則方程變?yōu)?4x+x=120一3xTOC\o"1-5"\h\z1 3 22x=50一x一x1 2 4化簡(jiǎn)后得x=25一0.5x一0.5x化簡(jiǎn)后得1 2 4x=20一x+2x3 2 4代入目標(biāo)函數(shù)可得z代入目標(biāo)函數(shù)可得z=1250+5x一25x2 2 4得到下一個(gè)基本可行解（25，0，20，0），并完成了第一次迭代。新解是最優(yōu)解嗎？需進(jìn)行最優(yōu)檢驗(yàn)。由于目標(biāo)函數(shù)中x的系數(shù)仍為2正，說(shuō)明多生產(chǎn)椅子仍有利可圖，該解仍不是最優(yōu)解。再次迭代。

入基，X入基，X3出基’換基后典則形式變?yōu)閦=1350—5x一15xTOC\o"1-5"\h\z3 3 4x=15+0.5x一1.5x1 3 4x=20一x+2x2 3 4第三個(gè)基本可行解為（15，20，0，0），松弛變量都已為零，表明資源已得到充分利用；非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)值，說(shuō)明目標(biāo)函數(shù)已無(wú)法進(jìn)一步改善，因此該解已是最優(yōu)解。2.1單純形法原理、構(gòu)造初始可行基引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型若約束條件中附加變量的系數(shù)是-1或原約束即為等式，則必須引入人工變量，以構(gòu)成初始可行基目標(biāo)函數(shù)中，附加變量的系數(shù)為0,而人工變量的系數(shù)為M（很大的正數(shù)）、求出一個(gè)基本可行解用非基變量表示基變量和目標(biāo)函數(shù)式+x）54x+3x+8x+M（2—x一x+x）+M（5一2x+x）51 2 3 1 3 4 2 5=（4-M）x+（3-M）x+（8-3M）x+Mx+Mx+7M1 2 3 4 5求出一個(gè)基本可行解及相應(yīng)的z值三、最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)的依據(jù)一檢驗(yàn)數(shù)。j最優(yōu)解判別定理：若在極小化問(wèn)題中，對(duì)于某個(gè)基本可行解，所有檢驗(yàn)數(shù)。＞0,且人工變量為0,則這個(gè)基本可行解是最優(yōu)j解。對(duì)于極大化問(wèn)題，只要把上述定理中飩＞0改成。＜0即可。jj這里的檢驗(yàn)數(shù)。即為（c-z）。jjj無(wú)窮多最優(yōu)解判別定理：若在極小化問(wèn)題中,對(duì)于某個(gè)基本可行解，所有檢驗(yàn)數(shù)，＞0,又存在某個(gè)非基變量的檢驗(yàn)數(shù)為0，j且人工變量為0,則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。無(wú)可行解情況若在極小化問(wèn)題中，對(duì)于某個(gè)基本可行解，所有檢驗(yàn)數(shù)＞0，j但人工變量工0,則該線性規(guī)劃問(wèn)題無(wú)可行解。四、基變換基本可行解的改進(jìn)定理?yè)Q入變量的確定換出變量的確定最小非負(fù)比值規(guī)則Q=b/a=min{b/ala＞0}rrkiiikik在單純形法迭代中,基變換帶來(lái)可行域頂點(diǎn)的變換,且相鄰兩次迭代所對(duì)應(yīng)的頂點(diǎn)也是相鄰的。無(wú)有限最優(yōu)解（無(wú)界解）判定定理：若在極小化問(wèn)題中,對(duì)于

某個(gè)基本可行解，有一個(gè)非基變量的檢驗(yàn)數(shù)＜0,但P列中kk沒(méi)有正元素，且人工變量為0，則線性規(guī)劃問(wèn)題無(wú)有限最優(yōu)解（具有無(wú)界解）。2.2單純形法的表格形式一、構(gòu)造初始可行基，并計(jì)算檢驗(yàn)蛻j。=C-zjjj12mjBjz=(c,c,?,c)?P=(C)?P'12mjBjj二、從表中找到基本可行解和相應(yīng)目標(biāo)函數(shù)值三、最優(yōu)性檢驗(yàn)四、基變換1.換入變量的確定負(fù)檢驗(yàn)數(shù)中最小2.換出變量的確定最小非負(fù)比值規(guī)則3.主元素的確定換入元素所在列和換出元素所在行交點(diǎn)處二、從表中找到基本可行解和相應(yīng)目標(biāo)函數(shù)值三、最優(yōu)性檢驗(yàn)四、基變換1.換入變量的確定負(fù)檢驗(yàn)數(shù)中最小2.換出變量的確定最小非負(fù)比值規(guī)則3.主元素的確定換入元素所在列和換出元素所在行交點(diǎn)處的元素4.取主變換4.取主變換通過(guò)矩陣行的初等變換，把換入向量變換為單位列向量。即基變換，亦即單純形法的一次迭代。2.3大M法和兩階段法根據(jù)處理人工變量的方法不同，單純形法的兩種常見(jiàn)形式。大M法也叫罰函數(shù)法，前已介紹。兩階段法將線性規(guī)劃問(wèn)題的求解分為兩個(gè)階段。第一階段：判斷原線性規(guī)劃問(wèn)題是否有可行解。該階段所要求解的線性規(guī)劃問(wèn)題的約束條件即原問(wèn)題的約束條件，而目標(biāo)函數(shù)取全部人工變量之和，求其最小值。若求解結(jié)果是上述目標(biāo)函數(shù)的最小值為0，則說(shuō)明所有人工變量都能退出基，原問(wèn)題有可行解，且第一階段的最終單純型表上的基本可行解就是原問(wèn)題的一個(gè)基本可行解。若求解的結(jié)果是上述目標(biāo)函數(shù)的最小值大于0，則說(shuō)明最終人工變量不能完全退出基，原問(wèn)題無(wú)可行解，應(yīng)停止計(jì)算。第二階段：求解原線性規(guī)劃問(wèn)題的最優(yōu)解。以第一階段的最終單純型表為基礎(chǔ)，去掉其中的人工變量列，把目標(biāo)函數(shù)換成原問(wèn)題的目標(biāo)函數(shù)，并修正因c改變而改變的(C)T、o和jBj-Z。以此作為第二階段的初始表，繼續(xù)迭代，得原問(wèn)題的最優(yōu)解。438000迭代次數(shù)(c)TB基變量x1x2xx34xb51■8_x3-2102-113x20023-1922.4退化問(wèn)題、什么是退化當(dāng)基本解、基本可行解、最優(yōu)基本可行解中有基變量為0時(shí)，即出現(xiàn)了退化。退化情況下，即使存在最優(yōu)解，也可能出現(xiàn)循環(huán)現(xiàn)象，即迭代過(guò)程總是重復(fù)解的某一部分序列，目標(biāo)函數(shù)值總是不變，永遠(yuǎn)達(dá)不到最優(yōu)解。二、 攝動(dòng)法1.攝動(dòng)法簡(jiǎn)介對(duì)線性規(guī)劃原問(wèn)題，為了避免退化情況下發(fā)生循環(huán)，而使向量b攝動(dòng)。確定換出變量的步驟舉例三、 勃蘭特方法法則1：在極小化問(wèn)題中，如果有幾個(gè)檢驗(yàn)數(shù)c-z）都是負(fù)的，那jj么選其中下標(biāo)最小的非基變量作為換入變量。法則2：在極小化問(wèn)題中，根據(jù)最小非負(fù)比值規(guī)則確定換出變量時(shí)，如果有幾個(gè)比值同時(shí)達(dá)到最小比值，那么選其中下標(biāo)最小的基變量作為換出變量。定理：只要在迭代時(shí)，遵循上述法則，就不會(huì)出現(xiàn)循環(huán)。3.5改進(jìn)單純形法每次迭代只計(jì)算換入列、常數(shù)列及檢驗(yàn)數(shù)行以提高計(jì)算效率。一、單純形法的矩陣形式用矩陣（分塊）形式表示線性規(guī)劃標(biāo)準(zhǔn)型

把矩陣A、C、X分別按“基”與“非基”分成兩塊A=(B,N)C=(C,C)BNXBXN其中B=N=P，PB=N=P，P，1P，Pm+1m+P)m，P)nC=(c,c,?,c)C=(c,c,?,c)B12C=(c,cN,?,c2x1x2xm+1xm+2將分塊結(jié)果代入標(biāo)準(zhǔn)型，BX+NX=bBNX>0,XBNminzminz=CXBXNN用矩陣（分塊）形式表示基本解、目標(biāo)函數(shù)值及檢驗(yàn)數(shù)X=B一ib-B一1NXBNz=CB」+(C-CB一iN)XBNBNb=C-CB_1NNNB令X=0,可得NX=B_]bBz=CB_1bB3.單純型乘子Y。Y=CBB、改進(jìn)單純形法的求解步驟1.完成第0次迭代表。構(gòu)造初始可行基，計(jì)算B-1。再利用公式0b=C-CB-1N=C-CN，計(jì)算第0次迭代表中的檢驗(yàn)N0N0 B0 00N0B00ork數(shù)。確定換入向量為P，換出向量為P，主元素是orkkBr計(jì)算B_1i+1構(gòu)造基矩陣Bi+1計(jì)算B_1i+1第一種方法：已知B，用初等變換法求其逆矩陣B_1。i+1 i+1第二種方法：已知B_1和第i次迭代表的換入列P'，主元素為a，,i k rk通過(guò)取主變換求出B_1。i+1計(jì)算第i+1次迭代表的常數(shù)列和檢驗(yàn)數(shù)。常數(shù)列=B_1?bY=C?B_ii+1Bi+1 i+1=CN=CNi+1 Ni+1-YNi+1 i+1進(jìn)行最優(yōu)性檢驗(yàn)如果。＞0,且人工變量為0則已經(jīng)得到最優(yōu)解。否則，轉(zhuǎn)下步。N5.計(jì)算第i+1次迭代表中的換入列P'kP'=B-?Pk i+1 k6.確定第i+1次迭代表中換出向量的下標(biāo)B。r最小非負(fù)比值規(guī)則令i=i+1,返回步驟2。三、 逆的乘積形式B_1=EE??EEi+1ii_1 10改進(jìn)單純形法的基本思想就是給定初始基本可行解后,通過(guò)修改舊基的逆來(lái)獲得現(xiàn)行基的逆,進(jìn)而完成單純形法的其他運(yùn)算。四、 計(jì)算舉例01212000121200「-1o—T11_211_22常數(shù)列105」L_2Y=C?B-i=(8,3J 03 B3 3 _2 1b =C-YN=(ccccc)_Y(PPPPP)N3 N33314567 314567=(400MM)-(2 3)1_1010、I00_101丿(400MM)_(2_2 _3 23)=(223M-2M-3)第三章線性規(guī)劃的對(duì)偶原理3.1線性規(guī)劃的對(duì)偶問(wèn)題一、 對(duì)偶問(wèn)題的提出換位思考家具廠的線性規(guī)劃問(wèn)題，該問(wèn)題站在家具廠管理者的角度追求銷售收入最大maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012某企業(yè)家有一批待加工的訂單，有意利用該家具廠的木工和油漆工資源來(lái)加工他的產(chǎn)品。他需要與家具廠談判付給該廠每個(gè)工時(shí)的價(jià)格。如果該企業(yè)家已對(duì)家具廠的經(jīng)營(yíng)情況有詳細(xì)了解，他可以構(gòu)造一個(gè)數(shù)學(xué)模型來(lái)研究如何才能既讓家具廠覺(jué)得有利可圖，肯把資源出租給他，又使自己付的租金最少。目標(biāo):租金最少；y-付給木工工時(shí)的租金；y-付給油漆工工時(shí)的租金12minw=120y+50y12所付租金應(yīng)不低于家具廠利用這些資源所能得到的利益1）支付相當(dāng)于生產(chǎn)一個(gè)桌子的木工、油漆工的租金應(yīng)不低于生產(chǎn)一個(gè)桌子的收入4y+2y>50122）支付相當(dāng)于生產(chǎn)一個(gè)椅子的木工、油漆工的租金應(yīng)不低于生產(chǎn)一個(gè)椅子的收入3y+y>30123）付給每種工時(shí)的租金應(yīng)不小于零 y>0,y>012二、 原問(wèn)題與對(duì)偶問(wèn)題的數(shù)學(xué)模型對(duì)稱形式的對(duì)偶原問(wèn)題和對(duì)偶問(wèn)題只含有不等式約束時(shí)，一對(duì)對(duì)偶問(wèn)題的模型是對(duì)稱的，稱為對(duì)稱形式的對(duì)偶。原問(wèn)題：minz=CX<AX>bX>0對(duì)偶問(wèn)題：maxw=YbYA<CY>0非對(duì)稱形式的對(duì)偶若原問(wèn)題的約束條件全部是等式約束（即線性規(guī)劃的標(biāo)準(zhǔn)型），即一minz=CXAX=bX>0則其對(duì)偶問(wèn)題的數(shù)學(xué)模型為maxw=YbYA<CY是自由變量可把原問(wèn)題寫成其等價(jià)的對(duì)稱形式：minz=CXAX>b

AX<bX?0minz=CXb-bX>0設(shè)Y]=（y],y2,…,ym）,Y2=（ym+1，ym+2，?,y2m）。根據(jù)對(duì)稱形式的對(duì)偶模型,寫出上述問(wèn)題的對(duì)偶問(wèn)題：maxw=(Y1maxw=(Y1,Y2)b-b（丫1，丫2）?「a]c-A.0 Y2,0maxw=(Y1-Y2)?b(Y1-Y2)A.C丫詳0 Y2,0令Y=Y1-Y2,得對(duì)偶問(wèn)題為：12,maxw=YbYA<CY是自由變量

原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)minz目標(biāo)函數(shù)maxwn個(gè)變量n個(gè)約束變量＞0約束＜變量＜0約束＞自由變量約束=m個(gè)約束m個(gè)變量約束＞變量＞0約束＜變量＜0約束=自由變量約束條件的限定向量目標(biāo)函數(shù)的價(jià)值向量目標(biāo)函數(shù)的價(jià)值向量約束條件的限定向量maxz=2x+x+3x+x1 2 3 4x+x+x+x<5原問(wèn)題： 21x-+3x=-4TOC\o"1-5"\h\zV 1 2 3x一x+x>1134x,x>0,x,x無(wú)約束1 3 2 4minw=5y一4y+y1 2 3y+2y+y>21 2 3對(duì)偶問(wèn)題： y1-y2=1vy+3y一y>3123y+y=11 3y>0,y無(wú)約束，y<01 2 3

minz=3x一2x一3x+4x1234原問(wèn)題：x一2x+3x+4x<31234原問(wèn)題：x+3x+4x>-5TOC\o"1-5"\h\zV 2 3 42x一3x一7x一4x=21 2 3 4x>0,x<0,x,x無(wú)約束1 4 2 3maxw=3y一5y+2y1 2 3y+2y<313對(duì)偶問(wèn)題： 一2y1+y2-3y3=2v3y+3y一7y=-31234y+4y一4y>41 2 3y<0,y>0,y無(wú)約束1233.2對(duì)偶問(wèn)題的基本性質(zhì)和基本定理一、 對(duì)稱性定理對(duì)稱性定理：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題、弱對(duì)偶性定理弱對(duì)偶性定理：若X（0）和Y（0）分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則(0)>Y(0)>Y(0)b。三、 最優(yōu)性定理最優(yōu)性定理：若X（0）和Y（0）分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，且有CX（0）=Y（0）b,則X（0）和Y（0）分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。四、 對(duì)偶定理對(duì)偶定理：有一對(duì)對(duì)偶的線性規(guī)劃問(wèn)題，若其一有一個(gè)有限的最優(yōu)解，則另一個(gè)也有最優(yōu)解，且相應(yīng)的目標(biāo)函數(shù)值相等。若任一個(gè)問(wèn)題具有無(wú)界解，則另一個(gè)問(wèn)題無(wú)可行解。五、 單純型乘子Y的定理單純型乘子Y的定理：若線性規(guī)劃原問(wèn)題有一個(gè)對(duì)應(yīng)于基B的最優(yōu)基本可行解，則此時(shí)的單純型乘子丫=CBi是相應(yīng)于對(duì)偶問(wèn)題的一B個(gè)最優(yōu)解。六、 對(duì)稱形式對(duì)偶的互補(bǔ)松弛定理對(duì)稱形式對(duì)偶的互補(bǔ)松弛定理：若X（o）和Y（o）分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則X（o）和Y（o）都是最優(yōu)解的充要條件是，對(duì)所有i和j,下列關(guān)系式成立：如果x（o）＞O,必有Y（o）P=cjjj如果Y（o）P＜c，必有x（o）=Ojjj如果y（°）＞0,必有AX（o）=biii如果AX（o）＞b，必有y（0）=0iii其中P是A的第j列，A是A的第i行。ji互補(bǔ)松弛定理意味著：如果原問(wèn)題最優(yōu)解X（0）中第j個(gè)變量X（0）為正，j則其對(duì)偶問(wèn)題中與之對(duì)應(yīng)的第j個(gè)約束式在最優(yōu)情況下必呈嚴(yán)格等式（即其松弛變量為0）；而如果對(duì)偶問(wèn)題中第j個(gè)約束式在最優(yōu)情況下呈嚴(yán)格不等式，則原問(wèn)題最優(yōu)解X（0）中第j個(gè)變量X（0）必為0。類似地，j如果對(duì)偶問(wèn)題最優(yōu)解Y（0）中第i個(gè)對(duì)偶變量y（0）為正，則其原問(wèn)題中i與之對(duì)應(yīng)的第i個(gè)約束在最優(yōu)情況下必呈嚴(yán)格等式（即其剩余變量為0）；而如果原問(wèn)題中第i個(gè)約束在最優(yōu)情況下呈嚴(yán)格不等式，則對(duì)偶問(wèn)題最優(yōu)解Y（0）中第i個(gè)對(duì)偶變量y（°）必為0。i互補(bǔ)松弛性：YX=oYX=0x,Y為最優(yōu)解SS對(duì)一對(duì)對(duì)偶規(guī)劃的最優(yōu)解而言，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量的值為非零，則該約束條件取嚴(yán)格等式；反之，如果某個(gè)約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。七、 非對(duì)稱形式對(duì)偶的互補(bǔ)松弛定理非對(duì)稱形式對(duì)偶的互補(bǔ)松弛定理：若X（o）和Y（o）分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則X（o）和Y（o）都是最優(yōu)解的充要條件是，對(duì)所有j,下列關(guān)系式成立：如果x（0）>0,必有Y（o）P=cjjj如果Y（o）P<c，必有x（o）=Ojjjmaxz=x+x12例：已知線性規(guī)劃問(wèn)題-X1+X2+X3-2彳一2x+x—x<1123x,x,x>0123試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解該問(wèn)題存在可行解，如x=（0,0,0）又對(duì)偶問(wèn)題為minw=2y+y12-y-2y>112y+y>122y-y>012y,y>012由第一個(gè)約束條件知對(duì)偶問(wèn)題無(wú)可行解,由此可知其原問(wèn)題無(wú)最優(yōu)解八、 最優(yōu)對(duì)偶變量（影子價(jià)格）的經(jīng)濟(jì)解釋由對(duì)偶定理可知,當(dāng)達(dá)到最優(yōu)解時(shí),原問(wèn)題和對(duì)偶問(wèn)題的目標(biāo)函數(shù)值相等。如果在得到最優(yōu)解時(shí)，某種資源并未完全利用，其剩余量就是該約束中剩余變量的取值，那么該約束相對(duì)應(yīng)的影子價(jià)格一定為零。因?yàn)樵诘玫阶顑?yōu)解時(shí)，這種資源并不緊缺，故此時(shí)再增加這種資源不會(huì)帶來(lái)任何效益。反之，如果某種資源的影子價(jià)格大于零，就說(shuō)明再增加這種資源的可獲量，還回帶來(lái)一定的經(jīng)濟(jì)效益，即在原問(wèn)題的最優(yōu)解中，這種資源必定已被全部利用，相應(yīng)的約束條件必然保持等式。3.3對(duì)偶單純形法一、 對(duì)偶單純形法與單純形法的區(qū)別單純形法在整個(gè)迭代過(guò)程中，始終保持原問(wèn)題的可行性，即常數(shù)列>0,而檢驗(yàn)數(shù)C-CB-A（即C-YA）由有負(fù)分量逐步變?yōu)槿俊?（即B變?yōu)闈M足YA<C,Y是對(duì)偶問(wèn)題的可行解），即同時(shí)得到原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。對(duì)偶單純形法在整個(gè)迭代過(guò)程中，始終保持對(duì)偶問(wèn)題的可行性，即全部檢驗(yàn)數(shù)>0，而常數(shù)列由有負(fù)分量逐步變?yōu)槿?gt;0（即變?yōu)闈M足原問(wèn)題的可行性），即同時(shí)得到原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。二、 對(duì)偶單純形法的求解步驟和計(jì)算舉例給定一個(gè)初始對(duì)偶可行的基本解進(jìn)行最優(yōu)性檢驗(yàn)若現(xiàn)行常數(shù)列b'>0,則停止計(jì)算。否則，轉(zhuǎn)下步。確定換出變量將現(xiàn)行常數(shù)列b'中最小的負(fù)元素所在行的基變量換出確定換入變量最大負(fù)比值規(guī)則：在換出變量所在的第r行約束式中，找出各非基變量列中系數(shù)為負(fù)的那些元素，用相應(yīng)的檢驗(yàn)數(shù)。'分別除以這些負(fù)元j素，所得各負(fù)比值中最大者所在列即為換入列。以a'為主元素進(jìn)行取主變換rk返回步驟2，繼續(xù)迭代。三、 關(guān)于初始對(duì)偶可行的基本解構(gòu)造擴(kuò)充問(wèn)題minz=CXX+XPx=bB jjjwRX>0其中R是非基變量下標(biāo)的集合。再增加一個(gè)變量和一個(gè)約束條件，得到其擴(kuò)充問(wèn)題：minz=CXX+XPx=bB jjjWRx+乙x=Mn+1 jjwRx>0(i=1,2, ,n+1)i求擴(kuò)充問(wèn)題的初始對(duì)偶可行的基本解若基本解x(o)不是對(duì)偶可行的，即檢驗(yàn)數(shù)中有負(fù)的，并假設(shè)負(fù)檢驗(yàn)數(shù)B中最小的一個(gè)為Q，則以Q相應(yīng)的變量x為換入變量，以x為換出k k k n+1變量，即以a 為主元素進(jìn)行取主變換，可得到全部檢驗(yàn)數(shù)>0，即m+1,k得到一個(gè)對(duì)偶可行的基本解。用對(duì)偶單純形法求解擴(kuò)充問(wèn)題，并得到原問(wèn)題的解答因?yàn)閿U(kuò)充問(wèn)題的對(duì)偶問(wèn)題有可行解，根據(jù)對(duì)偶原理可知，擴(kuò)充問(wèn)題或無(wú)可行解或有有限最優(yōu)解。若擴(kuò)充問(wèn)題無(wú)可行解，則原問(wèn)題也無(wú)可行解，若擴(kuò)充問(wèn)題得到最優(yōu)解X（0=（x（0）,…,x（0）,x（O）），則X（0）=（x（0）,…,x（0））是原問(wèn)題的可仃解。右擴(kuò)充1 n n+1 1 n問(wèn)題的目標(biāo)函數(shù)最優(yōu)值與M無(wú)關(guān)，則X（0）就是原問(wèn)題的最優(yōu)解。4.計(jì)算舉例3.4靈敏度分析研究初始單純型表上的系數(shù)變化對(duì)最優(yōu)解的影響，研究這些系數(shù)在什么范圍內(nèi)變化時(shí)，原最優(yōu)基仍是最優(yōu)的；右原最優(yōu)基不再是最優(yōu)的如何用最簡(jiǎn)便的方法找到新的最優(yōu)解。假定線性規(guī)劃標(biāo)準(zhǔn)型最終表上已得到最優(yōu)基B,最優(yōu)結(jié)果為：-X■—B-1b—BX0N1- -1minz=CB-1bB、改變價(jià)值向量Cc'=c+Acrrr在最終表內(nèi)，x是非基變量rC，z=CB-1P均不變；僅j變化。B j B j rJ'=c'一z=c+Ac一z=J+Acrrrrrrrr若j'>0，即Ac>-a，則最優(yōu)解不變;若?！?lt;0，則原最優(yōu)基不再是最優(yōu)的了。以x為換入變量，把最終表rr上的。換成廠，c換成C',繼續(xù)用單純形法求解。rrrr在最終表內(nèi)，x是基變量rC要改變，并因此影響到各個(gè)檢驗(yàn)數(shù)。B若max/a'Ia若max/a'Ia'<0 Ackjkjr<min/a'Ia'>。｝，則所有q'>0，kjkjj即最優(yōu)解不變。若Ac超出上述允許變化范圍，即有.<o，則以原最終表為基礎(chǔ)，換rj上變化后的價(jià)值系數(shù)和檢驗(yàn)數(shù)，繼續(xù)迭代，可求出新的最優(yōu)解。二、 改變限定向量bb'=b+Ab\x 〕 \x 〕max｛一冊(cè)Id'>0\<Ab<min｛一 Id'<0\i〔d'irJriId'irJ

ir ir若Ab超過(guò)上述范圍，則新得到的解為不可行解。但由于，的變化不rr影響檢驗(yàn)數(shù)，故仍保持所有檢驗(yàn)數(shù)>0，即滿足對(duì)偶可行性。這時(shí)可在原最終表的基礎(chǔ)上，換上改變后的右端常數(shù)及相應(yīng)的一z值，用對(duì)偶單純形法繼續(xù)迭代，以求出新的最優(yōu)解。三、 改變約束矩陣A1.非基向量列p改變?yōu)閜'jj影響最終表上的第j列數(shù)據(jù)和第j個(gè)檢驗(yàn)數(shù)。q'=c—CB-1PjjBj若q'>0，則原最優(yōu)解仍是新問(wèn)題的最優(yōu)解。j若?！?lt;0，則原最優(yōu)基在非退化情況下不再是最優(yōu)基。這時(shí)，應(yīng)在原j最終表的基礎(chǔ)上，換上改變后的第j列數(shù)據(jù)B-1P和b',把x作為換入jjj變量，用單純形法繼續(xù)迭代。2.基向量列P改變?yōu)閜'jj重新計(jì)算四、 增加一個(gè)新的約束條件nXax<bm+1,jj m+1j=1AX<bm+1 m+1若原最優(yōu)解滿足這個(gè)新約束，則它就是新問(wèn)題的最優(yōu)解否則，引進(jìn)松弛變量乂，有n+1(A)X+(A)X+x=b

m+1BBm+1NNn+1m+1(b-(A)B-1b)>0m+1 m+1B則現(xiàn)行對(duì)偶可行的基本解是新問(wèn)題的可行解，亦即最優(yōu)解(b-(A)B-1b)<0m+1 m+1B則在原最終表的基礎(chǔ)上，增加新約束式的數(shù)據(jù)，通過(guò)矩陣行的初等變換，把原最終表上的各基向量列及新增列P化為單位陣，再用對(duì)偶n+1單純形法繼續(xù)求解。五、 增加一個(gè)新的變量對(duì)原問(wèn)題最優(yōu)解的可行性無(wú)影響。:c-CB-1Pn+1 B n+1，則原最優(yōu)解就是新問(wèn)題的最優(yōu)解b<0n+1，須把b<0n+1n+1作為換入變量，按單純形法繼續(xù)迭代，得到新的最優(yōu)解。第四章應(yīng)用實(shí)例4.1產(chǎn)銷平衡的運(yùn)輸問(wèn)題mnminz=乙乙cxijij

i=1j=1n乙x=a(i=1,2,…?,m)ij ij=1為x=b(j=1,2,…,n)ij jx>0(i=1,2,…，m;j=1,2,…，n)ij由于產(chǎn)銷平衡，有x111x121m乙ai=1x21x111x121m乙ai=1x21mnnmn=乙(乙x)=乙乙x=乙b

ijx22i=1xijj=1j=1i=1j=1xm2xmn較為簡(jiǎn)潔的求解方法—表上作業(yè)法不做要求）。另，可與整數(shù)規(guī)劃結(jié)合而帶來(lái)求解的方便。4.2套裁下料問(wèn)題思路舉例：某工廠要做100套鋼架，每套用長(zhǎng)為2.9m、2.1m和1.5m的元鋼各一根。已知原料長(zhǎng)7.4m,問(wèn)應(yīng)如何下料，可使所用原料最省。簡(jiǎn)單裁法將使料頭數(shù)量增多，應(yīng)使用套裁的方法。須先設(shè)計(jì)出若干種較好的套裁方案如下表,分設(shè)按各種方案下料的原料根數(shù)為x，可列寫其數(shù)學(xué)模型：i長(zhǎng)料7123452.9120102.1002211.531203合計(jì)7.47.37.27.16.6料頭00.10.20.30.8minz=0x+0.1x+0.2x+0.3x+0.8xTOC\o"1-5"\h\z1 2 3 4 5x+2x+x=1001242x+2x+x=1003 4 53x+x+2x+3x=1001 2 3 5x>0且為整數(shù)(j=1,2, ,5)j汽油混合問(wèn)題變量的選取，是模型設(shè)立的關(guān)鍵。邏輯關(guān)系的明晰，是模型設(shè)立的基礎(chǔ)。購(gòu)買汽車問(wèn)題明晰乘和的關(guān)系，用數(shù)字等數(shù)學(xué)符號(hào)將文字的約束關(guān)系表達(dá)出來(lái)產(chǎn)品加工問(wèn)題順序理清方可使表達(dá)式明了。投資計(jì)劃問(wèn)題列舉各可行計(jì)劃，