对偶单纯形法编程

《对偶单纯形法编程》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、云南大学数学与统计学实验教学中心实验报告云南大学数学与统计学实验教学中心实验报告课程名称：运筹学实验学期：2012~2013学年第二学期成绩：指导教师：葛瑜学生姓名：卢富毓学生学号：20101910072实验名称：对偶单纯形法编程实验要求：必做实验学时：2学时实验编号：02实验日期：2013/3/8完成日期：2013/3/11学院：数学与统计学院专业：信息与计算科学年级：2010级一、实验目的编程实现对偶（改进）单纯形法求解线性规划问题，加深对单纯形法的理解和掌握二、实验环境VS2010（C++）三、实验内容改进单纯形法的实验：由于在一些情况下，当检验数Cj-Zj都小于零后了，

2、但是其b的值却存在有负数了。这样的话，x中就会存在负值，这样与约束条件中xi>0，就不符合。所以需要对单纯形法改进，得到对偶单纯形法。四、实验过程A、对偶单纯形法的算法思想1.先用单纯形法计算，当检验数都为非正后，检查b是否有存在负值，若是有则使用对偶单纯形法。2.确定换出量，找到b中为负值的最小值。确定对应的xi的换出。3.再对单纯形表中的xi所在行的各系数进行检查，若所有Aij都大于零，则表示无可行解。若存在Aij小于零，则计算，找到其所换入的列以保证的到的对偶问题仍有可行解。4.然后再按照原单纯形算法经行求解。重复上述步骤。B、编译运行程序，输入约束方程的系数矩阵A，常矩

3、阵B,价值系数C,得到最优解为了保证得到的算法既能对特殊情形（有bi<0）的情况下能求解，也能对一般的问题求解。这里给出了一下两组数据。1、上一个实验报告中的求解的数据。B=[2;14;2];X=[3-420-5500]第10页共10页云南大学数学与统计学实验教学中心实验报告2、参照课本P62例题6中的2-6表给出的数据X=[-2-3-400]D、运行结果如下图：1）下图表示的是第一个数据带入后得到的结果。表示对偶单纯形法对一般的数据成立2）下图表示的对偶单纯形法对b中存在负值时纠正的结果：a、初始化后的结果：第10页共10页云南大学数学与统计学实验教学中心实验报告b、优化后的

4、结果：c、最后得到的结果：第10页共10页云南大学数学与统计学实验教学中心实验报告最后得到的结果与书上例题所有的结果完全吻合。所以所编写的算法为对偶单纯形法。五、实验总结通过对对偶单纯形法算法的程序编写，进一步掌握了单纯形法。同时，在编写的过程中，对，b的变换有了更加清晰的理解。以及在求解过程中，对线性约束的标准型也有了明确的掌握。六、源代码源代码如下：#include#includeusingnamespacestd;#defineM-1000classDanChun{private:doubleA[100][120],B[30];//创

5、建一个二维数组，用来存储xi值以及b的值doubleC[110],CB[40];//定义一个C矩阵用来存储x的价值系数doubleCZ[110];//CZ用来存储cj-zj的值doublesita[30];//用来存储sita的值intXB[30];//用来存XB的值doubleX[100];//用来存储最后计算的X的值doublew[100];//Cj-Zj/X[i]的替换。public:intn,m;voidinit();//1.将不等式约束的各矩阵进行赋值boolFindE(inti,intj);//2.寻找A矩阵中的基向量voidFindCB();//3.寻找有用价值系

6、数，Cj-Zj需要用到的intCj_Zj();//4.1求出cj-zj的值intC_sita(intk);//4.2计算sita的值voidCom_DC();//4.用来计算单纯形法的主函数voidCom_E(intl,intk);//4.3求其单位向量第10页共10页云南大学数学与统计学实验教学中心实验报告boolP_CjZj();//4.4intBbool(doubleb[],intk);//判断b中是否有负值存在intTH(intl);//b有负值是，进行替换操作voidDisplay();voidDisplay1();};voidDanChun::init(){inti

7、=0,j=0;cout<<"请输入m,n：";cin>>m;cin>>n;cout<<"请输入线性约束矩阵："<>A[i][j];}else{A[i][j]=0;if(j==n+i){A[i][j]=1;}}}}cout<>B[i];CB[i]=0;}cout<