整数规划隐枚举法实验报告.docx
- 文档编号:18546639
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:12
- 大小:39.17KB
整数规划隐枚举法实验报告.docx
《整数规划隐枚举法实验报告.docx》由会员分享,可在线阅读,更多相关《整数规划隐枚举法实验报告.docx(12页珍藏版)》请在冰点文库上搜索。
整数规划隐枚举法实验报告
整数规划隐枚举法实验报告
实验报告
名称:
运筹学上机实习
一、实验的目的与要求
1、实现整数规划隐枚举法的计算机实现实验(本实验是通过c++编程实现的)。
2、实验成果要求
基本要求:
能够完成整数规划隐枚举法的计算(给出的是标准形式的整数规划问题)。
提高要求:
求解分成两种情况:
(1)求最大值max。
(2)求最小值min。
二、实验分析
由实验要求知,需要在运行界面里输入一个整数规划的标准型(包括系数矩阵,目标函数矩阵,b列值,变量x的取值矩阵),然后运行界面会返回输出结果。
实验实现过程:
#include
#include
/*本程序为整数规划隐枚举法*/
voidmain()
{
floata[30],c[30][30],b[30],c_b[30];
intx[30][100],m,n,i,j,p=0,shuru,e,f;
//a[]为目标系数,c[][]系数矩阵,c_b[]判是否符合要求的数列,b[]为b列值。
//x[][]为变量的取值,m行,n列。
其中m行,n列是系数矩阵c[][]的行列值。
//shuru为选择变量(目标函数求最大max值输入1,目标函数求最小min值输入2)。
//本方法要将x1,x2,x3...的取值(0或1)以纵向形式(二进制形式)输入。
cout<<"/*"< cout<<"本设计方法要将x1,x2,x3,x4...的取值(0或1)以纵向形式(且为二进制形式)输入。 "< cout<<"请输入系数矩阵c[][]的行数m为: "<<"\n"; cin>>m; cout<<"请输入系数矩阵c[][]的列数n为: "<<"\n"; cin>>n; cout<<"请输入目标函数a[]的系数: "<<"\n"; for(i=0;i cin>>a[i]; cout<<"请输入系数矩阵c[][]: "<<"\n"; for(i=0;i for(j=0;j cin>>c[i][j]; cout<<"b列值: "<<"\n"; for(i=0;i cin>>b[i]; cout<<"请输入变量的取值(变量x1,x2,x3......只能取整数0和1,且以二进制的形式)"<<"\n"; cout<<"以纵向形式写出x[][]矩阵的取值"<<"\n"; cout<<"即: (x1,x2,x3...)T(x1,x2,x3...)T(x1,x2,x3...)T(x1,x2,x3...)T...: "<<"\n"; cout<<"(其中T表示矩阵的转置)"< for(i=0;i for(j=0;j cin>>x[i][j]; for(i=0;i { c_b[i]=0; } cout<<"若目标函数求最大max值请输入1"<<"\n"; cout<<"若目标函数求最小min值请输入2"<<"\n"; cin>>shuru; floatz=0.0; //目标函数求最大max值的情况 if(shuru==1) {//用试探法找初始可行解。 cout<<"目标函数求最大max值"< for(i=0;i for(j=0;j c_b[i]+=c[i][j]*x[j][p]; intt,s; for(i=0;i { if(c_b[i]>b[i]&&p<=pow(2,n)-1) {p++; for(s=0;s { c_b[s]=0; } for(t=0;t for(j=0;j c_b[t]+=c[t][j]*x[j][p]; i=-1; } if(p>pow(2,n)-1) {cout<<"无可行解"<<"\n"; break; } } //产生过滤条件。 for(j=0;j z+=a[j]*x[j][p]; //改进过滤条件,求最优解的过程。 floattemp; intl,w; e=p; f=p; while(p<=pow(2,n)-1) { temp=0.0; for(j=0;j { temp+=a[j]*x[j][p]; } if(temp { p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } if(temp>=z) { for(l=0;l { if(c_b[l]<=b[l]); elsebreak; } if(l==m) { z=temp; e=p; p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } elseif(l { p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } } } if(f {cout< "<<"\n"; cout<<"z="< cout<<"最优解为,即x1,x2,x3......的取值: "<<"\n"; for(j=0;j cout< cout<<"\n"; } } //目标函数求最小min值的情况 elseif(shuru==2) {//用试探法找初始可行解。 cout<<"目标函数求最小min值"<<"\n"; for(i=0;i for(j=0;j c_b[i]+=c[i][j]*x[j][p]; intt,s; for(i=0;i { if(c_b[i] {p++; for(s=0;s { c_b[s]=0; } for(t=0;t for(j=0;j c_b[t]+=c[t][j]*x[j][p]; i=-1; } if(p>pow(2,n)-1) {cout<<"无可行解"<<"\n"; break; } } //产生过滤条件。 for(j=0;j z+=a[j]*x[j][p]; //改进过滤条件,求最优解的过程。 floattemp; intl,w; e=p; f=p; while(p<=pow(2,n)-1) { temp=0.0; for(j=0;j { temp+=a[j]*x[j][p]; } if(temp>z) { p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } if(temp<=z) { for(l=0;l { if(c_b[l]>=b[l]); elsebreak; } if(l==m) { z=temp; e=p; p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } elseif(l { p++; for(w=0;w { c_b[w]=0; } for(t=0;t for(s=0;s c_b[t]+=c[t][s]*x[s][p]; } } } if(f {cout< "<<"\n"; cout<<"z="< cout<<"最优解为,即x1,x2,x3......的取值: "<<"\n"; for(j=0;j cout< cout<<"\n"; } } cout< cout<<"程序结束"<<"\n"; } 三、解题如下 例题: Maxz=3x1-2x2+5x3St.x1+2x2-x3<=2 x1+4x2+x3<=4 x1+x2<=3 4x1+x3<=6 m行: 4 n列: 3 目标系数: a[3]={3,-2,5} 系数矩阵: c[4][3]={{1,2,-1},{1,4,1},{1,1,0},{4,0,1}} b列值: b[3]={2,4,3,6} 运行结果如图: 四、实验总结 通过本次上机实验,使我对整数规划隐枚举法解题有了更加深入的了解,也复习了c++编程技术。 进一步知道了整数规划隐枚举法运行过程中易出错的地方,进一步掌握了整数规划隐枚举法解题的技巧。 五、参考文献 《运筹学教程》(第三版)清华大学出版社
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划 枚举 实验 报告