线性规划与单纯形法样本.doc
《线性规划与单纯形法样本.doc》由会员分享,可在线阅读,更多相关《线性规划与单纯形法样本.doc(20页珍藏版)》请在咨信网上搜索。
1、资料内容仅供您学习参考,如有不当或者侵权,请联系改正或者删除。1.1线性规划问题及其数学模型一、 问题的提出在生产经营管理中, 需要经常进行计划或者规划, 虽然各行业的计划或规划千差万别, 但其共同点可归纳为: 在各项资源条件的限制下, 如何确定方案, 使预期的目标达到最优。例1.1某工厂在计划期内要安排生产、 两种产品, 已知生产单位产品所需的设备台时及A、 B两种原材料的消耗如下表所示: 资源限制设备128台时原材料A4016原材料B0412利润23该工厂生产一件产品、 的利润分别为2元、 3元, 问应如何安排生产才使该工厂的获利最大? 二、 数学模型的建立L.P问题数学模型的三要素: 1
2、.决策变量: 一般是根据所问问题假设决策变量, 一组决策变量( ) 表示某一方案, 这一组决策变量的值就代表一个具体方案。2.目标函数: 经过决策变量, 将要实现的目标用函数式表示出来, 常见的目标函数有两种表示式。(1) 目标是求最大化: (2) 目标是求最小化: 3.约束条件: 主要是对变量或目标的约束, 一般见未知量的线性等式或不等式来表示。例1.3: 某公司经销一种产品, 它下设三个生产点, 每日产量分别为, , , 该公司把这些产品分别运往四个销售点, 各销售点每日销量分别为, 已知每吨产品从各生产点到各销售点的运价如下表所示, 问该公司应如何调运产品, 在满足各销售点需要前提下,
3、使总运费最少? 销量运价411310192874105解: 三、 L.P数学模型的一般形式st.上述模型的简写形式为: st.用向量形式表示时, 上述模型可写为: st.式中: ; 价值系数用矩阵形式来表示可写为: 技术系数工艺系数资源系数st.( 假定线性规划问题中含n个变量, 分别用表示, 在目标函数中的系数为, 称为价值系数; 的取值受m种资源的限制, 用表示i第种资源的拥有量, 用表示变量取值为1单位时所消耗或含有的第i种资源的数量, 一般称为技术系数或工艺系数) 1.2 图解法图解法简单直观, 能帮助我们了解L.P的基本原理。一、 图解法基本步骤1. 在平面上建立直角坐标系; 2.
4、图示全部约束条件, 找出可行域; 3. 图示目标函数和寻找最优解。例1.4: 经过例1.1来说明图解法的具体运用 s.t 二、 L.P求解的几种解的情况1. 有唯一最优解。( 如上例所示) 2. 有无穷多最优解( 多重解) 如上例中, 若将目标函数改为, 则表示目标函数中以参数z的这族平行直线与约束条件的边界线平行。当z值由小变大时, 将与线段Q2Q3重合, 则点Q2与Q3之间的可行域边界上各点均为最优点, 它们对应同一最优值。3.无可行解若上例中再增加一个约束条件, 时, 该问题的可行域为空集, 即该LP模型无可行解也不存在最优解。如出现这种情况表明数学模型中存在矛盾的约束条件。4.无界解如
5、果全部约束条件构成的可行域是无界的, 则有可能出现最优解无界, 产生无界解的原因是由于在建立实际问题的数学模型时, 遗漏了某些必要的资源约束条件。如下述线性规划问题: 三、 由图解法得到的启示从LP图解法能够得出以下几点启示: 1.LP的解的情况有四种: 唯一最优解、 无穷多最优解、 无界解、 无可行解。2.LP的可行域为凸集, 特殊情况下为无界域或空集; 3.LP若有最优解, 一定能够在其可行域的顶点上得到; 4.解题思路是: 先找出凸集的任一顶点, 计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大, 如果否, 则该顶点是最优解的点若最优解的点之一, 否则, 转到比这个点
6、的目标函数值更大的另一顶点, 重复上述过程, 一起到找到使目标函数值最大的顶点为止。图解法虽然直观、 简便, 但当变量数多于三个以上时, 它就无能为力, 只能用另外一种代数法单纯形法来求解。作业: 1.用图解法求解下列线性规划问题, 并指出问题具有惟一最优解、 无穷多最优解、 无界解还是无可行解。( 1) 4s.t (2) s.t (3) s.t (4) s.t 2.美佳公司计划制造I、 II两种家电产品。已知各制造一件时分别占用的设备A,B的台时、 调试时间及调试设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如表11所示。问该公司应制造A、 B两种家电各多少件, 使获取的
7、利润为最大。表1-1项目III每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润( 元) 213.(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012合同租借期限1
8、个月2个月3个月4个月所需仓库面积(元/100m2)28004500600073001.3线性规划问题的标准形式一、 标准形式LP的数学模型有各种不同的形式, 为了便于讨论和制定统一的算法, 有必要用统一的标准形式来表示。规定LP的标准形式如下: 二、 LP一般式转化为标准形式1.决策变量在标准形式中要求所有决策变量, 但一般式中决策变量不一定才是大于等于0。(1) 若(2) 若(3) 若2.目标函数(1) 若目标函数是求极大值, 则不变; (2) 若目标函数是求极小值, 即: 因为求, 令, 即可化为3.资源系数标准形式中要求, 若时, 只需将等式或不等式两端同乘( -1) , 则等式右端必
9、大于0。4.约束条件不等式(1) 若约束条件为”, 则不变; (2) 若约束条件为”, 则在不等式左侧增加一个非负松驰变量, 使其转化为”; (3) 若约束条件为”, 则在不等式左侧减去一个非负剩余变量( 也称松驰变量) , 使其转化为”。松驰变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数, 均未转化为价值和利润, 因此, 引进模型后它们在目标函数中的系数均为0。例1.5, 经过例1.1来说明一般形式向标准形式的转化: s.t例1.6将下列LP转化为形式: ( 让学生演算) st.作业习题1、 将下列线性规划问题化为标准型(1) Max z = 3x1+ 5x2- 4x3+
10、 2x4 s.t. 2x1+ 6x2- x3+ 3x4 18 x1- 3x2+ 2x3- 2x4 13 -x1+ 4x2- 3x3- 5x4 = 9 x1, x2, x4 0(2) Min f = 3x1+ x2+ 4x3+ 2x4 1 s.t. 2x1+ 3x2- x3- 2x4 -51 3x1- 2x2+ 2x3- x4 -7 2x1+ 4x2- 3x3+ 2x4 = 15 x1 , x2 0, x4 01.4单纯形法原理一、 线性规划问题的解的概念LP1.可行解: 满足上述约束条件的解, 称为LP的可行解。2.最优解: 使目标函数达到最大值的可行解叫最优解。3.基: 设A是约束方程组的阶
11、系数矩阵( 设) , 则矩阵A的秩为, 若B是矩阵A中的一个阶的满秩子矩阵, 称B为LP的一个基。也就是说, 矩阵B是由m个线性独立的列向量组成的, 不失一般性地设: B中的每一个列向量称为基向量, 与基向量对应的变量称为基变量, LP中除基变量以外的变量称为非基变量。4.基解: 在约束方程组中, 令所有非基变量, 又因有, 根据克莱姆法则, 则m个约束方程能够得出m个基变量的唯一解, 将这个解加上非基变量取0的值有: , 称X为LP的基解。显然在基解中变量取非零值的个数不大于方程数m, 故基解的总数不超过个。5.基可行解: 满足变量非负约束条件的基解称为基可行解。6.可行基: 对应于基可行解
- 配套讲稿:
如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。