规划数学大作业

PAGE规划数学大作业学院：控制与计算机工程学号：1122227184姓名：贺焕PAGE1目录1问题背景描述 12问题建模 23计算机求解 34结果分析 45附录 6PAGE11问题背景描述从1947年丹捷格（G.B.Dantzig）提出单纯形求解方法以来，线性规划作为运筹学的一个重要分支，无论是在理论方面还是在算法方面都日益趋向成熟和完善，并在实践中取得了良好的应用效果；尤其是随着计算机处理能力的不断提高，使其得以更广泛的应用。规划问题往往与资源的有限性密切相关，处理的是有限资源条件下的成本最小或利润最大等问题。在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。以下对一个生产管理问题进行分析和研究。某工厂在某一计划期内准备生产甲、乙、丙三种产品，生产需要消耗A、B、C三种资源，已知各种产品中A、B、C的含量，原料成本，各种原料的每月限制用量，三种产品的单位加工费及售价如下表1所示。表1原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%25%2.002000B20%25%25%1.502500C20%60%50%1.001200加工费（元/千克）0.500.400.30售价3.402.852.25每月应生产这三种产品各多少千克，才能使该厂获利最大呢？对于此问题可以考虑建立线性规划的数学模型进行求解，针对此问题建立数学模型。

2问题建模针对上面提出的问题，用以下的数学模型来描述，设x1、x2、x3分别表示每月应生产甲、乙、丙这三种产品的千克数。因为原料A、B、C的限量，可以得到以下不等式：该厂的目标是在不超过所有资源限量的条件下，如何确定产量x1、x2、x3以得到最大的利润。若用z表示利润，这时综合上述，该计划问题可用数学模型表示为：目标函数：满足约束条件：

3计算机求解单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。对于上面建立的数学模型考虑用单纯形法进行求解。引入松弛变量x4、x5、x6。将目标函数整理得：约束条件变为：由上述数据即可构造初始单纯形表，如表2所示。表2cj1.21.1750.575000CBXBbx1x2x3x4x5x60x420000.600.150.251000x525000.200.250.250100x612000.200.600.50001使用计算机求解得到最优解为：X*=(3090.91,969.697,0,0,1639.39,0)T目标函数值为：z*=4848.48

4结果分析根据以上的计算结果可以知道，每月生产甲产品3090.91千克，乙产品969.697千克，不生产丙产品，可使该厂获利最大，达到4848.48元。讨论线性规划问题时，假定aij、bi、cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。以下将针对上述模型中的cj、bi的变化进行讨论。当cj是非基变量xj的系数时，若满足，则原最优解仍然为最优解，否则需重新计算。假设丙产品开始畅销，其售价由原来的2.25元/千克上涨至3元/千克。那么重新计算的结果为：每月生产甲产品2800千克，丙产品1280千克，不生产乙产品，可使该厂获利最大，达到5056元。若售价由原来的2.25元/千克上涨至2.75元/千克。重新计算的结果仍然为原最优解。由以上分析中的公式可知丙产品售价小于2.837879元/千克时，原最优解不变。以上两组数据验证了这一灵敏度分析。当cj是基变量xj的系数时，若满足，j=1，2，…，n，则原最优解仍然为最优解，否则需重新计算。假设甲产品开始畅销，其售价由原来的3.40元/千克上涨至6元/千克。那么重新计算的结果仍然为原最优解。若甲产品开始滞销，其售价由原来的3.40元/千克下调至2.5元/千克。那么重新计算的结果为：每月生产乙产品2000千克，不生产甲产品和丙产品，可使该厂获利最大，达到2350元。由以上分析中的公式，j=1，2，…，n，可知甲产品的售价介于2.59和6.9元/千克之间时最优解不变。以上两组数据验证了这一灵敏度分析。当br发生变化时，若满足，则原最优基不变，但最优解的值发生了变化，所以为新的最优解。假设工厂新增了原料B，每月的限制用量上调至3000千克，那么重新计算的结果为：每月生产甲产品3090.91千克，生产乙产品969.697千克，不生产丙产品，可使该厂获利最大，达到4848.48元。若工厂减少了原料B，每月的限制用量下调至500千克，那么重新计算的结果为：每月生产甲产品2500千克，不生产乙产品和丙产品，可以使该厂获利最大，达到3000元。由以上分析中的公式，可知当原料B的限制用量大于530.303千克时，可以使得原最优基不变，但最优解的值会发生变化。以上两组数据验证了这一灵敏度分析。

