第三節線性規劃問題的單純形解法線性規劃問題解的基本概念單純形解法解的最優性檢驗表解形式的單純形法單純形解法的一些問題及其處理方法一、線性規劃問題解的基本概念可行解最優解基及基本解可行基及基本可行解代數解與幾何解的關系單純形法的要點二、單純形解法建立基本可行解計算變量的檢驗數判斷是否最優若不是最優解，換基計算新的基本可行解迭代計算直到求得最優解或可判斷無最優解為止建立初始基本可行基對于小于等于情況，通過標準化，每個約束條件的左邊加上了一的松弛變量，該松弛變量的系數矢量時單位矢量。當約束條件的右手項都大于等于零時，可令松弛變量為初始基本可行基。例1.1的標準型線性方程組的增廣矩陣表示它的初始可行基初始基本可行解初始基變量是松弛變量。初始可行解（只要滿足非負條件）初始基本可行解目標函數與最優性檢驗第一次迭代確定入基變量，應當是，它的系數是4。確定出基變量，方法如下，得確定新基和求解新的基本可行解新基新的基變量：新的基本可行解新的基本可行解和目標函數基本可行解目標函數第二次迭代確定入基變量：確定出基變量：確定新基和求解新的基本可行解

新基新的基變量：新的基本可行解新的基本可行解和目標函數基本可行解目標函數第三次迭代確定入基變量：確定出基變量：確定新基和求解新的基本可行解新基新的基變量：新的基本可行解基本可行解目標函數這是最優解。最大目標函數值為2600。新的基本可行解和目標函數三、關于解的最優性檢驗設線性規劃模型為令基為B，并作相應的矩陣分割，從約束條件得代入目標函數得令則目標函數可寫成所以可用判斷是否最優解，它叫做檢驗數。四、表解形式的單純形法表的格式在表上的計算方法表上計算的原理表解單純形法的實例：例1-1初始單純形表43000b0001600250040025122.50100010001800500400043000第一次迭代43000b00480050040000122.50100010-2-5140020016000300-4第二次迭代43000b034400200400001010100-0.80.402-212004002200000-1.22第三次迭代43000b0342006002000010100.51-0.5-0.4-0.40.4100000-1-0.40五、單純形解法中的一些問題及其處理方法換入變量的選擇問題下標最先原則檢驗數最大原則換出變量的選擇問題比值最小原則下標最先原則無換出變量的情況—無界解非基變量檢驗數有等于零—多個最優解的情況多個最優解情況假設載重車每輛獲利2千元，則目標函數變為它與約束條件平行，因此可行域頂點B和C都市最優解，其凸組合邊BC都是最優解。第一次迭代42000b00480050040000122.50100010-2-5140020016000200-4一個檢驗數=0，第一個最優解42000b024400200400001010100-0.80.402-212004002000000-0.80迭代一次后得到另一個最優解42000b0242006002000010100.51-0.5-0.4-0.40.41002000000-0.80最優解一個最優解點B：X1=(2