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

陈晓杰

（中国矿业大学理学院，江苏徐州 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〉情况下……