運籌學(xué)課程講義

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

三、任一模型如何化為標準型?1.若原模型要求目標函數(shù)實現(xiàn)最大化，如何將其化為最小化問題？1.2.若原模型中約束條件為不等式，如何化為等式?3.若原模型中變量xk2.若原模型中約束條件為不等式，如何化為等式?3.若原模型中變量xk是自由變量，如何化為非負變量?4.若原模型中變量xj有上下界，如何化為非負變量?maxz=-5x-6x-7x一x+5x一3x>15-5x-6x+10x<20x1-x2-x3=一5x<0,x>0,x無約束令x'=-x,x=x'-x'',x',x''>0,-Z=Z'TOC\o"1-5"\h\z1133333minz'=-5x'+6x+7x'一7x''+0x一Mx一Mx1233567x'+5x—3x'+3x''—x+x=151233465x'—6x+10x'—10x''+x=20v12335x'+x+x'—x''+x=—512337x',x,x',x",x,x,x,x>0123345672圖解法該法簡單直觀，平面作圖適于求解二維問題。使用該法求解線性規(guī)劃問題時，不必把原模型化為標準型。一、圖解法步驟1.由全部約束條件作圖求出可行域2.作出一條目標函數(shù)的等值線3.平移目標函數(shù)等值線，作圖求解最優(yōu)點，再算出最優(yōu)值一、圖解法步驟1.由全部約束條件作圖求出可行域2.作出一條目標函數(shù)的等值線3.平移目標函數(shù)等值線，作圖求解最優(yōu)點，再算出最優(yōu)值、從圖解法看線性規(guī)劃問題解的幾種情況有唯一最優(yōu)解有無窮多組最優(yōu)解無可行解無有限最優(yōu)解（無界解）minz=6x+4x2x1+x2-13最優(yōu)解（L,0），最優(yōu)值3<3x.+4xZ—2x.,x>0直觀結(jié)論：1）線性規(guī)劃問題的可行域為凸集，特殊情況下為無界域（但有有限個頂點）或空集；2）線性規(guī)劃問題若有最優(yōu)解，一定可以在其可行域的頂點上得到。1.3線性規(guī)劃的基本概念和基本定理一、線性規(guī)劃問題的基與解可行解最優(yōu)解基基向量非基向量基變量非基變量基本解基本可行解最優(yōu)基本可行解退化的基本解二、幾何意義上的幾個基本概念凸集凸組合頂點三、線性規(guī)劃問題的基本定理定理1：若線性規(guī)劃問題存在可行域，則其可行域是凸集。引理1：線性規(guī)劃問題的可行解乂=(x,x,,x)t為基本可行解的充要12n條件是X的正分量對應(yīng)的系數(shù)列向量是線性無關(guān)的。定理2：線性規(guī)劃問題的基本可行解對應(yīng)于可行域的頂點。引理2：K是有界凸集，則任何一點XeK可表示為K的頂點的凸組合。定理3：如果線性規(guī)劃問題有有限最優(yōu)解，則其目標函數(shù)最優(yōu)值一定可以在可行域的頂點上達到。四、求解線性規(guī)劃問題的基本思路在有限個基本可行解中尋找最優(yōu)基本可行解。找一個基本可行解(m個線性無關(guān)的系數(shù)列向量)，由其換到另一個基本可行解。實質(zhì)即為換基。前提是保證新的基本可行解的目標函數(shù)值比原來的更優(yōu)而不是更劣。第二章單純形法它是求解線性規(guī)劃最為成熟的算法。勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子售價30元/個，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？maxz=50x+30%'4%1+3%2<120<2%+%<50%『%2>0將其變形，得4%1+3%2+%3=120<2%.+%+%=50%,%,%,%>011234將%,%對應(yīng)的單位矩陣作為初始可行基。令%,%為基變量，%,%為非343412基變量。原模型變形為maxz=50%1+30%2%3=基變量。原模型變形為maxz=50%1+30%2<%=50-2%■-%%,%,%,%>011234如果令非基變量％,%等于零，得一個基本可行解（0，0，120,50），12對應(yīng)的目標函數(shù)值z=0最優(yōu)性檢驗：該解是否最優(yōu)？顯然不是。經(jīng)濟意義分析:％%等于零./V,意味著家具廠不開工生產(chǎn)，銷售收入為零，資源未得到充分利用。數(shù)學(xué)角度分析：非基變量％,%前的系數(shù)都為正，表明目標函數(shù)值有增12加的可能。只要將系數(shù)為正的非基變量與某一基變量對換，當換入變量的值增加時，目標函數(shù)值就可能增加。換基迭代：尋找下一個可行解需要進行換基迭代。換基后需滿足：（1）新的解仍是基本可行解；（2）目標函數(shù)得到改善。選擇入基變量：x?x系數(shù)均為正。對求目標函數(shù)極大化的問題，我們12希望目標值增加得越快越好，因此應(yīng)選系數(shù)最大他入基。1選擇出基變量r入基后，其值從零增加并引起其他變量取值的變化。1由問題的典則表達式和變量必須取正值的條件，得下列不等式關(guān)系:x=120-4x-3x>0x=50-2x-x>0因迭代后x仍為取零值的非基變量，上式可簡化為2120-4x>050-2x1>0很明顯，只有選x1=min（120/4,50/2）=25時，才能使上述不等式成立，并使基變量x變?yōu)榱?，正好滿足非基變量必須為零的條件，所以可令4x出基，新的典則方程變?yōu)閤44x+x=120-3x2x=50-x-x化簡后得x1=25-°?5x2-°5x4x=20-x+2x代入目標函數(shù)可得乙2=1250+5x2-25x4得到下一個基本可行解（25,0，20，0），并完成了第一次迭代。新解是最優(yōu)解嗎？需進行最優(yōu)檢驗。由于目標函數(shù)中x的系數(shù)仍為2正，說明多生產(chǎn)椅子仍有利可圖，該解仍不是最優(yōu)解。再次迭代。x入基，x出基，換基后典則形式變?yōu)?3z3=1350-5x3-15x4x=15+0.5x-1.5xx=20-x+2x第三個基本可行解為（15，20，0,0）,松弛變量都已為零，表明資源已得到充分利用；非基變量在目標函數(shù)中的系數(shù)全為負值，說明目標函數(shù)已無法進一步改善，因此該解已是最優(yōu)解。2.1單純形法原理一、構(gòu)造初始可行基引入附加變量，把數(shù)學(xué)模型化為標準型若約束條件中附加變量的系數(shù)是1或原約束即為等式，則必須引入人工變量，以構(gòu)成初始可行基目標函數(shù)中，附加變量的系數(shù)為0，而人工變量的系數(shù)為M（很大的正數(shù)）二、求出一個基本可行解用非基變量表示基變量和目標函數(shù)式4x+3x+8x+M（2—x—x+x）+M（5—2x—2x+x）123134255=（4-M）x+（3-M）x+（8-3M）x+Mx+Mx5+7M求出一個基本可行解及相應(yīng)的z值三、最優(yōu)性檢驗最優(yōu)性檢驗的依據(jù)一檢驗數(shù)。最優(yōu)解判別定理：若在極小化問題中，對于某個基本可行解，所有檢驗數(shù)°,0，且人工變量為0，則這個基本可行解是最優(yōu)J解。對于極大化問題，只要把上述定理中魄>0改成°<0即可。這里的檢驗數(shù)°即為（c-z）。JJJ無窮多最優(yōu)解判別定理：若在極小化問題中，對于某個基本可行解，所有檢驗乳,0，又存在某個非基變量的檢驗數(shù)為0，且人工變量為0，則線性規(guī)劃問題有無窮多最優(yōu)解。無可行解情況若在極小化問題中，對于某個基本可行解，所有檢驗數(shù),0，J但人工變量芝0，則該線性規(guī)劃問題無可行解。四、基變換基本可行解的改進定理換入變量的確定換出變量的確定最小非負比值規(guī)則o=b/a=min{b/ala>0}rrk^iikik在單純形法迭代中，基變換帶來可行域頂點的變換，且相鄰兩次迭代所對應(yīng)的頂點也是相鄰的。無有限最優(yōu)解（無界解）判定定理：若在極小化問題中，對于某個基本可行解，有一個非基變量的檢驗魏＜0,但P列中沒有正元素，且人工變量為0,則線性規(guī)劃問題無有限最優(yōu)解（具有無界解）。2.2單純形法的表格形式、構(gòu)造初始可行基，并計算檢驗麴J=c-zJJz=(c,c，…,c)?P=(C)?P'J12mJBJ二、從表中找到基本可行解和相應(yīng)目標函數(shù)值三、最優(yōu)性檢驗四、基變換換入變量的確定負檢驗數(shù)中最小換出變量的確定最小非負比值規(guī)則主元素的確定換入元素所在列和換出元素所在行交點處的元素取主變換通過矩陣行的初等變換，把換入向量變換為單位列向量。即基變換，亦即單純形法的一次迭代。2.3大M法和兩階段法根據(jù)處理人工變量的方法不同，單純形法的兩種常見形式。大M法也叫罰函數(shù)法，前已介紹。兩階段法將線性規(guī)劃問題的求解分為兩個階段。第一階段：判斷原線性規(guī)劃問題是否有可行解。該階段所要求解的線性規(guī)劃問題的約束條件即原問題的約束條件而目標函數(shù)取全部人工變量之和，求其最小值。若求解結(jié)果是上述目標函數(shù)的最小值為0，則說明所有人工變量都能退出基，原問題有可行解，且第一階段的最終單純型表上的基本可行解就是原問題的一個基本可行解。若求解的結(jié)果是上述目標函數(shù)的最小值大于0，則說明最終人工變量不能完全退出基，原問題無可行解，應(yīng)停止計算。第二階段：求解原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純型表為基礎(chǔ)，去掉其中的人工變量列，把目標函數(shù)換成原問題的目標函數(shù)，并修正因c改變而改變的（C）t、.和-z。以此作為第二階段的初始表，繼續(xù)迭代，得原問題的最優(yōu)解。438000迭代次數(shù)（c）T基變量匚xxxxbB1234518七-2102-113x20023-19」二22.4退化問題一、什么是退化當基本解、基本可行解、最優(yōu)基本可行解中有基變量為）時，即出現(xiàn)了退化。退化情況下，即使存在最優(yōu)解，也可能出現(xiàn)循環(huán)現(xiàn)象，即迭代過程總是重復(fù)解的某一部分序列，目標函數(shù)值總是不變，永遠達不到最優(yōu)解。二、攝動法攝動法簡介對線性規(guī)劃原問題，為了避免退化情況下發(fā)生循環(huán)，而使向量b攝動。確定換出變量的步驟舉例三、勃蘭特方法法則1：在極小化問題中，如果有幾個檢驗數(shù)C-z）都是負的，那JJ么選其中下標最小的非基變量作為換入變量。法則2：在極小化問題中，根據(jù)最小非負比值規(guī)則確定換出變量時，如果有幾個比值同時達到最小比值，那么選其中下標最小的基變量作為換出變量。定理：只要在迭代時，遵循上述法則，就不會出現(xiàn)循環(huán)。3.5改進單純形法每次迭代只計算換入列、常數(shù)列及檢驗數(shù)行以提高計算效率。一、單純形法的矩陣形式用矩陣（分塊）形式表示線性規(guī)劃標準型把矩陣A、C、X分別按“基”與“非基”分成兩塊A=(B,N)C=(c,C)BN~X~x=bx1-NJ其中B=(P,P,…，P)TOC\o"1-5"\h\z12mN=(P,P,…，P)m+1m+2nC=(c,c，…,c)1'2’'Bmc=(c,c，…,c)Nm+1m+2nX1V—xYV—2B\X

