vc_simply.txt

单纯形优化算法的VC实现

//线性规划的单纯形法；

　　//C++实现，在VC++6.0中通过

　　#include<stdio.h>

　　#include<math.h>

　　#include<iostream.h>

　　floatmatrix[100][100],x[100];/*记录总方程的数组,解的数组*/

　　inta[100];/*记录基础,非基础的解的情况,0:非基础,1:基础*/

　　intm,n,s,type;/*方程变量,约束数,求最大最小值的类型,0:最小1:最大*/

　　intindexe,indexl,indexg;/*剩余变量,松弛变量,人工变量*/

　　voidJckxj()

　　{

　　inti,j;

　　for(i=0;i<n;i++)

　　for(j=0;j<s;j++)

　　if(matrix[i][j]==1&&a[j]==1){

　　x[j]=matrix[i][s];

　　j=s;

　　}

　　for(i=0;i<s;i++)

　　if(a[i]==0)x[i]=0;

　　}

　　intRj()

　　{

　　inti;

　　for(i=0;i<s;i++)

　　if(fabs(matrix[n][i])>=0.000001)

　　if(matrix[n][i]<0)return0;

　　return1;

　　}

　　intMin()

　　{

　　inti,temp=0;

　　floatmin=matrix[n][0];

　　for(i=1;i<s;i++)

　　if(min>matrix[n][i]){

　　min=matrix[n][i];

　　temp=i;

　　}

　　returntemp;

　　}

　　voidJustArtificial()

　　{

　　inti;

　　for(i=m+indexe+indexl;i<s;i++)

　　if(fabs(x[i])>=0.000001){

　　printf("NoAnswer\n");

　　return;

　　}

　　}

　　intCheck(intin)

　　{

　　inti;

　　floatmax1=-1;

　　for(i=0;i<n;i++)

　　if(fabs(matrix[i][in])>=0.000001&&max1<matrix[i][s]/matrix[i][in])

　　max1=matrix[i][s]/matrix[i][in];

　　if(max1<0)

　　return1;

　　return0;

　　}

　　intSearchOut(int*temp,intin)

　　{

　　inti;

　　floatmin=10000;

　　for(i=0;i<n;i++)

　　if(fabs(matrix[i][in])>=0.000001&&(matrix[i][s]/matrix[i][in]>=0)&&min>matrix[i][s]/matrix[i][in]){

　　min=matrix[i][s]/matrix[i][in];

　　*temp=i;

　　}

　　for(i=0;i<s;i++)

　　if(a[i]==1&&matrix[*temp][i]==1)returni;

　　}

　　voidMto(intin,inttemp)

　　{

　　inti;

　　for(i=0;i<=s;i++)

　　if(i!=in)

　　matrix[temp][i]=matrix[temp][i]/matrix[temp][in];

　　matrix[temp][in]=1;

　　}

　　voidBe(inttemp,intin)

　　{

　　inti,j;

　　floatc;

　　for(i=0;i<=n;i++){

　　c=matrix[i][in]/matrix[temp][in];

　　if(i!=temp)

　　for(j=0;j<=s;j++)

　　matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;

　　}

　　}

　　voidAchange(intin,intout)

　　{

　　inttemp=a[in];

　　a[in]=a[out];

　　a[out]=temp;

　　}

　　voidPrint()

　　{

　　inti,j,k,temp=0;

　　for(i=0;i<n;i++){

　　for(k=temp;k<s;k++)

　　if(a[k]==1){

　　printf("X%d",k);

　　temp=k+1;

　　k=s;

　　}

　　for(j=0;j<=s;j++)

　　printf("%8.2f",matrix[i][j]);

　　printf("\n");

　　}

　　printf("Rj");

　　for(j=0;j<=s;j++)

　　printf("%8.2f",matrix[n][j]);

　　printf("\n");

　　}

　　voidInitPrint()

　　{

　　inti;

　　printf("X");

　　for(i=0;i<s;i++)

　　printf("a%d",i);

　　printf("b\n");

　　Print();

　　printf("\n");

　　}

　　voidResult()

