割平面法编程.doc

云南大学数学与统计学实验教学中心实验报告 第 PAGE 6 页 共 NUMPAGES 14 页 云南大学数学与统计学实验教学中心实验报告 第 PAGE 1 页 共 NUMPAGES 2 页 云南大学数学与统计学实验教学中心 实 验 报 告 课程名称：运筹学实验 学期：2012~2013学年第二学期 成绩： 指导教师：葛瑜 学生姓名：卢富毓 学生学号：20101910072 实验名称：割平面法编程 实验要求： 必做 实验学时：2学时 实验编号：04 实验日期： 2013/4/4 完成日期：2013/4/17 学院： 数学与统计学院 专业 ： 信息与计算科学 年级： 2010级 一、实验目的 编程实现割平面整数线性规划问题，加深对割平面法以及单纯形法的理解和掌握 二、实验环境 VS2010（C++） 三、实验内容 在对偶单纯形的基础上，考虑x 的不可分性，也就是不能为小数。这样就需要我们在求的最优解得基础上，保证x的取值为整数。 经过学习，有两种方法可以用来求解：分支定界法，以及割平面法。 割平面法就是通过一定的约束，将非整数解割去，在其凸边上得到相应的整数解。 首先不考虑变量xi是整数这一条件，但是增加线性约束条件（称为割平面），使得原来可行解区域切去一部分，但没有切去任何整数可行解。该方法是指出怎样找到适当的割平面，使得切割后得到可行解区域的某顶点（称极点，对应基本可行解）恰好是整数线性规划问题的最优解 四、实验过程 A、割平面法的算法思想（课本割平面法部分由具体算法P121） 给定整数线性规划（ILP）的实例，用原始单纯形算法解决ILP的松弛线性规划（LP），得到LP的最优基本可行解x，其基为B，最后单纯形表中的第i个方程为（i=1,2,…,m) xi + ∑k aik xk = bi (5.1) 由于方程5.1中的变量是非负的，则 ∑k [aik]xk ≤∑k aik xk (5.2) 从而方程(5.1)可变为 xi + ∑k [aik]xk ≤bi （5.3 因为在ILP中x的限制为整数，从而(5.3)的左边为整数，进而(5.3)的右边也为整数，于是得到 xi + ∑k [aik]xk ≤ [bi] (5.4) 用(5.1)减去(5.4)，得到 ∑k（aik - [aik]）xk ≥ bi - [bi] (5.5) 令fik=aik - [aik]和 fi=bi - [bi]，这里fik（fi）称为aik （bi）小数部分，满足 0 ≤fik 1 和 0 ≤fi 1 (5.6) 从而由(5.5)和 (5.6)得到下面的式子然后再按照原单纯形算法经行求解。重复上述步骤。 直到得到的解为整数。才停止运算。 B、编译运行程序，输入约束方程的系数矩阵A，常矩阵B,价值系数C,得到最优解 为了保证得到的算法能求得解，并且求的的最优解是对的。这里选取了P118页的例题3。 约束条件 整理化简后，得到初始表如下： Cj 1 1 0 0 CB XB b x1 x2 x3 x4 0 x3 1 -1 1 1 0 0 x4 4 3 1 0 1 D、运行结果如下图： 1）代数上述表中的值： a、初始化后的结果：这时候，它是按照对偶单纯形来求解的 b、对偶单纯形优化后的结果： 得到最优解，但是此时得到的解为小数而非整数解 c、运用割平面法经行优化改进 割平面法添加条件后出事后以及第一次优化的结果 割平面法的第二次第三次优化： d、最后得到的结果： 最后得到的结果与书上例题所有的结果完全吻合。所以所编写的算法为割平面法。 五、实验总结 通过对割平面算法编程进一步加强了对本章知识的掌握，当然这不局限于割平面法，对分支定界法也有进一步的了解。 六、源代码 这里需要说明的是。这个算法是在对偶单纯形算法的基础上修来得来的。 源代码如下： #includeiostream #includeiomanip using namespace std; #define M -10000 class DanChun{ public: double A[100][120],B[30]; //创建一个二维数组，用来存储xi值以及b的