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