对偶单纯形法编程

1、云南大学数学与统计学实验教学中心实验报告云南大学数学与统计学实验教学中心 实 验 报 告课程名称：运筹学实验学期：20122013学年第二学期成绩：指导教师：葛瑜学生姓名：卢富毓学生学号：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 -4 2 0 -5 5 0 02、参照课本p62例题6中的2-6表给出的数据x=-2 -3 -4 0 0 d、运行结果如下图：1）下图表示的是第一个数据带入后得到的结果。表示对偶单纯形法对一般的数据成立2）下图表示的对偶单纯形法对b中存在负值时纠正的结果：a、初始化后的结果：b、优化后的结果：c、最后得到的结果：最后得到的结果与书上例题所有的结果完全吻合。所以所编写的算法为对偶单纯

4、形法。五、实验总结通过对对偶单纯形法算法的程序编写，进一步掌握了单纯形法。同时，在编写的过程中，对，b的变换有了更加清晰的理解。以及在求解过程中，对线性约束的标准型也有了明确的掌握。六、源代码源代码如下：#include<iostream>#include<iomanip>using namespace std;#define m -1000class danchunprivate:double a100120,b30; /创建一个二维数组，用来存储xi值以及b的值double c110,cb40;/定义一个c矩阵用来存储x 的价值系数double cz110;/cz用

5、来存储cj-zj的值double sita30;/用来存储sita的值int xb30;/用来存xb的值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需要用到的int cj_zj(); /4.1求出cj-zj的值int c_sita(int k);/4.2计算sita的值void com_dc();/4.用来计算单

6、纯形法的主函数void com_e(int l, int k);/4.3求其单位向量bool p_cjzj();/4.4int 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 ："cin>>m;cin>>n;cout<<"请输入线性约束矩阵："<<endl;for(

7、i=0; i<m;i+)for(j=0;j<n+m; j+)if(j<n)cin>>aij; else aij=0;if(j=n+i)aij=1;cout<<endl;cout<<"请输入b的值："<<endl;for(i=0;i<m;i+)cin>>bi;cbi=0;cout<<endl;cout<<"请输入价值系数 c："<<endl;for(i=0;i<n+m;i+)if(i<n)cin>>ci; else

8、ci = m;xi=0;n = m+n;void danchun:display()int i,j;cout<<"价值系数 c："for(i=0;i<n;i+)cout<<ci<<" "cout<<endl;cout<<"b的值："for(i=0;i<m;i+)cout<<bi<<" "cout<<endl;cout<<"线性约束矩阵a："<<endl;for(i=

9、0; i<m; i+)for(j=0;j<n; j+)printf("%0.3lft",aij);cout<<endl;cout<<endl;cout<<"价值系数 cb："for(i=0;i<m;i+)cout<<cbi<<" "cout<<endl;bool danchun:p_cjzj()int j;for(j=0;j<n;j+)if(czj>0)return true;return false;int danchun:th(i

10、nt l)int i=0, k=0;double min = 1000;for(i=0; i<n; i+)wi = 0;for(i=0; i<n; i+)if(ali>=0)wi = -m;elsewi = czi/ali;for(i=0; i<n; i+)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; i<k; i+)if(min>bi)min = bi;l = i; /找出行下标

11、if(min< 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;i<n;i+)favl += ci*xi;cout<<"当前为最优解：favl = "<<favl<<endl;cout<<"有最优解时，x的取值如下："<<endl;for(i=0;i<n;i+)j=i;cout<<"x&quo

12、t;<<j+1<<" ="<<xi<<endl;void danchun:com_dc()int i,j=0,k,l,p=0;bool b;double favl=0;dob =true;k=cj_zj();/得到cj-zj的大于0的maxif(k = -1)if( (l=bbool(b,m) >=0)k = th(l);b = false; else display1();return; if(b)l=c_sita(k); if(l=-1)cout<<"无解！"<<endl;

13、return;cbl=ck;xbl=k;com_e(l,k);/*if(!b)k=cj_zj();*/p+;cout<<"-第"<<p<<"次优化开始-"<<endl;cout<<endl<<"xb的值："for(i=0;i<m;i+)cout<<xbi<<" "cout<<endl;display();cout<<"-第"<<p<<"次

14、优化结束-"<<endl;while(p_cjzj() | !b);void danchun:com_e(int l, int k)int i,j;bl=bl/alk;for(j=0;j<n;j+)if(j=k) continue;alj= alj/alk;alk=1;for(i=0;i<m;i+)if(i=l)continue;for(j=0;j<n;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=

15、0;for(j=0;j<n;j+)for(i=0;i<m;i+)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+;elsesitai=-m;if(j=0) /表示没有一个aik是大于0的return -1;for(i=0;i<m;i+)if(sitai<min)min=sitai;k=i;return k;bool danchun:finde(int i,int j) /判断是否是单位列int k=0;while(k<m)if(akj !=0 && k!=i)return false;el