运筹学第四版线性规划及单纯形法.pptx
《运筹学第四版线性规划及单纯形法.pptx》由会员分享,可在线阅读,更多相关《运筹学第四版线性规划及单纯形法.pptx(249页珍藏版)》请在咨信网上搜索。
1、线性规划及 单纯形法线性规划及单纯形法v线性规划问题及其数学模型v图解法v单纯形法原理v单纯形法的计算步骤第一节 线性规划问题及其数学模型一、问题的提出线性规划主要解决:如何利用现有有限的资源,使得预期目标达到最优的问题。例1 某工厂在计划期内要安排生产A、B两种产品(假定产品畅销)。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗,如表1.1所示问该厂应如何安排生产使获利最大?表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120问题要求给出一个方案(产品A生产多少;产品B生产多少)设该工厂生产A、B两种产品产量分别为确定决策变量表1
2、-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120制定方案的目标是什么?该厂获取的利润可表示为 问题的目标:确定目标函数利润最大化表1-1产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120方案的制定受到那些现实条件制约:人力资源(劳动力)的限制:设备工时的限制:原材料资源的限制:此外,决策变量的取值不应为负值即确定约束条件其中目标函数约束条件资源约束非负约束约束条件可记 s.t (subject to),意思为“以为条件“、”假定“、”满足“之意。综上所述,我们得到了这个问题的数学模型建立问题的线性规划模型
3、步骤1 确定决策变量决策变量是模型所要决定的未知量,也是模型最重要的参数它用以表明规划中的用数量表示的方案、措施,可由决策者决定和控制2 确定目标函数就是将决策者所追求的目标表示为决策变量的函数它决定了线性规划优化的方向,是线性规划的重要组成部分3 确定约束条件这些约束条件可用含有决策变量的等式或不等式来表示例2 给海狸鼠配饲料饲料中营养要求:Va每天至少700克,Vb每天至少30克,VC每天刚好200克。现有五种饲料,搭配使用,饲料成分如下表:饲料VaVbVc价格元/KG 资源量IIIIIIIVV32161810.50.220.50.510.220.8274955060507040营养要求7
4、0030200问:应如何搭配饲料,使费用最小?v确定决策变量:设抓取饲料I x1kg;饲料II x2kg;饲料III x3kgv确定目标函数:minZ=2x1+7x2+4x3+9x4+5x5v确定约束条件:3x1+2x2+x3+6x4+18x5 700 x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5=200 x1 50,x2 60,x3 50,x4 70,x5 40 x1 0,x2 0,x3 0,x4 0,x5 0 营养要求用量要求非负约束综上所述,便得到如下的数学模型:美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、
5、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况,如表1-2所示。问该公司应制造两种家电各多少件,使获取的利润最大?课堂练习项目每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润(元)21表1-2其数学模型为:例3:捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表1-4。租借仓库的合同每月初都可办理,每份合同具体规定租用面积和期限。因此该厂可根据需要,在任何一个月初办理租借合同。每次办理时可签一份合同,也可签若干份租用面积和租用期限不同的合同
6、。试确定该公司签订租借合同的最优决策,目的是使所租借费用最少。月份 1 2 3 4所需仓库面积15 10 20 12表1-3表1-4合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位:100m2单位;元/100m2月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位:100m2单位;元/100m2解:设 表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同(单位为100m2)。1
7、5102012经过上面的讨论,得到下面的LP模型:目标函数约束条件每一个问题都有一组变量-称为决策变量,一般记为下面从数学的角度来归纳上述三个例子的共同点。每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。对决策变量每一组值:代表了一种决策方案。通常要求决策变量取值非负,即二。线性规划问题的数学模型 都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP(linear programming)其数学模型为:上述模型的简写形式为:若令线性规
8、划问题可记为矩阵和向量的形式:用向量表示时,上述模型可写为:三。线性规划问题的标准形式:LP问题的数学模型的标准形式为:其中常数项 LP问题标准形式的特征是:求目标函数的最大值;约束条件为等式;决策变量非负。下面分析如何将LP问题标准化:若目标函数为引进新的目标函数则的最小值即为的最大值,即:从而目标函数变换为:(2)若约束条件为不等式,分为两种情况讨论:加入松弛变量加入剩余变量(3)对于决策变量非负的要求,分为两种情况讨论:非正变量:即xk 0 令xk=-xk即可自由变量:即xk无约束 令xk=xkxk例1 将LP问题化为标准形。解:引进新的目标函数于是原LP问题化为标准形式:例2 将LP问
9、题化为标准形。松弛变量例3 将LP问题化为标准形。剩余变量例4 将LP问题化为标准形。课堂练习例4 将LP问题化为标准形。我们得到例4的标准形为:1.2 线性规划问 题的图解法1.2线性规划图解法v所谓图解法,就是在平面直角坐标上画出各个约束条件所允许变化的范围,通过图上作业法求出最优解和目标函数值。一个线性规划问题有解,是指能找出一组xj(j=1,2,n),满足所有约束条件,称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解,称全部可行解的集合为可行域。在用图解法求解时,可形象的看到可行域。在可行域中使目标函数值达到最优的可行解称为最优解对不存在可行解的线性规划问题,称该问题无解图
10、解法背景知识图解法背景知识由中学知识可知:y=ax+b是一条直线。同理(如果Z值固定)Z=70 x1+120 x2x2=-70/120 x1+Z/120也是一条直线x2=-70/120 x1+Z/120也是一组平行的等值线1.2.1图解法的步骤v1、建立直角坐标系;v2、根据约束条件描绘可行域;v3、作目标函数的等高线;v4、求解最优点和最优目标函数值。例题1生产计划问题v某厂生产两种产品,需要三种资源,已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表:产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120问题:如何安排生产计划,使得获利最多?例
11、1 图解法.90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300Z=70 x1+120 x2maxZ=70X1+120X2 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20最优解(20,24),Z=4280可行域课堂练习用图解法求解下述线性规划问题。1)2)3)答案:1)2)3)x1=1,x2=1.5 Z*=17.5x1=15/4,x2=3/4 Z*=33/4x1=2,x2=6 Z*=361.2.2求解的几种可能结局v1、无穷多最优解。v2、唯一最优解。v2、无
12、界解。v3、无解或无可行解。解的可能性 v多重最优解:无穷多个最优解。若在两个顶点同时得到最优解,则它们连线上的每一点都是最优解。v唯一最优解:只有一个最优点。x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D例例1的数学模型变为的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.Z=24Z=36Z=12解的可能性解的可能性v无界解:线性规划问题的可行域无界,使目标函数无限增大而无界。(缺乏必要的约束条件)例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-
13、3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1Z=6Z=12S.t.解的可能性解的可能性v无可行解:若约束条件相互矛盾,则可行域为空集例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1S.t.由图解法得到的启示图解法虽然只能用来求解只具有两个变量的线性规划问题,但它的求解思路和几何上直观得到的一些概念判断,对于单纯形法有很大启示1、求解线性规划问题时,解的情况有:唯一最优解;无穷多最优解;无界解;无可行解2、若线性规划问题的可行解存在,
14、则可行域是一个凸集3、若线性规划问题的最优解存在,则最优解或最优解之一一定是可行域的凸集的某个顶点。由图解法得到的启示4、解题思路是:先找出凸集的任一顶点,计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大,如果为否,则该顶点就是最优解的点或最优解的点之一;否则转到比这个点的目标函数值更大的另一个顶点,重复上述过程,一直到找出使目标函数值达到最大的顶点为止。1.3 单纯形法 原 理数学试验LINDO软件包LINDO软件包介绍v初试LINDOv用LINDO求解整数规划v注意事项LINDO是一种专门用于求解数学规划问题的优化计算软件包,版权现在由美国 LINDO系统公司(Lind
15、o System Inc.)所拥有.LINDO软件包的特点是程序执行速度很快,易于输入、修改、求解和分析一个数学规划(优化问题),因此LINDO在教育、科研和工业界得到广泛应用.有关该软件的发行版 本、发行价格和其他最新信息都可以从LINDO系统公司的INTERNET 网络站点http:/获取,该站点还提供部分LINDO软件的演示版本或测试版本学生版和演示版与发行版的主要区别在于对优化问题的规模(变量和约束数)有不同的限制.LINDO是Linear Interactive and Discrete Optimizer 字首的缩写形式,可以用来求解线性规划(LP-Linear Programmi
16、ng)、整数规划(IP-Integer Programming)和 二次规划(QP-Quadratic Programming)问题.LINDO学生版可求解多达 200 个变量和100个约束的规划问题.初试 LINDO如解如下LP 问题:LINDO 中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO 也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“=”可用“”代替.上述问题用键盘输入如下::MAX 2X+3Y?ST(说明:也可写成S.T.,SUCH THAT 或 SUBJECT TO 等)?4X+3Y10?3X+5Y12?END:
17、注:目标函数为第1行,两个约束条件分别为第2,3行.直接键入运行命令(GO)就可得到解答,屏幕显示如下:GO LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)7.4545450VARIABLE VALUE REDUCED COST X 1.272727 .000000Y 1.636364 .000000ROW SLACK OR SURPLUS DUAL PRICES 2).000000 .090909 3).000000 .545455 NO.ITERATIDNS=2 DO RANGE(SENSITIVITY)ANALYSIS?单纯形
18、法在2次迭代后得到最优解。最优目标值最优解::GO LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)7.4545450VARIABLE VALUE REDUCED COST X 1.272727 .000000 Y 1.636364 .000000ROW SLACK OR SURPLUS DUAL PRICES 2).000000 .090909 3).000000 .545455 NO.ITERATIDNS=2 DO RANGE(SENSITIVITY)ANALYSIS?单纯形进行了2次迭代带有松弛变量和剩余变量的最优解:检验数减少
19、的成本对偶价格一个问题解答之后,LINDO会询问是否需要作灵敏度分析(DO RANGE(SENSITIVITY)ANALYSIS?).如果不需要,你应回答 N(No),回到提示符:之下.如果想重新看到刚才输入的模型,可键入 LOOK命令,LINDO 会询问具体的行号范围(也可直接将行号范围写在LOOK后).典型的行号范围可以是3,或1-2,或ALL,而结果相应地会显示出第3行、第1-2行,或问题的所有行.如:LOOK ROW:3 (等价于直接命令“LOOK3”)3)3X+5Y=12:如果想修改问题,可键入ALTER命令,LINDO会询问行号,变量名及新的系数,例如:若想将上述问题中约束条件4x
20、+3y 10,修改为6x+3y10,然后再全部看一下,并求解新问题,那么键入ALTER命令后相应要键入2,X,6然后再键入:“LOOK ALL”.在相应位置再键入“GO”,就会给出解答.以下是屏幕上演示过程::ALTER ROW:2 VAR:XNEW COEFFICIENT:6 (等价于直接命令“ALTER2X6”):LOOK ALLMAX 2X+3YSUBJECT TO2)6X+3Y=103)3X+5Y=12END:GOLP OPTIMUM FOUND AT STEP O OBJECTIVE FUNCTION VALUE 1)7.333333VARIABLE VALUE REDUCED CO
21、STX .666667 .000000Y 2.0000 .000000ROWSLACK OR SURPLUS DUAL PRICES 2).000000 .047619 3).000000 .571429NO.ITERATIONS=0DO RANGE(SENSITIVITY)ANALYSIS?N:QUIT改动约束条件的右端项,可以将RHS(即right-hand side)作为变量名.改变约束条件中的不等号方向(如,可以将DIR作为变量名.修改问题还可用EXT命令(增加新的约行),DEL命令(去掉一行)和APPC 命令(增加一个新的变量),也可用EDIT全屏幕编辑器.灵 敏 度 分 析下面用一
22、个具体例子来说明 LINDO 软件求对偶变量及进行灵敏度分析.例 有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.每个书桌每个桌子每个椅子资源总数术料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价 60单位30单位20单位表 1若要求桌子的生产量不超过 5 件,问如何安排三种产品的产量可使收入最大?用 分别表示书桌、桌子、椅子的生产量.建立LP 模型:将上述模型输入LINDO并求解::MAX 6OX1+3OX2+2OX3?S.T?2)8X1+6X2+x348?3)4X
23、I+2X2+1.5X3 20?4)2XI+1.5X2+0.5X3 8?5)X2 5?END:GOLP OPTIMUM FOUND AT STEP 2OBJECTIVE FUNCTION VALUE1)280.00000VARIABLE VALUE REDUCED COSTXI 2.000000 .000000X2 .000000 5.000000X3 8.000000 .000000 ROW SLACK OR SURPLUS DUAL PRICES 2)24.000000 .000000 3).000000 10.000000 4).000000 10.000000 5)5.000000 .0
24、00000LINDO在2次迭代后得到最优解。最优目标值最优解带有松弛变量的最优解检验数NO.ITERATIONS=2 DO RANGE(SENSITIVITY)ANALYSIS?YRANGES IN WHICH THE BASIS IS UNCHANGED.OBJ COEFFICIENT RANGESVARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE Xl 60.000000 20.000000 4.000000 X2 30.000000 5.000000 INFINITY X3 20.000000 2.500000 5.00
25、0000价值系数ciC1在区间60-4,60+20=56,80的范围内变化时,最优基保持不变(最优解的值也不变,但最优值可能要改变)。30-,30+5=(-,35是否需要作灵敏度分析?RIGHT HAND SIDE RANGESROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 48.000000 INFINITY 24.000000 3 20.000000 4.000000 4.000000 4 8.000000 2.000000 1.333333 5 5.000000 INFINITY 5.000000约束行的右端项值在什么范围内
- 配套讲稿:
如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。