LmXm+1v—x—m+2

N:X_n將分塊結(jié)果代入標準型，得BX+NX=bBNX>0,X>0BNminz=CX+CXBbNn用矩陣(分塊)形式表示基本解、目標函數(shù)值及檢驗數(shù)X=B"B]NXBNz=CB】b+(C-CB】N)XBNBN=C-CB_1NNNB令X=0,可得X=B_1bz=CB_1b單純型乘子Y。Y=CB日二、改進單純形法的求解步驟完成第0次迭代表。構(gòu)造初始可行基，計算B-1。再利用公式0b=C-CB-1N=C-CN，計算第0次迭代表中的檢驗數(shù)。確定換入向量為P，換出向量為P，主元素是a。kBrrk令i=0計算B_ii+1構(gòu)造基矩陣Bi+1計算B_1i+1第一種方法：已知B，用初等變換法求其逆矩陣Bt。第二種方法：已知B_i和第i次迭代表的換入列P'，主元素為a.,通過取主變換求出B_1。i+1計算第i+1次迭代表的常數(shù)列和檢驗數(shù)。常數(shù)列=B_1?bi+10

=CN.+i%i-Y+N+i進行最優(yōu)性檢驗如果=CN.+i%i-Y+N+iN5.計算第i+1次迭代表中的換入列P,kP=B1?P—1ki+1k6.確定第i+1次迭代表中換出向量的下標B。最小非負比值規(guī)則令i=i+1,返回步驟2。三、逆的乘積形式B1=EE???EE

