规划数学大作业模板.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。

规划数学大作业

学院: 控制与计算机工程
学号:
姓名: 贺焕

目录
1 问题背景描述 1
2 问题建模 2
3 计算机求解 3
4 结果分析 4
5 附录 6

1问题背景描述
从1947年丹捷格( G.B.Dantzig) 提出单纯形求解方法以来, 线性规划作为运筹学的一个重要分支, 无论是在理论方面还是在算法方面都日益趋向成熟和完善, 并在实践中取得了良好的应用效果; 特别是随着计算机处理能力的不断提高, 使其得以更广泛的应用。
规划问题往往与资源的有限性密切相关, 处理的是有限资源条件下的成本最小或利润最大等问题。在生产管理和经营活动中经常提出一类问题, 即如何合理地利用有限的人力、 物力、 财力等资源, 以便得到最好的经济效果。
以下对一个生产管理问题进行分析和研究。
某工厂在某一计划期内准备生产甲、 乙、 丙三种产品, 生产需要消耗A、 B、 C三种资源, 已知各种产品中A、 B、 C的含量, 原料成本, 各种原料的每月限制用量, 三种产品的单位加工费及售价如下表1所示。
表1
原料
甲
乙
丙
原料成本( 元/千克)
每月限制用量( 千克)
A
60%
15%
25%
2.00

B
20%
25%
25%
1.50
2500
C
20%
60%
50%
1.00
1200
加工费( 元/千克)
0.50
0.40
0.30

售价
3.40
2.85
2.25

每月应生产这三种产品各多少千克, 才能使该厂获利最大呢?
对于此问题能够考虑建立线性规划的数学模型进行求解, 针对此问题建立数学模型。
2问题建模
针对上面提出的问题, 用以下的数学模型来描述, 设x1、 x2、 x3分别表示每月应生产甲、 乙、 丙这三种产品的千克数。因为原料A、 B、 C的限量, 能够得到以下不等式:

该厂的目标是在不超过所有资源限量的条件下, 如何确定产量x1、 x2、 x3以得到最大的利润。若用z表示利润, 这时

综合上述, 该计划问题可用数学模型表示为:
目标函数:

满足约束条件:

3计算机求解
单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但能够从线性方程组中找出一个个的单纯形, 每一个单纯形能够求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。
对于上面建立的数学模型考虑用单纯形法进行求解。
引入松弛变量x4、 x5、 x6。
将目标函数整理得:

约束条件变为:

由上述数据即可构造初始单纯形表, 如表2所示。
表2
cj
1.2
1.175
0.575
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
0
x4

0.60
0.15
0.25
1
0
0
0
x5
2500
0.20
0.25
0.25
0
1
0
0
x6
1200
0.20
0.60
0.50
0
0
1
使用计算机求解得到最优解为: 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元/千克。那么重新计算的结果为: 每月生产乙产品 千克, 不生产甲产品和丙产品, 可使该厂获利最大, 达到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(i=0;i<N;i++)
{
X[i]=0;
}
for(i=0;i<M;i++)
{
X[XB[i]]=b[i];
}
for(i=0;i<N;i++)
{
cout<<X[i]<<"";
}
cout<<endl<<"目标函数值为: ";
floatsum=0;
for(i=0;i<M;i++)
{
sum+=CB[i]*b[i];
}
cout<<sum<<endl;
return0;
}
}
运行截图如下: