线性规划问题

一． 实验课题

某牧场饲养一批动物,平均每头动物需要700g蛋白质,30g矿物质和100g维生

素;现有五种饲料可供选择,每千克饲料的营养成分单位：g与价格单位：元/kg如下表所示： 蛋白质 3 2 1 6 12 矿物质 维生素 价格 A B C D E 试求能满足动物生长营养需求又最经济的选饲料方案;

二. 实验内容

1. 单纯形法求解

下面建立描述这一问题的数学模型;利用单纯形法和Matlab的优化工具箱求解; 设x1,x2,x3,x4和x5分别表示这五种饲料的用量x1,x2,x3,x4和x5是决策变量;显

然,我们的目标是在不小于所需求量的条件下,如何确定五种饲料x1,x2,x3,x4,x5的用量以使所用的资金最少;用Z表示所用的总的资金,那么,这样,该规划问题可用数学模型表示为： Z=x1+x2+x3+x4+x5 目标函数

Min Z= x1+x2+x3+x4+x5

约束条件

x1+x2+x3+x4+x5>= x1+x2+x3+x4+x5>= x1+x2+x3+x4+x5>=

x1>=0,x2>=0,x3>=0,x4>=0,x5>=0

这是一个含5个变量的线性规划模型,它是求一个线性函数在非负自变量受到线性不

等式约束时的极值问题,所求极值问题的解即为线性规划的最优解;

由于上述数学模型不是线性规划的标准型,因此需要把它化为标准型,其标准型为： 目标函数

Max Z=x5+0x6+0x7+0x8 约束条件

x1+x2+x3+x4+x5-x6= x1+x2+x3+x4+x5-x7= x1+x2+x3+x4+x5-x8=

Xk>=0,k=1,2,3,4,5,6,7,8 在标准型下,其约束条件的系数矩阵为 A=

-1 0 0

0 -1 0 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=x1+x2+x3+x4+ X7=x1+x2+x3+x4+ 1 X8=x1+x2+x3+x4+ 将1代入目标函数有

Z=x5 2

在1式中令非基变量x1=x2=x3=x4=x5=0,就得Z=0, X=0,0,0,0,0,,,’; 这个解表明：牧场没有选用饲料x1,x2,x3,x4,x5,所以消耗的资金Z=0;分析目标

函数的表达式2可知：非基变量的系数都是负数,而根据实际情况应当选用它们中的一部分,所以就需要将非基变量与基变量进行对换;确定x5为换入变量,x6为换出变量,则1变成：

X5=56+80x4

X7=++x2+x3+x4+x6 3 X8=+x1+x2+x3+x4+x6

将3代入目标函数Z= 令非基变量x1=x2=x3=x4=x6=0,得 Z=

而此时基变量x7=,x8=,均小于0,不满足约束条件,因此,该组解不是一组可行解; 再确定x1为换入变量,x8为换出变量,则3变成： X5=x2+x3+x4+1290872x8+ X7=x6+x8+ 4 X1=x6+x8+

将4代入目标函数有： Z=

其中所有的非基变量x2,x3,x4,x6,x8前面的系数都是负的,这说明只有

x2=x3=x4=x6=x8=0时,目标函数达到最大值;即当A种饲料选用,E种饲料选用时,所消耗的资金最少; 由此 便得到了该线性规划问题的最优解;

2. Matlab优化工具箱求解

将上述数学模型化为可以使用linprog命令的如下形式：

目标函数

Min Z= x1+x2+x3+x4+x5 约束条件

x5<= x5<= x5<=

在命令窗口键入命令：

c=,,,,;

a= ;... ;... ; b= ;

x=linprogc,a,b,,,zeros1,2,3,4,5,z=cx

运行后得到如下结果： x =

z =

由上可以看出,利用两种方法求得的解几乎是一致的,都是解决线性规划问题的有效方法,但更加方便,更加快捷的方法是使用Matlab优化工具箱