陈晓杰 (中国矿业大学理学院，江苏 徐州 221002)

对偶单纯形法在生产资料分配问题中的应用

陈晓杰 (中国矿业大学理学院，江苏 徐州 221002)

阐述了单纯形法和对偶单纯形法的基本思想，并应用对偶单纯形法解决了生产资料分配问题。

单纯形法；对偶单纯形法；生产资料分配

1 单纯形法和对偶单纯形法的基本思想

给出一个线性规划问题：

(1)

其对偶问题是：

(2)

单纯形法解决线性规划问题的思想是：从问题(1)的一个基解X0开始迭代到另一个基解，在迭代过程中保持基解的可行性，同时它对应的对偶问题(2)的基解Y0=CBB-1的不可行性逐步消失，直到Y0是对偶问题(2)的可行解时，X0就是问题(1)的最优解了[1-2]。

对偶单纯形法正是基于对称的想法，从一个基解X0开始，X0不是基可行解，但它的检验数全部非正，即它对应的对偶问题的基解Y0=CBB-1是基可行解；从X0迭代到另一个基解X1，在迭代过程中保持它们对应的对偶问题的基解是基可行解，逐步消除原问题基解的不可行性，最终达到两者同时为可行解时，也就同时是最优解了。这就是对偶单纯形法的基本思想[1-2]。

2 生产问题的线性规划模型

设一生产问题的线性规划模型是:

maxz=c1x1+c2x2+…+cnxn

(3)

生产问题中显然价值系数c1,c2,…,cngt;0，技术系数a11,…,a1n,…,am1,…,amn≥0，资源系数b1,b2,…,bm≥0[3]。

定义1 线性规划问题(3)中满足：

则xi称为定基元素。

线性规划问题(3)的标准形为：

maxz=c1x1+c2x2+…+cnxn

(4)

定理1 线性规划问题(3)的标准形(4)中，用定基变量xi替换xn+1,…,xn+m的某一元素必得到至少一组该线性规划问题的基变量，且基变量中有至少一组对应的基解是正则解。……