线性规划之单纯形法实验指导样本.doc
《线性规划之单纯形法实验指导样本.doc》由会员分享,可在线阅读,更多相关《线性规划之单纯形法实验指导样本.doc(18页珍藏版)》请在咨信网上搜索。
1、资料内容仅供您学习参考,如有不当或者侵权,请联系改正或者删除。实验指导 线性规划 一、 实验目的 了解线性规划的基本知识, 熟悉应用matlab解决线性规划问题的一般方法。 二、 实验内容 1. 线性规划的基本概念 2. 生产计划问题 3. 运输问题 三、 实验仪器和设备 1. 计算机若干台( 装有matlab6.5及以上版本软件) 2. 打印机 四、 实验要求 1. 独立完成各个实验任务; 2. 实验的过程保存成 .m 文件, 以备检查; 3. 实验结果保存成 .mat 文件 五、 实验原理在生产和经营等管理工作中, 需要经常进行计划或规划。虽然内容千差万别, 但它们都有其共同点: 在现有资
2、源限制下, 如何确定方案, 使预期目标达到最优。这能够归结为数学规划问题。在这类问题中, 最简单的是线性规划问题, 即在一组线性不等式约束下求线性目标函数的极大或极小值问题。因为线性规划问题用数学语言描述管理工作中的实际问题, 因此又被称为数学模型。建立数学模型的过程是, 由实际问题出发, 设置变量, 确定目标函数, 并根据资源条件的限制写出约束条件, 最后给出线性规划问题。本章只介绍两种典型问题的模型, 生产计划问题和运输问题。 ( 一) 线性规划的基本概念 线性规划问题是求决策变量在一组线性等式或线性不等式约束下, 使目标函数达到最小或最大值的一类优化问题。 求解线性规划问题的计算方法中最
3、简单的是图解法, 以下面问题为例 例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的左下方的区域正是控制变量满足约束条件的几何图形。区域中的任一点代表控制变量满足
4、线性规划约束条件的一组值x1, x2, 称为线性规划问题的可行解。 图1 全部可行解的集合称为可行域.使线性规划的目标函数达到最优值(依具体问题,或是极大值,或是极小值)的可行解称为线性规划问题的最优解。 在这一问题中, 最优解对应于直线族x1 + x2 = c中, 与可行域相切的一条直线。切点正好是最优解(6/5, 6/5), 因为这个点在可行域的边界上正好是两直线的交点, 即方程组 的解 x1=6/5 x2=6/5 用图解法求解线性规划问题时应注意几点 1图解法适用于两个变量的线性规划问题; 2线性规划问题的解有四种情况: 有唯一最优解、 有无穷多最优解、 有无界解、 无可行解; 3线性规
5、划问题如果有最优解,则可行域的某个顶点必定是最优解.为求最优解,可先计算可行域上某顶点的目标函数值,再考察相邻顶点处的目标函数值是否比它更优,如果为否,则这个点就是最优点;如果其它点更优,则转到其它顶点上去重复这一过程。 对于例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) 求解该问题。
6、输入问题中的全部数据, 并调用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, v
7、lb, 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), 则有如下数学模型 m
8、ax 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 = 125
9、00 这说明在制定生产计划时安排甲类产品生产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。因
10、此第一条直线过点(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
11、, 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), 得可行域
12、图形。 图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种资源数量为a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 单纯 实验 指导 样本
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。