对偶单纯形法编程

1、某某大学数学与统计学实验教学中心实验报告课程名称：运筹学实验学期：20122013学年第二学期成绩：指导教师：葛瑜学生某某：卢富毓学生学号：20101910072实验名称：对偶单纯形法编程实验要求：必做实验学时：2学时实验编号：02实验日期：2013/3/8完成日期：2013/3/11学院：数学与统计学院专业：信息与计算科学年级：2010级一、实验目的编程实现对偶改良单纯形法求解线性规划问题，加深对单纯形法的理解和掌握二、实验环境VS2010 C+三、实验内容改良单纯形法的实验：由于在一些情况下，当检验数 Cj-Zj都小于零后了，但是其b的值却存在有负数了。这样 的话，x中就会存在负值，这样与约束条件中xi0，就不符合。所以需要对单纯形法改良，得 到对偶单纯形法。四、实验过程A、对偶单纯形法的算法思想1. 先用单纯形法计算，当检验数都为非正后，检查 b是否有存在负值，假如是有如此 使用对偶单纯形法。2. 确定换出量，找到b中为负值的最小值。确定对应的 xi的换出。3. 再对单纯形表中的xi所在行的各系数进展检查，假如所有Aij都大于零，如此表示无可行解。假如存在 Aij小于零，如此计算

2、min，找到其所换入的列以保证jaj的到的对偶问题仍有可行解。4. 然后再按照原单纯形算法经行求解。重复上述步骤。B、 编译运行程序，输入约束方程的系数矩阵A，常矩阵B,价值系数C,得到最优解为了保证得到的算法既能对特殊情形有bi0的情况下能求解，也能对一般的问题求解。这里给出了一下两组数据。1、上一个实验报告中的勺求解的:数据。412011001 0A113011100 0231022010 1B=2 ; 14 ; 2;X=3 -4 2 0 -5 5 0 02、参照课本P62例题6中的2-6表给出的数据maxz2x13X3 4X3Xi2x2X332x1X23X34Xi0;i1,2,312 11 0A2130 1B 12X=-2 -3 -4 0 0D、运行结果如如下图:1如下图表示的是第一个数据带入后得到的结果。表示对偶单纯形法对一般的数据成PSI C.V ndQV.5；ysteitiS2md.exe9.00&0.6000-000-1-0001.0003.0008.0001.0000.8000.0000-5003.030o.see0.00B愉值系数CI； 0謹禍鍛;舀般笊x ri 申X

3、(2=(3X L3 J X4 K LSIM L6 K ? KISKt9 3 KC10) 请按任意键继夢2如下图表示的对偶单纯形法对 b中存在负值时纠正的结果:a、初始化后的结果：b、优化后的结果:c、最后得到的结果:最后得到的结果与书上例题所有的结果完全吻合。所以所编写的算法为对偶单纯形法。五、实验总结通过对对偶单纯形法算法的程序编写，进一步掌握了单纯形法。同时，在编写的过程中，对 Cb、Xb、 、Cj-Zj，b的变换有了更加清晰的理解。 以与在求解过程中，对线性约束的标准型也有了明确的掌握。六、源代码源代码如下：#inelude #include usingn amespace std;#define M -1000 class DanChunprivate :double A100120,B30;/创建一个二维数组，用来存储 xi值以与b的值double C110,CB40;/定义一个C矩阵用来存储x的价值系数double CZ110; /CZ 用来存储 cj-zj 的值double sita30;/ 用来存储 sita 的值int XB30; /用来存XB勺值double X10

4、0; /用来存储最后计算的X的值double w100;Cj-Zj/Xi的替换。public :int n,m;void init();bool FindE( int i, int j);void FindCB();/3.寻找有用价值系数，Cj-Zj需要用到的int Cj_Zj();int C_sita( int k);void _DC();void _E( int l, int k);bool P_CjZj();int Bbool( double b, int k);/判断b中是否有负值存在int TH(int l);/b有负值是，进展替换操作void Display。；void Display1();void DanChun:init() int i=0,j=0;cout请输入 m,n cinm;cinn;cout请输入线性约束矩阵：e ndl;for (i=0; im;i+)for (j=0;jn+m; j+) if (j Aij; else Aij=0;if (j=n+i)Aij=1;coute ndl;cout请输入 B勺值：endl;for (i=0;im;i+)ci nB

5、i;CBi=0;coute ndl;cout请输入价值系数 C: endl;for (i=0;in+m;i+) if (in)ci nCi; else Ci = M;Xi=0;n = m+n;void DanChun:Display()int i,j;coutvv价值系数C:;for (i=0;in;i+)coutCi ;coute ndl;coutB 的值：;for (i=0;im;i+)coutvBivv ;coute ndl;cout线性约束矩阵A: endl; for (i=0; im; i+) for (j=0;jn; j+)printf( %0.3lft,Aij); coute ndl;coute ndl;coutvv价值系数CB:;for (i=0;im;i+)coutvCBivv ;coute ndl;bool DanChun:P_CjZj()int j;for (j=0;j0) returntrue ;returnfalse ;int DanChun:TH( int l)int i=0, k=0;double min = 1000;for (i=0; in; i+)w

6、i = 0;for (i=0; i=0)wi = -M; else wi = CZi/Ali;for (i=0; iwi)min = wi;k = i;return k;int DanChun:Bbool( double b, int k)int i=0, l=0, s=0;double min = 0;for (i=0; ibi)min = bi;l = i; /找岀行下标if (min 0)return l;return -1;void DanChun:Display1()int i,j=O,p=O;double favl=0;for ( i=0;im;i+)XXBi=Bi;for (i=0;in;i+)favl += Ci*Xi;cout当前为最优解：favl = vvfavlvve ndl; cout有最优解时，x的取值如下：e ndl;for (i=0;in;i+)j=i;cout X j+1 = Xi=0)k = TH(l);b = false ; else Display1();return ;if (b)l=C_sita(k);if (l=-1)cout无解！ endl

7、; return ; CBl=Ck; XBl=k;_E(l,k);/*if(!b) k=Cj_Zj();*/第p次优化开始第p次优化完毕P+;coute ndl; coutendl XB的值：；for (i=0;im;i+)coutXBi ;coute ndl;Display。；coute ndl; while (P_CjZj() | !b);void DanChun:_E( int l, int k)int i,j;Bl=Bl/Alk;for (j=0;jn;j+)if (j=k) continue ;Alj= Alj/Alk;Alk=1;for (i=0;im;i+)if (i=l) continue ;for (j=0;jn;j+)if (j=k) continue ;Aij=Aij-Aik*Alj;Bi=Bi-Aik*Bl;Aik=0;int DanChun:Cj_Zj()int i,j,k=0;double sum=0,max=0;for (j=0;jn;j+)for (i=0;im;i+)sum+=CBi*Aij;CZj=Cj-sum;sum=0;for (j=0;jmax & CZj0)max=CZj;

《对偶单纯形法编程》由会员新**分享，可在线阅读，更多相关《对偶单纯形法编程》请在金锄头文库上搜索。