线性规划问题

线性规划问题 一 实验课题 某牧场饲养一批动物，平均每头动物需要700g蛋白质，30g矿物质和100g维生素。现有五种饲料可供选择，每千克饲料的营养成分（单位：g）与价格（单位：元/kg）如下表所示： 蛋白质 矿物质 维生素 价格 A 3 1.0 0.5 0.4 B 2 0.5 1.0 1.4 C 1 0.2 1.2 0.8 D 6 2.0 2.0 1.6 E 12 0.5 0.8 1.6试求能满足动物生长营养需求又最经济的选饲料方案。二. 实验内容1. 单纯形法求解 下面建立描述这一问题的数学模型。利用单纯形法和Matlab的优化工具箱求解。 设x1,x2,x3,x4和x5分别表示这五种饲料的用量（x1,x2,x3,x4和x5是决策变量）。显然，我们的目标是在不小于所需求量的条件下，如何确定五种饲料x1,x2,x3,x4,x5的用量以使所用的资金最少。用Z表示所用的总的资金，那么，这样，该规划问题可用数学模型表示为： Z=0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5 目标函数 Min Z= 0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5 约束条件 0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5>=0.7 0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5>=0.03 0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5>=0.1 x1>=0,x2>=0,x3>=0,x4>=0,x5>=0 这是一个含5个变量的线性规划模型，它是求一个线性函数在非负自变量受到线性不等式约束时的极值问题，所求极值问题的解即为线性规划的最优解。 由于上述数学模型不是线性规划的标准型，因此需要把它化为标准型，其标准型为： 目标函数 Max Z=-0.4*x1-1.4*x2-0.8*x3-1.6*x4-1.6*x5+0*x6+0*x7+0*x8 约束条件 0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5-x6=0.7 0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5-x7=0.03 0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5-x8=0.1 Xk>=0,k=1,2,3,4,5,6,7,8 在标准型下，其约束条件的系数矩阵为 A= 0.003 0.002 0.001 0.006 0.012 -1 0 0 0.001 0.0005 0.0002 0.002 0.0005 0 -1 0 0.0005 0.001 0.0012 0.002 0.0008 0 0 -1 =(p1 p2 p3 p4 p5 p6 p7 p8) 可见，x6,x7,x8的系数列向量 p6=(-1 0 0) p7=(0 -1 0) p8=(0 0 -1) 为矩阵A的列向量的一个极大线性无关组，是基向量，相应的变量x6,x7,x8是基量，而其余的变量x1,x2,x3,x4,x5成为非基变量。从标准型可得 X6=0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5-0.7 X7=0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5-0.03 （1） X8=0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5-0.1 将（1）代入目标函数有 Z=-0.4*x1-1.4*x2-0.8*x3-1.6*x4-1.6*x5 (2) 在（1）式中令非基变量x1=x2=x3=x4=x5=0,就得Z=0, X=(0,0,0,0,0,-0.7,-0.03,-0.1)。 这个解表明：牧场没有选用饲料x1,x2,x3,x4,x5,所以消耗的资金Z=0。分析目标函数的表达式（2）可知：非基变量的系数都是负数，而根据实际情况应当选用它们中的一部分，所以就需要将非基变量与基变量进行对换。确定x5为换入变量，x6为换出变量，则（1）变成： X5=56+80*x6-0.24*x1-0.16*x2-0.08*x3-0.48*x4 X7=-0.002+0.00088x1+0.00492*x2+0.00199*x3+0.00176*x4+0.04*x6 (3) X8=-0.0552+0.000308*x1+0.000872*x2+0.001136*x3+0.001616*x4+0.064*x6将（3）代入目标函数Z=-89.6-0.784*x1-1.656*x2-0.928*x3-20368*x4-128*x6 令非基变量x1=x2=x3=x4=x6=0,得 Z=-89.6 而此时基变量x7=-0.002,x8=-0.0552,均小于0，不满足约束条件，因此，该组解不是一组可行解。 再确定x1为换入变量，x8为换出变量，则（3）变成： X5=0.512*x2+0.808*x3+0.768*x4+1290872*x6-779.232*x8+12.992 X7=0.0025*x2-0.0013*x3-0.0028*x4-0.1429*x6+2.8572*x8+0.1557 (4) X1=-2.8*x2-3.7*x3-5.2*x4-207.8*x6+3246.8*x8+179.2 将（4）代入目标函数有： Z=-1.0992*x2-0.6128*x3-0.7488*x4-124.6752*x6-51.9488*x8-92.4672 其中所有的非基变量x2,x3,x4,x6,x8前面的系数都是负的，这说明只有x2=x3=x4=x6=x8=0时，目标函数达到最大值。即当A种饲料选用179.2g,E种饲料选用12.992g时，所消耗的资金最少。 由此 便得到了该线性规划问题的最优解。2. Matlab优化工具箱求解将上述数学模型化为可以使用linprog命令的如下形式： 目标函数 Min Z= 0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5 约束条件 -0.003*x1-0.002*x2-0.001*x3-0.006*x4-0.012*x5<=-0.7 -0.001*x1-0.0005*x2-0.0002*x3-0.002*x4-0.0005*x5<=-0.03 -0.0005*x1-0.001*x2-0.0012*x3-0.002*x4-0.0008*x5<=-0.1在命令窗口键入命令： c=0.4,1.4,0.8,1.6,1.6;a=-0.003 -0.002 -0.001 -0.006 -0.012;.-0.001 -0.0005 -0.0002 -0.002 -0.0005;. -0.0005 -0.001 -0.0012 -0.002 -0.0008;b=-0.7 -0.03 -0.1;x=linprog(c,a,b,zeros(1,2,3,4,5),z=c*x 运行后得到如下结果： x = 195.1016 0.0000 0.0000 0.0000 9.5579z = 93.3333 由上可以看出，利用两种方法求得的解几乎是一致的，都是解决线性规划问题的有效方法，但更加方便，更加快捷的方法是使用Matlab优化工具箱