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单纯形法(Dant
5、zig G.B.,1947)单纯形法(simplex methods)是从可行域的一个顶点到相邻的使目标函数值严格下降的另一个顶点迭代，直到达到最优点它是非多项式时间算法但在概率平均意义下不仅时间复杂性是多项式的，并且是线性时间复杂性，这就解释了为什么它在实践中的高效性这是一个在实践中久经考验的算法，是用得最多的算法，至今仍然是好的选择许多线性规划软件中实现了此算法第一步：作单纯形表. (1)把原线性规划问题化为标准形式； (2)找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； (3)目标函数非基化； (4)作初始单纯形表. 第二步：最优解的判定. (1)若所有检验数都是非正数，则此时线
6、性规划问题已取得最优解. (2)若存在某个检验数是正数，而所对应的列向量无正分量，则线性规划问题无最优解. (3)如果以上两条都不满足，则进行下一步. 第三步：换基迭代. (1)找到最大正检验数，并确定其所在列的非基变量为进基变量. (2)对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者； (3)换基：用进基变量替换出基变量，从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基； (4)利用矩阵的行初等变换，将主元变为 1，其所在列其他元素都变为零，从此得到新的单纯形表； (5)
7、回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.今需合成一种新材料，该材料中必须含有元素 A 和元素 B, 其含量不得少于 9,19。今有 6 种原料中都可以提取出该两种元素，每种原料的价格及其所含的 A、B，如下表所示：原料元素每单位原料一 二 三 四 五 六最小含量A 1 0 2 2 1 2 9B 0 1 3 1 3 2 19价格 35 30 60 50 27 22#include #include #include #define M 30000int r,c; /global parameter row and colum;int turn = 1;i
8、nt variable = 0; /自变量个数 ,初始化为零,在 main 函数中设定int restriction = 0; /约赖条件个数int maxormin = 0;int loose = 0; /松驰变量int remain = 0; /剩余变量int dummy = 0; /虚拟变量void title()cout 0 if(maxormin=1)cout=或strainij;if(strainij=0)dummy+;coutn“;elsecoutstrainij;for(i=0; it“;elsecout“=t“;elsecoutstrainij“t“;coutendl;cou
9、t“对吗?“;getchar();r = restriction+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 = var
10、iable; j+)ptrij = 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
11、; j+)if(i1 = j1)ptrij=1;elseptrij=0;j1+;i1+;for(i=0;ir;i+)for(j=0;jc;j+)coutptrij“t“;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;ptr22=0;ptr23=1
12、; 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;ptr15=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;
