规划数学大作业模板

规划数学大作业

学院：控制与计算机工程

学号：—

姓名：

目录

1问颍背景描述............................................1

2问题建模...............................................2

3计算机求解.............................................3

4结果分析...............................................4

5附录...................................................6

1问题背景描述

从1947年丹捷格（GB.Dantzig）提出单纯形求解方法以来，线

性规划作为运筹学的一个重要分支，无论是在理论方面还是在算

法方面都日益趋向成熟和完善，并在实践中取得了良好的应用效

果；特别是随着计算机处理能力的小断提高，使其得以更广泛的应

用。

规划问题往往与资源的有限性密切相关，处理的是有限资源条

件下的成本最小或利润最大等问题。在生产管理和经营活动中经常

提出一类问题，即如何合理地利用有限的人力、物力、财力等资

源，以便得到最好的经济效果。

以下对一个生产管理问题进行分析和研究。

某工厂在某一计划期内准备生产甲、乙、丙三种产品，生产需

要消耗A、B、C三种资源，已知各种产品中A、B、C的含量原

料成本，各种原料的每月限制用量，三种产品的单位加工费及售价

如下表1所示。

表1

原料甲乙丙原料成本（元/千克）每月限制用量（千克）

A60%15%25%2.00

B20%25%25%1.502500

C20%60%50%1.001200

加工费（元/千克）0.500.400.30

售价3.402.852.25

每月应生产这三种产品各多少千克，才能使该厂获利最大呢?

对于此问题能够考虑建立线性规划的数学模型进行求解，针对

此问题建立数学模型。

2问题建模

针对上面提出的问题，用以下的数学模型来描述，设I、X2、

X3分别表示每月应生产甲、乙、丙这三种产品的千克数。因为原

料A、B、C的限量，能够得到以下不等式：

().60否十0.1+0.25X3<2000

0.20玉+0.25与+0.25与<2500

0.20X]+0.60X2+0.50巧-1200

该厂的目标是在不超过所有资源限量的条件下，如何确定产

量X、X2、X3以得到最大的利润。若用Z表示利润，这时

Z=(3.40-0.50)再+(2.85-0.40)x2+(2.25-0.30)当

-2.()()(().6()为+().15%2+().25.q)

—1.50(0.20$+0.259+0.25X3)

一1.00(0.20为+0.60X2+O.5O^3)

综合上述，该计划问题可用数学模型表示为：

目标函数：

maxz=(3.40-0.50)x,+(2.85-0.40)x2+(2.25-0.3())当

-2.00(0.60%,+0.15X2+0.25与)

-1.5(X0.20X1+0.25X2+0.25x3)

-1.00(0.20%)+0.60X2+O.5OX3)

满足约束条件：

z

0.60Xj+0.15J2+0.25/3-2000

<0.20x,+0.25I2+O.25X3<2500

0.20./+0.60.%+0.50/V1200

、xpx2,x3>0

3计算机求解

单纯形法求解线性规划的思路：一般线性规划问题具有线性方

程组的变量数大于方程个数，这时有不定的解。但能够从线性方程

组中找出一个个的单纯形，每一个单纯形能够求得一组解，然后再

判断该解使目标函数值是增大还是变小，决定卜一步选择的单纯

形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问

题就得到了最优解。

对于上面建立的数学模型考虑用单纯形法进行求解。

引入松弛变量X5、X6o

将目标函数整理得：

maxz=1.2X1+1.175+0.575x3+0x4+0x5+O.r6

约束条件变为:

0.60X1+0.15X2+0.25X3+x4+0x5+0x6<2000

0.20xj+0.25%+0.25X3+O.r4+x5+0x6<2500

0.20x1+0.60X2+0.50^3+0x4+0x5+x6<1200

、王，工2户3，匕，毛，16NO

由上述数据即可构造初始单纯形表，如表2所示。

表2

Cj1.21.1750.575000

b

CBXBX|X2X3X4X5X6

0X40.600.150.25I00

0X525000.200.250.25010

0X612000.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、b、Cj都是常数。但实际二这

些系数往往是估计值和预测值。如市场条件一变,q值就会变化;ay

往往是因工艺条件的改变而改变；b是根据资源投入后的经济效果

决定的一种决策选择。以下将针对上述模型中的勺、bi的变化进行

讨论。

当5是非基变量$的系数时，若满足的+八9-。心7与＜0,则原

最优解依然为最优解，否则需重新计算。

假设丙产品开始畅销，其售价由原来的2.25元/千克上涨至3元

/千克。那么重新计算的结果为：每月生产甲产品2800千克，丙产品

1280千克，不生产乙产品，可使该厂获利最大，达到5056元。若售

价由原来的2.25元/千克上涨至2.75元/千克。重新计算的结果依然

为原最优解。由以上分析中的公式J+金氏有40可知丙产品售

价小于2.837879元/千克时，原最优解不变。以上两组数据验证了这

一灵敏度分析。

当cj是基变量xj的系数时，若满足邑-如"弘-八的点工。，j=l,

2,…,n,则原最优解依然为最优解，否则需重新计算。

假设甲产品开始畅销，其售价由原来的3.40元/千克上涨至6元

