《塑性加工中的线性规划问题.doc》由会员分享，可在线阅读，更多相关《塑性加工中的线性规划问题.doc（19页珍藏版）》请在三一文库上搜索。
1、塑性加工中的线性规划问题1线性规划问题的教学模型线性规划研究的是线性目标函数在线性约束条件下取最大值或最小值问题，一般地，线性规划问题的数字模型是已知 其中 都是常数， 是非负变量，求 的最大值或最小值，这里 是常量。这是两个变量的线性规划问题，这类问题可以用图解法来求最优解，涉及更多变量的线性规划问题不能用图解法求解。比如线性不等式 不能用图形来表示它，那么对四元线性规划问题就不能用图形来求解了。线性规划在材料学中应用较为广泛，例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小等等。实例1：某家具厂有方木料 ，五合板 ，准备加工成书桌和书橱出售，已知生产每张书桌需要方木料 、五合
2、板 ，生产每个书橱需要方木料 、五合板 ，出售一张书桌可获利润80元，出售一个书橱可获利润120元，如果只安排生产书桌，可获利润多少？如何只安排生产书橱，可获利润多少？怎样安排生产时可使所得利润最大？（1）先将已知数据列成下表（2）设生产书桌x张，生产书橱y张，获利润为z元。分析：显然这是一个二元线性问题，可归结于线性规划问题，并可用图解法求解。（3）目标函数 在第一个问题中，即只生产书桌，则 ，约束条件为 最多生产300张书桌，获利润 元这样安排生产，五合板先用光，方木料只用了 ，还有 没派上用场。在第二个问题中，即只生产书橱，则 ，约束条件是 最多生产600张书橱，获利润 元这样安排生产，
3、五合板也全用光，方木料用去了 ，仍有 没派上用场，获利润比只生产书桌多了48000元。在第三个问题中，即怎样安排生产，可获利润最大？ ，约束条件为 对此，我们用图解法求解，先作出可行域，如图阴影部分。 时得直线 与 平行的直线 过可行域内的点M（0，600）。因为与 平等的过可行域内的点的所有直线中， 距原点最远，所以最优解为 ，即此时 因此，只生产书橱600张可获得最大利润，最大利润是72000元。B讨论为什么会出现只生产书橱，可获最大利润的情形呢？第一，书橱比书桌价格高，因此应该尽可能多生产书橱；第二，生产一张书橱只需要五合板 ，生产一张书桌却需要五合板 ，按家具厂五合板的存有量 ，可生产
4、书橱600张，若同时又生产书桌，则生产一张书桌就要减少两张书橱，显然这不合算；第三，生产书橱的另种材料，即方木料是足够供应的，家具厂方木料存有量为 ，而生产600张书橱只需要方木料 。这是一个特殊的线性规划问题，再来研究它的解法。C改变这个例子的个别条件，再来研究它的解法。将这个例子中方木料存有量改为 ，其他条件不变，则作出可行域，如图阴影部分，且过可行域内点M（100，400）而平行于 的直线 离原点的距离最大，所以最优解为（100，400），这时 （元）。故生产书桌100、书橱400张，可获最大利润56000元。 2单纯形法(Dantzig G.B.,1947) 单纯形法(simplex
5、methods)是从可行域的一个顶点到相邻的使目标函数值严格下降的另一个顶点迭代，直到达到最优点它是非多项式时间算法但在概率平均意义下不仅时间复杂性是多项式的，并且是线性时间复杂性，这就解释了为什么它在实践中的高效性这是一个在实践中久经考验的算法，是用得最多的算法，至今仍然是好的选择许多线性规划软件中实现了此算法第一步：作单纯形表. (1)把原线性规划问题化为标准形式； (2)找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； (3)目标函数非基化； (4)作初始单纯形表. 第二步：最优解的判定. (1)若所有检验数都是非正数，则此时线性规划问题已取得最优解. (2)若存在某个检验数是正数
6、，而所对应的列向量无正分量，则线性规划问题无最优解. (3)如果以上两条都不满足，则进行下一步. 第三步：换基迭代. (1)找到最大正检验数，并确定其所在列的非基变量为进基变量. (2)对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者； (3)换基：用进基变量替换出基变量，从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基； (4)利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； (5)回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭
7、代，直到问题得到解决为止.今需合成一种新材料，该材料中必须含有元素A和元素B, 其含量不得少于9,19。今有6种原料中都可以提取出该两种元素，每种原料的价格及其所含的A、B，如下表所示：原料元素每单位原料一 二 三 四 五 六最小含量A1 0 2 2 1 29B0 1 3 1 3 219价格35 30 60 50 27 22#include #include #include #define M 30000int r,c; /global parameter row and colum;int turn = 1;int variable = 0; /自变量个数,初始化为零,在main函数中设定
8、int restriction = 0; /约赖条件个数int maxormin = 0;int loose = 0; /松驰变量int remain = 0; /剩余变量int dummy = 0; /虚拟变量void title() cout-endlendl; cout 塑性加工优化单纯形(大M法)计算endlendl; cout programmed by:黄俊endl; cout-endl;float *acquireM(int row1, int colomn1) /creat a matrix int i; float *ptr1; ptr1 = new float *row1;
9、 for(i = 0; i 0 & i c) if(i r) i = i + (c - r); else i = i - r + 1; else i = -1; return i;*/void inputobject(float *Min, int temp) int i; if(maxormin=1) coutMin = a(; else coutMax = a(; for(i=0; itemp-1; i+) couti+1)Xi+1+a(; couttemp)endl; for(i=0; itemp; i+) couta(i+1)Mini; if(maxormin=1) cout目标函数为
10、: Min = ; else cout目标函数为: Max = ; for(i=0; itemp-1; i+) coutMini Xi+1 + ; coutMintemp-1 对吗?; getchar(); if(maxormin=2) coutn目标函数被转化为: Min = ; for(i=0; itemp-1; i+) Mini=(-1)*Mini; coutMini Xi+1 + ; Mintemp-1=(-1)*Mintemp-1; coutMintemp-1endlendl; void inputstrain(float *strain, int *xx) int i,j; for
11、(i=0; irestriction; i+) cout第i+1个约束条件:t; for(j=0; jvariable; j+) cout+a(i+1,j+1)X(j+1); cout=或 b(i+1)endl; for(j=0; jvariable+2; j+) if(j=variable) do cout等于号请输0,小于号请输1,大于号请输2strainij; if(strainij=0) dummy+; cout=n; else if(strainij=1) loose+; coutn; else if(strainij=2) remain+; dummy+; coutn; else
12、cout输入不对,请重输endl; while( strainij!= 0 & strainij != 1 & strainij != 2 ); else couta(i+1,j+1) ?strainij; for(i=0; irestriction; i+) coutt; for(j=0; jvariable+2; j+) if(j=variable) if(strainij=1) coutt; else if (strainij=2) coutt; else cout=t; else coutstrainijt; coutendl; cout对吗?; getchar(); r = rest
13、riction+1; c = variable+restriction+remain+1; for(i=0;irestriction;i+) xxi=i+variable+1;int initiateM(float *ptr, float *strain, float *Min) /初始化单纯形表 int i, j, i1=1, j1=1; for(i = 0; i r-1; i+) ptri0 = strainivariable+1; ptrr-10 = 0; for(i = 0; i r-1; i+) /初始化非基变量列 for(j = 1; j = variable; j+) ptrij
14、 = strainij-1; for(j=1;j=variable;j+) ptrr-1j=Minj-1; for(i=0;ir-1;i+) if(strainivariable=0 | strainivariable=2) ptrr-1j-=strainij-1*M; j = variable+1; for(i = 0; i restriction; i+) if(strainivariable = 2) ptrij = (-1); ptrr-1j = M; j+; for(i=0; ir; i+) /初始化基变量列 j1=1; for(j = variable+remain+1; j c;
15、 j+) if(i1 = j1) ptrij=1; else ptrij=0; j1+; i1+; for(i=0;ir;i+) for(j=0;jc;j+) coutptrijt; coutendl; system(cls); title(); coutendl;/*void initiateM1(float *ptr) ptr00=12;ptr01=1;ptr02=0;ptr03=0;ptr04=0;ptr05=2;ptr06=2; ptr10=8; ptr11=0;ptr12=1;ptr13=0;ptr14=0;ptr15=1;ptr16=2; ptr20=16;ptr21=0;ptr2
16、2=0;ptr23=1; ptr24=0;ptr25=4;ptr26=0; ptr30=12;ptr31=0;ptr32=0;ptr33=0;ptr34=1;ptr35=0;ptr36=4; ptr40=0; ptr41=0;ptr42=0;ptr43=0;ptr44=0;ptr45=-2;ptr46=-3;void initiateM2(float *ptr) ptr00=9;ptr01=1;ptr02=0;ptr03=2;ptr04=2;ptr05=1;ptr06=2;ptr07=-1;ptr08=0; ptr10=19; ptr11=0;ptr12=1;ptr13=3;ptr14=1;p
17、tr15=3;ptr16=2;ptr17=0;ptr18=-1; ptr20=0;ptr21=0;ptr22=0;ptr23=-100; ptr24=-50;ptr25=-98;ptr26=-108;ptr27=35;ptr28=30;*/void output(float *ptr, int *xx) int i, j; cout-endl; cout基变量tBt; for(j = 1; j c; j+) coutXjt; coutendl; cout-endl; for(i = 0; i r-1; i+) cout Xxxit; for(j = 0; j c; j+) coutptrijt
18、; coutendl; cout-endl; cout itt; for(j = 1; j c; j+) coutptrr-1jt; coutendl; cout-endl;int process2(float *ptr) /第二步,确定换入变量 int j, value = 1; float min; cout第二步：确定换入变量tttttt第turn轮 1) min = ptrr-11; for(j = 1; j = ptrr-1j) min = ptrr-1j; value = j; else cout没有非基变量,无法求解!endl; exit(1); cout换入变量Xvalue:m
19、inendlendl; cout按任意键继续.endl; getchar(); return value;int process3(float *ptr, int value, int *xx) /第三步,确定主元与换出变量 int i, j, row, flag = 0; float min, kr-1; cout第三步：确定主元与换出变量ttttt第turn轮endl; for(i = 0; i 0) ki = (ptri0)/(ptrivalue); flag = 1; else ki = 0; if(flag = 0) row = -1; min = 0; else for(i = 0
20、; i r-1; i+) /find first non-zero if(ki != 0) row = i; couti+1= kit; min = ki; break; if(i != r-2 & r != 1) /find min non-zero for(j = i+1; j r-1; j+) if( kj != 0) coutj+1= kjt; if(kj = min) row = j; min = kj; coutendlr= min(; for(i = 0; i r-1; i+) if(ki != 0) coutki,; coutb)=minendl; cout主元为: a(row
21、+1,value)t换出变量为: Xxxrowendl; xxrow = value; cout按任意键继续.endl; getchar(); return row;void process4(float *ptr, int m, int n) int i, j; float temp; temp = ptrmn; for(j = 0; j c; j+) ptrmj = ptrmj/temp; cout第四步：用行变换求出新的单纯形表tttt第turn轮endl; if( m != 0) for(i = 0; i m; i+) if(ptrin != 0) temp = ptrin; for(
22、j = 0; j c; j+) ptrij = ptrij-ptrmj*temp; if(m != r-2) for(i = m+1; i r-1; i+) if(ptrin != 0) temp = ptrin; for(j = 0; j c; j+) ptrij = ptrij-ptrmj*temp; if(ptrr-1n != 0) temp = ptrr-1n; for(j = 1; j c; j+) ptrr-1j = ptrr-1j-ptrmj*temp; float result(float *ptr, float *pts, int *xx, float *Min) int i
23、, j , m, n, i1 = 1; float S=0; for(i=1;i=variable;i+) for(j=0;jrestriction;j+) if(xxj=i) ptsi-1=ptrj0; for(i = 0; i variable; i+) coutXi+1 = ptsit; if(maxormin = 1) for(i=0;ivariable;i+) S+=ptsi*Mini; i+; S+=Mini; else for(i=0;i=variable;i+) Mini=(-Mini); for(i=0;ivariable;i+) S+=ptsi*Mini; i+; S+=M
24、ini; return S;int main() int i, j, row, column, flag, *xx; float *pter,*strain, *pts, *Min,temp; title(); cout输入自变量个数variable; cout输入约束条件个数restriction; r=restriction+1; cout求最小值输入1,求最大值输入2maxormin; if(maxormin != 1 & maxormin != 2) cout输入不对,请重输endl; while( maxormin != 1 & maxormin != 2 ); Min = new
25、float variable + 1; xx = new int restriction; cout请输入目标函数:endl; inputobject(Min,variable + 1); cout请输入约束条件:endl; strain = acquireM(restriction,variable+2); inputstrain(strain,xx); pter = acquireM(r,c); pts = new float variable; initiateM(pter,strain,Min); cout第一步：作出初始单纯形表ttttt第turn轮endl; output(pter
26、,xx); cout按任意键继续.endl; getchar(); flag = 0; column = process2(pter); row = process3(pter, column,xx); if(row 0) exit(1); process4(pter, row, column); output(pter,xx); for(j = 1; j c; j+) if(pterr-1j 0) flag = 1; cout判别数存在非负：pterr-1jendl; cout重复第二步到第四步。endl; turn+; break; cout按任意键开始新的一轮.endl; getchar(); for(j = 1; j c; j+) if(pterr-1j 0) flag = 1; break; while(flag = 1) flag = 0; column = process2(pter); row = process3(pter, column,xx); if(row 0) exit(1); process4(pter, row, column); output(pter,xx);