线性规划之单纯形法实验指导样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。实验指导 线性规划 一、 实验目的 了解线性规划的基本知识, 熟悉应用matlab解决线性规划问题的一般方法。 二、 实验内容 1. 线性规划的基本概念 2. 生产计划问题 3. 运输问题 三、 实验仪器和设备 1. 计算机若干台( 装有matlab6.5及以上版本软件) 2. 打印机 四、 实验要求 1. 独立完成各个实验任务; 2. 实验的过程保存成 .m 文件, 以备检查; 3. 实验结果保存成 .mat 文件 五、 实验原理在生产和经营等管理工作中, 需要经常进行计划或规划。虽然内容千差万别, 但它们都有其共同点: 在现有资源限制下, 如何确定方案, 使预期目标达到最优。这能够归结为数学规划问题。在这类问题中, 最简单的是线性规划问题, 即在一组线性不等式约束下求线性目标函数的极大或极小值问题。因为线性规划问题用数学语言描述管理工作中的实际问题, 因此又被称为数学模型。建立数学模型的过程是, 由实际问题出发, 设置变量, 确定目标函数, 并根据资源条件的限制写出约束条件, 最后给出线性规划问题。本章只介绍两种典型问题的模型, 生产计划问题和运输问题。 ( 一) 线性规划的基本概念 线性规划问题是求决策变量在一组线性等式或线性不等式约束下, 使目标函数达到最小或最大值的一类优化问题。 求解线性规划问题的计算方法中最简单的是图解法, 以下面问题为例 例1 求解问题 max z = x1+ x2 s. t. 2x1+3x26 3x1+2x26 x10, x20 这是一个求函数最大值问题。其中, 变量 x1, x2, 的一组值就是实际问题中的一个决策, 因此称它们为决策变量( 也称为控制变量) 。决策变量是取实数值的连续变量。函数 z = x1+ x2 称为目标函数。而不等式组 2x1+3x26 3x1+2x26 x10, x20 称为约束条件。在图1中, 平面坐标系第一象限内由直线2x1+3x26的左下方以及直线3x1+2x26的左下方的区域正是控制变量满足约束条件的几何图形。区域中的任一点代表控制变量满足线性规划约束条件的一组值x1, x2, 称为线性规划问题的可行解。 图1 全部可行解的集合称为可行域.使线性规划的目标函数达到最优值(依具体问题,或是极大值,或是极小值)的可行解称为线性规划问题的最优解。 在这一问题中, 最优解对应于直线族x1 + x2 = c中, 与可行域相切的一条直线。切点正好是最优解(6/5, 6/5), 因为这个点在可行域的边界上正好是两直线的交点, 即方程组 的解 x1=6/5 x2=6/5 用图解法求解线性规划问题时应注意几点 1图解法适用于两个变量的线性规划问题; 2线性规划问题的解有四种情况: 有唯一最优解、 有无穷多最优解、 有无界解、 无可行解; 3线性规划问题如果有最优解,则可行域的某个顶点必定是最优解.为求最优解,可先计算可行域上某顶点的目标函数值,再考察相邻顶点处的目标函数值是否比它更优,如果为否,则这个点就是最优点;如果其它点更优,则转到其它顶点上去重复这一过程。 对于例1中目标函数最大值问题, 为了用MATLAB命令直接求解, 应转化为最小值问题, 即 min z = x1 x2 s. t. 2x1+3x26 3x1+2x26 x10, x20 取向量 cT = ( 1 1 ) bT =( 6 6 ) e0 = ( 0 0 ) 矩阵 用MATLAB求解线性规划问题命令LP的下面格式 lp(c, A, b, e0, e1) 求解该问题。输入问题中的全部数据, 并调用LP命令。程序段如下 c=-1 -1; A=2 3; 3 2; b=6; 6; e0=0 0; x=lp(c, A, b, e0) 计算机运行后的数据结果为 ans = 6/5 6/5 因此, 最优解为 x1 = 6/5 x2 = 6/5 这一结论与图解法的结果是一致的。 在MATLAB中, 常见的求解线性规划问题的命令使用格式有以下几种 (1). 最简单的调用格式: X=lp(c, A, b) (2). 使用控制变量的上、 下界调用格式: X=lp(f, A, b, vlb, vub) (3). 使用控制变量的初始点进行迭代格式: X=lp(f, A, b, vlb, vub, X0) (4). 由A和b定义的约束条件中前N个为等式约束条件使用格式: X=lp(f, A, b, vlb, vub, X0, N) ( 二) 生产计划问题 现在考虑一个生产计划问题。 例2 某工厂生产甲、 乙两种同类产品, 需要用到三种原料。两类产品中每单位的产品对三种原料的不同的需求量数据如下表所示 表1原料 甲 乙 原料可供应量 第一种原料( kg) 1 1 3500 第二种原料( kg) 1 0 1500 第三种原料( kg) 5 2 10000 单位产品利润( 元) 5 3 问如何安排生产使总利润最大? 设生产甲、 乙各x1, x2(kg), 则有如下数学模型 max z = 5 x1 + 3 x2 s.t. 由于原问题不是MATLAB所规定的标准形式, 将原问题转化为等价的线性规划问题 min z = 5 x1 3 x2 s. t. 用MATLAB求解线性规划命令求解时所需的数据结构有 , 用MATLAB求解程序段如下 c=5 3; A=1 1; 1 0; 5 2; b= 3500 1500 10000; e0=0 0; lp(-c,A,b,e0) 计算结果为 ans = 1000 2500 因此, 这一问题的最优决策是取变量 x1 = 1000 x2 = 2500 在不退出MATLAB环境条件下, 继续使用命令c*ans, 可得 ans = 12500 这说明在制定生产计划时安排甲类产品生产1000kg, 乙类产品生产2500kg, 能够在原料供应量的限制下获得最大的生产利润12500元。制定生产计划表如下 表2 甲 乙 共计 计划生产( kg) 1000 2500 3500 产品利润( 元) 5000 7500 12500 第一种原料( kg) 1000 2500 3500 第二种原料( kg) 1000 0 1000 第三种原料( kg) 5000 5000 10000 现在用人工计算的图解法验证上面结论。 为了画出约束条件 对应的三条直线图形, 需知道直线上的两个点的坐标数据。第一条直线在坐标轴上截距分别为3500, 3500。因此第一条直线过点(3500, 0), ( 0, 3500) , 它们的横坐标和纵坐标分别为3500, 0, 0, 3500。第二条直线过点(1500, 0)与X1轴相垂直, 因此它过点(1500, 0), (1500, 5000), 它们的横坐标和纵坐标分别为1500, 1500, 0, 5000。第三条直线截距分别为10000/5和10000/2, 因此它过点( , 0), (0, 5000), 它们的横坐标和纵坐标分别为 , 0, 0, 5000。 输入下面绘直线命令 line(3500, 0, 0, 3500) line(1500, 1500, 0, 5000) line( , 0, 0, 5000) 可得图形 图2 由图2可知, 需要分别求出第一条直线与第三条直线交点, 第二条直线与第三条直线交点。用求解线性方程组的左除命令 1 1; 5 23500; 100001 0; 5 21500; 10000 可得交点P13(1000, 2500), P23(1500, 1250), 由此得可行域对应的多边形角点坐标如下 P0(0, 0) P1(0, 3500) P13(1000, 2500) P23(1500, 1250) P3(1500, 0) 用填充命令 fill(0, 0, 1000, 1500, 1500, 0, 3500, 2500, 1250, 0, r), 得可行域图形。 图3将P13的坐标代入目标函数得 zmax=5100032500=12500 为了在可行域图上画出直线 5x1 + 3x2 = 12500 的图形。首先计算出该直线在坐标轴上的截距分别为: 12500/5和12500/3。使用两点绘直线命令 line(12500/5, 0, 0, 12500/3) 得直线的图形如图3所示, 直线与可行域多边形相切。切点正好是可行域的一个角点, 该角点的坐标P13(1000, 2500)就是原问题的最优解。 一般的生产计划问题可作如下描述: 有m种资源: A1, , Am, 拟生产n种产品: B1, , Bn。生产第j种产品一个单位需用第i种资源数量为aij,第i种资源的最大数量为bi,销售一个单位的第j种产品可得产值cj。现需要制定生产计划, 确定各种产品生产多少, 使利用有限资源, 获取最大的收获。可将有关数据列表如下 表3 产品类 资源类 B1 Bn A1 a11 a1n b1 . Am am1 amn bm 产值 c1 cn 设生产第j种产品的数量为xj (j=1, 2, , n)。则向量X=(x1 x2, xn)T的一组确定的值代表一个生产计划。每个产品最低产量计划为: xj ej。拟定生产计划使总产值最高。目标函数为 或 z = cT x 约束条件为 数学模型为 max z = cT x s.t. 例7.2 某工厂制造A、 B两种产品, 制造A每吨用煤9吨, 电4千瓦, 3个工作日; 制造B每吨用煤5吨,电5千瓦, 10个工作日。制造A和B每吨分别获利7000元和1 元, 该厂有煤360吨, 电力 千瓦, 工作日3000个可利用。问A、 B各生产多少吨获利最大。 首先将数据列表如下 表4 A B 上限 煤(吨) 9 5 360 电(千瓦) 4 5 工作日(天) 3 10 3000 利润(千元): 7 12 设计划生产A、 B两种产品的数量分别为x1, x2 (吨), 获得的总利润为z。则目标函数为 Z = 7x1+12x2 约束条件为各种资源的上限 9x1+5x2360 4x1+5x2200 3x1+10x2300 x10, x20 令 , , , 建立数学模型如下 max z = cTx s. t. 现在用MATLAB求解线性规划命令LP求解这一问题, 注意将极大值问题转化为极小值问题, 以便符合规定的标准形式。输入数据和求解命令如下 c=7 12 A=9 5; 4 5; 3 10 b=360; 200; 300 e0=0 0 lp(-c, A, b, e0) 最后得计算结果 ans = 20 24 这说明取决策变量 x1 = 20 x2 = 24 即计划A产品生产20吨, B产品生产24吨是最优决策。 ( 三) 运输问题 运输问题从数学模型上能够分为三类: 产销平衡运输问题、 产大于销运输问题、 销大于产运输问题。本节只介绍产销平衡的这一类。 例3从甲城调出蔬菜 吨, 从乙城调出蔬菜1100吨, 分别供应A地1700吨, B地1100吨, C地200吨, D地100吨, 每吨运费 (元)如下 表5 A地 B地 C地 D地 甲城 21 25 7 15 乙城 51 51 37 15 为了确定运费最省的调拨计划, 用x11, x12, x13, x14分别表示从甲城调往A, B, C, D四地的蔬菜量; 用x21, x22, x23, x24分别表示从乙城调往A, B, C, D四地的蔬菜量。 目标函数( 即总运费) 能够表示为 f =21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24 因为甲城和乙城共调出蔬菜3100吨, 而A地、 B地、 C地、 D地一共需要蔬菜也是3100吨, 因此这是产销平等的运输问题。由产地甲城和乙城调出的蔬菜量得约束条件为 x11 + x12 + x13 + x14 = x21 + x22 + x23 + x24=1100 由A地、 B地、 C地和D地需要的蔬菜量得另一组约束条件 x11 + x21 =1700 x12 + x22=1100 x13 + x23=200 x14 + x24 =100 显然运输量应满足非负性约束条件 xij 0, i=1,2; j= 1,2,3,4 实际问题需要求目标函数 f 的极小值, 由此得数学模型 min f = 21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24 s. t. xij0, i =1, 2; j = 1, 2, 3, 4 现在考虑用MATLAB命令求解这一数学模型。由于决策变量是二维数组, MATLAB的标准形式规定线性规划问题的决策变量为一维数组( 向量) 。做变量代换, 令 y1 = x11, y2 = x12, y3 = x13, y4 = x14 y5 = x21, y6 = x21, y7 = x21, y8 = x21 因此, 目标函数转换为 f = 21y1+25y2+7y3+15y4+51y5+51y6+37y7+15y8 约束条件转换为 y1 + y2 + y3 + y4 = y5 + y6 + y7 + y8 = 1100 y1 + y5 = 1700 y2 + y6 = 1100 y3 + y7 = 200 y4 + y8 = 100 由此得向量 y = y1 y2 y3 y4 y5 y6 y7 y8T c = 21 25 7 15 51 51 37 15T b = 1100 1700 1100 200 100T e0 =0 0 0 0 0 0 0 0 以及矩阵 写出线性规划问题如下 min F = cT y s.t. A y = b y 0 在约束条件中, 只有等式约束条件和非负约束条件。这不由于一般的MATLAB规定的标准形式, 用LP命令求解时, 必须注明由A和b定义的约束条件中前六个为等式约束条件。根据LP命令使用格式, 需要用更多参数。因此, 在使用命令时不但要给出控制变量的下界, 还需要给出控制变量的上界。因为产地的蔬菜供应量最大值为 吨, 故取向量 e1 = 为控制变量的上界。并取控制变量的初始值为 v0 =0 0 0 0 0 0 0 0 在MATLAB中输入数据和命令如下 c=21 25 7 15 51 51 37 15; b = ; 1100; 1700; 1100; 200; 100; e0= 0 0 0 0 0 0 0 0; e1 = ; v0 =0 0 0 0 0 0 0 0 A=1 1 1 1 0 0 0 0; 0 0 0 0 1 1 1 1; 1 0 0 0 1 0 0 0; 1 0 0 0 1 0 0; 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 y = lp(c, A, b, e0, e1, v0, 6) 最后得计算结果 y = 1700 100 200 0 -1/4821 1000 1/8729 100 这说明第四、 五、 七个控制变量应取值为0, 即一组最优解为 y1 = 1700 y2 = 100 y3 = 200 y4 = 0 y5 = 0 y6 = 1000 y7 = 0 y8 = 100 为了求出最优解的目标函数 F = cT y 的值, 不退出MATLAB环境, 键入命令 c*y 得数据 ans = 92100 由此可得最优解的目标函数值为92100( 元) , 最优解为 X11 = 1700 X12 = 100 X13 = 200 X14 = 0 X21 = 0 X22 = 1000 X23 = 0 X24 = 100 构造调度表如下 表6 蔬菜运输调度计划( 单位: 吨) A地 B地 C地 D地 甲城 1700 100 200 0 乙城 0 1000 0 100 六、 实验任务 1. 某糕点厂用面粉加佐料, 经过电烤生产A、 B两种饼干。已知生产A、 B两种类型的饼干各1吨所需面粉、 用电量和所得利润如下表 面粉(吨) 电(度) 利润(千元) A 0.72 80 2.1 B 0.96 60 2.2 现在每天只能供应面粉3.6吨, 电260度, 问如何生产才能获利润最大? 3.某中药厂用当归作原料, 制成当归丸和当归膏投入市场, 生产一盒当归丸和一瓶当归膏所需劳动力( 单位: 小时) 和原料( 单位: 千克) 以及工厂现有劳动力、 原料数量如下表: 当归丸 当归膏 现有资源 劳动力(小时) 4 2 4000 原料(千克) 2 4 5000 利润(元) 100 80 问中药厂应如何安排生产, 才能获利润最多? 4某种物品先存放在两个仓库A1和A2中,再运往三个使用地B1,B2,B3,其间的距离(或单位运价),各仓库的存量和使用地的需用量如下 B1 B2 B3 产量 A1 3 4 2 10 A2 3 5 3 4 销量 3 5 6 建立使总运输量最小的运输问题的数学模型。 5某部门有3个生产同类产品的工厂A1、 A2、 A3, 生产的产品由4个销售点B1、 B2、 B3、 B4出售, 各工厂的生产量、 各销售点的销售量( 单位均为吨) 以及各工厂到各销售点的单位运价( 元/吨) 的所有数据列表如下 B1 B2 B3 B4 产量 A1 4 12 4 11 16 A2 2 10 3 9 10 A3 8 5 11 6 22 销量 8 14 12 14 48 问如何调运才能使总运费最小? 6编写一个MATLAB函数, 函数的功能是利用LP命令求解运输问题。要求输入运输费用数据( 二维数组) , 产地约束条件数据( 一维数组) 和销地约束条件数据( 一维数组) , 最后输出运输调度表( 二维数组) , 以及对应的总运输费用。 7食谱问题: 一饲养场饲养供实验用的动物, 已知动物生长对饲料中的三种营养成分, 蛋白质、 矿物质和维生素特别敏感, 每个动物每天至少需要蛋白质70克, 矿物质3克, 维生素10毫克, 该场能搞到五种饲料, 每种饲料10千克的成本如下: 饲料: A1 A2 A3 A4 A5 成本( 元) : 2 7 4 3 5 每一千克饲料中所含的营养成分如下表: 饲料 蛋白质(克) 矿物质(克) 维生素(毫克) A1 0.3 0.10 0.05 A2 2.0 0.05 0.10 A3 1.00 0.02 0.02 A4 0.60 0.20 0.20 A5 1.8 0.05 1.8 确定既能满足动物需要, 又使总成本为最低的饲料配方 。