/千克。那么重新计算的结果依然为原最优解。若甲产品开始滞销,

其售价由原来的3.40元/千克下调至2.5元/千克。那么重新计算的

结果为：每月生产乙产品千克，不生产甲产品和丙产品，可使该厂

获利最大，达到2350元。由以上分析中的公式

j=l,2,…,n,可知甲产品的售价介于2.59和6.9元/千克之间时最优

解小变。以上两组数据验证s这一灵敏度分析。

当br发生变化时，若满足X/J=B~](/?+△/?)>(),则原最优基不变,

但最优解的值发生了变化，因此X；为新的最优解。

假设工厂新增了原料B,每月的限制用量上调至3000千克,那

么重新计算的结果为：每月生产甲产品3090.91千克，生产乙产品

969.697千克，不生产丙产品，可使该厂获利最大，达到4848.48元。

若工厂减少了原料B,每月的限制用量下调至500千克，那么重新

计算的结果为：每月生产甲产品2500千克，不生产乙产品和丙产品,

能够使该厂获利最大，达到3000元。由以上分析中的公式

X；=B'(b+附皿可知当原料B的限制用量大于530.303千克时,

能够使得原最优基不变，但最优解的值会发生变化。以上两组数据

验证了这一灵敏度分析。

5附录

计算机求解使用的语言是C++,实现代码如下所示：

#include<iostream>

usingnamespacestd;

intmain(intargc,_TCHAR*argvn)

(

intM,N,XB[lOO],human[l00],num,iJ,kJ;

floatA[100][100],a[100][100],b[100],th[100],C[100],cj_zj[100],CB

[100];

〃获取初始数据

coutv<”构建初始单纯形表。“Vendl

输入决策变量的个数N二"；

cin»N;

cout<<”输入价值向量C:

for(i=0;i<N;i++)

(

cin»C[i];

)

coutv〈”输入约束方程组中方程的个数M二”；

cin»M;

8E《”输入约束方程组的增广矩阵:"«endl;

for(i=0;i<M;i++)

for(intj=0;j<N;j++)

cin»A[i][j];

)

cin»b[i];

)

coutv<”输入初始的CB:

for(i=0;i<M;i++)

(

cin»CB[i];

)

cout<<”输入初始的XB:"；

for(i=0;i<M;i++)

(

cin»XB[i];

XB[i]-;

)

coutv〈”输入人工变量的个数:

cin»num;

if(num>0)

coutvv”输入人工变量:"«endl;

for(i=0;i<num;i++)

(

cin»human[i];

humanfil-;

)

)

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]=O;

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]«n";

)

cout«endl«endl;

〃判断是否所有cj-zj<=0

for(j=0;j<N;j++)

(

if(cj_zjU]>0)

break;

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];

)

coul<<”换入变量为："«k+I«endl«endl;

〃求旋转变量

coutvv”旋转变量为：

for(i=0;i<M;i++)

(

if(A[i][k]>0)

(

th[i]=b[i]/A[i][k];

)

else

(

th[i]=-l;

)

cout«th[ij«"";

)

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<v"换出变量为："«XB[1]+1«endl«endl;

〃迭代运算

XB[l]=k;

CBLlJ=C[k];

noatbb[100];

for(i=0;i<M;i++)

(

for(j=0;j<N;j++)

(

a[il[j]=A[i][j];

bb[i]=b[i];

)

b[l]=bb[l]/a[l][k];

for(j=0;j<N;j++)

An][jl=a[llfjl/a[l]fk];

)

for(i=0;i<M;i++)

(

if(i==l)

(

continue;

)

for(j=0;j<N;j++)

(

A[i]U]=a[i]U]-A[l]Ul*a[i][k];

)

b[i]=bb[i]-b[l]*a[i][k];

)

coutvv”增广矩阵为："«endl;

for(i=0;i<M;i++)

for(j=0;j<N;j++)

cout«A[i]Lj]«n";

)

cout«b[i]«endl;

)

cout«endl;

gotoloop;

)

else

(

cout«”此问题无界！"«endl;

returnO;

)

)

else

(

for(i=0;i<M;i++)

(

for(j=0;j<num;j++)

if(XB[i]==human[j]&&CB[i]!=0)

cout<<”此问题无可行解！“<<endl;

returnO;

)

)

)

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]==O)

coutv<”此问题有无穷多最优解！“<<endl;

returnO;

)

)

)

coutvv”此问题有唯一解！”《endl;

coutvv”最优解为:H«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]«nn;

)

cout«endlv<”目标函数值为：

floatsuin=0;

for(i=0;i<M;i++)

sum+=CB[i]*b[i];

cout«sum«endl;

returnO;

运行截图如下:

初

第

祟

纯

表

建

困

。

数

量

典

又

入

个6

值N=

题l

向

入-1H1

约

程•

白0R

中

BC.组47^5

方

人

则

羹

M广^

组

巨

0知

的

削

方

入g:

L60S1020

.2

L200.1255025010250800

■*

L20L6。0000

灾

台

人.5

9力^000

CB•

刀2

入•

台46

幽

・

XB量

・