單純形法步驟

原文地址：快速掌握單純形法

一、標準型

1）目標函數統一為求極大值(或極小值)；

2）所有約束條件（除變量的非負條件外）必須都是等式，約束條件右端常數項(right-hand-side)b_i必須全為非負值；

3）所有變量的取值必須全為非負值。

?下面模型即為標準形式的展開型：

?二、轉化

線性規劃問題往往并非標準形式。

?這個過程包括四個部分的轉換：

1.?目標函數的轉換：

統一求極大值，若是求極小值，則可將下面的式子乘以（-1）。即：

? ? ?轉化為：

2.?變量的轉換：

（1）對于已經是大于等于零的變量 x_j ≥ 0?不做變化；

（2）對于小于等于零的變量 x_j，取負號令其變為大于等于零的變量，即若 x_j ≤ 0，則 定義新變量x_j' = -x_j，x_j' ≥ 0；

（3）若 x_j?取值無約束，可令兩個新的非負變量x_j', ?x_j'', ?然后用x_j = x_j' - x_j''替換原問題中的x_j。

3. 約束條件的右端項常數的轉換：

b_i < 0 時，只需將等式或不等式兩端同乘（-1）；

4. 約束條件的轉換：

將所有不等式全部轉換為等式：

對于“≤ ”型約束加入一個變量 x_s，x_s?≥ 0；

對于“≥ ”型約束則減去一個變量 x_s，x_s?≥ 0。

加到原約束條件中的變量，稱為松弛變量，在實際問題中它表示未被充分利用的資源或缺少的資源，所以在引入模型后它們在目標函數中的系數均為零。

為了構造出初始基變量，約束條件還可能需要加上人工變量。人工變量最終必須等于0才能保持原問題性質不變。為保證人工變量為0，在目標函數中令其系數為M。M為無限大的正數，這是一個懲罰項，倘若人工變量不為零，則目標函數就永遠達不到最優，所以必須將人工變量逐步從基變量中替換出去。如若到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當然亦無最優解。

替換后的結果：

?注：x_4, x_5是將自由變量x_3轉化為非負變量而引入的新變量，x_6, x_7是松弛變量，x_8, x_9是人工變量。

三、矩陣式

矩陣A如下式：

A為m×n矩陣。假設A的秩為m，即假設不存在冗余的約束條件，則m>n（應該是<？）時，因為方程數量比變量數目多，必定有多個可行解，即可利用單純形法來計算最優解。

四、單純形法的算法步驟

1.?確定初始可行基和初始基可行解，

? ? 建立初始單純形表；

2. 最優性檢驗? ??若在當前表的目標函數對應的行中，所有非基變量的系數非正，則可判斷得到最優解（目標值不會再繼續增大，不會出現更優解），可停止計算。否則轉入下一步；

3.?若單純形表中1至m列構成單位矩陣，在j=m+1至n列中，若有某個對應x_k的系數列向量?P_k ≤ 0，則此問題是無界，停止計算。否則，轉入下一步；

4.?挑選目標函數對應行中系數最大的非基變量作為進基變量。假設x_k為進基變量，按θ規則[1]計算，可確定x_l為出基變量，轉下一步；

5.?以a_lk為主元素進行迭代（即用高斯消去法或稱為旋轉運算），把x_k所對應的列向量進行變換[2]；

6. 重復2-5步，直到所有檢驗數非正后終止，得到最優解。

[1] θ規則

其中b_i是當前表中的右手項，a_ik即為在第i個約束中變量k的系數。（找最小值，防止待進基的變量值過大使得出基變量量為負）

[2] x_k列變換

五、例子

對于線性規劃問題：

?

加入松弛變量，轉化為標準形式得：

?

于是我們可以構造單純形表，其中最后一行有星號的列為基變量。初始基可行解為(x_4, x_5, x_6, x_7)。

在單純形表中，我們發現非基變量x的系數大于零，因此可以通過增加這些x的值，來使目標函數增加。

上表中c_2最大，因此我們選擇x_2作為新的基變量。按照θ規則，x_7出基。通過高斯變換得到的新的單純形表為：

繼續計算，我們得到：

此時我們發現，所有非基變量的系數全部非正，即增大任何基變量的值并不能使得目標函數增大。于是我們可以斷定該問題的最優解是z = 32, X = (0, 1, 3, 0, 2, 0, 0).