【文章內容簡介】 （ 3）求初始解（即找出一個方案）； （ 4）畫出單純形表，應用矩陣初等行變換知識，進行表上運算； （ 5）確定變換的“列”和“行”（在“檢驗行”定列，利用“商最小原理”定行），“列”和“行”交叉的元素變?yōu)椤?1”，該“列”其余元素變?yōu)椤?0”； （ 6）重復（ 4） ~（ 5），若“檢驗行”所有元素均 = 0 時，線性規(guī)劃的最優(yōu)化解找到。 幾種特殊情況的說明 ： * 無可行解：線性規(guī)劃的最優(yōu)解里，人工變量 0，該線性規(guī)劃無可行解。 * 無界解：在單純形表的某次迭代中，如果存在著一個大于零的檢驗數(shù)，并且該列的系數(shù)向量的每一個于是都是小于或等于零，此線性規(guī)劃問題是無界的。此類問題由建模的錯誤引起。 * 無窮多最優(yōu)解：對于某最優(yōu)的基本可行解，如存在某個非基變量的檢驗數(shù)為零，有無窮多最優(yōu)解。 仍然用上述實例說明：（ 1）（省略）； （ 2）設 :材料剩余 s1公斤，工時剩余 s2工時，外協(xié)件剩余 s3個。我們可以得到： Max Z = 60 X1 + 30 X2 + 0s1 + 0s2 + 0s3 s . t . 2 X1 + 4 X2 + 1s1 + 0s2 + 0s3 = 320 3 X1 + 1 X2 + 0s1 + 1s2 + 0s3 = 180 2 X1 + 0 X2 + 0s1 + 0s2 + 1s3 = 100 X1 , X2 , s1, s2, s3 = 0 （ 3）求初始解：令 X1 = 0 , X2 = 0 , 可得， s1 = 320 , s2 = 180 , s3 = 100. 這就是一個方案，一個不安排生產的方案。 （ 4）畫出單純形表，如下： 價格 解 量 60 30 0 0 0 向量 向量 向量 X1 X2 s1 s2 s3 0 s1 320 2 4 1 0 0 0 s2 180 3 1 0 1 0 0 s3 100 2 0 0 0 1 檢驗 Z 0 60 30 0 0 0 X1 X2 s1 s2 s3 0 s1 220 0 4 1 0 1 0 s2 30 0 1 0 1 3/2 60 X1 50 1 0 0 0 189。 檢驗 Z 3000 0 30 0 0 30 0 s1 100 0 0 1 4 5 30 X2 30 0 1 0 1 3/2 60 X1 50 1 0 0 0 189。 檢驗 Z 3900 0 0 0 30 15 0 s3 20 0 0 1/5 4/5 1 30 X2 60 0 1 3/10 1/5 0 60 X1 40 1 0 1/10 2/5 0 檢驗 Z 4200 0 0 3 18 0 結論：根據(jù)計算可知： Z = 4200 , X1= 40 , X2 = 60 , S1 = 0 , S2 = 0 , S3 = 20. 即最優(yōu)生產方案是： 甲產品生產 40件； 乙產品生產 60件； 利潤為 4200元。 此時，材料用完，工時用完，外協(xié)件剩余 20個。 說明：如果約束方程中，還有大于等于、等于的情況，將引進人工變量并用“大 M法”求解。 二、運輸問題 運輸問題就是研究物資調運中的供應需求平衡時，如何使運輸成本最低?？梢?，運輸問題本質上是線性規(guī)劃問題。 由于其約束方程全是等式，必須應用“大M法”求解，而且計算量很大（指人工計算）。 為此，介紹一種“表上運算方法”。 實例：某公司有三個生產面包的工廠A1 , A2 , A3；有四個銷售門市部 B1 , B2 , B3 , B4 ，資料如下： B1 B2 B3 B4 產量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 說明： 橙色數(shù)字 表示產銷量（噸 /天）； 綠色數(shù)字 表示運輸費用（百元 /噸） 問題：食品公司應該如何調運，可以使其運輸費用最低？ （ 1）運輸問題解題步驟（表上作業(yè)法）： ?按規(guī)定格式畫出調運表格； ?按“最小元素法”求出“初始調運方案”； ?用“閉回路法”檢驗方案是否最優(yōu)； ?若不是最優(yōu)，則沿“閉回路”方向進行調整； ?重復 4步； ?直到所有“閉回路”所形成的運價的代數(shù)和都大于或等于零為止，此時最優(yōu)解確定。 （ 2）最小元素法：在運輸價格中找出最小的，從此方格對應的產、銷數(shù)量中選擇小的數(shù)填入，為 0 的行（列）者，該行（列）劃掉。若行（列）同時為 0 ，只能劃掉其一。 （ 3）閉回路法：從任何一個空格出發(fā)，見到有運量的方格，才能轉向 90。 ，直到能轉回出發(fā)的空格，形成閉回路。最優(yōu)化檢驗是將閉回路中奇數(shù)轉彎處的運輸價格看成負數(shù)，偶數(shù)轉彎處的運輸價格看成正數(shù)，沿閉回路求其代數(shù)和。代數(shù)和 0 的，不調整；代數(shù)和 = 0 的有多個最優(yōu)解，可不調整；代數(shù)和 0 的，要調整。調整方法是，將奇數(shù)轉彎處的運輸量進行 比較，選擇 最小的運輸量 作為調整依據(jù)，沿著閉回路，將奇數(shù)轉彎處的運輸量 減去 這個最小的運輸量 ；偶數(shù)轉彎處的運輸量 加上 這個 最小的運輸量 ，直到完成所有轉彎處的運算。（上述運算過程，可以簡約成：逢“雙”加，逢“單”減。） （ 4）注意： *運輸問題必須產銷平衡； *填有運輸量的方格數(shù)量，必須滿足 m+n1,以保證實現(xiàn)閉回路。若小于，填 0 占位。 B1 B2 B3 B4 產量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 3 0 1 1 0 4 4 0 3 6 0 3 3 0 3 0 0 3 這個就是初始調運方案，運輸費用 =86百元 =8600元。此方案是否最優(yōu)化？？ 進行最優(yōu)化檢驗： B1 B2 B3 B4 產量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （噸 /天） 4 3 3 1 6 3 ?A2B4— A1B4— A1B3— A2B3。 ?A1B1— A2B1— A2B3— A1B3: ?A3B1A3B4A1B4A1B3A2B3A2B1: ?A3B3— A3B4— A1B4— A1B3: ?A1B2— A3B2— A3B4— A1B4: ?A2B2A3B2A3B4A1B4A1B3A2B3: 閉回路法檢驗表明：紅色線條所形成的“代數(shù)和”小于零，此回路上的運輸量應調整。其余不調整。調整結果如下表 :