　　{

　　inti;

　　printf("(");

　　for(i=0;i<s;i++)

　　printf("%8.2f",x[i]);

　　printf(")");

　　if(type==1)

　　printf("Zmax=%f\n\n",matrix[n][s]);

　　elseprintf("Zmin=%f\n\n",matrix[n][s]);

　　}

　　voidPrintResult()

　　{

　　if(type==0)printf("TheMinimal:%f\n",-matrix[n][s]);

　　elseprintf("TheMaximum:%f\n",matrix[n][s]);

　　}

　　voidMerge(floatnget[][100],floatnlet[][100],floatnet[][100],floatb[])

　　{

　　inti,j;

　　for(i=0;i<n;i++){

　　for(j=m;j<m+indexe;j++)

　　if(nget[i][j-m]!=-1)matrix[i][j]=0;

　　elsematrix[i][j]=-1;

　　for(j=m+indexe;j<m+indexe+indexl;j++)

　　if(nlet[i][j-m-indexe]!=1)matrix[i][j]=0;

　　elsematrix[i][j]=1;

　　for(j=m+indexe+indexl;j<s;j++)

　　if(net[i][j-m-indexe-indexl]!=1)matrix[i][j]=0;

　　elsematrix[i][j]=1;

　　matrix[i][s]=b[i];

　　}

　　for(i=m;i<m+indexe+indexl;i++)

　　matrix[n][i]=0;

　　for(i=m+indexe+indexl;i<s;i++)

　　matrix[n][i]=100;

　　matrix[n][s]=0;

　　}

　　voidProcessA()

　　{

　　inti;

　　for(i=0;i<m+indexe;i++)

　　a[i]=0;

　　for(i=m+indexe;i<s;i++)

　　a[i]=1;

　　}

　　voidInput(floatb[],intcode[])

　　{

　　inti=0,j=0;

　　printf("TheequatorVariableandRestrictor\n");/*输入方程变量和约束数*/

　　cin>>m>>n;

　　for(i=0;i<n;i++){

　　printf("Inputb[]andRestrictorcode0:<=1:=2:>=\n");/*输入方程右边的值,code的值*/

　　cin>>b[i]>>code[i];

　　printf("TheXiShu\n");

　　for(j=0;j<m;j++)

　　cin>>matrix[i][j];/*输入方程*/

　　}

　　printf("TheType0:Min1:Max\n");/*输入求最大值还是最小值*/

　　do{

　　cin>>type;

　　if(type!=0&&type!=1)printf("Error,ReInput\n");

　　}while(type!=0&&type!=1);

　　printf("TheZ\n");/*输入z*/

　　for(i=0;i<m;i++)

　　cin>>matrix[n][i];

　　if(type==1)

　　for(i=0;i<m;i++)

　　matrix[n][i]=-matrix[n][i];

　　}

　　voidXartificial()

　　{

　　inti,j,k;

　　if(indexg!=0){

　　for(i=m+indexe+indexl;i<s;i++){

　　for(j=0;j<n;j++)

　　if(matrix[j][i]==1){

　　for(k=0;k<=s;k++)

　　matrix[n][k]=matrix[n][k]-matrix[j][k]*100;

　　j=n;

　　}

　　}

　　}

　　}

　　voidProcess(floatc[][100],introw,intvol)

　　{

　　inti;

　　for(i=0;i<n;i++)

　　if(i!=row)c[i][vol]=0;

　　}

　　voidSstart(floatb[],intcode[])

　　{

　　inti;

　　floatnget[100][100],nlet[100][100],net[100][100];/*剩余变量数组,松弛变量数组,人工变量数组*/

　　indexe=indexl=indexg=0;

　　for(i=0;i<n;i++){

　　if(code[i]==0){nlet[i][indexl++]=1;Process(nlet,i,indexl-1);}

　　if(code[i]==1){net[i][indexg++]=1;Process(net,i,indexg-1);}

　　if(code[i]==2){

　　net[i][indexg++]=1;

　　nget[i][indexe++]=-1;

　　Process(net,i,indexg-1);Process(nget,i,indexe-1);

　　}

　　}

　　s=indexe+indexl+indexg+m;

　　Merge(nget,nlet,net,b);/*合并*/

　　ProcessA();/*初始化a[]*/

　　InitPrint();/*初始化打印*/

　　Xartificial();/*消去人工变量*/

　　}

