整数规划分枝定界法模型研究.docVIP

《运筹学》课程设计 整数规划分枝定界法模型研究 一．设计题目：整数规划分枝定界法模型研究 某公司计划用资金60万元来购买A、B、C三种运输汽车。已知A种汽车每辆1万元，每班需一名司机，可完成2100t?km。B种汽车每辆2万元，每班需两名司机、可完成3600t?km。C种汽车每辆2.3万元、每班需要两名司机、可完成3780t?km。每辆汽车每天最多安排三班，每个司机每天最多安排一班。购买汽车的数量不能超过30辆、司机不超过145人。问：每种汽车应购买多少辆，可使该公司今后每天完成的t?km数最大？ 二、理论分析、研究方法、编程思路 利用整数规划的分支定界法，配合单纯型法及对偶单纯型法（交替单纯型法）的运算步骤进行编程。对于分支的情况进行判断，调用不同的方法函数。 三．数学模型 设买A种车分别用于每天安排一班，二班，三班的为X1，X2，X3；同样设买B种车的为X4，X5，X6；C种车：X7，X8，X9。 max 21x1+42x2+63x3+36x4+72x5+108x6+37.8x7+75.6x8+113.4x9 s.t.?? x1+x2+x3+2x4+2x5+2x6+2.3x7+2.3x8+2.3x960 x1+x2+x3+x4+x5+x6+x7+x8+x930 x1+2x2+3x3+2x4+4x5+6x6+2x7+4x8+6x9145 Xj=0(j=1,2…..9),且为整数 四．程序 用C++编出程序计算 #includeiostream #includeiomanip #includecmath using namespace std; int main() { int jibianhuan(double**,int,int); int liangjieduan(double**,int,int); int danchunxinfa(double**,double*,int,int); int zhengshuguihua(double**,double*,int,int); double f(double a);//取整函数 cout.precision(3); cout\n\n\t\t欢迎使用单纯形法及整数规划求解程序!endlendlendl; cout\t1.单纯形法求解endl\t2.整数规划求解endl\t3.退出endlendl; cout请输入下一步操作:; int index; cinindex; double **a; double*p; int m,n,i,j; while(index!=3) { cout输入变量个数:; cinn; cout输入约束条件个数:; cinm; a=new double*[m+2]; for(i=0;im+2;i++) a[i]=new double[n+1]; p=new double[n+1]; cout输入约束条件中右边b的值:; for(i=1;im+1;i++) cina[i][0]; cout输入约束条件的增广矩阵：endl; for(i=1;im+1;i++) for(j=1;jn+1;j++) cina[i][j]; cout请输入目标函数：; for(i=1;in+1;i++) cinp[i]; p[0]=0; if(index==1) danchunxinfa(a,p,n+1,m+2); else if(index==2) zhengshuguihua(a,p,n+1,m+2); cout\n\n\n\t\t欢迎使用单纯形法及整数规划求解程序!endlendlendl; cout\t1.单纯形法求解endl\t2.整数规划求解endl\t3.退出endlendl; cout请输入下一步操作:; cinindex; } /*//输出两阶段法的第一个表 for(i=0;im+2;i++) { coutendl; for(j=0;jn+1;j++) coutsetw(7)a[i][j]; } coutendl;*/ return 0; } int liangjieduan(double**b,int n,int m) { int jibianhuan(double**,int,int); int i,j,index,tempi,tempj,k=0; double temp; double**a; a=new double*[m+2]; for(i=0;im+2;i++) a[i]=new double[n+m+1]; //对加入人工变量后的矩阵赋初值 for(i=0;in+1;i++)//第一行(表示该列是否为基矩阵) a[0][i]=0; for(i=n+1;in+m+1;i++)//第一行 a[0][i]=i-n; for(i=1;im+1;i++