[管理學(xué)]線性規(guī)劃的圖解法與單純形解法-文庫(kù)吧資料
2025-01-25 07:42本頁(yè)面
【正文】 最優(yōu)解是存在的。 將人工變量 除去，目標(biāo)函數(shù)改為 m a x z = – 3 x1+ 0 x2+ x3+ 0 x4+0 x5 cj – 3 0 1 0 0 CB XB x1 x2 x3 x4 x5 b θi 0 0 – 3 x4 x2 x1 0 0 0 1 – 1/ 2 0 1 1/ 3 0 0 1 0 [ 2/ 3] 0 1/ 2 0 3 1 –– 9 2/ 3 ?j 0 0 3 0 3/ 2 0 0 1 x4 x2 x3 0 0 0 1 – 1/ 2 – 1/ 2 1 0 0 – 1 / 4 3/ 2 0 1 0 3 / 4 0 5/ 2 3/ 2 ?j – 3/ 2 0 0 0 – 3/ 2 z = 3/ 2 單純形法計(jì)算可能的循環(huán)現(xiàn)象 下 面的線性規(guī)劃問(wèn)題 ，經(jīng)過(guò) 6 次迭代后，得到的單純形表與初始單純形表相同。 線性規(guī)劃求解兩階段法舉例 例 用兩階段法求解上例。 我們可以構(gòu)造如下輔助問(wèn)題 m in w = xn +1+ … + xn + m+0 x1+ … +0 xn a11 x1+ a12 x2+ … + a1 nxn+ xn +1 = b1 a21 x1+ a22 x2+ … + a2 nxn + xn +2= b2 … … am 1 x1+ am 2 x2+ … + amnxn+ xn + m = bm x1, x2, … , xn , xn +1, … , xn + m≥ 0 ?????????線性規(guī)劃求解的兩階段法 然后用單純形法求解所構(gòu)造的新模型，若得到 w=0，這時(shí)，若基變量中不含人工變量，則說(shuō)明原問(wèn)題存在基可行解，可進(jìn)行第二步計(jì)算； 否則，原問(wèn)題無(wú)可行解，應(yīng)停止計(jì)算。 線性規(guī)劃求解的大 M法 線性規(guī)劃求解的大 M法 max z = c 1 x 1 + c 2 x 2 + … + c n x n M ( x n + 1 + … + x n + m ) a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 線性規(guī)劃求解的大 M法舉例 例 用單純形法求解線性規(guī)劃問(wèn)題 m a x z = 3 x1+ x3 x1+ x2+ x3 ≤ 4 2 x1+ x2 x3≥ 1 3 x2+ x3 = 9 x1, x2, x3≥ 0 解 先化標(biāo)準(zhǔn)型 m a x z = 3 x1+ x3+ 0 x4+0 x5 x1+ x2+ x3+ x4 =4 2 x1+ x2 x3 x5=1 3 x2+ x3 = 9 x1, x2, x3, x4, x5≥ 0 線性規(guī)劃求解的大 M法舉例 添加人工變量 x6, x7，將原線性規(guī)劃問(wèn)題變?yōu)? m a x z = 3 x1+ x3+ 0 x4+0 x5 M x6 M x7 x1+ x2+ x3+ x4 =4 2 x1+ x2 x3 x5+ x6=1 3 x2+ x3 + x7= 9 x1, x2, x3, x4, x5, x6, x7≥ 0 線性規(guī)劃求解的大 M法舉例 cj – 3 0 1 0 0 – M – M CB XB x1 x2 x3 x4 x5 x6 x7 b θi 0 x4 1 1 1 1 0 0 0 4 4 – M x6 – 2 [ 1] – 1 0 – 1 1 0 1 1 – M x7 0 3 1 0 0 0 1 9 3 ?j – 2 M – 3 4 M 1 0 – M 0 0 0 x4 3 0 2 1 1 – 1 0 3 1 0 x2 – 2 1 – 1 0 – 1 1 0 1 –– – M x7 [ 6] 0 4 0 3 – 3 1 6 1 ?j 6 M – 3 0 4 M +1 0 3 M – 4 M 0 0 x4 0 0 0 1 1/ 2 – 1 – 1/ 2 0 –– 0 x2 0 1 1/ 3 0 0 0 1/ 3 3 9 – 3 x1 1 0 [ 2/ 3] 0 1/ 2 – 1/ 2 1/ 6 1 3/ 2 ?j 0 0 3 0 3/ 2 – M – 3/ 2 M + 1/ 2 0 x4 0 0 0 1 – 1/ 2 – 1/ 2 – 1/ 2 0 0 x2 – 1/ 2 1 0 0 – 1/ 4 1/ 4 1/ 4 5/ 2 1 x3 3/ 2 0 1 0 3/ 4 – 3/ 4 1/ 4 3/ 2 ?j 0 0 0 0 – 3/ 4 – M + 3 / 4 – M – 1/ 4 z = 3/ 2 線性規(guī)劃求解的兩階段法 兩階段法的基本思路是： 第一階段 ，首先不考慮原問(wèn)題是否存在基可行解 ， 先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即令目標(biāo)函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù) ( 一般取 1) ，在保持原問(wèn)題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。 ?由于人工變量對(duì)目標(biāo)函數(shù)有很大的負(fù)影響，單純形法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到原問(wèn)題的一個(gè)可行基。如果在最終單純形表中還存在非零的人工變量，這表示無(wú)可行解。 由于單位陣可以作為基陣，因此，可選加入的人工變量為基變量。 線性規(guī)劃求解的人工變量法 ? 人工變量法 引用人工變量是用單純形法求解線性規(guī)劃問(wèn)題時(shí)解決可行解問(wèn)題的常用方法。 （ 4 ） 根據(jù) ?規(guī)則，求出：? ?11111( ) ( )m i n 0( ) ( )ilkiilB b B bBPB P B Pkk??????????? ? ??????? 它對(duì)應(yīng)的基變量lX 為換出變量，于是可給出一組新的基變量以及新的基矩陣1B 。求出初始解： ??????????????01bBXXNB （ 2 ） 計(jì)算非基變量NX的檢驗(yàn)數(shù)N? ， NBCC BNN 1???? ，若0?N?已得到最優(yōu)解，停止計(jì)算，若還存在Njj ?? ,0? ，轉(zhuǎn)入下一步。 j1?? （ 5 ） 當(dāng) B 為最優(yōu)基時(shí)，在上表中應(yīng)有 ?????????0011BCABCCBBN 因 X B的檢驗(yàn)數(shù)可寫(xiě)作01 ?? ? BBCC BB 所以 有 ?????????0011BCABCCBB
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1