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

实验报告实验课程名称的运营学实验项目名大m法或二阶段法的上位实验学年专家学生姓名取得学位00学院实验时间：年月日姓名取得学位实验组实验时间指导教师成绩实验项目名称大m法或两步法的上机实验实验的目的和要求：实验目的：学会了用Tora软件和Lindo软件解线性规划问题2 .理解在每一步的迭代计算中的基和外基变量等，并且了解最大m法或两步法的高级实验。实验要求：作业P97页完成第六题及第七题(4)。实验(或算法)原理：1 .大m法的想法：基于单纯形法，为了使解线性规划具有统一的解法，求目标函数的最小值的问题都成为求目标函数的最大值的问题。 只要将目标函数乘以-1，就能够将原本求出目标函数最小值的问题作为求出目标函数的最大值的问题。 要查找满足条件的单位向量(非负向量)，必须添加人工变量。 请注意，人工变量、松弛变量和剩馀变量是不同的。 缓和变量和人工变量可以取零值，也可以取正值，但人工变量只能取零值。 不这样做是不等价的。 我们将人工变量的目标函数中的系数设为-M，m是任意大的数，如果人工变量大于0，则求出的目标函数是任意小的数，为了使目标函数达到最大，将人工变量设为替换为基变量。 到最后，人工变量不能由基变量替换。 换句话说，它是人工变量还不是零，这个问题就解决不了。 这样，为了构筑初始可执行基底并得到初始可执行解，将人工变量“强制”加入原来的制约方程式，为了尽可能地将人工变量从基底变量置换，求最大目标函数的系数为-M的方法称为大m法，将m称为罚因子。2 .两步法原理：二阶段法是处理人工变量的另一种方法，将添加了人工变量的线性规划问题分为两个阶段来解决。 第一阶段：确定原始线性规划问题是否存在基本可能的解，维持线性规划问题的约束条件，与原始线性规划问题相同，目标是求人工变量的反对数之和的最大值，如果该值大于零，则不存在可能将所有人工变量归零的解，即原始问题可能的解如果此值为零，则表示存在所有人工变量都可能为零的解。 第二阶段：取消第一阶段的最终单纯形表中的人工变量(全部为非基变量)，用原始目标函数替换目标函数，计算该可能解作为初始解，以下计算与单纯形法的计算原理相同。实验硬件和软件平台：PC、Tora软件和互联网。实验步骤：大m法步骤：打开TORA命令窗口2 .选择线性编程- selectinputmode-gotoinputscreen3 .输入求解方程式- slolvemenu-solveproroblem-algebraic-iterations- m-method-输入值- gotooutputformatscreen- gotooutputscreen- allteration4 .发出驾驶结果。5 .改变第三步骤中的值(例如，100改变为100000 )，然后执行该步骤以获得结果。6 .观察比较结果。两步法步骤：打开TORA命令窗口2 )选择线性编程- selectinputmode-gotoinputscreen3 )输入要求解的方程式- slolvemenu-solveproblem-algebraic-iterations- two-phase method- gotofutputformatscreen- allterations；4 )出现驾驶结果。实验内容，包括实验的具体内容、算法分析、源代码等；1 .书的P97页第6题：用大m法和二阶段法解决以下线性规划问题。max z=5约束条件：a :大m法图1.1图1.2根据以上结果可知，满足求出的目标函数的最佳解x1=16、x2=0、x3=0、sx4=16、Rx5=0、sx=0，最佳值为80。 即使m的值被改为100000，当m为100时仍然相同并且得到有效的解。b :两阶段法图1.3如从图1.3显而易见，先行于线性规划的第一阶段，令人满意且z值为零指示存在可能的解，使得所有人工变量为零，其中x2=2.5，sx6=21，并且在该馀数为零时获得z=0。 接着，进行第二阶段，设为z=5x1 x2 3x3-0sx4 0Rx5 0sx6，与m的分析方法同样，最终设为x1=16、x2=0、x3=0、sx4=6、Rx5=0、sx6=0、最佳值为80 .2 .本书P97页第7题(4)大m法和二阶段法解决以下线性规划问题。max z=约束条件：a :大m法图2.1图2.2根据以上的图2.1，首先进行将作为输入数据的线性规划的系数设为图2.1所示的maxz=-0sx40sx6-mrx5的下一次反复，直到求出为止用相同的方法继续，能够得到目标函数的最佳解： x1=4、sx4=12、sx6=12，在其馀数为0的情况下，最佳值为即使m的值被改为100000，当m为100时仍然相同并且得到有效的解。b :两阶段法图2.3如从图2.3可见，先执行线性规划的第一阶段，其中z=0x1-0x20 x3-0sx4- rx5-0sx 6经过迭代满足，指示z值为零(即，存在可能的解)且所有人工变量为零。 此时，x1=1，sx6=18，sx7=12，其馀为零，从而获得z=0。 接下来是第二阶段与最大m分析方法类似，z=2x1 x2 1x3 0sx4 0Rx5 0sx6 0sx7最终具有x1=4、x2=0、x3=0、sx4=12、Rx5=0、sx6=12和最佳值8。实验结果和讨论：1 .首先找出初步的基本可行解，进行了最优性检测、基础变化程序，最后得出了结果。 同时，学会了使用Tora软件求解线性规划问题，在求解过程中学会了解各步迭代计算中的基础和基础变量。2 .为了构筑初始可执行基，得到初始可执行解，将人工变量“强制”加入原来的制约方