—1i+1ii—110改進單純形法的基本思想就是給定初始基本可行解后，通過修改舊基的逆來獲得現(xiàn)行基的逆，進而完成單純形法的其他運算。22常數(shù)列=四、計算舉例22常數(shù)列=「1001「101一2—211一2—21022Y=C?B-i=(8,3)120=G,3)b=C-YN=(ccccc)-Y(PPPPP)N3N33314567314567(\(/1-1010]=(400MM)-(23)[00-101)=(400MM)-(2-2-323)=(223M-2M-3)第三章線性規(guī)劃的對偶原理3.1線性規(guī)劃的對偶問題一、對偶問題的提出換位思考家具廠的線性規(guī)劃問題，該問題站在家具廠管理者的角度追求銷售收入最大maxz-50x+30%'4%+3%<120<2%+%<50%1，%2>0某企業(yè)家有一批待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。他需要與家具廠談判付給該廠每個工時的價格。如果該企業(yè)家已對家具廠的經(jīng)營情況有詳細了解，他可以構(gòu)造一個數(shù)學(xué)模型來研究如何才能既讓家具廠覺得有利可圖，肯把資源出租給他，又使自己付的租金最少。目標:租金最少；廣付給木工工時的租金；y-付給油漆工工時的租金minw=120y+50y所付租金應(yīng)不低于家具廠利用這些資源所能得到的利益生產(chǎn)一個桌子的收入1）支付相當于生產(chǎn)一個桌子的木工、油漆工的租金應(yīng)不低于4y1+2y2>50生產(chǎn)一個椅子的收入2）支付相當于生產(chǎn)一個椅子的木工、油漆工的租金應(yīng)不低于3y1+y2>30生產(chǎn)一個桌子的收入生產(chǎn)一個椅子的收入3）付給每種工時的租金應(yīng)不小于零y>0y>0y,y二、原問題與對偶問題的數(shù)學(xué)模型對稱形式的對偶原問題和對偶問題只含有不等式約束時，一對對偶問題的模型是對稱的，稱為對稱形式的對偶。原問題：minz=CX彳AX>bX>0對偶問題：maxw=Yb\YA<CY>0非對稱形式的對偶若原問題的約束條件全部是等式約束（即線性規(guī)劃的標準型）即^minz=CXAX=bX>0則其對偶問題的數(shù)學(xué)模型為maxw=YbYA<CY是自由變量可把原問題寫成其等價的對稱形式：minz=CXAX>b

AX<bX〉0minz=CXX>0設(shè)Y=(yy…,y),Y=(yy…,y)。根據(jù)對稱形式的對偶模型,112m2m+1m+22m寫出上述問題的對偶問題：maxw=（丫廣2）?(Y廣2)?<Cmaxw=（Y-Y2）?b（y-y2）a<cY>0Y>01-2-令Y=Y-Y得對偶問題為：(Y廣2)?<Cmaxw=YbYA<CY是自由變量

原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)minz目標函數(shù)maxwn個變量n個約束變量＞0約束＜變量＜0約束＞自由變量約束=m個約束m個變量約束＞變量＞0約束＜變量＜0約束=自由變量約束條件的限定向量目標函數(shù)的價值向量目標函數(shù)的價值向量約束條件的限定向量maxz=2x+x+3x+xx+x+x+x<5原問題：21x-2x+33x=-4V123氣-x3+x4^1x,x>0,x,x無約束1324minw=5y-4y+yy+2y+y>2對偶問題：y1-y2=1vy1+3y2-y3>3y1”3=1y1>0,y2無約束,y3<0minz=3x-2x-3x+4xx一2x+3x+4x<3原問題：I1x2+3x3+4x4二52x一3x一7x一4x=2x>0,x<0,x,x無約束11423maxw=3y-5y+2y'y1+2y3<3對偶問題：一2y1+y2-3y3=2<3y+3y_7y=-34y+4y一4y>4123y<0,y>0,y無約束3.2對偶問題的基本性質(zhì)和基本定理一、對稱性定理對稱性定理：對偶問題的對偶是原問題。二、弱對偶性定理弱對偶性定理：若X。和丫⑼分別是原問題和對偶問題的可行解，則有CX。＞Y"。三、最優(yōu)性定理最優(yōu)性定理：若X（0）和Y。分別是原問題和對偶問題的可行解，且有CX（0）=Y（0）b，則X。和丫⑼分別是原問題和對偶問題的最優(yōu)解。四、對偶定理對偶定理:有一對對偶的線性規(guī)劃問題，若其一有一個有限的最優(yōu)解，則另一個也有最優(yōu)解，且相應(yīng)的目標函數(shù)值相等。若任一個問題具有無界解，則另一個問題無可行解。五、單純型乘子Y的定理單純型乘子Y的定理：若線性規(guī)劃原問題有一個對應(yīng)于基B的最優(yōu)基本可行解，則此時的單純型乘子Y=CbB1是相應(yīng)于對偶問題的一個最優(yōu)解。六、對稱形式對偶的互補松弛定理對稱形式對偶的互補松弛定理：若X（o）和Y（o）分別是原問題和對偶問題的可行解，則X（o）和Y（o）都是最優(yōu)解的充要條件是，對所有i和j，下列關(guān)系式成立：如果x（°）>0，必有Y（o）P=c如果Y（0）P<c，必有x（o）=0JJj如果y⑼>0，必有AX（0）=b如果AX（0）>b，必有y（o）=O其中P是A的第j列，A是A的第i行?；パa松弛定理意味著：如果原問題最優(yōu)解X（0）中第j個變量x（0）為正，j則其對偶問題中與之對應(yīng)的籠個約束式在最優(yōu)情況下必呈嚴格等式（即其松弛變量為0）；而如果對偶問題中第j個約束式在最優(yōu)情況下呈嚴格不等式，則原問題最優(yōu)解X（0）中第j個變量x（0）必為0。類似地，j如果對偶問題最優(yōu)解丫⑼中第i個對偶變量y（0）為正，則其原問題中與之對應(yīng)的第i個約束在最優(yōu)情況下必呈嚴格等式（即其剩余變量為0）；而如果原問題中第i個約束在最優(yōu)情況下呈嚴格不等式，則對偶問題最優(yōu)解丫⑴中第i個對偶變量y（0）必為0。互補松弛性"Xs=0%x=0X,y為最優(yōu)解對一對對偶規(guī)劃的最優(yōu)解而言，如果對應(yīng)某一約束條件的對偶變量的值為非零，則該約束條件取嚴格等式；反之，如果某個約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。七、非對稱形式對偶的互補松弛定理非對稱形式對偶的互補松弛定理：若X（o）和Y（o）分別是原問題和對偶問題的可行解，則X（o）和Y（o）都是最優(yōu)解的充要條件是，對所有j，下列關(guān)系式成立：如果x（°）>0，必有Y（o）P=c如果Y（o）P<c，必有x（o）=OJJjmaxz=尤+尤例：已知線性規(guī)劃問題」X1+X2+X3-2{—2x+X—X<1x.,x,x>o試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解該問題存在可行解，如x=（0,0,0）又對偶問題為minw=2y+y—y—2y>1y2+y2>1y—y>0y1,y2>0由第一個約束條件知對偶問題無可行解，由此可知其原問題無最優(yōu)解八、最優(yōu)對偶變量（影子價格）的經(jīng)濟解釋由對偶定理可知，當達到最優(yōu)解時，原問題和對偶問題的目標函數(shù)值相等。如果在得到最優(yōu)解時，某種資源并未完全利用，其剩余量就是該約束中剩余變量的取值，那么該約束相對應(yīng)的影子價格一定為零。因為在得到最優(yōu)解時，這種資源并不緊缺，故此時再增加這種資源不會帶來任何效益。反之，如果某種資源的影子價格大于零，就說明再增加這種資源的可獲量，還回帶來一定的經(jīng)濟效益，即在原問題的最優(yōu)解中，這種資源必定已被全部利用，相應(yīng)的約束條件必然保持等式。3.3對偶單純形法一、對偶單純形法與單純形法的區(qū)別單純形法在整個迭代過程中，始終保持原問題的可行性，即常數(shù)列>0，而檢驗數(shù)C-CBB_]A（即C-YA）由有負分量逐步變?yōu)槿浚?（即變?yōu)闈M足YAvC，Y是對偶問題的可行解），即同時得到原問題和對偶問題的最優(yōu)解。對偶單純形法在整個迭代過程中，始終保持對偶問題的可行性，即全部檢驗數(shù)>0，而常數(shù)列由有負分量逐步變?yōu)槿?gt;0（即變?yōu)闈M足原問題的可行性），即同時得到原問題和對偶問題的最優(yōu)解。二、對偶單純形法的求解步驟和計算舉例給定一個初始對偶可行的基本解進行最優(yōu)性檢驗若現(xiàn)行常數(shù)列b>0,則停止計算。否則，轉(zhuǎn)下步。確定換出變量將現(xiàn)行常數(shù)列b'中最小的負元素所在行的基變量換出確定換入變量最大負比值規(guī)則：在換出變量所在的箝行約束式中，找出各非基變量列中系數(shù)為負的那些元素，用相應(yīng)的檢驗數(shù)。：分別除以這些負元素，所得各負比值中最大者所在列即為換入列。以.，為主元素進行取主變換rk返回步驟2,繼續(xù)迭代。三、關(guān)于初始對偶可行的基本解構(gòu)造擴充問題minz=CXX+XPx=bXR>0其中R是非基變量下標的集合。再增加一個變量和一個約束條件，得到其擴充問題：minz=CXXB+EP?七=bx+靂x=Mn+1j沱Rx>0(i=1,2,,n+1)求擴充問題的初始對偶可行的基本解若基本解x(0)不是對偶可行的，即檢驗數(shù)中有負的，并假設(shè)負檢驗數(shù)B中最小的一個為b，則以b相應(yīng)的變量x為換入變量，以x為換出kkkn+1變量，即以a為主元素進行取主變換，可得到全部檢驗數(shù)>0，即得到一個對偶可行的基本解。用對偶單純形法求解擴充問題，并得到原問題的解答因為擴充問題的對偶問題有可行解，根據(jù)對偶原理可知，擴充問題或無可行解或有有限最優(yōu)解。若擴充問題無可行解，則原問題也無可行解，若擴充問題得到最優(yōu)解X（。=（.（0）,...,.（0）,.（0）），則X（0）=（.（0）,...,.（0））是原問題的可行解。若擴充1nn+11n問題的目標函數(shù)最優(yōu)值與M無關(guān)，則X（0）就是原問題的最優(yōu)解。計算舉例3.4靈敏度分析研究初始單純型表上的系數(shù)變化對最優(yōu)解的影響，研究這些系數(shù)在什么范圍內(nèi)變化時，原最優(yōu)基仍是最優(yōu)的；若原最優(yōu)基不再是最優(yōu)的，如何用最簡便的方法找到新的最優(yōu)解。假定線性規(guī)劃標準型最終表上已得到最優(yōu)翊，最優(yōu)結(jié)果為：-X]_「B-1b-XB-nX01-N-11-」minz=CB-1b一、改變價值向量Cc'=c+Ac1.在最終表內(nèi)，、是非基變量rCB，乙=CBB-1P均不變；僅C變化。b'=c'一z=c+Ac一z=b+Acrrrrrrrr若b'>0，即Ac>-a，則最優(yōu)解不變;