　　voidSimplix()/*单纯型算法*/

　　{

　　intin,out,temp=0;

　　while(1){

　　Jckxj();/*基础可行解*/

　　Print();/*打印*/

　　Result();/*打印结果*/

　　if(!Rj())in=Min();/*求换入基*/

　　else{

　　if(indexg!=0)JustArtificial();/*判断人工变量*/

　　PrintResult();/*打印最后结果*/

　　return;

　　}

　　if(Check(in)){/*判断无界情况*/

　　printf("NoDelimition\n");

　　return;

　　}

　　out=SearchOut(&temp,in);/*求换出基*/

　　Mto(in,temp);/*主元化1*/

　　Be(temp,in);/*初等变换*/

　　Achange(in,out);/*改变a[]的值*/

　　}

　　}

　　voidmain()

　　{

　　intcode[100];/*输入符号标记*/

　　floatb[100];/*方程右值*/

　　Input(b,code);/*初始化*/

　　Sstart(b,code);/*化标准型*/

　　Simplix();/*单纯型算法*/

　　}

　　实验报告：

　　*********************************计算机系2000级软件班1000432彭小聪******************************************************

　　*********************************运筹学单纯形法解线性规划问题（C＋＋实现,VC6.0中通过）**********************************

　　函数列表：

　　Jckxj

　　Rj

　　Min

　　JustArtificial

　　Check

　　SearchOut

　　Mto

　　Be

　　Achange

　　Print

　　InitPrint

　　Result

　　PrintResult

　　Merge

　　ProcessA

　　Input

　　Xartificial

　　Process

　　Sstart

　　Simplix

　　while

　　main

　　变量：

　　floatmatrix[100][100],x[100]记录总方程的数组,解的数组

　　inta[100]记录基础,非基础的解的情况,0:非基础,1:基础

　　intm,n,type方程变量,约束数,求最大最小值的类型,0:最小1:最大

　　intindexe,indexl,indexg剩余变量,松弛变量,人工变量

　　输入提示：

　　equatorVariable变量个数；

　　Restrictor约束条件个数；（注：这里程序默认X(i)>0；否则对每个X(i)我们均要添加一个约束条件X(i)>0）

　　b[]约束条件右端项；

　　Restrictorcode约束条件不等式符号编码;(0表示<=；1表示=；2表示>=)

　　TheXiShu各约束条件中X(i)对应的系数

　　TheTypeZ的最优方向（0表示MIN;1表示MAX）

　　TheZ目标函数的系数

　　输入例子：

　　MAXZ=4X(1)+3X(2)

　　S.T.2X(1)+3X(2)<=24

　　3X(1)+2X(2)<=26

　　X(1),X(2)>=0

　　运行1000432.exe

　　TheequatorVariableandRestrictor:

　　22

　　Inputb[]andRestrictorcode0:<=1:=2:>=

　　240

　　TheXiShu

　　23

　　Inputb[]andRestrictorcode0:<=1:=2:>=

　　260

　　TheXiShu

　　32

　　TheType0:Min1:Max

　　1

　　TheZ

　　43

　　结果输出：

　　Xa0a1a2a3b

　　X22.003.001.000.0024.00

　　X33.002.000.001.0026.00

　　Rj-4.00-3.000.000.000.00

　　X22.003.001.000.0024.00

　　X33.002.000.001.0026.00

　　Rj-4.00-3.000.000.000.00

　　(0.000.0024.0026.00)Zmax=0.000000

　　X00.001.671.00-0.676.67

　　X21.000.670.000.338.67

　　Rj0.00-0.330.001.3334.67

　　(8.670.006.670.00)Zmax=34.666668

　　X00.001.000.60-0.404.00

　　X11.000.00-0.400.606.00

　　Rj0.000.000.201.2036.00

　　(6.004.000.000.00)Zmax=36.000000

　　TheMaximum:36.000000

　　从而可知：MAXZ=36,此时X(1)=6,X(2)=4.

　　实验成功。