1、精選優(yōu)質(zhì)文檔-傾情為你奉上運(yùn)籌學(xué)課程講義第一部分 線性規(guī)劃第一章 線性規(guī)劃的基本性質(zhì)1.1 線性規(guī)劃的數(shù)學(xué)模型一、 線性規(guī)劃問題的特點(diǎn)勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子售價30元/個。生產(chǎn)桌子和椅子需木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？ 例：某工廠生產(chǎn)某一種型號的機(jī)床。每臺機(jī)床上需要2.9m、2.1m、1.5m的軸，分別為1根、2根和1根。這些軸需用同一種圓鋼制作，圓鋼的長度為74m。如果要生產(chǎn)100臺

2、機(jī)床，問應(yīng)如何安排下料，才能用料最省？二、 數(shù)學(xué)模型的標(biāo)準(zhǔn)型1. 繁寫形式2. 縮寫形式3. 向量形式4. 矩陣形式三、 任一模型如何化為標(biāo)準(zhǔn)型？1. 若原模型要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化，如何將其化為最小化問題？2. 若原模型中約束條件為不等式，如何化為等式？3. 若原模型中變量xk是自由變量，如何化為非負(fù)變量？4. 若原模型中變量xj有上下界，如何化為非負(fù)變量？令1. 2圖解法該法簡單直觀，平面作圖適于求解二維問題。使用該法求解線性規(guī)劃問題時，不必把原模型化為標(biāo)準(zhǔn)型。一、 圖解法步驟1. 由全部約束條件作圖求出可行域2. 作出一條目標(biāo)函數(shù)的等值線3. 平移目標(biāo)函數(shù)等值線，作圖求解最優(yōu)點(diǎn)，再算出最

3、優(yōu)值二、 從圖解法看線性規(guī)劃問題解的幾種情況1. 有唯一最優(yōu)解2. 有無窮多組最優(yōu)解3. 無可行解4. 無有限最優(yōu)解（無界解） 最優(yōu)解，最優(yōu)值3直觀結(jié)論：1）線性規(guī)劃問題的可行域為凸集，特殊情況下為無界域（但有有限個頂點(diǎn)）或空集； 2）線性規(guī)劃問題若有最優(yōu)解，一定可以在其可行域的頂點(diǎn)上得到。1.3 線性規(guī)劃的基本概念和基本定理一、 線性規(guī)劃問題的基與解可行解最優(yōu)解基基向量非基向量基變量非基變量基本解基本可行解最優(yōu)基本可行解退化的基本解二、 幾何意義上的幾個基本概念1. 凸集2. 凸組合3. 頂點(diǎn)三、 線性規(guī)劃問題的基本定理定理1：若線性規(guī)劃問題存在可行域，則其可行域是凸集。引理1：線性規(guī)劃問題

4、的可行解為基本可行解的充要條件是X的正分量對應(yīng)的系數(shù)列向量是線性無關(guān)的。定理2：線性規(guī)劃問題的基本可行解對應(yīng)于可行域的頂點(diǎn)。引理2：K是有界凸集，則任何一點(diǎn)XK可表示為K的頂點(diǎn)的凸組合。定理3：如果線性規(guī)劃問題有有限最優(yōu)解，則其目標(biāo)函數(shù)最優(yōu)值一定可以在可行域的頂點(diǎn)上達(dá)到。四、 求解線性規(guī)劃問題的基本思路在有限個基本可行解中尋找最優(yōu)基本可行解。找一個基本可行解（m個線性無關(guān)的系數(shù)列向量），由其換到另一個基本可行解。實(shí)質(zhì)即為換基。前提是保證新的基本可行解的目標(biāo)函數(shù)值比原來的更優(yōu)而不是更劣。第二章 單純形法它是求解線性規(guī)劃最為成熟的算法。勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子售價

5、30元/個，生產(chǎn)桌子和椅子需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？ 將其變形，得 將對應(yīng)的單位矩陣作為初始可行基。令為基變量，為非基變量。原模型變形為 如果令非基變量等于零，得一個基本可行解（0，0，120，50），對應(yīng)的目標(biāo)函數(shù)值z = 0最優(yōu)性檢驗：該解是否最優(yōu)？顯然不是。經(jīng)濟(jì)意義分析：等于零意味著家具廠不開工生產(chǎn)，銷售收入為零，資源未得到充分利用。數(shù)學(xué)角度分析：非基變量前的系數(shù)都為正，表明目標(biāo)函數(shù)值有增加的可能。只要將系

