| |
| |
2.3 多种产品的生优化决策
由于大多数企业进行的是多种产品的生产和销售，而且企业资源等大多都是有限的，每一种有限资源都将形成对企业生产能力的约束。另外，还要考虑市场需求量限制及其它一些经济指标的要求。这样，决策变量、约束条件将不只是两个而是多个。在这种多产品、多约束条件下，求解确定产品最佳生产组合方案的线性规划问题时，通常采用单纯形法。
(一)线性规划模型的标准形式
在一个线性规划模型中，目标函数是要求实现最大化，约束条件中有的是不小于不等式，有的是不大于不等式，也有的是等式。为了便于求解和分析，先要把各约束条件中的不等式约束化成等式约束的标准形式。具体方法为：在"≤"号约束的方程左边引进一个虚拟的，非负的松驰变量xn+i，或在"≥"号约束的方程左边减去一个虚拟的，非负的剩余变量xn+i， 就可把不等式变成等式。这样，对不等式约束的线性规划模型的求解，就可变成对下面标准形式的线性规划模型的求解：
解上述线性规划问题的基本思路是：
(1)问题的解首先应满足约束方程组。在约束方程组线性无关的前提下， 如果决策变量数等于或小于方程数，则约束方程组只有唯一解或无解。否则，满足约束方程组的解有无穷多个。在所有这些解中，满足目标函数极大化的解即为线性规划问题的解。
(2)约束方程中xj的系数组成系数列向量，其分量数为m，即系数向量是m维向量。因此，选定m个线性无关的决策变量系数向量可作为m维空间的基向量，相应的m个决策变量称为基变量, 当非基变量赋以零值时,这组基变量有唯一解，若均大于或等于零，则称为基本可行解。
(3)基本可行解并不能都保证目标函数极大化，若某一非基变量取大于零的非零值， 这组基变量的值将起变化，取这一非零值的非基变量将转化为基变量，而原有的基变量中的某一个将转化为取值等于零的非基变量，目标函数也随之改变。非基变量取值每增加一个单位，各基变量的取值将相应地减少，总收益也将减少。如果该非基变量增加一个单位的收益大于总收益的减少，则用此非基变量作为基变量是有利的。
(4)由于非基变量增加而引起的各基变量的减小值是不一样的。为了保证基变量取值不小于零,随着非基变量值增大而首先等于零的基变量，可以换出成为非基变量。
(5)经过基变量与非基变量的换进换出后，目标函数值有了增加。如此一直进行到所有非基变量从零增加一个单位，都将使目标函数值减小或不再增加时，就得到了问题的最大化解。
(二)线性规划模型的初始基本可行解
如上所述，在求解线性规划模型开始时必须选定一组基变量，这组基变量的系数列向量是线性无关的，且当非基变量赋零值时而得到的这组基变量值必须不小于零，方可作为基本可行解。然后通过基变量的换出换进，逐步逼近最优解。要确定一组初始基变量，可以考虑选取每个约束方程中引入的虚变量作为基变量。具体地，对于"≤"的约束方程，为使其标准化了而引入了松驰变量，其系数为＋1，即该松驰变量的系数列向量是单位向量， 可以选作为初始基变量；对于已是"＝"约束的标准化方程，直接加上一个人工变量，其系数也为＋1， 即该人工变量的系数列向量也是单位向量，可以作为基变量，在求取目标函数最大化的表达式中，给定此变量的系数是一个充分小的数-M，(M为充分大的正值)，这样，人工变量目标函数的负效应贡献使它不可能进入最优解；对于"≥"的约束方程，为使其标准化而引入了剩余变量，其系数为－1，不能满足可行性约束条件，所以，可以考虑在加上一个系数为＋1的人工变量，作为基变量，在目标函数中作与"＝"约束时的处理方法一样， 给定一个充分小的-M作为这一人工变量的系数。这样，可以很容易地得到一个由m个单位列向量构成的m维空间矩阵， 与各系数＋1对应的决策变量即为初始基变量。
约束方程组经过上述处理后，不失一般性，可以写成下列形式：
式中，xn’+1、xn’+2、…xn’+m即为初始基变量，它们的取值分别为：xn’+1=b1
xn’+2=b2, …xn’+I=bi…xn’+m=Qj，即为初始基本可行解。
[例4－2－2] 设有线性规划模型形如：
试确定该线性规划模型的初始基本可行解。
解：引进剩余变量x3和松驰变量x4，先将约束条件化成均为"＝"约束的标准形式，如下所示：
然后，再在第一个方程中加入人工变量x5，在第二个方程中加入人工变量x6，而在第三个方程中因x4是引入的松驰变量，系数已经为＋1，所以不必再加入其它新变量。 由此，约束条件方程组转化为：
式中，x4、x5、x6即为初始基变量，它们的取值分别为x4=3，x5=3和x6=6， 即为初始基本可行解。初始基变量对应的系数列向量构成一个三维空间矩阵。通常，为分析上的方便，将x4改为x7。引入剩余变量、松弛变量和人工变量后，目标函数也要作相应的修改，最后的形式为：
(三)线性规划模型最优解的求解方法
运用单纯形法求取模型最优解的原理， 是先列出初始单纯形表， 然后根据解题的基本思路，用最优性条件判断目标函数是否还有改进的可能。如果还能改进的话，则选取能使目标函数有最大改进的非基变量作为换入变量，再用可行性条件， 选出被替换后能使各xj都不小于0的基变量作为换出变量，并使换入变量列与换出变量行交叉系数为+1，进而通过迭代消去单纯形表中除换入变量列与换出变量行交叉系数外这一列的其它所有系数。这样，一次变换即算完成，此时已经求得使目标函数有所改进的另一个基本可行解。
依次下去，一直进行到目标函数f(x)中不再有能改进其函数值的非基变量为止， 这时的基本可行解即为最优解，相应的f(x)函数就为最优值。具体求解过程如下：
（1）列出初始单纯形表
对例4－2－2的线性规划模型，已经转化成含有初始基变量的形式， 形成单纯形初始解表的格式如表4－2－4所示。
表4-2-4 求解线性规划模型的单纯形初始解表
| 基变量 |
f(x) |
x1 x2 x3 |
x5 x6 x7 |
解 |
| f(x) |
(0) |
-4 -1 0 |
M M 0 |
0 |
x5
x6
x7
|
|
3 1 0
4 3 -1
1 2 0 |
1 0 0
0 1 0
0 0 1
|
3
6
3 |
表中，目标函数中各变量的价值系数都改变了符号，这相当于将原目标函数等号右边的方程移到了左边。这样,在单纯形表的迭代过程中,当基变量为某一确定的值， 同时又要消去该变量所在列的f(x)方程中系数时,右端的值即为此时的目标函数值。例如，在初始单纯形表中, x5、x6、x7为基变量， 这时应消去f(x)方程中x5和x6的系数M,使对应于x5、x6的列中除行列交叉处的系数为＋1外其余均为0，则只要把对应于x5的第一个约束方程和对应于x6的第二个约束方程各乘以（-M）加到目标函数行即可。迭代后的表格为：
| 基变量 |
f(x) |
x1 x2 x3 |
x5 x6 x7 |
解 |
| f(x) |
(0) |
-4-7M -1-4M +M |
M M 0 |
0 |
x5
x6
x7
|
|
3 1 0
4 3 -1
1 2 0 |
1 0 0
0 1 0
0 0 1
|
3
6
3 |
即当基变量x5=3、x6=6、x7=3时，f(x)=-9M。这张表仍作为初始单纯形表，为求解目标函数最大化运算作好了准备。
（2）确定换入变量
初始单纯形表列出后，可根据最优性条件从非基变量中确定出一个换入变量。对求最大化（最小化）的线性规划模型而言，最优性条件是指从单纯形表的f(x)方程中选取一个具有正(负)的最多的系数的变量作为换入变量，这相当于在原f(x)方程中选取一个具有正(负)的最多的系数的变量作为换入变量，若有几个变量系数相同时，则可任选其中的一个。 如在f(x)方程中再也找不出具有负（正）的系数的变量时，即已取得了最优解，求解过程结束。在上例中是求最大值，初始单纯形表内f(x)方程中
的系数（-4-7M）负的最多，所以，x1作为换入变量。
（3）确定换出变量
换入变量确定后，可再根据可行性条件从基变量中确定出一个换出变量。无论是求最大化的线性规划模型还是最小化的线性规划模型，可行性条件都是先求出单纯形表中解的列向量的各个分量与换入变量的约束系数列向量中大于0的对应分量比值， 然后再将对应于最小比值的基变量作为换出变量；若有几个比值相同时，则可任选其中的一个。 在上表中，解x5、x6和x7的列向量的各个分量分别为3、6和3，与换入变量
的约束系数列向量中大于0的对应分量3、4和1之比分别为1、1.5和3，其中，对应于基变量x5的比值最小，所以，x5作为换出变量。
（4）单纯形表的迭代
换入换出变量确定后，则在单纯形表中对应于换出变量的方程称为主方程。主方程中对应于换入变量的系数称为主元。如主元不等于1时，可将主方程除以主元，使其转化为1。然后，再用消元法消去换入变量系数列向量中除主元外的所有其它元素，使它们变为0。 这样，也就完成了一次迭代。
（5）确定最优解
一次迭代完成后，可用最优性条件对单纯形表中f(x)方程进行检验。如果在f(x)方程中，仍存在着负（正）的系数，则可重复从（2）开始的计算过程，直到f(x)方程中所有的系数都不小于（不大于）0时为止。这时，即已取得了最优解，求解过程结束。对前例4－2－2模型的全部运算过程如表4－2－5所示。
表4-2-5 单纯形法的运算过程
经过两次迭代后，单纯形表中f(x)方程的所有变量系数均已不小于0，所以，此时的模型已经取得最优解，组成了一个最佳产品生产组合方案，其值分别为x1*=3/5和x2*=6/5， 最优解f*(x)=18/5。
含有更多决策变量的线性规划模型求解过程与此相同。
|
|
|
1.1