生產(chǎn)問題中單純形解法的改進(jìn)

陳曉杰

（中國礦業(yè)大學(xué)理學(xué)院，江蘇徐州 221008）

生產(chǎn)問題中單純形解法的改進(jìn)

陳曉杰

（中國礦業(yè)大學(xué)理學(xué)院，江蘇徐州 221008）

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

單純形法；對偶單純形法；價值系數(shù)；資源系數(shù)；技術(shù)系數(shù)

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

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

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

2 舉例分析

設(shè)一生產(chǎn)資料分配問題的線性規(guī)劃模型的標(biāo)準(zhǔn)型［4］為：

aij稱為技術(shù)系數(shù)，cj稱為價值系數(shù)，bi稱為資源系數(shù).生產(chǎn)問題模型顯然滿足：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〉存在某些技術(shù)系數(shù)aij=0，（1≤i≤m,1≤j≤n）.

2.1 分析〈1〉

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

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

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

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

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

2.1.2 舉例［5］：

設(shè)一線性規(guī)劃問題的標(biāo)準(zhǔn)型為:

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

2.2 分析〈2〉

2.2.1 定義

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

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

2.2.2 舉例

下面有一線性規(guī)劃問題的標(biāo)準(zhǔn)型

由上分析，顯然取x3為進(jìn)基變量，x7為初基變量，基變量為（x5，x6，x3，x8），非基變量為（x1，x2，x4，x7），經(jīng)計算，非基變量檢驗數(shù)為σN=（-3，2，-7，-2），再用單純形法，x2入基，x8出基，基變量變?yōu)椋▁5，x6，x3，x2），非基變量為（x1，x8，x4，x7），非基變量檢驗數(shù)為σN=（-4，-1，-10，-2），B-1b=（2，7，3，8）T，maxz=28.

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

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

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

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

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

[5][美]斯蒂芬·羅賓斯.管理學(xué)[M].黃衛(wèi)偉，譯.北京：中國人民大學(xué)出版社，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—），女，安徽宿州人，中國礦業(yè)大學(xué)理學(xué)院2009級數(shù)學(xué)系運籌學(xué)與控制論專業(yè)研究生.