6、數(shù)為正的非基變量與某一基變量對換，當(dāng)換入變量的值增加時，目標(biāo)函數(shù)值就可能增加。換基迭代：尋找下一個可行解需要進(jìn)行換基迭代。換基后需滿足：（1）新的解仍是基本可行解；（2）目標(biāo)函數(shù)得到改善。選擇入基變量：系數(shù)均為正。對求目標(biāo)函數(shù)極大化的問題，我們希望目標(biāo)值增加得越快越好，因此應(yīng)選系數(shù)最大的入基。選擇出基變量：入基后，其值從零增加并引起其他變量取值的變化。由問題的典則表達(dá)式和變量必須取正值的條件，得下列不等式關(guān)系： 因迭代后仍為取零值的非基變量，上式可簡化為很明顯，只有選時，才能使上述不等式成立，并使基變量變?yōu)榱悖脻M足非基變量必須為零的條件，所以可令出基，新的典則方程變?yōu)?化簡后得 代入目標(biāo)函

7、數(shù)可得 得到下一個基本可行解（25，0，20，0），并完成了第一次迭代。新解是最優(yōu)解嗎？需進(jìn)行最優(yōu)檢驗。由于目標(biāo)函數(shù)中的系數(shù)仍為正，說明多生產(chǎn)椅子仍有利可圖，該解仍不是最優(yōu)解。再次迭代。入基，出基，換基后典則形式變?yōu)?第三個基本可行解為（15，20，0，0），松弛變量都已為零，表明資源已得到充分利用；非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)值，說明目標(biāo)函數(shù)已無法進(jìn)一步改善，因此該解已是最優(yōu)解。2.1 單純形法原理一、 構(gòu)造初始可行基1. 引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型2. 若約束條件中附加變量的系數(shù)是-1或原約束即為等式，則必須引入人工變量，以構(gòu)成初始可行基3. 目標(biāo)函數(shù)中，附加變量的系數(shù)為0，而

8、人工變量的系數(shù)為M（很大的正數(shù)）二、 求出一個基本可行解1. 用非基變量表示基變量和目標(biāo)函數(shù)式 2. 求出一個基本可行解及相應(yīng)的z值三、 最優(yōu)性檢驗1. 最優(yōu)性檢驗的依據(jù)檢驗數(shù)2. 最優(yōu)解判別定理：若在極小化問題中，對于某個基本可行解，所有檢驗數(shù)0，且人工變量為0，則這個基本可行解是最優(yōu)解。對于極大化問題，只要把上述定理中的0改成0即可。這里的檢驗數(shù)即為（c-z）。3. 無窮多最優(yōu)解判別定理：若在極小化問題中，對于某個基本可行解，所有檢驗數(shù)0，又存在某個非基變量的檢驗數(shù)為0，且人工變量為0，則線性規(guī)劃問題有無窮多最優(yōu)解。4. 無可行解情況若在極小化問題中，對于某個基本可行解，所有檢驗數(shù)0，但人

9、工變量0，則該線性規(guī)劃問題無可行解。四、 基變換1. 基本可行解的改進(jìn)定理2. 換入變量的確定3. 換出變量的確定最小非負(fù)比值規(guī)則 =b/a=b/a|a>0 在單純形法迭代中，基變換帶來可行域頂點(diǎn)的變換，且相鄰兩次迭代所對應(yīng)的頂點(diǎn)也是相鄰的。4. 無有限最優(yōu)解（無界解）判定定理：若在極小化問題中，對于某個基本可行解，有一個非基變量的檢驗數(shù)<0，但P列中沒有正元素，且人工變量為0，則線性規(guī)劃問題無有限最優(yōu)解（具有無界解）。2.2 單純形法的表格形式一、 構(gòu)造初始可行基，并計算檢驗數(shù)=c-zz=(c,c,c)P=(C)P二、 從表中找到基本可行解和相應(yīng)目標(biāo)函數(shù)值三、 最優(yōu)性檢驗四、 基

