对偶单纯形法编程

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

2、在有负数了。这样 的话，x中就会存在负值，这样与约束条件中xi>0，就不符合。所以需要对单纯形法改进，得 到对偶单纯形法。四、实验过程先用单纯形法计算, 对偶单纯形法。确定换出量，找到 再对单纯形表中的当检验数都为非正后，检查 b是否有存在负值，若是有则使用A、对偶单纯形法的算法思想1.2.3.4.b中为负值的最小值。确定对应的 Xi的换出。Xi所在行的各系数进行检查，若所有Aij都大于零，则表示无可行解。若存在Aij小于零，则计算mi门9，找到其所换入的列以保证的到的对j aij偶问题仍有可行解。A，常矩阵B,价值系数C,得到最优解（有 bi<0）的情况下能求解，也能对一般的问题

3、然后再按照原单纯形算法经行求解。重复上述步骤。B、编译运行程序，输入约束方程的系数矩阵 为了保证得到的算法既能对特殊情形 求解。这里给出了一下两组数据。1、上一个实验报告中的求解的数据。B=2 ； 14 ; 2;X=3 -4 2 0 -5 5 0 02、参照课本P62例题6中的2-6表给出的数据max z 2x1 3x3 4x3x2x2X332x1X23x34Xi0；i1,2,3X=-2 -3 -4 0 0D、运行结果如下图：1）下图表示的是第一个数据带入后得到的结果。表示对偶单纯形法对一般的数据成立r廊 Cn d ov/5syite it.3 2cmd e-T.see 0.000-2.500

