生產問題中單純形解法的改進

陳曉杰

（中國礦業大學理學院，江蘇徐州 221008）

生產問題中單純形解法的改進

陳曉杰

（中國礦業大學理學院，江蘇徐州 221008）

闡述了單純形法和對偶單純形法的思想與一般解法，在生產問題的線性規劃模型中，利用價值系數，資源系數，技術系數的一些關系和對非基變量檢驗數產生的影響，通過一些特定變量的進出基運算，使得單純形法的一般求解步驟減少，運算得到簡化.

單純形法；對偶單純形法；價值系數；資源系數；技術系數

1 單純形法與對偶單純形法

單純形法解決線性規劃問題的思想是：從一個基解X0，X0是基可行解且X0的非基變量檢驗數σj不全非正，開始迭代到另一個基解X1，在迭代過程中保持基解的可行性，直到得到的基可行解Xt的非基變量的檢驗數全部非正，則得到的Xt就是線性規劃問題的最優解［1,2］.

對偶單純形法正是基于對稱的想法，從一個基解X0開始，X0不是基可行解，但它的檢驗數全部非正，即它對應的對偶問題的基解Y0=CBB-1是基可行解；從X0迭代到另一個基解X1，在迭代過程中保持它們對應的對偶問題的基解是基可行解，逐步消除原問題基解的不可行性，最終達到兩者同時為可行解時，也就同時是最優解了［3］.這就是對偶單純形法的基本思想.

2 舉例分析

設一生產資料分配問題的線性規劃模型的標準型［4］為：

aij稱為技術系數，cj稱為價值系數，bi稱為資源系數.生產問題模型顯然滿足：aij≥0,cj＞0,bi＞0，（1≤i≤m,1≤j≤n），下面分兩種情況討論.

〈1〉所有aij＞0,cj＞0,bi＞0，（1≤i≤m,1≤j≤n）；〈2〉存在某些技術系數aij=0，（1≤i≤m,1≤j≤n）.

2.1 分析〈1〉

在〈1〉情況下，若選擇xk為換入變量，xn+l為換出變量，由第l行我們有：

定義2在〈1〉的條件下，稱（1）中每一行的一類變量對應的資源系數與此行一類變量的技術系數比值為一類比值.

定義3在〈1〉的條件下，稱（1）中每個非基變量所在列對應的資源系數與技術系數比值中最小的為此列的一類最小比值.

解決〈1〉情況下的線性規劃問題的步驟是：

STEP1：依次找出每行是一類變量和一類比值；

2.1.2 舉例［5］：

設一線性規劃問題的標準型為:

27便可得到最優解，進出基之后得最后結果基變量為(x5,x6,x2,x8)，非基變量為(x1,x3,x4,x7)，非基變量檢驗數為σN=(-3,-2,-7,-2)，B-1b=(2,7,3,10)，maxz=6.

2.2 分析〈2〉

2.2.1 定義

定義5在〈2〉的條件下，稱每一行的二類變量對應的資源系數與此行二類變量的技術系數比值為二類比值.

定義6在〈2〉的條件下，排除非基變量系數為0的情況，稱每個非基變量所在列對應的資源系數與技術系數比值中最小的為二類最小比值.

2.2.2 舉例

下面有一線性規劃問題的標準型

由上分析，顯然取x3為進基變量，x7為初基變量，基變量為（x5，x6，x3，x8），非基變量為（x1，x2，x4，x7），經計算，非基變量檢驗數為σN=（-3，2，-7，-2），再用單純形法，x2入基，x8出基，基變量變為（x5，x6，x3，x2），非基變量為（x1，x8，x4，x7），非基變量檢驗數為σN=（-4，-1，-10，-2），B-1b=（2，7，3，8）T，maxz=28.

上述方法求解線性規劃問題，減少了計算步驟和計算量，在生產問題中具有實用性.

[1]錢正英，張光斗.中國可持續發展水資源戰略研究綜合報告及各專題報告[M].北京：中國水利水電出版社，2009：5-67.

[2]錢頌迪.運籌學[M].北京：清華大學出版社，1990：1-99.

[3]薛秀謙.運籌學[M].徐州：中國礦業大學出版社，2001：1-116.

[4]張瑩.運籌學基礎[M].北京：清華大學出版社，1994：1-62.

[5][美]斯蒂芬·羅賓斯.管理學[M].黃衛偉，譯.北京：中國人民大學出版社，1997：1-90.

The Improvement of Simplex Method in Production Problem

CHEN Xiao-jie
(School of Science,China University of Mining and Technology,Xuzhou 221008,China)

This paper expounds the simplex method and dual simplex method thought and the general solution, in the production question's linear programming model,by using the value coefficient,the resources coefficient, technology coefficient's relations and the influence on the non-base variable test number.Through the opera?tions of getting in and out of some specific variable base,steps of the simplex method can be reduced and opera?tions can be simplified.

simplex method;dual simplex method;value coefficient;resources coefficient;technology coefficient

O221.1

A

1008-2794（2011）08-0039-04

2011-06-10

陳曉杰（1987—），女，安徽宿州人，中國礦業大學理學院2009級數學系運籌學與控制論專業研究生.