10、變換1. 換入變量的確定 負(fù)檢驗數(shù)中最小2. 換出變量的確定 最小非負(fù)比值規(guī)則3. 主元素的確定 換入元素所在列和換出元素所在行交點(diǎn)處的元素4. 取主變換通過矩陣行的初等變換，把換入向量變換為單位列向量。即基變換，亦即單純形法的一次迭代。2. 3 大M法和兩階段法根據(jù)處理人工變量的方法不同，單純形法的兩種常見形式。大M法也叫罰函數(shù)法，前已介紹。兩階段法將線性規(guī)劃問題的求解分為兩個階段。第一階段：判斷原線性規(guī)劃問題是否有可行解。該階段所要求解的線性規(guī)劃問題的約束條件即原問題的約束條件，而目標(biāo)函數(shù)取全部人工變量之和，求其最小值。若求解結(jié)果是上述目標(biāo)函數(shù)的最小值為0，則說明所有人工變量都能退出基，原

11、問題有可行解，且第一階段的最終單純型表上的基本可行解就是原問題的一個基本可行解。若求解的結(jié)果是上述目標(biāo)函數(shù)的最小值大于0，則說明最終人工變量不能完全退出基，原問題無可行解，應(yīng)停止計算。第二階段：求解原線性規(guī)劃問題的最優(yōu)解。以第一階段的最終單純型表為基礎(chǔ)，去掉其中的人工變量列，把目標(biāo)函數(shù)換成原問題的目標(biāo)函數(shù)，并修正因c改變而改變的(C)、和-z。以此作為第二階段的初始表，繼續(xù)迭代，得原問題的最優(yōu)解。 4 3 8 0 0 0迭代次數(shù) 基變量 1 2.4 退化問題 一、 什么是退化當(dāng)基本解、基本可行解、最優(yōu)基本可行解中有基變量為0時，即出現(xiàn)了退化。退化情況下，即使存在最優(yōu)解，也可能出現(xiàn)循環(huán)現(xiàn)象，即迭

12、代過程總是重復(fù)解的某一部分序列，目標(biāo)函數(shù)值總是不變，永遠(yuǎn)達(dá)不到最優(yōu)解。二、 攝動法1. 攝動法簡介對線性規(guī)劃原問題，為了避免退化情況下發(fā)生循環(huán)，而使向量b攝動。2. 確定換出變量的步驟3. 舉例三、 勃蘭特方法法則1：在極小化問題中，如果有幾個檢驗數(shù)（c-z）都是負(fù)的，那么選其中下標(biāo)最小的非基變量作為換入變量。法則2：在極小化問題中，根據(jù)最小非負(fù)比值規(guī)則確定換出變量時，如果有幾個比值同時達(dá)到最小比值，那么選其中下標(biāo)最小的基變量作為換出變量。定理：只要在迭代時，遵循上述法則，就不會出現(xiàn)循環(huán)。3. 5 改進(jìn)單純形法每次迭代只計算換入列、常數(shù)列及檢驗數(shù)行以提高計算效率。一、單純形法的矩陣形式1. 用

13、矩陣（分塊）形式表示線性規(guī)劃標(biāo)準(zhǔn)型把矩陣A、C、X分別按“基”與“非基”分成兩塊A=(B,N)C=(C,C)其中 B=（P，P，P） N=（P，P，P） C=（c1,c2,c） C=(c,c,c) X= X=將分塊結(jié)果代入標(biāo)準(zhǔn)型，得 BX+NX=bX0, X0+ CX2. 用矩陣（分塊）形式表示基本解、目標(biāo)函數(shù)值及檢驗數(shù) X=Bb- BNX z =CBb + (C- CBN) X =C- CBN令X= 0， 可得 X= Bbz =CBb3. 單純型乘子Y。 Y= CB二、 改進(jìn)單純形法的求解步驟1. 完成第0次迭代表。構(gòu)造初始可行基，計算B。再利用公式=C- C BN= C- C N，計算第0

14、次迭代表中的檢驗數(shù)。確定換入向量為P，換出向量為P，主元素是a。令i = 02. 計算B1） 構(gòu)造基矩陣B2） 計算B第一種方法：已知B，用初等變換法求其逆矩陣B。第二種方法：已知B和第i次迭代表的換入列P，主元素為a，通過取主變換求出B。3. 計算第i +1次迭代表的常數(shù)列和檢驗數(shù)。常數(shù)列= B·bY=C·B=C- YN4. 進(jìn)行最優(yōu)性檢驗如果 0，且人工變量為0，則已經(jīng)得到最優(yōu)解。否則，轉(zhuǎn)下步。5. 計算第i + 1次迭代表中的換入列P。 P= B·P6. 確定第i +1次迭代表中換出向量的下標(biāo)B。最小非負(fù)比值規(guī)則令i =i +1，返回步驟2。三、 逆的乘積形