5附录计算机求解使用的语言是C++，实现代码如下所示：#include<iostream>usingnamespacestd;intmain(intargc,_TCHAR*argv[]){ intM,N,XB[100],human[100],num,i,j,k,l; floatA[100][100],a[100][100],b[100],th[100],C[100],cj_zj[100],CB[100]; //获取初始数据 cout<<"构建初始单纯形表。"<<endl <<"输入决策变量的个数N="; cin>>N; cout<<"输入价值向量C："; for(i=0;i<N;i++) { cin>>C[i]; } cout<<"输入约束方程组中方程的个数M="; cin>>M; cout<<"输入约束方程组的增广矩阵："<<endl; for(i=0;i<M;i++) { for(intj=0;j<N;j++) { cin>>A[i][j]; } cin>>b[i]; } cout<<"输入初始的CB："; for(i=0;i<M;i++) { cin>>CB[i]; } cout<<"输入初始的XB："; for(i=0;i<M;i++) { cin>>XB[i]; XB[i]--; } cout<<"输入人工变量的个数："; cin>>num; if(num>0) { cout<<"输入人工变量："<<endl; for(i=0;i<num;i++) { cin>>human[i]; human[i]--; } }loop: //计算cj-zj cout<<"cj-zj为："<<endl; for(j=0;j<N;j++) { boolflag=false; for(i=0;i<M;i++) { if(j==XB[i]) { flag=true; break; } } if(flag) { cj_zj[j]=0; cout<<cj_zj[j]<<""; continue; } floatsum=0; for(i=0;i<M;i++) { sum+=CB[i]*A[i][j]; } cj_zj[j]=C[j]-sum; cout<<cj_zj[j]<<""; } cout<<endl<<endl; //判断是否所有cj-zj<=0 for(j=0;j<N;j++) { if(cj_zj[j]>0) { break; } } if(j<N) { for(i=0;i<M;i++) { if(A[i][j]>0) { break; } } if(i<M) { //确定换入变量 floatmaxj=0; k=0; for(j=0;j<N;j++) { if(cj_zj[j]>maxj) { k=j; maxj=cj_zj[j]; } } cout<<"换入变量为："<<k+1<<endl<<endl; //求旋转变量 cout<<"旋转变量为："; for(i=0;i<M;i++) { if(A[i][k]>0) { th[i]=b[i]/A[i][k]; } else { th[i]=-1; } cout<<th[i]<<""; } cout<<endl<<endl; //确定换出变量 floatminj=1000000; for(i=0;i<M;i++) { if(th[i]<0) { continue; } if(th[i]<minj) { minj=th[i]; /*l=XB[i];*/ l=i; } } cout<<"换出变量为："<<XB[l]+1<<endl<<endl; //迭代运算 XB[l]=k; CB[l]=C[k]; floatbb[100]; for(i=0;i<M;i++) { for(j=0;j<N;j++) { a[i][j]=A[i][j]; } bb[i]=b[i]; } b[l]=bb[l]/a[l][k]; for(j=0;j<N;j++) { A[l][j]=a[l][j]/a[l][k]; } for(i=0;i<M;i++) { if(i==l) { continue; } for(j=0;j<N;j++) { A[i][j]=a[i][j]-A[l][j]*a[i][k]; } b[i]=bb[i]-b[l]*a[i][k]; } cout<<"增广矩阵为："<<endl; for(i=0;i<M;i++) { for(j=0;j<N;j++) { cout<<A[i][j]<<""; } cout<<b[i]<<endl; } cout<<endl; gotoloop; } else { cout<<"此问题无界！"<<endl; return0; } } else { for(i=0;i<M;i++) { for(j=0;j<num;j++) { if(XB[i]==human[j]&&CB[i]!=0) { cout<<"此问题无可行解！"<<endl; return0; } } } for(i=0;i<N;i++) { for(j=0;j<M;j++) { if(i==XB[j]) { break; } } if(j<M) { continue; } else { if(cj_zj[i]==0) { cout<<"此问题有无穷多最优解！"<<endl; return0; } } } cout<<"此问题有唯一解！"<<endl; cout<<"最优解为："<<endl; floatX[100]; for(