运筹学-大M法或两阶段法的上机试验

1、运筹学 - 大 M 法或两阶段法的上 机实验实验报告实验课程名称 运 筹 学实验项目名称 大 M法或两阶段法的上机实验年级专业学生姓名学号00 学 院实验时间：实验项目名称大 M法或两阶段法的上机实验姓学实 验名号组实 时验 间指 导 教 师成 绩实验目的及要求 ：实验目的：1. 学会用 Tora 软件或 Lindo 软件求解线性规划问题，2. 理解每一步迭代计算中进基与出基变量等，了解大 M 法或两段法的上机实验。 实验要求：完成作业 P97页第 6 题及第 7 题（4）。实验（或算法）原理：1. 大 M法思路： 在单纯形法的基础上，为了使解线性规划有一个统一的解法，我们把所有求目标函 数最

2、小值的问题化为求目标函数最大值的问题。 只要把目标函数乘以 -1 ，就可以把原来 求目标函数最小值的问题化为求目标函数最大值问题。 为了找到一个满足条件的单位向 量（非负），就需要加人工变量，注意人工变量与松弛变量和剩余变量是不同的，松弛 变量和人工变量可以取零值也可以取正值， 而人工变量只可以取零值， 否则就会不等价。 我们规定人工变量在目标函数中的系数为 -M，M为任意大的数，这样只要人工变量大于 零，所求的目标函数就是一个任意小的数，为了使目标函数最大，就必须将人工变量从 基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量 仍不为零，则该问题无可行解。像这样，为

3、了构造初始可行基得到初始可行解，把人工 变量”强行”的加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出 来就令人工变量在求最大的目标函数里的系数为 -M 的方法叫做大 M法，M叫做罚因子。2. 两阶段法原理：两阶段法是处理人工变量的另一种方法， 这种方法是将加入人工变量后的线性规划 问题分两阶段求解。第一阶段：要判断原线性规划问题是否有基本可行解，保持线性规 划问题的约束条件原线性规划问题一样，而目标是求人工变量的相反数之和的最大值， 如果此值大于零，即说明不存在使所有人工变量都为零的可行解，即原问题无可行解， 因停止计算。如果此值为零，即说明存在一个可行解使得所有的人工变量都为

4、零。第二 阶段：将第一阶段的最终单纯形表中的人工变量（都是非基变量）取消，将目标函数换 为原来的目标函数， 把此可行解作为初始解进行计算， 接下来的计算和单纯形法计算原 理是一样的。实验硬件及软件平台 ：PC 机， Tora 软件， Internet 网。实验步骤 ：大 M法步骤：1. 打开 TORA命令窗口；2. 选择 Linear programming-Select input mode-Go to input screen;3. 输入待解的方程组 - Slolve menu -Solve problem-Algebraic-Iterations-M-method-输入值 - 点击 Go

5、 To Output Format Screen- 点击 Go To Output Screen- 点击 All lterations。4. 得出运行结果。5. 改变 3 步骤中的值（例 100 改为 100000），再按之后的步骤运行，得出结果。6. 观察对比结果。 两阶段法步骤：1）打开 TORA命令窗口；2）选择 Linear programming-Select input mode-Go to input screen；3）输入待解的方程组 - Slolve menu -Solve problem-Algebraic-Iterations-Two-phase method- 点击 G

6、o To Output Format Screen- 点击 All lterations ；4）得出运行结果。实验内容（包括实验具体内容、 算法分析、 源代码等等）：1.书上 P97页第 6题：用大 M法和两阶段法求解下列线性规划问题。max z=5x1 x 2 3x3；约束条件： x1 4x 2 2x3 10 ，x1 -2x2 x3 16.A：大 M法图 1.1由上面的结果可知，x3=0，sx4=16，Rx5=0，的，这样就可以得出当图 1.2满足所求出的 j 0 ，得出目标函数的最优解 x1=16，x2=0， sx=0，最优值是 80。当把 M的值改为 100000 后，值还是一样 M为

7、100 时，已经得出有效解。B：两阶段法6图 2.1图 2.2由上面的图 2.1 可知，首先先输入数据即线性规划的系数如图 2.1 所示令 max z=2x1 x 2 x3-0sx4+0sx6+0sx7-MRx5； 进行下一次迭代，以同样的方法一直下去，直 到所求出的 j 0为止 ，就可以得出目标函数的最优解： x1=4， sx4=12，sx6=12，其余 为 0 时，最优值为 8 。当把 M的值改为 100000 后，值还是一样的，这样就可以得出当 M 为 100 时，已经得出有效解。B：两阶段法图 2.39由图 2.3 可知，先进行线性规划的第一阶段， z=0x1+0x2+0x3+0sx4

8、-Rx5+0sx6， 通 过迭代，满足 j 0，且 z值为零，即说明存在一个可行解使得所有的人工变量都为零， 此时 x1=1，sx6=18， sx7=12，其余为 0，得出 z=0。接下来进行第二阶段，令 z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7，和大 M 的分析方法一样， 最终将得到满足 j 0 时达到最优解：当 x1=4，x2=0，x3=0，sx4=12，Rx5=0，sx6=12，最优值为 8。10实验结果与讨论 ：1. 首先找出一个初始基本可行解，然后进行最优性检验，基变化的步骤，最后得到 结果。同时学会了用 Tora 软件求解线性规划问题，并在求解过程中学会理解每一步迭 代计算中进基与出基变量。2. 为了构造初始可行基得到初始可行解， 把人工变量”强行” 的加到原来的约束方程 中去，又为了尽力地把人工变