15、式B=EEEE改進(jìn)單純形法的基本思想就是給定初始基本可行解后，通過修改舊基的逆來獲得現(xiàn)行基的逆，進(jìn)而完成單純形法的其他運(yùn)算。四、 計算舉例求：常數(shù)列第三章 線性規(guī)劃的對偶原理3.1 線性規(guī)劃的對偶問題一、 對偶問題的提出換位思考家具廠的線性規(guī)劃問題，該問題站在家具廠管理者的角度追求銷售收入最大 某企業(yè)家有一批待加工的訂單，有意利用該家具廠的木工和油漆工資源來加工他的產(chǎn)品。他需要與家具廠談判付給該廠每個工時的價格。如果該企業(yè)家已對家具廠的經(jīng)營情況有詳細(xì)了解，他可以構(gòu)造一個數(shù)學(xué)模型來研究如何才能既讓家具廠覺得有利可圖，肯把資源出租給他，又使自己付的租金最少。目標(biāo):租金最少；-付給木工工時的租金；-

16、付給油漆工工時的租金所付租金應(yīng)不低于家具廠利用這些資源所能得到的利益1）支付相當(dāng)于生產(chǎn)一個桌子的木工、油漆工的租金應(yīng)不低于生產(chǎn)一個桌子的收入 2）支付相當(dāng)于生產(chǎn)一個椅子的木工、油漆工的租金應(yīng)不低于生產(chǎn)一個椅子的收入 3）付給每種工時的租金應(yīng)不小于零 二、 原問題與對偶問題的數(shù)學(xué)模型1. 對稱形式的對偶原問題和對偶問題只含有不等式約束時，一對對偶問題的模型是對稱的，稱為對稱形式的對偶。原問題： 對偶問題： 2. 非對稱形式的對偶若原問題的約束條件全部是等式約束（即線性規(guī)劃的標(biāo)準(zhǔn)型），即 則其對偶問題的數(shù)學(xué)模型為 可把原問題寫成其等價的對稱形式：min z =CXAXbAXbX0即 min z =

17、CXXX0設(shè)Y1=(y1,y2,ym), Y2=(ym+1,ym+2,y2m)。根據(jù)對稱形式的對偶模型，寫出上述問題的對偶問題：max w =(Y1,Y2)·(Y1,Y2)·CY10 Y20即 max w =( Y1-Y2)·b( Y1-Y2)ACY10 Y20令Y= Y1-Y2, 得對偶問題為： max w = YbYACY是自由變量3. 原問題與對偶問題的對應(yīng)關(guān)系原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標(biāo)函數(shù)min z目標(biāo)函數(shù)max wn個變量n個約束變量0約束變量0約束自由變量約束=m個約束m個變量約束變量0約束變量0約束=自由變量約束條件的限定向量目標(biāo)函

18、數(shù)的價值向量目標(biāo)函數(shù)的價值向量約束條件的限定向量原問題： 對偶問題： 原問題： 對偶問題： 3.2 對偶問題的基本性質(zhì)和基本定理一、 對稱性定理對稱性定理：對偶問題的對偶是原問題。二、 弱對偶性定理弱對偶性定理：若X和Y分別是原問題和對偶問題的可行解，則有C XYb。三、 最優(yōu)性定理最優(yōu)性定理：若X和Y分別是原問題和對偶問題的可行解，且有C X=Yb，則X和Y分別是原問題和對偶問題的最優(yōu)解。四、 對偶定理對偶定理：有一對對偶的線性規(guī)劃問題，若其一有一個有限的最優(yōu)解，則另一個也有最優(yōu)解，且相應(yīng)的目標(biāo)函數(shù)值相等。若任一個問題具有無界解，則另一個問題無可行解。五、 單純型乘子Y的定理單純型乘子Y的定

19、理：若線性規(guī)劃原問題有一個對應(yīng)于基B的最優(yōu)基本可行解，則此時的單純型乘子Y= CB是相應(yīng)于對偶問題的一個最優(yōu)解。六、 對稱形式對偶的互補(bǔ)松弛定理對稱形式對偶的互補(bǔ)松弛定理：若X和Y分別是原問題和對偶問題的可行解，則X和Y都是最優(yōu)解的充要條件是，對所有i和j，下列關(guān)系式成立：1. 如果x>0，必有YP=c2. 如果Y P< c，必有x=03. 如果y>0，必有AX=b4. 如果AX>b，必有y=0其中P是A的第j列，A是A的第i行。互補(bǔ)松弛定理意味著：如果原問題最優(yōu)解X中第j個變量x為正，則其對偶問題中與之對應(yīng)的第j個約束式在最優(yōu)情況下必呈嚴(yán)格等式（即其松弛變量為0）；而

