【正文】 的基 B，令非基變量等于零，利用式（ ）解出基變量，則這組解稱為基 Ｂ 的基本解。 01 ?）（X ）（ 2X反之 ， 可行解不一定是基本可行解 例如 滿足式 （ ） ～ （ ） ， 但不是 任何基矩陣的基本解 。 2121基本最優(yōu)解 最優(yōu)解是基本解稱為基本最優(yōu)解。A點是基本最優(yōu)解 ,同時也是最優(yōu)解、基本可行解、基本解和可行解。直到找到一個頂點為其最優(yōu)解，就是使得其目標函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。參看表 16 最優(yōu)解判斷標準 當所有檢驗數(shù) λj≤0（ j=1， … ， n）時，基本可行解為最優(yōu)解。其中基變量的檢驗數(shù)必為零； ： （ a） 若 λj≤０ （ j＝１ ， ２ ， … ， n） 得到最解； （ b） 某個 λk0且 aik≤０ （ i=1， 2,… ,m） 則線性規(guī)劃具有無界解 (見例 118)。 Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 － 3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 0 x4 2 x2 λj 1 x1 2 x2 λj 表 1－ 7 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 － 9 0 － 2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 － 1/9 2/3 35/3 0 0 － 98/9 － 1/9 － 7/3 最優(yōu)解 X=(25， 35/3， 0， 0， 0)T，最優(yōu)值 Z=145/3 。 aLk為主元素； (c） 求新的基可行解：用初等行變換方法將 aLk 化為１ ,k列其它元素化為零 （ 包括檢驗數(shù)行 ） 得到新的可行基及基本可行解 ， 再判斷是否得到最優(yōu)解 。 檢驗數(shù) 目標函數(shù)用非基變量表達時的變量系數(shù) 單純形法全過程的計算 ， 可以用列表的方法計算更為簡潔 ，這種表格稱為單純形表 （ 表 16） 。 【 解 】 化為標準型 ， 加入松馳變量 x x4則標準型為 121 2 31 2 41 2 3 4m a x 3 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)解，可以從目標函數(shù)中的系數(shù)看出。 它是一種逐步逼近最優(yōu)解的迭代方法 。 1Q2Q基本最優(yōu)解 、 最優(yōu)解 、 基本可行解 、 基本解 、 可行解的關(guān)系如下所示： 基本最優(yōu)解 基本可行解 可行解 最 優(yōu) 解 基本解 例如 ,B點和 D點是可行解 ,不是基本解 。 當最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。 TX )8,0,0,0,53(?非可行解 (Infeasible solution) 無界解 (unbound solution) 顯然，只要基本解中的基變量的解滿足式（ ）的非負要求，那么這個基本解就是基本可行解。 基本可行解 (basis feasible solution) 若基本解是可行解則稱為是基本可行解 （ 也稱基可行解 ） 。 當確定某一矩陣為基矩陣時，則基矩陣對應的列向量稱為 基向量 (basis vector)，其余列向量稱為 非基向量 。 基 (basis)A中 m m子矩陣 B并且有 r（ B） =m，則稱 B是線性規(guī)劃的一個基（或基矩陣 basis matrix ）。 綜合起來得到下列標準型： 3321 33m a x xxxxZ ???????????????????????????????????????????05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、【 例 29】 ：將以下線性規(guī)劃問題轉(zhuǎn)化為標準形式 Min f = 2 x1 3x2 + 4 x3 . 3 x1 + 4x2 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = 9 x1 , x2 , x3 ≥ 0 解：首先 ,將目標函數(shù)轉(zhuǎn)換成極大化： 令 z= f = 2x1+3x24x3 其次考慮約束 ， 有 2個不等式約束 ， 引進松弛變量 x4， x5 ≥ 0。≤b－ a并且將原問題所有 x用 x= x39。 當某一個右端項系數(shù)為負時 ， 如 bi0， 則把該等式約束兩端同時乘以 1， 得到： ai1 x1ai2 x2 … ain xn = bi。如果原問題中有若干個非等式 約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量。 ? 影子價格 當約束條件中的常數(shù)項增加一個單位時，最優(yōu)目標函數(shù)值增加的數(shù)量。 當有多個系數(shù)同時變化時 例 27的計算報告 百分之一百法則： 對于所有變化的目標函數(shù)決策系數(shù)（約束條件右邊常數(shù)值），當其所有允許增加的百分比與允許減少的百分比之和不超過 100%時，最優(yōu)解不變（對偶價格不變，最優(yōu)解仍是原來幾個線性方程的解）。 2 5 02 0 01 0 01 0 0 2 0 0 3 0 0ABCDOB ’C ’ 假設原料 A 增加 10 千克時 ， 即 b2變化為 410， 這時可行域擴大 ， 但 最優(yōu)解仍為 x2 = 250 和 x1 + x2 = 300 的交點 x1 = 50， x2 = 250 。 ? 假設產(chǎn)品 Ⅱ 的利潤 100元不變，即 c2 = 100，代到式（ *）并整理得 0 ? c1 ? 100 ? 假設產(chǎn)品 Ⅰ 的利潤 50 元不變，即 c