生产问题中单纯形解法的改进

陈晓杰

（中国矿业大学理学院，江苏徐州 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级数学系运筹学与控制论专业研究生.