運籌學-第2講線性規(guī)劃模型(編輯修改稿)
2025-07-13 12:59 本頁面
【文章內容簡介】 P,...,P,PaaaaaaaaaB ???????????????????B 中的每一個列向量 Pj（ j=1,2,…,m ）稱為 基向量 ，與基向量 Pj 對應的變量 xj 稱為 基變量 。除基變量以外的其它變量稱為 非基變量。 基 B的 m個列向量是線性無關的。 標準形式 max z = 3x1+5x2 ????????????????),j(xxxxxxxxj543210182312245214231 ?????????100230102000101A ? ??????????100010001P,P,P 543? ?543 P,P,P 是一個基，對應的變量 x3,x4,x5是基變量， x1,x2是非 基變量。 基解 ：假設系數矩陣 A 的秩為 m，不妨設 A 中前 m 個列向量線性獨立，方程可以寫為 nmnn2n11m1mm1m21m1m21mmmm2m122m221211m2111xaaaxaaabbbxaaaxaaaxaaa???????????????????????????????????????????????????????????????????????????????令所有非基變量 xm+1=?=xn=0， 由 |B|≠0，根據克萊姆規(guī)則，可得 m個基變量的唯一解 xb=(x1,x2,…,x m) 加上所有取值為 0 的非基變量，得： x=(x1,x2,…,x m,0,…,0) 稱 x 為線性規(guī)劃問題的基解。 令 x1=x2=0，解得 x3=4,x4=12,x5=18,則 x=(0,0,4,12,18)T是一個基解。 ????????????????),j(xxxxxxxxj543210182312245214231 max z = 3x1+5x2 ?????????100230102000101A? ??????????100010001P,P,P 543基可行解 ： 滿足變量非負約束條件 (c)的基解稱為基可行解。 可行基 ：對應于基可行解的基稱為可行基。 可行解 基 解 基可行解 令 x1=x2=0，解得 x3=4,x4=12,x5=18,則 x=(0,0,4,12,18)T是一個基解。 由于該基解中所有變量取值為非負，故是基可行解，對應的基 ? ?543 P,P,P 是可行基。 可行基往往不只一個。 ?????????100230102000101A如（ P1,P4,P5）也是 可行基。 最多可能有多少個 ? 例：求下述線性規(guī)劃的基可行解 4,1014223m a x42132121????????????jxxxxxxxxxzjA= =( A1 , A2 , A3 , A4 ) 2 1 1 0 1 1 0 1 B1=( A3 , A4 )= X(1)=( 0 , 0 , 4 , 1 )T 基解 1 0 0 1 B2=( A1 , A4 )= X(2)=( 2 , 0 , 0 , 3 )T 基解 2 0 1 1 B3=( A1 , A2 )= X(3)=( 1 , 2 , 0 , 0 )T 基解 2 1 1 1 B4=( A2 , A3 )= X(4)=( 0 , 1 , 3 , 0 )T 基解 1 1 1 0 B5=( A1 , A3 )= X(5)=( 1 , 0 , 6 , 0 )T 基解 2 1 1 0 B6=( A2 , A4 )= X(6)=( 0 , 4 , 0 , 3 )T 基解 1 0 1 1 基可行解 解 幾何思路 圖解法的介紹 1. 確定 可行解集合 R， 即 可行域 的圖形 . 注：滿足所有約束條件的解稱為線性規(guī)劃問題的可行解。 2. 作出 目標函數等值線 . 3. 確定 最優(yōu)解 ，記為 x*. ? 注：圖解法僅適應與求解 兩個 決策變量的 LP問題 ? ? ? ? ? 0 x , x 18 x 2 x 3 12 x 2 4 x 2 1 2 1 2 1 max z = 3x1+5x2 當目標函數的等值線沿著梯度方向移動到剛離開可行域時，即可得到目標函數有最大值的解。 ? ? ? ? ? 0 x , x 18 x 2 x 3 12 x 2 4 x 2 1 2 1 2 1 max z = 3x1+2x2 ? ? 0 x , x 4 x 2 1 1 max z = 3x1+5x2 1212121212m in 3 542 12. . 3 2 183 5 500 , 0Z x xxxs t x xxxxx???????????????? ? ??圖解法求解結果 有可能出現以下各種情形： （ 1 ）有最優(yōu)解并且唯一；
教學教案相關推薦
鄂ICP備17016276號-1