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