• /  69
  • 下載費用: 29.9積分  

單純形法大M法求解線性規劃問題.ppt

'單純形法大M法求解線性規劃問題.ppt'
第二章 單純形法 單純形法的一般原理 表格單純形法 借助人工變量求初始的基本可行解 單純形表與線性規劃問題的討論 改進單純形法 1 考慮到如下線性規劃問題 其中A一個m×n矩陣,且秩為m,b總可以被調整為一個m維非負列向量,C為n維行向量,X為n維列向量。 根據線性規劃基本定理: 如果可行域D={ X∈Rn / AX=b,X≥0}非空有界, 則D上的最優目標函數值Z=CX一定可以在D的一個頂點上達到。 這個重要的定理啟發了Dantzig的單純形法, 即將尋優的目標集中在D的各個頂點上。單純形法的一般原理 2  Dantzig的單純形法把尋優的目標集中在所有基本可行解 ?。纯尚杏蝽旤c)中?!   ∑浠舅悸肥菑囊粋€初始的基本可行解出發,尋找一條達到  最優基本可行解的最佳途徑。 單純形法的一般步驟如下: (1)尋找一個初始的基本可行解。 (2)檢查現行的基本可行解是否最優,如果為最優, 則停止迭代,已找到最優解,否則轉一步。 (3)移至目標函數值有所改善的另一個基本可行解, 然后轉會到步驟(2)。 3 確定初始的基本可行解 確定初始的基本可行解等價于確定初始的可行基,一旦初始的可行基確定了,那么對應的初始基本可行解也就唯一確定 為了討論方便,不妨假設在標準型線性規劃中,系數矩陣A中前m個系數列向量恰好構成一個可行基,即 A=(BN),其中 B=(P1,P2,…Pm)為基變量x1,x2,…xm的系數列向量 構成的可行基, N=(Pm+1,Pm+2, …Pn)為非基變量xm+1,xm+2, …xn的 系數列向量構成的矩陣。 4所以約束方程  就可以表示為 用可行基B的逆陣B-1左乘等式兩端,再通過移項可推得: 若令所有非基變量    , 則基變量  由此可得初始的基本可行解5問題:要判斷m個系數列向量是否恰好構成一個基并不是一件容易的事?;上禂稻仃嚕林衜個線性無關的系數列向量構成。但是要判斷m個系數列向量是否線性無關并非易事。即使系數矩陣A中找到了一個基B,也不能保證該基恰好是可行基。因為不能保證基變量XB=B-1b≥0。為了求得基本可行解 ,必須求基B的逆陣B-1。但是求逆陣B-1也是一件麻煩的事。結論:在線性規劃標準化過程中設法得到一個m階單位矩陣I作為初始可行基B,6若在化標準形式前,約束方程中有“≥”不等式,那么在化標準形時除了在方程式左端減去剩余變量使不等式變成等式以外,還必須在左端再加上一個非負新變量,稱為人工變量.若在化標準形式前,約束方程中有等式方程,那么可以直接在等式左端添加人工變量?! 榱嗽O法得到一個m階單位矩陣I作為初始可行基B,可在性規劃標準化過程中作如下處理: 若在化標準形式前,m個約束方程都是“≤”的形式, 那么在化標準形時只需在一個約束不等式左端都加上一個松弛變 量xn+i (i=12…m)。7判斷現行的基本可行解是否最優   假如已求得一個基本可行解將這一基本可行解代入目標函數,可求得相應的目標函數值 其中                  分別表示基變量和 非基變量所對應的價值系數子向量。8  要判定      是否已經達到最大值,只需將            代入目標函數,使目標函數用非基變量表示,即:    其中         稱為非基變量XN的檢驗向量,它的各個分量稱為檢驗數。若σN的每一個檢驗數均小于等于0,即σN≤0,那么現在的基本可行解就是最優解。9定理1:最優解判別定理 對于線性規劃問題                若某個基本可行解所對應的檢驗向量          , 則這個基本可行解就是最優解。定理2:無窮多最優解判別定理    若     是一個基本可行解,所對應的檢驗向量           ,其中存在一個檢驗數σm+k=0,  則線性規劃問題有無窮多最優解。10 基本可行解的改進 如果現行的基本可行解X不是最優解,即在檢驗向量     中存在正的檢驗數,則需在原基本可行解X的基礎上尋找一個新的基本可行解,并使目標函數值有所改善。具體做法是:先從檢驗數為正的非基變量中確定一個換入變量,使它從非基變量變成基變量(將它的值從零增至正值),再從原來的基變量中確定一個換出變量,使它從基變量變成非基變量(將它的值從正值減至零)?!∮纱丝傻靡粋€新的基本可行解,由 可知,這樣的變換一定能使目標函數值有所增加。11 換入變量和換出變量的確定:換入變量的確定— 最大增加原則 假設檢驗向量                 , 若其中有兩個以上的檢驗數為正,那么為了使目標函數值增加得快些,通常要用“最大增加原則”,即選取最大正檢驗數所對應的非基變量為換入變量,即若  則選取對應的   為換入變量, 由于    且為最大, 因此當   由零增至正值,可使目標函數值 最大限度的增加。12 換出變量的確定— 最小比值原則 如果確定  為換入變量,方程            其中  為A中與   對應的系數列向量?!‖F在需在        中確定一個基變量為換出變量。 當  由零慢慢增加到某個值時, 的非負性可能被打破。為保持解的可行性,可以按最小比值原則確定換出變量: 若則選取對應的基變量  為換出變量。 13 定理3:無最優解判別定理 若   是一個基本可行解,有一個檢驗數     , 但是     ,則該線性規劃問題無最優解。證:令        ,則得新的可行解將上式代入            因為    , 故當λ→+∞時,Z→+∞。14 用初等變換求改進了的基本可行解 假設B是線性規劃           的可行基,則令非基變量   ,則基變量     ?!】傻没究尚薪?  。  用逆陣  左乘約束方程組的兩端,等價于對方程組施以一系列的初等“行變換”。變換的結果是將系數矩陣A中的可行基B變換成單位矩陣I,把非基變量系數列向量構成的矩陣N變換成   ,把資源向量b變換成   。15 且改進了的基本可行解 只是在X的基變量的基礎上用一個換入變量替代其中一個換出變量,其它的基變量仍然保持不變。這些基變量的系數列向量是單位矩陣I中的單位向量。為了求得改進的基本可行解  ,只需對增廣矩陣 施行初等行變換,將換入變量的系數列向量變換成換出變量所對應的單位向量即可?! ∮捎谛谐醯茸儞Q后的方程組           與原約束方程組    或          同解16例1解:(1)確定初始的基本可行解。          ,基變量 。省略部分。 2-1/2101Z02200因但所以原問題無最優解52 退化解   當線性規劃問題的基本可行解中有一個或多個基變量取零值時,稱此基本可行解為退化解。 產生的原因:在單純形法計算中用最小比值原則確定換出變量時,有時存在兩個或兩個以上相同的最小比值θ,那么在下次迭代中就會出現一個甚至多個基變量等于零。遇到的問題:當某個基變量為零,且下次迭代以該基變量作為換出變量時,目標函數并不能因此得到任何改變(由旋轉變換性質可知,任何一個換入變量只能仍取零值,其它基變量的取值保持不變)。通過基變換以后的前后兩個退化的基本可行解的坐標形式完全相同。從幾何角度來解釋,這兩個退化的基本可行解對應線性規劃可行域的同一個頂點,解決的辦法:最小比值原則計算時存在兩個及其以上相同的最小比值時,選取下標最大的基變量為換出變量,按此方法進行迭代一定能避免循環現象的產生(攝動法原理)。53例8、求解下述線性規劃問題:解:引入松弛變量    化標準型54000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410x1 30-1130-3-800x5 0-11001001x7 000106-1-2410x6 0000136-4-3210x5 0x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C θ 第一次迭代中使用了攝動法原理,選擇下標為6的基變量x6離基??傻米顑灲?,目標函數值maxZ=5,55 無窮多最優解   無窮多最優解判別原理:若線性規劃問題某個基本可行解所有的非基變量檢驗數都小于等于零,但其中存在一個檢驗數等于零,那么該線性規劃問題有無窮多最優解。例3:最優表:非基變量檢驗數   , 所以有無窮多最優解?!∽顑灲饧癁榭尚杏騼蓚€頂點的凸組合:C1 2 0 0 0θCBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z’8 0 0 0 0 -156改進單純形法的特點  利用單純形表求解線性規劃時,每一次迭代都把整個單純形表計算一遍,事實上我們關心的只是以下一些數據:基本可行解     ,其相應的目標函數值      ,非基變量檢驗數        ,及其換入變量  , 設 主元列元素   ,及其換出變量  ,  設  利用它們可得到一組新的基變量以及新的可行基B1。改進單純形法為基變量下標為非基變量下標57  對任一基本可行解X,只要知道  ,上述關鍵數據都可以從線性規劃問題的初始數據直接計算出來。因此如何計算基本可行解X對應的可行基B的逆陣  成為改進單純形法的關鍵.  改進單純形法推導出從可行基B變換到B1時, 到的變換公式。當初始可行基為單位矩陣Ι時,變換公式將更具有優越性,因為這樣可以避免矩陣求逆的麻煩以下推導從  到  的變換公式:58 假設當前基             ,               基變換中用非基變量  取代基變量 可得新基前后二個基相比僅相差一列,且比較以上二式,可得  其中 表示第 個元素為1,其它元素均為零的單位列向量,  為主元列元素。 59假設 ,則第 列(換出變量 對應列 )第 行所以由主元素60 改進單純形法的步驟(1) 根據給出的線性規劃問題的標準型,確定初始基變量和初始可行基B。求初始可行基B的逆陣B-1,得初始基本可行解            。 (2)計算單純形乘子    ,得目標函數當前值(3) 計算非基變量檢驗數            , 若σN≤0,則當前解已是最優解,停止計算;否則轉下一步。(4)  根據         ,確定非基變量  為換入變量,計算   ,若   ≤0,則問題沒有有限最優解,停止計算,否則轉下一步。61(5) 根據     ,確定基變量  為換出變量。 (6) 用  替代 得新基B1,由變換公式          計算新基的逆陣B1-1,求出新的基本可行解   其中  為變換矩陣,構造方法是: 從一個單位矩陣出發,把換出變量  在基B中的對應列的單位 向量,替換成換入變量 對應的系數列向量 ,并做如下變形, 主元素 (應在主對角線上)取倒數,其它元素除以主元素 并取相反數?! ≈貜停?)~(6)直至求得最優解。 62換入無界解換出≤0≤0①②④③⑤最優解初始基新基⑥63  例9、試用改進單純形法求解 解:(1)觀察法確定                                  ,   為基變量 為非基變量 64 (2)計算單純行乘子   目標函數當前值 (3)非基變量檢驗數(4)  選擇換入變量    故  為換入變量。計算65(5)確定換出變量    確定  為換出變量,主元素=2(6) 用 代替 得新可行基 為基變量, 為非基變量, 重復以上步驟,進入第二循環66(1)(2)(3)67(4) 選擇 換入變量(5) 選擇 換出變量,主元素=(6) 用  代替  得新可行基 為基變量, 為非基變量, 進入第三循環.68 (1) (2) (3) 非基變量對應的檢驗數全部非正, 故當前解 即為最優解, 相應的目標函數最優值 。69
關 鍵 詞:
單純 線性規劃 問題 求解
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:單純形法大M法求解線性規劃問題.ppt
鏈接地址: http://www.476824.live/p-51330289.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 双色球定胆杀号九九准 广西快3走基本走势图 黑龙江省11选五结果 安卓游戏急速赛车 黑龙江省十一选五开奖结果查询 股票推荐公众号 小龙女的投资哲学 云南时时彩官网平台 体彩福建31选7开奖结果19210 股票指数行情app gt赛车4安卓破解版