《运筹学-大M法或两阶段法的上机实验.pdf》由会员分享，可在线阅读，更多相关《运筹学-大M法或两阶段法的上机实验.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实 验 报 告实验课程名称实验课程名称运运筹筹学学实验项目实验项目名称 大大 M M 法或两阶段法的上机实验法或两阶段法的上机实验年年级级专专业业学学 生生学学号号0000 学学 院院实验时间：实验时间：年月 日学姓名号指导教实 验 时 间师实验项目名称大 M 法或两阶段法的上机实验实验组成绩实验目的及要求实验目的及要求：实验目的：实验目的：1.学会用 Tora 软件或 Lindo 软件求解线性规划问题，2.理解每一步迭代计算中进基与出基变量等，了解大 M 法或两段法的上机实验。实验要求：实验要求：完成作业 P97 页第 6 题及第 7 题4。实验或算法原理：实验或算法原理：1.1.大大 M
2、M 法思路：法思路：在单纯形法的基础上，为了使解线性规划有一个统一的解法，我们把所有求目标函数最小值的问题化为求目标函数最大值的问题。只要把目标函数乘以-1，就可以把原来求目标函数最小值的问题化为求目标函数最大值问题。为了找到一个满足条件的单位向量非负，就需要加人工变量，注意人工变量与松弛变量和剩余变量是不同的，松弛变量和人工变量可以取零值也可以取正值，而人工变量只可以取零值，否则就会不等价。我们规定人工变量在目标函数中的系数为-M，M 为任意大的数，这样只要人工变量大于零，所求的目标函数就是一个任意小的数，为了使目标函数最大，就必须将人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基
3、变量中换出，也就是说人工变量仍不为零，则该问题无可行解。像这样，为了构造初始可行基得到初始可行解，把人工变量”强行”的加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大的目标函数里的系数为-M 的方法叫做大 M 法，M 叫做罚因子。12.2.两阶段法原理：两阶段法原理：两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两阶段求解。第一阶段：要判断原线性规划问题是否有基本可行解，保持线性规划问题的约束条件原线性规划问题一样，而目标是求人工变量的相反数之和的最大值，如果此值大于零，即说明不存在使所有人工变量都为零的可行解，即原问题无可行
4、解，因停止计算。如果此值为零，即说明存在一个可行解使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量都是非基变量取消，将目标函数换为原来的目标函数，把此可行解作为初始解进行计算，接下来的计算和单纯形法计算原理是一样的。实验硬件及软件平台实验硬件及软件平台：PC 机，Tora 软件，Internet 网。实验步骤实验步骤：大大 M M 法步骤：法步骤：1.打开 TORA 命令窗口；2.选择 Linear programming-Select input mode-Go to input screen;3.输入待解的方程组-Slolve menu-Solve problem-
5、Algebraic-Iterations-M-method-输入值-点击 Go 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
6、-Iterations-Two-phase method-点击 Go To Output Format Screen-点击 All lterations；4)得出运行结果。2实验内容包括实验具体内容、算法分析、源代码等等实验内容包括实验具体内容、算法分析、源代码等等：1.书上书上 P97P97 页第页第 6 6 题：题：用大 M 法和两阶段法求解以下线性规划问题。max z=5x1 x23x3；约束条件：x1 4x2 2x310，x1-2x2 x316.A A：大：大 M M 法法3由上面的结果可知，满足所求出的j0，得出目标函数的最优解 x1=16，x2=0，x3=0，sx4=16，Rx5=
7、0，sx=0，最优值是 80。当把 M 的值改为 100000 后，值还是一样的，这样就可以得出当 M 为 100 时，已经得出有效解。4B B：两阶段法：两阶段法5图图 1.31.3由图 1.3 可知，先进行线性规划的第一阶段，满足j0，且 z 值为零，即说明存在一个可行解使得所有的人工变量都为零，此时 x2=2.5，sx6=21，其余为 0 得出 z=0。接下来进行第二阶段，令 z=5x1+x2+3x3-0sx4+0Rx5+0sx6，和大M 的分析方法一样，最终将得到满足j0时到达最优解：当 x1=16，x2=0，x3=0，sx4=6，Rx5=0，sx6=0，最优值为 80。2.2.书上书
8、上 P97P97 页第页第 7 7 题题4 4大 M 法和两阶段法求解以下线性规划问题。max z=2x1x2x3；约束条件：4x1 2x2 2x3 4，2x14x2 20，4x18x22x316，A A：大：大 M M 法法6由上面的图2.1 可知，首先先输入数据即线性规划的系数如图2.1 所示令 maxz=2x1 x2 x3-0sx4+0sx6+0sx7-MRx5；进行下一次迭代，以同样的方法一直下去，直到所求出的j 0为止，就可以得出目标函数的最优解：x1=4，sx4=12，sx6=12，其余为 0 时，最优值为8。当把 M 的值改为 100000 后，值还是一样的，这样就可以得出当M为
9、 100 时，已经得出有效解。7B B：两阶段法：两阶段法8由图 2.3 可知，先进行线性规划的第一阶段，z=0 x1+0 x2+0 x3+0sx4-Rx5+0sx6，通过迭代，满足j0，且 z 值为零，即说明存在一个可行解使得所有的人工变量都为零，此时 x1=1，sx6=18，sx7=12，其余为 0，得出 z=0。接下来进行第二阶段，令z=2x1+x2+1x3+0sx4+0Rx5+0sx6+0sx7，和大 M 的分析方法一样，最终将得到满足j0时到达最优解：当 x1=4，x2=0，x3=0，sx4=12，Rx5=0，sx6=12，最优值为 8。9实验结果与讨论实验结果与讨论：1.首先找出一个初始基本可行解，然后进行最优性检验，基变化的步骤，最后得到结果。同时学会了用 Tora 软件求解线性规划问题，并在求解过程中学会理解每一步迭代计算中进基与出基变量。2.为了构造初始可行基得到初始可行解，把人工变量”强行”的加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来就令人工变量在求最大的目标函数里的系数为-M 的方法叫做大 M 法。大 M 法以及另一种应用人工变量的方法即两阶段法的求解，更加完善了有关线性规划问题的解决，同时给生活中很多相似问题的解决提供了方便。指导教师意见指导教师意见：签名：签名：年年月月日日10