若廠<0，則原最優(yōu)基不再是最優(yōu)的了。以、為換入變量，把最終表rr上的。換成?！?，C換成c,，繼續(xù)用單純形法求解。在最終表內(nèi)，x是基變量rc要改變，并因此影響到各個檢驗數(shù)。B若maxi/a'Ia'<0L△c<mini/a'Ia'>。｝，則所有Q'>0，即最優(yōu)jkjkjrjkjkjj解不變。若△c超出上述允許變化范圍，即包<0，則以原最終表為基礎(chǔ)，換上變化后的價值系數(shù)和檢驗數(shù)，繼續(xù)迭代，可求出新的最優(yōu)解。、改變限定向量bmax\^-—B^|d'>0max\^-—B^|d'>01<△biIdirJir若△b超過上述范圍，則新得到的解為不可行解。但由^的變化不

影響檢驗數(shù)，故仍保持所有檢驗數(shù)>0,即滿足對偶可行性。這時可x—Brirrr\x<min<-—BriId'irir三、改變約束矩陣A1.非基向量列p改變?yōu)閜‘影響最終表上的第j列數(shù)據(jù)和第j個檢驗數(shù)。i；=c-cB-1P若b>0，則原最優(yōu)解仍是新問題的最優(yōu)解。j若a'<0，則原最優(yōu)基在非退化情況下不再是最優(yōu)基。這時，應(yīng)在原最終表的基礎(chǔ)上，換上改變后的第j列數(shù)據(jù)b-1p,和?！?，把x作為換入變量，用單純形法繼續(xù)迭代。2.基向量列P改變?yōu)閜重新計算四、增加一個新的約束條件Zam+疽尸氣+1j=1氣+1xv氣+1若原最優(yōu)解滿足這個新約束，則它就是新問題的最優(yōu)解。否則，引進松弛變量工，有n+1(A)X+(A)X+x=bm+1BBm+1NNn+1m+1(b-(A)B-1b)>0則現(xiàn)行對偶可行的基本解是新問題的可行解，亦即最優(yōu)解。(b-(A)B-1b)<0則在原最終表的基礎(chǔ)上，增加新約束式的數(shù)據(jù)，通過矩陣行的初等變換，把原最終表上的各基向量列及新增列P化為單位陣，再用對偶單純形法繼續(xù)求解。五、增加一個新的變量對原問題最優(yōu)解的可行性無影響。^n+1=J+1-CBB-1Pn+1若°>0，則原最優(yōu)解就是新問題的最優(yōu)解。n+1若°<0，須把B-1P加入到原最終表內(nèi)，并以新變量X作為換入變量，按單純形法繼續(xù)迭代，得到新的最優(yōu)解。xn1第四章應(yīng)用實例4.1產(chǎn)銷平衡的運輸問題minz=乙乙cx