20、如果對偶問題中第j個約束式在最優(yōu)情況下呈嚴(yán)格不等式，則原問題最優(yōu)解X中第j個變量x必為0。類似地，如果對偶問題最優(yōu)解Y中第i個對偶變量y為正，則其原問題中與之對應(yīng)的第i個約束在最優(yōu)情況下必呈嚴(yán)格等式（即其剩余變量為0）；而如果原問題中第i個約束在最優(yōu)情況下呈嚴(yán)格不等式，則對偶問題最優(yōu)解Y中第i個對偶變量y必為0。互補(bǔ)松弛性： 為最優(yōu)解 對一對對偶規(guī)劃的最優(yōu)解而言，如果對應(yīng)某一約束條件的對偶變量的值為非零，則該約束條件取嚴(yán)格等式；反之，如果某個約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。七、 非對稱形式對偶的互補(bǔ)松弛定理非對稱形式對偶的互補(bǔ)松弛定理：若X和Y分別是原問題和對偶問題的可行解，

21、則X和Y都是最優(yōu)解的充要條件是，對所有j，下列關(guān)系式成立：1. 如果x>0，必有YP=c2. 如果Y P< c，必有x=0例：已知線性規(guī)劃問題試用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解該問題存在可行解，如又對偶問題為由第一個約束條件知對偶問題無可行解，由此可知其原問題無最優(yōu)解八、 最優(yōu)對偶變量（影子價格）的經(jīng)濟(jì)解釋由對偶定理可知，當(dāng)達(dá)到最優(yōu)解時，原問題和對偶問題的目標(biāo)函數(shù)值相等。如果在得到最優(yōu)解時，某種資源并未完全利用，其剩余量就是該約束中剩余變量的取值，那么該約束相對應(yīng)的影子價格一定為零。因為在得到最優(yōu)解時，這種資源并不緊缺，故此時再增加這種資源不會帶來任何效益。反之，如果某種資源

22、的影子價格大于零，就說明再增加這種資源的可獲量，還回帶來一定的經(jīng)濟(jì)效益，即在原問題的最優(yōu)解中，這種資源必定已被全部利用，相應(yīng)的約束條件必然保持等式。3.3 對偶單純形法一、 對偶單純形法與單純形法的區(qū)別單純形法在整個迭代過程中，始終保持原問題的可行性，即常數(shù)列 0，而檢驗數(shù)C-CBA(即C-YA)由有負(fù)分量逐步變?yōu)槿?（即變?yōu)闈M足YAC，Y是對偶問題的可行解），即同時得到原問題和對偶問題的最優(yōu)解。對偶單純形法在整個迭代過程中，始終保持對偶問題的可行性，即全部檢驗數(shù)0，而常數(shù)列由有負(fù)分量逐步變?yōu)槿?（即變?yōu)闈M足原問題的可行性），即同時得到原問題和對偶問題的最優(yōu)解。二、 對偶單純形法的求解步驟

23、和計算舉例1. 給定一個初始對偶可行的基本解2. 進(jìn)行最優(yōu)性檢驗若現(xiàn)行常數(shù)列b0,則停止計算。否則，轉(zhuǎn)下步。3. 確定換出變量將現(xiàn)行常數(shù)列b中最小的負(fù)元素所在行的基變量換出4. 確定換入變量最大負(fù)比值規(guī)則：在換出變量所在的第r行約束式中，找出各非基變量列中系數(shù)為負(fù)的那些元素，用相應(yīng)的檢驗數(shù)分別除以這些負(fù)元素，所得各負(fù)比值中最大者所在列即為換入列。5. 以為主元素進(jìn)行取主變換返回步驟2，繼續(xù)迭代。三、 關(guān)于初始對偶可行的基本解1. 構(gòu)造擴(kuò)充問題其中R是非基變量下標(biāo)的集合。再增加一個變量和一個約束條件，得到其擴(kuò)充問題： 2. 求擴(kuò)充問題的初始對偶可行的基本解若基本解不是對偶可行的，即檢驗數(shù)中有負(fù)的

