【正文】 0 0 4 0 02 4 03 / 2 3 0, , , 0Z x xx x xx x xx x x x??? ? ???? ? ??? ??系數(shù)矩陣 A及可行基 B1 2 1 1 01 3 / 2 0 1A ??? ???????????10011Br(B1)=2， B1是一個初始基 ,x x4為基變量 ， x x2為非基變量 ， 令 x1=0、 x2=0由約束方程知 x3=x4=30得到初始基本可行解 X(1)=(0,0,40,30)T 【 例 212】 用單純形法求例 11線性規(guī)劃的最優(yōu)解 以上得到的一組基可行解是不是最優(yōu)解，可以從目標(biāo)函數(shù)中的系數(shù)看出。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。其中基變量的檢驗數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個 λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 (見例 118)。直到找到一個頂點為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。 2121基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。 TX )1,27,21,0,0(? 基本解 (basis solution) 對某一確定的基 B，令非基變量等于零，利用式（ ）解出基變量，則這組解稱為基 Ｂ 的基本解。 【 解 】 約束方程的系數(shù)矩陣為 2 5矩陣 ?????????10261001115A,610 151 ????????B ,010 152 ????????B ,110 053 ????????B ?????? ??26114B???????10019B,12017 ????????B ,02118 ????????B,16016 ???????B,06 115 ???????B容易看出 r(A)=2， 2階子矩陣有 C52=10個，其中第 1列與第 3列構(gòu)成的 2階矩陣不是一個基，基矩陣只有 9個，即 由線性代數(shù)知，基矩陣 B必為非奇異矩陣并且 |B|≠0。 【 例 28】 將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 321 3m in xxxZ ????????????????????????無符號要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【 解 】 : (1)目標(biāo)函數(shù)為 min，令 Z’=Z； (2)因為 x3無符號要求 ，即 x3取正值也可取負值，標(biāo)準(zhǔn)型中要求變量非負，所以令 0, 33333 ????????? xxxxx 其中 (4)第二個約束條件是 ≥號，在 ≥號 左端減去剩余變量 (Surplus variable)x5， x5≥0。 b. 當(dāng)某一個決策變量 xj沒有符號限制時，可以令 xj = xj’ xj” 其中 xj’≥0， xj”≥0 即用兩個非負變量之差來表示一個無符號限制的變量，當(dāng)然 xj的符號取決于 xj’和 xj”的大小。 在使用百分之一百法則進行靈敏度分析時 ， 要注意： 1） 當(dāng)允許增加量 （ 允許減少量 ） 為無窮大時 ， 則對任意增加量 （ 減少量 ） ， 其允許增加 （ 減少 ） 百分比均看作 0； 2） 百分之一百法則是充分條件 ， 但非必要條件；也就是說超過 100%并不一定變化； 3） 百分之一百法則不能用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右邊常數(shù)值同時變化的情況 。 增加的利潤： (50 60+ 100 250) (50 50+100 250) = 500元 ， 單位臺時增加的利潤為： 500 / 10 = 50 元 。 一般地，將目標(biāo)函數(shù)直線放在可行域中，求最大值時直線沿著矢量方向移動，求最小值時沿著矢量的反方向移動。 則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成 1 1 2 211 1 12 2 1 121 1 22 2 2 21 1 2 2m a x( m in)( , )( , )( , )0 , 1 , 2 , ,nnnnnnm m m n n mjZ c x c x c xa x a x a x ba x a x a x ba x a x a x bx j n? ? ? ?? ? ? ? ? ???? ? ? ? ? ?????? ? ? ? ? ??????或或或為了書寫方便，上式也可寫成： 線性規(guī)劃的數(shù)學(xué)模型 11m a x( m i n)( , ) 1 , 2 , ,0 , 1 , 2 , ,njjjnij j ijjZ c xa x b i mx j n????? ? ? ???? ????? 或在實際中一般 xj≥0,但有時 xj≤0或 xj無符號限制 。 根據(jù)統(tǒng)計 ， 商場每天需要的營業(yè)員如表 12所示 。 ?其特征是： ?1．解決問題的目標(biāo)函數(shù)是多個決策變量的 線性函數(shù)，通常是求最大值或 最小值； ?2．解決問題的 約束條件 是一組多個決策變量 的線性不等式或等式。 ? 當(dāng)一個系數(shù)發(fā)生變化時，其他系數(shù)保持不變； ? 兩個及兩個以上系數(shù)同時發(fā)生變化。 此變化對總利潤無影響 ， 該約束條件的對偶價格為 0 。 ? 對偶價格 當(dāng)約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標(biāo)函數(shù)值改進的數(shù)量。 c. 絕對值不等式 當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束 ： 974 321 ??? xxx可將其化為兩個不等式，再加入松馳變量化為等式： ??????????974974321321xxxxxxd. a≤x≤b (a、 b均大于零 ) 有兩種方法： 一種方法是增加兩個約束 x≥a及 x≤b 另一種方法是令 x39。 第三個約束條件的右端值為負，在等式兩邊同時乘 1。 基向量對應(yīng)的變量稱為 基變量 (basis variable)，非基向量對應(yīng)的變量稱為 非基變量 在上例中 B2的基向量是 A中的第一列和第四列 ， 其余列向量是非基向量 ， x x4是基變量 ， x x x5是非基變量 。 在例 211中 ， 對 B1來說 ， x1,x2是基變量 ， x3,x4， x5是非基變量 ，令 x3=x4=x5=0， 則式 （ ） 為 ???????2610352121xxxx－,610151 ????????B對 B2來說 ， x1,x4,為基變量 ， 令非基變量 x2,x3,x5為零 ， 由式 （ ） 得到 ， x4=4， 511 ??x因 |B1|≠０，由克萊姆法則知， x x2有唯一解 x1＝ 2/5,x2=1則 基本解為 ( 1 ) 2( , 1 , 0 , 0 , 0 )5TX ?由于