1、1.4節中關于大M法和兩階段法的課堂例題討論課堂討論題 習題 1.5(2)P.51用大M法和兩階段法求解min z 3x1 x2x1x22x1 x24x1x2x1,x2 0標準化后為min z 3x1 x2x1 x2 x32x1 x2x44x1x2x1,x2,x3,x4采用大M法數學模型為min z 3x1X2M(X5X6)x1x2X3X532x1 x2X44x1x2X 3Xi,X2,X60單純形表法求解如下:Cj3100MMCbbX1X2X3X4X5XMX531(1)-101030X442101004M沁31100013CjZj3-2M1-2MM0001X2311-1110-0X411010

2、-101MX000(1)0-110CjZj201-M02M-10Cj3100MMCbXbbX2X3X4X5X61X231100010X4110001-10X30001-101CjZj32000MM-1因此的最優解如下*tX 0301,最優目標函數min z=3采用兩階段法。第一階段的數學模型是：minX5X6X1X2X3X532x1X2X44x1 x2X63X1,X2,X60單純形表法的求解如下Cj000011CbbX1X2X3X4X5X1X31(1)-101030X442101004131100013CjZj-2-210000X2311-1110-0X411010-1011X000(1)0-

3、110Cjz00-1020Cj000011CbXbbX1X2X3X4X5X0X231100010X4110001-10X30001-101Cjz3000010第二階段的數學模型基標準化了的模型。 通過第一階段的計算，我們101求得了一個可行基，即BF2Pt F3110，解出相100應的基變量后，可的單純形表如下cj3100CbXbXX，X3X41X2311000X4110000X30001-1Cjz32000上述結果和將第一階段的最后一張表的人工變量列刪除，并且將原問題的價值系數換上再計算檢驗數的結果一樣。上述問題是退化問題，若按 Bia nd法則，第一次換基時應讓 Xi入基, 相應的過程如下

4、：Cj000011CbbX1X2X3X4X5X1X5311-101030X4（2）1010021X31100013CjZj-2-21000iX510(1/2)-1-1/21020xi211/201/2004iX101/20-1/2012CjZj0-11100Cj000011LbX1X2X3X4X5X60201-2-120-0xi11011-1011000(1)0-110CjZj300-1020Cj000011CbbxiX2X3X4X5X02010-1020X1110010-10X300010-11Cjz3000011已得第一階段最優解，第二階段的可行基是111BP2 P P3120110初始單純形表如下Cj3100CbXbbXX2X3X41X22010-1-3X1100110X300010-Cjz3000-2Cj3100CBXbbXXX3X4100X2X4X3310110100001010Cj召30000的最優解，與前述結果一樣，但由于選擇的換基次序不同（即尋優的 方向不同），在第一階段中多了一步迭代，同時第一階段的最優解不 是原問題（第二階段）