4、0.0000.000&.0B01.0902.560-1.00312.500 a.eee2.see0.0901.B0B±.0000.506S.090-0.500o.aee-1.5001.0000.5000-0900.060Q.aOQ0.5060.0900.5000.O0Q1价值系数CB： 0 5 -4-比优仃结审-1xri 1 =ft K=8 KU J -a x(4 -0 XIS -0 X(6 -6 XI? -0 KES -10 XIYJ -0 xLiei =e 谓按任意键继缠-B2）下图表示的对偶单纯形法对 b中存在负值时纠正的结果: a、初始化后的结果：请输A n,n ：

5、2 5 请ft入线性约束拒阵-1 -2 -1 1 H -21-301请输入B的值:-3 -4第7页共10页请输入价值系数-2 -3-4001'谨费数C. -2Dm值；-3 -4 线柱约束矩申;-1.000 -2,000-2.000 1.000-3 -4 Qa -1000-teas-1.Q0Q -3 .0001.0000*000a,Q0O i0阳1 .OQ0 0.0000.000I价值系数CB： 0 Bb、优化后的结果:C、最后得到的结果:圈awi*''Systsm52C"nd.ekeH怪软 C： 2 -3 -4 0 i 0.4 2,2 勺束矩阵氛-3.9001

6、.0001.0900.00&O -1000-1000价值系数CB： -3-0-2001-4圏-0.403 -8.2900.260-0-4000.Z&0-0.460-0.200-a.40a-2卜:：二石苍匚簇决锚化结碁faul = -S.6有解时 曲取值如下XL1J iil21 XC3 xr4i X151 xr6i HC71 请按任意键继续.=2.2 =0.4 =0 =0 =H =00最后得到的结果与书上例题所有的结果完全吻合。所以所编写的算法为对偶单纯形法。五、实验总结通过对对偶单纯形法算法的程序编写，进一步掌握了单纯形法。同时，在编写的过程中，对 Cb、Xb、 、Cj-Zj，

7、 b的变换有了更加清晰的理解。以及在求解过程中，对线性约束的标准型也有了明确的掌握。 六、源代码源代码如下：#include <iostream>#include <iomanip>using namespacestd;#define M -1000class DanChunprivate :doubledoubledoubledoubleA100120,B30;/创建一个二维数组，用来存储 Xi值以及b的值C110,CB40;/定义一个C矩阵用来存储X的价值系数CZ110; /CZ用来存储cj-zj的值sita30;/用来存储sita的值int XB30; /用来存X

8、B的值 double X100; /用来存储最后计算的X的值 double w100; /Cj-Zj/Xi的替换。public :int n,m;void init();/1.将不等式约束的各矩阵进行赋值bool FindE( int i, int j); /2.寻找A矩阵中的基向量void FindCB();/3.寻找有用价值系数，Cj-Zj需要用到的求岀cj-zj的值/4.2计算sita的值 用来计算单纯形法的主函数 int k); /4.3求其单位向量int Cj_Zj(); /4.1 int C_sita( int k); void Com_DC0;/4. void Com_E(nt

9、l,bool P_CjZj(); /4.4int Bbool( double b, int k);/判断b中是否有负值存在int TH(int l);/b有负值是，进行替换操作void DisplayO;void Display1();void DanChun:init()int i=0,j=0;cout<<"请输入 m,n :"cin>>m;cin>>n;for (i=0; i<m;i+)for (j=0;j<n+m; j+) ifcoutvv"请输入线性约束矩阵："<<e ndl;(j<

10、;n)cin> >Aij; else Aij=0;if (j=n+i)Aij=1;coutvve ndl;cout<<"请输入 B的值："<<endl; for (i=0;i<m;i+)ci n>>Bi;CBi=0;cout<<e ndl;cout<<"请输入价值系数 C: "<<endl;for (i=0;i<n+m;i+) if (i<n) ci n>>Ci; else Ci = M; Xi=0;n = m+n;void DanChun:

11、Display() int i,j;cout<<"价值系数C:" for (i=0;i<n;i+) cout<<Ci<<coutvve ndl;coutvv "B 的值： for (i=0;ivm;i+) coutvvBivv coutvve ndl;coutvv"线性约束矩阵A： "vvendl; for (i=0; ivm; i+)for (j=0;jvn; j+)printf( "%0.3lft",Aij);coutvve ndl;coutvve ndl;coutvv &quo

12、t;价值系数CB:" for (i=0;ivm;i+) coutvvCBivvcoutvve ndl;bool DanChun:：P_CjZj() int j;iffor (j=0;jvn;j+) (CZj>0) return true ;false ; returnint DanChun:TH( int l)int i=0, k=0;double min = 1000;for (i=0; ivn; i+) wi = 0;for (i=0; ivn; i+)if (Ali>=0) wi = -M; else wi = CZi/Ali; for (i=0; ivn; i+)

13、 if (min>wi) 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; ivk; i+) if (min>bi) min = bi;l = i; /找岀行下标 if(mi nv 0) return l; return -1; void DanChun:Display1()int i,j=0,p=0;double favl=0;for ( i=0;i<m;i+)XXBi=Bi;for (i=0;ivn;i+) fav

14、l += Ci*Xi;coutvv"当前为最优解：favl = " vvfavlvve ndl; coutvv "有最优解时，x的取值如下："vve ndl; for (i=0;ivn;i+)j=i;coutvv "X" vvj+1vv" =" vvXivvendl;Da nChu n:Com_DC() voidint i,j=0,k,l,p=0;bool b;double favl=0;dob = true ;if ifk=Cj_Zj(); / 得到 cj-zj 的大于 0的max (k = -1)if ( (l

15、=Bbool(B,m) >=0)k = TH(l);b = false ; else Dis play1(); return ;(b) l=C_sita(k); if (l=-1)云南大学数学与统计学实验教学中心实验报告coutvv"无解！ "vvendl; return ;CBl=Ck;XBl=k;Com_E(l,k);/*if(!b)k=Cj_Zj();*/第10页共10页P+； COUtvv "第"vvp<<，次优化开始vve ndl; coutvvendlvv "XB的值："；for (i=0;ivm;i+)

16、 coutvvXBivvcoutvve ndl;Disp lay();coutvv"1111 11第"vvp <<"次优化结束11vve ndl;while (P_CjZj() II !b);void DanChun:Com_E(int l, int k) int i,j;Bl=Bl/Alk;for (j=0;jvn;j+)if (j=k) continue ;Alj= Alj/Alk;Alk=1;for 0=0)<口)+)if (i=l) continue ;for 0=0)<n;j+) if (j=k) continue ; intAi

17、j=Aij-Aik*Alj; Bi=Bi-Aik*Bl; Aik=0;Da nChu n:Cj_Zj() int i,j,k=0; double sum=0,max=0; for 0=0)<n;j+)for 0=0)<口)+) sum+=CBi*Aij;CZj=Cj-sum; sum=0;for (j=0;j<n;j+)if (CZj>max && CZj>0) max=CZj; k=j;if (max=0)return -1;return k;int DanChun:C_sita( int k)int i,j=0;double min=-M;for (i=0;i<m;i+)if (Aik>0)sitai=Bi/Aik; j+; else sitai=-M;if (j=0)/表示没有一个Aik 是大于0的return -1;iffor (i=0;i<m;i+)(sitai<mi n)mi n=sitai;k=i;k; returnbool DanChun:FindE( int i, int j)/ 判断是否是单位列int k=0;while (k<m)if (Akj !=0 &