【正文】 00001002）計(jì)算檢驗(yàn)數(shù)進(jìn)行最優(yōu)性檢驗(yàn)。 若已獲得最優(yōu)解（或確定無最優(yōu)解），則停止；否則進(jìn)行下一步。3）換基。根據(jù)的原則，確定為換入變量，計(jì)算（），按規(guī)則，確定為換出變量。4）通過初等行變換將系數(shù)矩陣中變量對應(yīng)列變換為第個(gè)元素為1的單位列向量，用代為新的基變量，列出新的單純形表，回到第二步驟。例3：用單純形法求解線性規(guī)劃問題 解 先將上述問題化成標(biāo)準(zhǔn)形式有 其約束條件系數(shù)矩陣的增廣矩陣為 是單位矩陣，構(gòu)成一個(gè)基，對應(yīng)變量是基變量。令非基變量等于零，即找到一個(gè)初始基可行解以此列出初始單純形表記作表2如下：表221000基01505100024[6]2010051100121000因表中有大于零的檢驗(yàn)數(shù)，故表中基可行解不是最優(yōu)解。因，故確定為換入變量。將列除以的同行數(shù)字得，由此6為主元素，作為標(biāo)志對主元素6加上方括號[ ]，主元素所在行基變量為換出量。用替換基變量，得到一個(gè)新的基，按上述單純形法計(jì)算步驟第三步，可以找到新的基可行解，并列出新的單純形表，記作表3如下：表321000基015051002412/601/60010[4/6]01/6101/301/30由于上表中還存在大于零的檢驗(yàn)數(shù)，故重復(fù)上述步驟得下表，記作表4：表421000基015/20015/415/227/21001/41/213/20101/43/20001/41/2上表中所有，且基變量中不含人工變量，故表中的基可行解為最優(yōu)解，代入目標(biāo)函數(shù)得。2．2．3對偶單純形法2．2．3．1單純形法計(jì)算的矩陣描述對稱形式線性規(guī)劃問題的矩陣表達(dá)式加上松弛變量后為： (1)上式中為松弛變量，為單位矩陣。單純形法計(jì)算時(shí)，總選取為初始基，對應(yīng)基變量為。設(shè)迭代若干步后，基變量為，在初始單純形表中的系數(shù)矩陣為。將在初始單純形表中單獨(dú)列出，而中去掉后的若干列后剩下的列組成矩陣，這樣(1)的初始單純形表可列成如表5的形式。 表5項(xiàng)目非基變量基變量00當(dāng)?shù)舾刹?，基變量為時(shí)，則該步的單純形表中由系數(shù)組成的矩陣為。又因單純形法的迭代是對約束增廣矩陣進(jìn)行的行的初等變換，對應(yīng)的系數(shù)矩陣在新表中應(yīng)為。故當(dāng)基變量為時(shí)，新的單純形表具有表6形式。 表6項(xiàng)目基變量非基變量10從表5和表6看出，當(dāng)?shù)蠡兞繛闀r(shí)，其在初始單純形表中的系數(shù)矩陣為，則有：1）對應(yīng)初始單純形表中的單位矩陣，迭代后的單純形表中為； 2）初始單純形表中基變量,，迭代后的表中；3）初始單純形表中約束系數(shù)矩陣為[，]＝[，]，迭代后的表中約束系數(shù)矩陣為[，]＝[，]＝[，]。4）若初始矩陣中變量的系數(shù)向量為迭代后為，則有 （2）5）當(dāng)為最優(yōu)解時(shí)，在表6中應(yīng)有 （3） （4） 因的檢驗(yàn)數(shù)可寫為 （5） 故(3)～(5)式可重寫為 （6） （7）稱為單純乘子，若令 則（6）、（7）式可改寫為 （8） 看出這時(shí)檢驗(yàn)數(shù)行，若取其相反數(shù)恰好是其對偶問題的一個(gè)可行解。將這個(gè)解代入對偶問題的目標(biāo)函數(shù)值 有 （9）由（9）式看出，當(dāng)原問題為最優(yōu)解時(shí)，這時(shí)對偶問題為可行解，且兩者具有相同的目標(biāo)函數(shù)值。2．2．3．2對偶問題的基本性質(zhì) 1）弱對偶性。如果是原問題的可行解，是其對偶問題的可行解，則恒有 由弱對偶性，可得出以下推論： ①原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。 ②如原問題有可行解且目標(biāo)函數(shù)值無界(具有無界解)，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解(注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對偶問題無可行解時(shí)，其原問題或具有無界解或無可行解，反之亦然)。 ③若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界。2）最優(yōu)性。如果是原問題的可行解, 是其對偶問題的可行解，且有 則是原問題的最優(yōu)解，是對偶問題的最優(yōu)解。3）強(qiáng)對偶性(或稱對偶定理)。若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。4）互補(bǔ)松弛性。在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。也即 若，則有， 即， 若，即，則有， 因此一定有。將互補(bǔ)松弛性質(zhì)應(yīng)用于其對偶問題時(shí)可以這樣敘述：如果有，則；如果有, 則。2．2．3．3對偶單純形法的基本思路 求解線性規(guī)劃的單純形法的思路是：對原問題的一個(gè)基可行解，判別是否所有檢驗(yàn)數(shù)。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。根據(jù)對偶問題的性質(zhì)，因?yàn)?，?dāng)，即有或，也即其對偶問題的解為可行解，由此原問題和對偶問題均為最優(yōu)解。反之，如果存在一個(gè)對偶問題的可行基，即對，有或，這時(shí)只要有，即原問題的解也為可行解，即兩者均為最優(yōu)解。否則保持對偶問題為可行解，找出原問題的相鄰基本解，判別是否有，循環(huán)進(jìn)行，一直使原問題也為可行解，從而兩者均為最優(yōu)解。對偶單純形法的基本思路：先找出一個(gè)對偶問題的可行基，并保持對偶問題為可行解條件下，如不存在，通過變換到一個(gè)相鄰的目標(biāo)函數(shù)值較小的基本解(因?qū)ε紗栴}是求目標(biāo)函數(shù)極小化)，并循環(huán)進(jìn)行，一直到原問題也為可行解(即)，這時(shí)對偶問題與原問題均為可行解。2．2．3．4對偶單純形法的計(jì)算步驟設(shè)某標(biāo)準(zhǔn)形式的線性規(guī)劃問題 （10） 存在一個(gè)對偶問題的可行基，不妨設(shè)，列出單純形表（見表7）。 表7基100010001000 表7中必須有，的值不要求為正。當(dāng)對，有時(shí)，即表中原問題和對偶問題均為最優(yōu)解。否則，通過變換一個(gè)基變量，找出原問題的一個(gè)目標(biāo)函數(shù)值較小的相鄰基本解。1）確定換出基的變量因?yàn)榭偞嬖冢?的，令，其對應(yīng)變量為換出基的變量。2）確定換入基的變量①為了使下一個(gè)表中第行基變量為正值，因而只有對應(yīng)的非基變量才可以考慮作為換入基的變量。②為了使下一個(gè)表中對偶問題的解仍為可行解，令 （11）稱為主元素，為換入基的變量。設(shè)下一個(gè)表中的檢驗(yàn)數(shù)為，由式 （12）分兩種情況說明滿足（11）式來選取主元素時(shí)，式（12）中（對）。（a）對 ，因 故 ，又因主元素，故，由此式（12）方括弧內(nèi)的值≤0，故有。（b）對，因，故有。 3）用換入變量替換換出變量，得到一個(gè)新的基。對新的基再檢查是否所有。如是，找到了兩