運(yùn)籌學(xué)課件第1章線性規(guī)劃與單純形法-第3節(jié)-資料下載頁(yè)
2025-01-04 01:33本頁(yè)面
【正文】 ln11,22211,2211111,11331 一般線性規(guī)劃問(wèn)題的約束方程組中加入松弛變量或人工變量后， 很容易得到上述形式 設(shè) x1,x2,…,xm為基變量，對(duì)應(yīng)的系數(shù)矩陣是 m m單位陣 I， 它是可行基。令非基變量 xm+1,xm+2,…,xn為零， 即可得到一個(gè)基可行解。 若它不是最優(yōu)解，則要另找一個(gè)使目標(biāo)函數(shù)值增大的基可行解。這時(shí)從非基變量中確定 xk為換入變量。顯然這時(shí) θ 為 lklikikii abaab??????????? 0m i n?在迭代過(guò)程中 θ 可表示為 39。39。39。39。39。0m i nlklikikii abaab????????????其中是經(jīng)過(guò)迭代后對(duì)應(yīng)于的元素值 。 39。39。, iki ab ik,按 θ 規(guī)則確定 xl為換出變量， xk, xl的系數(shù)列向量分別為 個(gè)分量第 lPaaaaPlmklkkkk???????????????????????????????????????????0010。21????為了使 xk與 xl進(jìn)行對(duì)換，須把 Pk變?yōu)閱挝幌蛄?，這可以通過(guò) (133)式系數(shù)矩陣的增廣矩陣進(jìn)行初等變換來(lái)實(shí)現(xiàn)。 )341(1111ln11,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ù)矩陣寫(xiě)成增廣矩陣 ??????????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é)束
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1