单纯形法实验报告
姓名：
学号：
班级：
专业：-----------------------
一：实验目的
1） 熟悉单纯形法求解线性规划问题，明确求解过程，熟悉掌握。
2） 使用目前熟悉的语言，实现所学单纯形法求解方程组，并正确运算测试结果。本人使用C++语言实现。
二：实验原理-单纯形法
1.单纯形法（Simplex Method）
（1） 单纯形法是解线性规划问题的一个重要方法。
其原理的基本框架为：
第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。 第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。 第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解。 （2） 用程序进行运算前，要将目标函数及约束方程变成标准形式。
maxzCXs.t1A40AXbX020410000810,b16,C2,3,0,0,01201
对于非标准形式须作如下变换：
a) 目标函数为极小值min z=CX时，转换为max z=-CX形式；
b) 在约束方程中有 “≤”时，在加上一个松弛变量；
c) 在约束方程中有 “≥”时，采用减去一个松弛变量，再加上一个人工变量；
d) 在约束方程中有 “=”时，加上一个人工变量； （3）
e) 所有的人工变量，松弛变量的目标函数系数置为0。 对于标准形式的线性规划问题。用单纯形法计算步骤的框图
三：设计程序算法：
#include
#include
#define M 10000
//全局变量大M float juzhen[11][31];//核心矩阵表
int m=0,n=0,t=0;//m:结构向量的个数 //n:约束不等式个数
//t:目标函数类型：－1代表求求最小值，1代表求最大值
void input() //输入接口函数 {
int i,j;
cout
cout
cout
m= \";
cin>>m;
cout
n= \";
cin>>n;
for (i=0;i
for (j=0;j
juzhen [i][j]=0;
//初始化矩阵，所有元素均为0
//读入约束条件
cout=）:\"
\";
for (i=1;i
cout
x\"
cout
for (i=1;i
{
cout
不等式\"
for (j=1;j
cin>>juzhen [i][j];
}
for (i=1;i
{
juzhen [i][0]=juzhen [i][m+2];
juzhen [i][m+2]=0;
}
//读入目标条件
cout
\";
for(i=1;i
cout
\";
cout
cout
\";
for (i=1;i
cin>>juzhen [0][i];
cin>>t;
//矩阵调整
if(t==-1)
for(i=1;i
juzhen [0][i]=(-1)*juzhen [0][i];
for(i=1;i
{
juzhen [i][m+i]=juzhen [i][m+1];
if(i!=1)
juzhen [i][m+1]=0;
} }
//算法函数
void comput()
{
int i,j,flag,temp1,temp2,h,k=0,temp3[10];
float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c;
求最大
//初始化
for(i=1;i
temp3[i]=0;
for(i=0;i
{
temp4[i]=0;
temp5[i]=0;
}
for(i=1;i
{
if(juzhen [i][m+i]==-1)
{
juzhen [i][m+n+i]=1;
juzhen [0][m+n+i]=M;
temp3[i]=m+n+i;
}
else
temp3[i]=m+i;
}
for(i=1;i
temp4[i]=juzhen [0][temp3[i]];
//循环求解
do{
for(i=1;i
{
a=0;
for(j=1;j
a+=juzhen [j][i]*temp4[j];
juzhen [n+1][i]=juzhen [0][i]-a;
}
for(i=1;i
{
if(juzhen [n+1][i]>=0) flag=1;
else
{
flag=-1;
break;
}
}
if(flag==1)
{
for(i=1;i
{
if(temp3[i]
else
{
temp1=-1;
break;
}
}
//输出结果
cout
cout
if(temp1==1)
{
cout
\";
for(i=1;i
temp5[temp3[i]]=juzhen [i][0];
for(i=1;i
f+=t*juzhen [0][i]*temp5[i];
for(i=1;i
{
cout
if(i!=m)
cout
}
cout
最优目标函数值f= \"
return ;
}
else
{
cout
return ;
}
}
if(flag==-1)
{
temp=100000;
for(i=1;i
if(juzhen [n+1][i]
{
temp=juzhen [n+1][i];
h=i;
}
for(i=1;i
{
if(juzhen [i][h]
else {
temp2=-1;
break;
}
}
}
if(temp2==1)
{
cout
return ;
}
if(temp2==-1)
{
c=100000;
for(i=1;i
{
if(juzhen [i][h]!=0) b[i]=juzhen [i][0]/juzhen [i][h];
if(juzhen [i][h]==0) b[i]=100000;
if(b[i]
b[i]=100000;
if(b[i]
{
c=b[i];
k=i;
}
}
temp3[k]=h;
temp4[k]=juzhen[0][h];
d=juzhen [k][h];
for(i=0;i
juzhen [k][i]=juzhen [k][i]/d;
for(i=1;i
{ if(i==k)
continue;
aa=juzhen [i][h];
for(j=0;j
juzhen [i][j]=juzhen [i][j]-aa*juzhen [k][j];
}
}
}
while(1);
return ; }
//主函数
void main()
{ cout
input();
comput(); }
四：程序测试及结果：
第一题：
max z=2*x1+3*x2+4*x3+7*x4;
2*x1+3*x2-x3-4*x4=8;
x1-2*x2+68x3-7*x4=-3；
x1,x2,x3,x4>=0; 第二题：
max z=x1+2*x2+3*x3;
5*x1+3*x2+x3
-5*x1+6*x2+15*x3
2*x1+x2+x3>=5;
x1,x2,x3>=0;
第三题：
max z=2*x1+3*x2+x3;
10/3*x1+40/3*x2+79/3*x3
1/30*x1+1/30*x2+1/30*x3
x1,x2,x3>=0;
六：程序设计的感想：
对于整体的设计框架在设计程序之前有个整体的规划，如何循环求解，如何将数据存入矩阵之中，怎样用矩阵变换将单行纯表表示计算下去。考虑全面以后，逐步设计编写程序。
