用VC實(shí)現(xiàn)解線性規(guī)劃中的單純形法問(wèn)題.  
 

 
發(fā)表日期：2003年6月16日    作者：pxc911  已經(jīng)有3171位讀者讀過(guò)此文 
 


這是我們運(yùn)籌學(xué)實(shí)踐題目，單純形算法作為線性規(guī)劃中的重點(diǎn)，其實(shí)現(xiàn)非常重要。

現(xiàn)給出源程序，請(qǐng)各位指教：

//線性規(guī)劃的單純形法；
//C++實(shí)現(xiàn)，在VC++6.0中通過(guò)

#include<stdio.h>
#include<math.h>
#include<iostream.h>
float matrix[100][100],x[100]; /* 記錄總方程的數(shù)組,解的數(shù)組 */
int a[100]; /* 記錄基礎(chǔ),非基礎(chǔ)的解的情況,0:非基礎(chǔ),1:基礎(chǔ) */
int m,n,s,type; /* 方程變量,約束數(shù),求最大最小值的類(lèi)型,0:最小 1:最大 */
int indexe,indexl,indexg; /* 剩余變量,松弛變量,人工變量 */ 
void Jckxj()
{
int i,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;
}

int Rj()
{
int i;
for(i=0;i<s;i++)
if(fabs(matrix[n][i])>=0.000001)
if(matrix[n][i]<0) return 0;
return 1;
}

int Min()
{
int i,temp=0;
float min=matrix[n][0];
for(i=1;i<s;i++)
if(min>matrix[n][i]){
min=matrix[n][i];
temp=i;
}
return temp;
}

void JustArtificial()
{
int i;
for(i=m+indexe+indexl;i<s;i++)
if(fabs(x[i])>=0.000001){
printf("No Answer\n");
return;
}
}

int Check(int in)
{
int i;
float max1=-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)
return 1;
return 0;
}

int SearchOut(int *temp,int in) 
{
int i;
float min=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) return i;
}

void Mto(int in,int temp)
{
int i;
for(i=0;i<=s;i++)
if(i!=in)
matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
matrix[temp][in]=1;
}

void Be(int temp,int in)
{
int i,j;
float c;
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;
}
}

void Achange(int in,int out)
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}

void Print()
{
int i,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");
}

void InitPrint()
{
int i;
printf("X");
for(i=0;i<s;i++)
printf(" a%d",i);
printf(" b\n");
Print();
printf("\n");
}

void Result()
{
int i;
printf(" (");
for(i=0;i<s;i++)
printf("%8.2f",x[i]);
printf(" ) ");
if(type==1)
printf(" Zmax=%f\n\n",matrix[n][s]);
else printf(" Zmin=%f\n\n",matrix[n][s]);
}

void PrintResult()
{
if(type==0) printf("The Minimal :%f\n",-matrix[n][s]);
else printf("The Maximum :%f\n",matrix[n][s]);
}

void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])
{
int i,j;
for(i=0;i<n;i++){
for(j=m;j<m+indexe;j++)
if(nget[i][j-m]!=-1) matrix[i][j]=0;
else matrix[i][j]=-1;
for(j=m+indexe;j<m+indexe+indexl;j++)
if(nlet[i][j-m-indexe]!=1) matrix[i][j]=0;
else matrix[i][j]=1;
for(j=m+indexe+indexl;j<s;j++)
if(net[i][j-m-indexe-indexl]!=1) matrix[i][j]=0;
else matrix[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;
}

void ProcessA()
{
int i;
for(i=0;i<m+indexe;i++)
a[i]=0;
for(i=m+indexe;i<s;i++)
a[i]=1;
}

void Input(float b[],int code[])
{
int i=0,j=0;
printf("The equator Variable and Restrictor\n"); /* 輸入方程變量和約束數(shù) */
cin>>m>>n;
for(i=0;i<n;i++){
printf("Input b[] and Restrictor code 0:<= 1:= 2:>=\n"); /* 輸入方程右邊的值,code的值 */
cin>>b[i]>>code[i];
printf("The XiShu\n");
for(j=0;j<m;j++)
cin>>matrix[i][j]; /* 輸入方程 */
}
printf("The Type 0:Min 1:Max \n"); /* 輸入求最大值還是最小值 */
do{
cin>>type;
if(type!=0&&type!=1) printf("Error,ReInput\n");
}while(type!=0&&type!=1);
printf("The Z\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];
}

void Xartificial()
{
int i,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;
}
}
}
}

void Process(float c[][100],int row,int vol)
{
int i;
for(i=0;i<n;i++)
if(i!=row) c[i][vol]=0;
}

