【正文】 ln11,1,11,111???????????????????????mlmnnmkmmlkmlkmnkmmlbbbaaaaaaaaabxxxxxx????????????? 變換的步驟是： (1) 將增廣矩陣 (134)式中的第 l行除以 al k，得到 )351(,1,0,0,1,0 ln1, ????????? ?lkllklkmllk abaaaaa????(2) 將 (134)式中 xk列的各元素 ， 除 al k變換為 1以外 ， 其他都應(yīng)變換為零 。 其他行的變換是將 (135)式乘以 ai k(i≠l) 后 ， 從 (134)式的第 i行減去 ， 得到新的第 i行 。 ???????????? ?? iklkliiklkiklkmlmilkik aabbaaaaaaaaaa lnln1,1, ,0,0,0,0 ????由此可得到變換后系數(shù)矩陣各元素的變換關(guān)系式： ??????????????????????liablibaabbliaaliaaaaalklilkikiilkljiklkljijij39。39。 是變換后的新元素。 39。39。 ,iij ba(3) 經(jīng)過(guò)初等變換后的新增廣矩陣是 )361(010101000139。39。39。1,39。39。ln39。1,39。139。139。1,1111????????????????????????????????mmnmmlkmklmllknmlkknkmmlbaaaabaaabaaaabxxxxxx??????????????????????????????(4) 由 (136)式中可以看到 x1,x2,…,x k,… ， xm的系數(shù)列向量構(gòu)成 m m單位矩陣 。它是可行基 . 當(dāng)非基變量 xm+1,… ， xl,…,x n為零時(shí)， 就得到一個(gè)基可行解 X(1)。 ? ? ? ?Tmll bbbbX 0,0,0,39。39。139。139。11 ??????在上述系數(shù)矩陣的變換中，元素 al k稱為主元素， 它所在列稱為主元列，它所在行稱為主元行。 元素 al k位置變換后為 1。 例 7 試用上述方法計(jì)算例 6的兩個(gè)基變換。 解 例 6的約束方程組的系數(shù)矩陣寫成增廣矩陣 ??????????1216810040010040012154321bxxxxx當(dāng)以 x3,x4,x5為基變量 ， x1,x2為非基變量 ， 令 x1,x2=0， 可得到一個(gè)基可行解 X(0)=(0,0,8,16,12)T 現(xiàn)用 x2去替換 x5，于是將 x3， x4,x2的系數(shù)矩陣變換為單位矩陣，經(jīng)變換后為 ?????????? ?31624/10010010042/1010154321bxxxxx 令非基變量 x1,x5=0， 得到新的基可行解 X(1)=(0,3,2,16,0)T 第 3節(jié) 結(jié)束 運(yùn)籌學(xué) （ 第三版） 《 運(yùn)籌學(xué) 》 教材編寫組 編 清華大學(xué)出版社 第 1章 線性規(guī)劃與單純形法 第 4節(jié) 單純型法的計(jì)算步驟 錢頌迪 制作 第 1章 線性規(guī)劃與單純形法 第 4節(jié) 單純型法的計(jì)算步驟 第 4節(jié) 單純型法的計(jì)算步驟 ? 根據(jù)以上討論的結(jié)果，將求解線性規(guī)劃問(wèn)題的單純形法的計(jì)算步驟歸納如下 ? 如利用單純型表，求解線性規(guī)劃問(wèn)題。 單純型表 ? 為了便于理解計(jì)算關(guān)系 ， 現(xiàn)設(shè)計(jì)一種計(jì)算表 ， 稱為單純形表 ， 其功能與增廣矩陣相似 ， 下面來(lái)建立這種計(jì)算表 。 ? 將 (122)式與目標(biāo)函數(shù)組成 n+1個(gè)變量，m+1個(gè)方程的方程組。 線性規(guī)劃的方程組 0111111221122111111????????????????????????????nnmmmmmnmnmmmmnnmmnnmmxcxcxcxczbxaxaxbxaxaxbxaxax??????為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣形式 ????????????????????????01000001000010211211,21,211,1121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxz???????????????? 若將 z看作不參與基變換的基變量，它與x1,x2,…,xm的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將 c1,c2,…,cm變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣。得到 ????????????????????????????????????miiimmiininmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz121111,11,21,211,11210001000001000010????????????????可根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表， 表 12。 ???????????????????????????miininmimiimmiiimmnmmmmmnmnmnmmBBinmmjaccaccbczaabxcaabxcaabxcxxxxbXCccccc111,111,221,2222111,1111111100100001???????????????????????表 12的說(shuō)明 ? XB列中填入基變量 ， 這里是 x1， x2,…， xm； ? CB列中填入基變量的價(jià)值系數(shù) ， 這里是c1,c2,…,cm；它們是與基變量相對(duì)應(yīng)的； ? b列中填入約束方程組右端的常數(shù)； ? cj行中填入基變量的價(jià)值系數(shù) c1,c2,…,； ? θ i列的數(shù)字是在確定換入變量后 ， 按 θ 規(guī)則計(jì)算后填入； ? 最后一行稱為檢驗(yàn)數(shù)行 ， 對(duì)應(yīng)各非基變量 xj的檢驗(yàn)數(shù)是 ????miijij njacc1,2,1, ? 計(jì)算步驟 ? 表 12稱為初始單純形表 ， 每迭代一步構(gòu)造一個(gè)新單純形表 。 ? 計(jì)算步驟： ? (1) 按數(shù)學(xué)模型確定 初始可行基 和 初始基可行解 ， 建立初始單純形表 。 ? (2) 計(jì)算 各非基變量 xj的檢驗(yàn)數(shù) ， 檢查檢驗(yàn)數(shù) ， 若所有檢驗(yàn)數(shù) ? 則已得到最優(yōu)解，可停止計(jì)算。否則轉(zhuǎn)入下一步。 ????miijijj acc1,?njj ?,2,1,0 ???? (3) 在 σ j＞ 0,j=m+1,…,n中 ， 若有某個(gè)σ k對(duì)應(yīng) xk的系數(shù)列向量 Pk≤ 0， 則此問(wèn)題是無(wú)界 ， 停止計(jì)算 。 ? 否則 ， 轉(zhuǎn)入下一步 。 ? (4) 根據(jù) max(σ j＞ 0)=σ k， 確定 xk為換入變量 ， 按 θ 規(guī)則計(jì)算 lklikikiabaab ????????? ?? 0m i n?? (5) 以 alk為主元素進(jìn)行迭代 (即用高斯消去法或稱為旋轉(zhuǎn)運(yùn)算 )， 把 xk所對(duì)應(yīng)的列向量 ? 將 XB列中的 xl換為 xk， 得到新的單純形表 。 重復(fù)(2)～ (5)， 直到終止 。 行第變換laaaaPmklkkkk???????????????????????????????????????????010021????現(xiàn)用例 1的標(biāo)準(zhǔn)型來(lái)說(shuō)明上述計(jì)算步驟。 ? (1) 取松弛變量 x3,x4,x5為基變量 ， 它對(duì)應(yīng)的單位矩陣為基 。 這就得到初始基可行解 X(0)=(0,0,8,16,12)T ? 將有關(guān)數(shù)字填入表中，得到初始單純形表，見(jiàn)表 13。表中左上角的 cj是表示目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)。在 CB列填入初始基變量的價(jià)值系數(shù)，它們都為零。 54321 00032m a x xxxxxz ?????5,2,10124164825241321???????????jxxxxxxxxj 目標(biāo)函數(shù)中各變量的價(jià)值系數(shù) 。 c j → 2 3 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 θ 0 x 3 8 1 2 1 0 0 8/2=4 0 x 4 16 4 0 0 1 0 0 x 5 12 0 [4] 0 0 1 12/4=3 z 0 2 3 0 0 0 ，由它確定為換人變量 θ，由它確定為換出變量 表 13 基變量 計(jì)算非基變量的檢驗(yàn)數(shù) ? 各非基變量的檢驗(yàn)數(shù)為 ? σ 1=c1z1=2(0 1+0 4+0 0)=2 ? σ 2=c2z2=3(0 2+0 0+0 4)=3 ? 填入表 13的底行對(duì)應(yīng)非基變量處。 進(jìn)行（ 2），（ 3） (2) 因檢驗(yàn)數(shù)都大于零，且 P 1 ， P 2 有正分量存在， 轉(zhuǎn)入下一步； (3) max( σ 1 , σ 2 )=max(2,3)=3 ，對(duì)應(yīng)的變量 x 2 為換入變量， 計(jì)算 θ 341201628022?????????????????? ,m i naabm i niiii? 它所在行對(duì)應(yīng)的 x5為換出變量 ， x2所在列和 x5所在行的交叉處 [4]稱為主元素或樞元素 (pivot element) 進(jìn)行（ 4） (4) 以 [4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算或迭代運(yùn)算，即初等行變換，使 P2變換為（ 0,0,1） T,在XB 列中將 x2 替換 x5 ,于是得到新表 14. c j → 2 3 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 θ 0 x 3 2 [1] 0 1 0 1/2 2 0 x 4 16 4 0 0 1 0 4 3 x 2 3 0 1 0 0 1 /4 z 9 2 0 0 0 3/4 換人變量 換出變量 主元素 (5) 檢查表 14的所有 cjzj,這時(shí)有 c1z1=2；說(shuō)明 x1應(yīng)為換入變量。重復(fù) (2)～ (4)的計(jì)算步驟，得表 15。 ? 還存在檢驗(yàn)數(shù) 〉 0，繼續(xù)進(jìn)行。 c j → 2 3 0 0 0 C B X B b x 1 x 2