//線性規劃的單純形法；

　　//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.

　　實驗成功。