24、，并假設(shè)負(fù)檢驗數(shù)中最小的一個為，則以相應(yīng)的變量為換入變量，以為換出變量，即以為主元素進(jìn)行取主變換，可得到全部檢驗數(shù)0，即得到一個對偶可行的基本解。3. 用對偶單純形法求解擴(kuò)充問題，并得到原問題的解答因為擴(kuò)充問題的對偶問題有可行解，根據(jù)對偶原理可知，擴(kuò)充問題或無可行解或有有限最優(yōu)解。若擴(kuò)充問題無可行解，則原問題也無可行解，若擴(kuò)充問題得到最優(yōu)解,則是原問題的可行解。若擴(kuò)充問題的目標(biāo)函數(shù)最優(yōu)值與M無關(guān)，則就是原問題的最優(yōu)解。4. 計算舉例3.4 靈敏度分析研究初始單純型表上的系數(shù)變化對最優(yōu)解的影響，研究這些系數(shù)在什么范圍內(nèi)變化時，原最優(yōu)基仍是最優(yōu)的；若原最優(yōu)基不再是最優(yōu)的，如何用最簡便的方法找到新的

25、最優(yōu)解。假定線性規(guī)劃標(biāo)準(zhǔn)型最終表上已得到最優(yōu)基B，最優(yōu)結(jié)果為： = 一、 改變價值向量C 1. 在最終表內(nèi)，是非基變量， 均不變；僅變化。若，即，則最優(yōu)解不變；若，則原最優(yōu)基不再是最優(yōu)的了。以為換入變量，把最終表上的換成，換成，繼續(xù)用單純形法求解。2. 在最終表內(nèi)，是基變量要改變，并因此影響到各個檢驗數(shù)。若，則所有，即最優(yōu)解不變。若超出上述允許變化范圍，即有，則以原最終表為基礎(chǔ)，換上變化后的價值系數(shù)和檢驗數(shù)，繼續(xù)迭代，可求出新的最優(yōu)解。二、 改變限定向量b 若超過上述范圍，則新得到的解為不可行解。但由于的變化不影響檢驗數(shù)，故仍保持所有檢驗數(shù)，即滿足對偶可行性。這時可在原最終表的基礎(chǔ)上，換上改變

26、后的右端常數(shù)及相應(yīng)的值，用對偶單純形法繼續(xù)迭代，以求出新的最優(yōu)解。三、 改變約束矩陣A1. 非基向量列改變?yōu)橛绊懽罱K表上的第j列數(shù)據(jù)和第j個檢驗數(shù)。 若，則原最優(yōu)解仍是新問題的最優(yōu)解。若，則原最優(yōu)基在非退化情況下不再是最優(yōu)基。這時，應(yīng)在原最終表的基礎(chǔ)上，換上改變后的第j列數(shù)據(jù)和，把作為換入變量，用單純形法繼續(xù)迭代。2. 基向量列改變?yōu)橹匦掠嬎闼摹?增加一個新的約束條件即 若原最優(yōu)解滿足這個新約束，則它就是新問題的最優(yōu)解。否則，引進(jìn)松弛變量，有 若 0則現(xiàn)行對偶可行的基本解是新問題的可行解，亦即最優(yōu)解。若 <0則在原最終表的基礎(chǔ)上，增加新約束式的數(shù)據(jù)，通過矩陣行的初等變換，把原最終表上的各

27、基向量列及新增列化為單位陣，再用對偶單純形法繼續(xù)求解。五、 增加一個新的變量對原問題最優(yōu)解的可行性無影響。 若 ，則原最優(yōu)解就是新問題的最優(yōu)解。若 ，須把加入到原最終表內(nèi)，并以新變量作為換入變量，按單純形法繼續(xù)迭代，得到新的最優(yōu)解。第四章 應(yīng)用實(shí)例4.1 產(chǎn)銷平衡的運(yùn)輸問題由于產(chǎn)銷平衡，有n行m行 較為簡潔的求解方法表上作業(yè)法（不做要求）。另，可與整數(shù)規(guī)劃結(jié)合而帶來求解的方便。4.2 套裁下料問題思路舉例：某工廠要做100套鋼架，每套用長為2.9m、2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應(yīng)如何下料，可使所用原料最省。簡單裁法將使料頭數(shù)量增多，應(yīng)使用套裁的方法。須先設(shè)計出若干種較好的套裁方案如下表，分設(shè)按各種方案下料的原料根數(shù)為，可列寫其數(shù)學(xué)模型：方案下料數(shù)（根）長度（m）123452.92.11.51