你的位置：
首页
>
IT圈
>
单纯形法的C++实现
2024年2月19日发(作者：浮涵梅)
/*本程序是利用单纯型法来求解线性规划问题
输入数据从文本中读入，按照如下的格式：
例如：需要求解如下的线性规划问题
max z = 2*x1 + 3*x2；
约束条件是：
x1 + x2<=8;
4*x1 <=16;
4*x2<=12;
x1,x2>=0;
则文件中的输入格式是：
2 3 未知数个数 约束条件个数
max 2 3
1 1 < 8 这里小于符号默认为小于等于，
4 0 < 16 注意为零的系数不能省略
0 4 < 12
所需数据从中读取
*/
#include
#include
#include
#include
using namespace std;
ifstream in("");
class DanChun
{
private:
double MuBiao[100];//目标函数
double XiShu[100][100];//系数矩阵，最后一列是常数项
double JianYanShu[100];//检验数，第一个数是最大（或最小）检验数的坐标
double TheTa[100];//theta
double CB[100];//
int XB[100];//
double Jie[100];//解
int BianLian;//变量个数
int FangCheng;//方程（约束条件）个数
string MaxMin;//求的是最大值还是最小值？
public:
DanChun(int BL,int FC,string MaxOrMin);
void Init();
void GetJianYanShu();
bool PanDuan();
void Display();
void setXiShu();
void setJie();
void playJie();
};
DanChun::DanChun(int BL,int FC,string MaxOrMin)
{
BianLian = BL;
FangCheng = FC;
MaxMin = MaxOrMin;
int i,j;
TheTa[0] = 9999.0;
for(i=0;i<100;i++)
{
MuBiao[i]=0;
JianYanShu[i]=0;//
TheTa[i]=0;//
CB[i]=0;//
XB[i]=0;//
Jie[i]=0;
for(j=0;j<100;j++)XiShu[i][j]=0;
}
}
void DanChun::Init()
{
for(int k=1;k<=BianLian;k++)
{
in>>MuBiao[k];
//XB[k]=MuBiao[k];
}
for(int i=1;i<=FangCheng;i++)
{
char op;//操作符
for(int j=1;j<=BianLian;j++)
{
in>>XiShu[i][j];
}
in>>op;
}
}
if(op=='<')
{
XiShu[i][0]=0;
}
else if(op=='>')
{
XiShu[i][0]=1;
}
int BL = BianLian + FangCheng;//加上松弛变量后的未知量个数
XiShu[i][BianLian+i] = 1;//加上单位矩阵
in>>XiShu[i][BL+1];
XB[i]=BianLian+i;
void DanChun::GetJianYanShu()
{
int h=-9999;//记录最大检验数的坐标
for(int i=1;i<=BianLian+FangCheng;i++)
{
double linshi=0;
for(int j=1;j<=FangCheng;j++)
{
linshi += (CB[j] * XiShu[j][i]);
//cout<<" linshi="< }
double ta=MuBiao[i]-linshi;
JianYanShu[i]=ta;
if(JianYanShu[h] {
h=i;
}
}
JianYanShu[0]=h;
//for(int w=1;w<6;w++)cout<<"检验数："< //cout<<"最大检验数坐标："<}
bool DanChun::PanDuan()
{
if(MaxMin=="max")
{
for(int i=1;i<=BianLian+FangCheng;i++)
{
if(JianYanShu[i]>0) return 1;
}
}
else if(MaxMin=="min")
{
for(int i=1;i<=BianLian+FangCheng;i++)
{
if(JianYanShu[i]<0) return 1;
}
}
return 0;
}
void DanChun::Display()
{
cout<<"输出系数矩阵："< for(int i=1;i<=FangCheng;i++)
{
cout< for(int j=1;j<=BianLian+1+FangCheng;j++)
cout< cout< }
cout<<"输出检验数："< for(i=1;i<=FangCheng+BianLian;i++)
{
cout< }
cout< }
void DanChun::setXiShu()
{
TheTa[0]=9999.0;
int kk=0;
int j = JianYanShu[0] , i;//确定换位的坐标
for(int k=1;k<=FangCheng;k++)
{
if(XiShu[k][ (int)JianYanShu[0] ] != 0)
{
TheTa[k] = XiShu[k][(int)(BianLian+FangCheng+1)]
XiShu[k][ (int)(JianYanShu[0]) ];
if((TheTa[0] > TheTa[k]) && TheTa[k] > 0)
{
/
TheTa[0] = TheTa[k];
kk=k;
}
}
//
}//得到TheTa值
i = kk;//i=3,j=2
CB[i]=MuBiao[j];
XB[i]=j;
//cout<<"TheTa[0]="< //cout<<"得到换处的数据XiShu["< for(int x=1;x<=FangCheng;x++)
{
if(x!=i)
{
double chushu = (-XiShu[x][j])
(XiShu[i][j]);//cout<<"chushu="< for(int y=1;y<=FangCheng+BianLian+1;y++)
{
XiShu[x][y] += XiShu[i][y]*chushu;
}
}//end if
else if(x==i)
{
double chushu = XiShu[i][j];
for(int y=1;y<=FangCheng+BianLian+1;y++)
{
XiShu[x][y] /= chushu;
}
}
}
}
void DanChun::setJie()
{
for(int i=1;i<=FangCheng;i++)Jie[XB[i]]=XiShu[i][BianLian+FangCheng+1];
}
void DanChun::playJie()
{
cout<<"该线性规划问题的最优解为："< for(int i=1;i<=BianLian+FangCheng;i++)
{
cout< }
cout<<")t"</
}
int main()
{
int x,y;//变量个数和约束条件个数
string str;//求max？min？
while(in>>x>>y>>str)
{
DanChun danchun(x,y,str);
();
nYanShu();
y();
while(n())
{
hu();
nYanShu();
y();
}
();
e();
}
return 0;
}
2024年2月19日发(作者：浮涵梅)
/*本程序是利用单纯型法来求解线性规划问题
输入数据从文本中读入，按照如下的格式：
例如：需要求解如下的线性规划问题
max z = 2*x1 + 3*x2；
约束条件是：
x1 + x2<=8;
4*x1 <=16;
4*x2<=12;
x1,x2>=0;
则文件中的输入格式是：
2 3 未知数个数 约束条件个数
max 2 3
1 1 < 8 这里小于符号默认为小于等于，
4 0 < 16 注意为零的系数不能省略
0 4 < 12
所需数据从中读取
*/
#include
#include
#include
#include
using namespace std;
ifstream in("");
class DanChun
{
private:
double MuBiao[100];//目标函数
double XiShu[100][100];//系数矩阵，最后一列是常数项
double JianYanShu[100];//检验数，第一个数是最大（或最小）检验数的坐标
double TheTa[100];//theta
double CB[100];//
int XB[100];//
double Jie[100];//解
int BianLian;//变量个数
int FangCheng;//方程（约束条件）个数
string MaxMin;//求的是最大值还是最小值？
public:
DanChun(int BL,int FC,string MaxOrMin);
void Init();
void GetJianYanShu();
bool PanDuan();
void Display();
void setXiShu();
void setJie();
void playJie();
};
DanChun::DanChun(int BL,int FC,string MaxOrMin)
{
BianLian = BL;
FangCheng = FC;
MaxMin = MaxOrMin;
int i,j;
TheTa[0] = 9999.0;
for(i=0;i<100;i++)
{
MuBiao[i]=0;
JianYanShu[i]=0;//
TheTa[i]=0;//
CB[i]=0;//
XB[i]=0;//
Jie[i]=0;
for(j=0;j<100;j++)XiShu[i][j]=0;
}
}
void DanChun::Init()
{
for(int k=1;k<=BianLian;k++)
{
in>>MuBiao[k];
//XB[k]=MuBiao[k];
}
for(int i=1;i<=FangCheng;i++)
{
char op;//操作符
for(int j=1;j<=BianLian;j++)
{
in>>XiShu[i][j];
}
in>>op;
}
}
if(op=='<')
{
XiShu[i][0]=0;
}
else if(op=='>')
{
XiShu[i][0]=1;
}
int BL = BianLian + FangCheng;//加上松弛变量后的未知量个数
XiShu[i][BianLian+i] = 1;//加上单位矩阵
in>>XiShu[i][BL+1];
XB[i]=BianLian+i;
void DanChun::GetJianYanShu()
{
int h=-9999;//记录最大检验数的坐标
for(int i=1;i<=BianLian+FangCheng;i++)
{
double linshi=0;
for(int j=1;j<=FangCheng;j++)
{
linshi += (CB[j] * XiShu[j][i]);
//cout<<" linshi="< }
double ta=MuBiao[i]-linshi;
JianYanShu[i]=ta;
if(JianYanShu[h] {
h=i;
}
}
JianYanShu[0]=h;
//for(int w=1;w<6;w++)cout<<"检验数："< //cout<<"最大检验数坐标："<}
bool DanChun::PanDuan()
{
if(MaxMin=="max")
{
for(int i=1;i<=BianLian+FangCheng;i++)
{
if(JianYanShu[i]>0) return 1;
}
}
else if(MaxMin=="min")
{
for(int i=1;i<=BianLian+FangCheng;i++)
{
if(JianYanShu[i]<0) return 1;
}
}
return 0;
}
void DanChun::Display()
{
cout<<"输出系数矩阵："< for(int i=1;i<=FangCheng;i++)
{
cout< for(int j=1;j<=BianLian+1+FangCheng;j++)
cout< cout< }
cout<<"输出检验数："< for(i=1;i<=FangCheng+BianLian;i++)
{
cout< }
cout< }
void DanChun::setXiShu()
{
TheTa[0]=9999.0;
int kk=0;
int j = JianYanShu[0] , i;//确定换位的坐标
for(int k=1;k<=FangCheng;k++)
{
if(XiShu[k][ (int)JianYanShu[0] ] != 0)
{
TheTa[k] = XiShu[k][(int)(BianLian+FangCheng+1)]
XiShu[k][ (int)(JianYanShu[0]) ];
if((TheTa[0] > TheTa[k]) && TheTa[k] > 0)
{
/
TheTa[0] = TheTa[k];
kk=k;
}
}
//
}//得到TheTa值
i = kk;//i=3,j=2
CB[i]=MuBiao[j];
XB[i]=j;
//cout<<"TheTa[0]="< //cout<<"得到换处的数据XiShu["< for(int x=1;x<=FangCheng;x++)
{
if(x!=i)
{
double chushu = (-XiShu[x][j])
(XiShu[i][j]);//cout<<"chushu="< for(int y=1;y<=FangCheng+BianLian+1;y++)
{
XiShu[x][y] += XiShu[i][y]*chushu;
}
}//end if
else if(x==i)
{
double chushu = XiShu[i][j];
for(int y=1;y<=FangCheng+BianLian+1;y++)
{
XiShu[x][y] /= chushu;
}
}
}
}
void DanChun::setJie()
{
for(int i=1;i<=FangCheng;i++)Jie[XB[i]]=XiShu[i][BianLian+FangCheng+1];
}
void DanChun::playJie()
{
cout<<"该线性规划问题的最优解为："< for(int i=1;i<=BianLian+FangCheng;i++)
{
cout< }
cout<<")t"</
}
int main()
{
int x,y;//变量个数和约束条件个数
string str;//求max？min？
while(in>>x>>y>>str)
{
DanChun danchun(x,y,str);
();
nYanShu();
y();
while(n())
{
hu();
nYanShu();
y();
}
();
e();
}
return 0;
}