void Sstart(float b[],int code[])
{
int i;
float nget[100][100],nlet[100][100],net[100][100]; /* 剩余變量數(shù)組,松弛變量數(shù)組,人工變量數(shù)組 */
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(); /* 消去人工變量 */
}

void Simplix() /* 單純型算法 */
{
int in,out,temp=0;
while(1){
Jckxj(); /* 基礎(chǔ)可行解 */
Print(); /* 打印 */
Result(); /* 打印結(jié)果 */
if(!Rj()) in=Min(); /* 求換入基 */
else {
if(indexg!=0) JustArtificial(); /* 判斷人工變量 */
PrintResult(); /* 打印最后結(jié)果 */
return;
}
if(Check(in)){ /* 判斷無(wú)界情況 */
printf("No Delimition\n");
return;
}
out=SearchOut(&temp,in); /* 求換出基 */
Mto(in,temp); /* 主元化1 */
Be(temp,in); /* 初等變換 */
Achange(in,out); /* 改變a[]的值 */
}
}

void main()
{
int code[100]; /* 輸入符號(hào)標(biāo)記 */
float b[100]; /* 方程右值 */
Input(b,code); /* 初始化 */
Sstart(b,code); /* 化標(biāo)準(zhǔn)型 */
Simplix(); /* 單純型算法 */
}


實(shí)驗(yàn)報(bào)告：

*********************************計(jì)算機(jī)系2000級(jí)軟件班1000432 彭小聰******************************************************
*********************************運(yùn)籌學(xué)單純形法解線性規(guī)劃問(wèn)題（C＋＋實(shí)現(xiàn),VC6.0中通過(guò)）**********************************
函數(shù)列表：
Jckxj
Rj
Min
JustArtificial
Check
SearchOut
Mto
Be
Achange
Print
InitPrint
Result
PrintResult
Merge
ProcessA
Input
Xartificial
Process
Sstart
Simplix
while
main

變量：
float matrix[100][100],x[100]       記錄總方程的數(shù)組,解的數(shù)組 
int a[100]                          記錄基礎(chǔ),非基礎(chǔ)的解的情況,0:非基礎(chǔ),1:基礎(chǔ)  
int m,n,type                        方程變量,約束數(shù),求最大最小值的類(lèi)型,0:最小 1:最大  
int indexe,indexl,indexg            剩余變量,松弛變量,人工變量  

輸入提示：
equator Variable                    變量個(gè)數(shù)；
Restrictor                          約束條件個(gè)數(shù)；（注：這里程序默認(rèn)X(i)>0；否則對(duì)每個(gè)X(i)我們均要添加一個(gè)約束條件X(i)>0）
b[]                                 約束條件右端項(xiàng)；
Restrictor code                     約束條件不等式符號(hào)編碼;(0表示<=；1表示=；2表示>=)
The XiShu                           各約束條件中X(i)對(duì)應(yīng)的系數(shù)
The Type                            Z的最優(yōu)方向（0表示MIN;1表示MAX）
The Z                               目標(biāo)函數(shù)的系數(shù)

輸入例子：
MAX Z=4X(1)+3X(2)
 S.T.  2X(1)+3X(2)<=24
       3X(1)+2X(2)<=26
       X(1),X(2)>=0
運(yùn)行1000432.exe
The equator Variable and Restrictor:
2 2
Input b[] and Restrictor code 0:<= 1:= 2:>=
24 0
The XiShu
2 3
Input b[] and Restrictor code 0:<= 1:= 2:>=
26 0
The XiShu
3 2
The Type 0:Min 1:Max
1
The Z
4 3
結(jié)果輸出：
X       a0      a1      a2      a3      b
X2     2.00    3.00    1.00    0.00   24.00
X3     3.00    2.00    0.00    1.00   26.00
Rj    -4.00   -3.00    0.00    0.00    0.00

X2     2.00    3.00    1.00    0.00   24.00
X3     3.00    2.00    0.00    1.00   26.00
Rj    -4.00   -3.00    0.00    0.00    0.00
 (    0.00    0.00   24.00   26.00 )  Zmax=0.000000

X0     0.00    1.67    1.00   -0.67    6.67
X2     1.00    0.67    0.00    0.33    8.67
Rj     0.00   -0.33    0.00    1.33   34.67
 (    8.67    0.00    6.67    0.00 )  Zmax=34.666668

X0     0.00    1.00    0.60   -0.40    4.00
X1     1.00    0.00   -0.40    0.60    6.00
Rj     0.00    0.00    0.20    1.20   36.00
 (    6.00    4.00    0.00    0.00 )  Zmax=36.000000

The Maximum :36.000000

從而可知：MAX Z=36,此時(shí)X(1)=6,X(2)=4.

實(shí)驗(yàn)成功。