具有人工变量的单纯形法计算
发布网友
发布时间：2022-05-10 06:07
共1个回答
热心网友
时间：2022-07-12 18:54
用单纯形法求解线性规划问题时，需要有一个单位矩阵作为初始基，当约束条件都是“≤”时，约束条件标准化后，其松弛变量均为正数，在约束方程组的系数矩阵中，就形成了一个初始基。但是，实际问题中常常出现“≥”或“=”的约束条件，经标准化后，约束方程组系数不存在单位矩阵，因而没有一个现成的初始基本可行解。为了解决此问题，采用人造基的办法，在约束方程中引入非负的人工变量。这种人工变量与前述松弛变量不同，它没有物理意义，仅是为了求解方程方便而引入，所以解的结果必须使这些变量为零，才能保持改变后的问题与原题等价，否则，说明原题无解。
处理人工变量的方法有-M法和两阶段法。
1.-M法
当线性规划数学模型中含有“≥”或“=”的约束方程时，需在其左端加一非负的人工变量yi，构成单位矩阵。但加入yi后的方程，就与原约束方程不等价，所以必须保证在最后的解中，yi=0才能与原约束方程等价。为此，在目标函数式中，给加入的人工变量yi一个很大的系数，对极大问题，系数用-M表示；对极小问题，系数用M表示（M本身为正值）。只有当yi=0时，才能使-Myi=0，目标函数才达到最优化。yi由于具有很大的系数而得到严格的控制，故这个-M称为“惩罚因子”。
当具有“≥”或“=”的约束方程加入人工变量yi后，即可以yi作为初始基本解，按上述单纯形法计算。
2.两阶段法
两阶段单纯形法就是将线性规划问题分两个阶段求解。
第一阶段是判断原线性规划问题是否有解，并寻求一个初始基本可行解。为此，用人工变量的和代替原来的目标函数，构造一个辅助规划，这个辅助规划具有一个单位矩阵，应用单纯形法，使辅助规划的目标函数最小化。若此辅助规划的最优解使其目标函数等于零，则说明没有一个人工变量在基本变量内取值，从而可得到原问题的一个基本可行解，转向第二阶段。否则，如果最小值为正，那么问题就以不存在可行解而结束。
第二阶段是求原问题的最优解。在第一阶段最后单纯形表的基础上，去掉人工变量，然后以第一阶段求得的最优解作为第一个基本可行解，以原问题的目标函数，继续用单纯形法进行迭代，直到求得最优解为止。