ijij

-Ij=lZjx=a(i=1,2,…，m)iji>1%ij￡x=b(j=1,2,??-,n)ijjn)>0(z=1,2,???,m;j=%ijn)由于產(chǎn)銷平衡，有Za=辛X)=ZZx=Lbiijijji=li=lj=lj=li=l7=1XX???XXX???X?.?XX?..X1112In21222nm1m2mn11?..111...111...111...111111?1較為簡潔的求解方法一表上作業(yè)法（不做要求）。另,可與整數(shù)規(guī)劃結(jié)合而帶來求解的方便。4.2套裁下料問題思路舉例:某工廠要做100套鋼架，每套用長為2.9m、2.1m和1.5m的元鋼各…根。已知原料長7.4m,問應(yīng)如何下料，可使所用原料最省。簡單裁法將使料頭數(shù)量增多，應(yīng)使用套裁的方法。須先設(shè)計出若十種較好的套裁方案如下表，分設(shè)按各種方案下料的原料根數(shù)為I，可列寫其數(shù)學(xué)模型:i料7數(shù)\方^)!123452.9120102.1002211.531203合計7.47.37.27.16.6料頭00.10.20.30.8minz=01+0.11+0.2i+0.3i+0.8ii+21+i=100<21+21+i=10031+i+21+31=100I.>0且為整數(shù)(j=1,2,,5)4.3汽油