下载此文档

《运筹学》复习参考资料知识点及习题.doc


文档分类:高等教育 | 页数:约29页 举报非法文档有奖
1/29
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/29 下载此文档
文档列表 文档介绍
一、两个变量的线性规划问题的图解法:㈠概念准备:定义:满足所有约束条件的解为可行解;可行解的全体称为可行(解)域。定义:达到目标的可行解为最优解。㈡图解法:图解法采用直角坐标求解:x1——横轴;x2——竖轴。1、将约束条件(取等号)用直线绘出;2、确定可行解域;3、绘出目标函数的图形(等值线),确定它向最优解的移动方向;注:求极大值沿价值系数向量的正向移动;求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题:(只要求下面这些有唯一最优解的类型)例1:某厂生产甲、乙两种产品,这两种产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示:品产耗消备设ABC利润(万元)甲乙3599537030有效总工时540450720——问:该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大?(此题也可用“单纯形法”或化“对偶问题”用大M法求解)解:设x1、x2为生产甲、乙产品的数量。⑴maxz=70x1+30x2⑵.⑸、⑹⑷⑶可行解域为oabcd0,最优解为b点。由方程组解出x1=75,x2=15∴X*==(75,15)T∴maxz=Z*=70×75+30×15=5700例2:用图解法求解⑴maxz=6x1+4x2⑵.⑸、⑹⑷⑶解:可行解域为oabcd0,最优解为b点。由方程组解出x1=2,x2=6∴X*==(2,6)T∴maxz=6×2+4×6=36例3:用图解法求解⑴minz=-3x1+.⑵⑶⑷⑸⑹、⑺解:可行解域为bcdefb,最优解为b点。由方程组解出x1=4,x2=∴X*==(4,)T∴minz=-3×4+=-11二、标准型线性规划问题的单纯形解法:㈠一般思路:1、用简单易行的方法获得初始基本可行解;2、对上述解进行检验,检验其是否为最优解,若是,停止迭代,否则转入3;3、根据θL规则确定改进解的方向;4、根据可能改进的方向进行迭代得到新的解;5、根据检验规则对新解进行检验,若是最优解,则停止迭代,否则转入3,直至最优解。㈡具体做法(可化归标准型的情况):设已知maxz=c1x1+c2x2+…++i,i=1,2,…,m,得到列表计算,格式、算法如下:+mθLx1x2…xn+mcn+1xn+1b1a11a12…a1n+mcn+2xn+2b2a21a22…a2n+m.........…………cn+mxn+mbnam1am2…amn+mz1z2…zn+mσ1σ2…σn+m注①:++2a2j+…+cn+mamj=,(j=1,2,…,n+m)σj=cj-zj,当σj≤0时,当前解最优。注②:由max{σj}确定所对应的行的变量为“入基变量”;由θL=确定所对应的行的变量为“出基变量”,行、列交叉处为主元素,迭代时要求将主元素变为1,此列其余元素变为0。例1:用单纯形法求解(本题即是本资料P2“图解法”例1的单纯形解法;也可化“对偶问题”求解)maxz=70x1+:加入松弛变量x3,x4,x5,得到等效的标准模型:maxz=70x1+30x2+0x3+0x4+:CBXBb7030000θLx1x2x3x4x50x354039100540/3=1800x445055010450/5=900x5720(9)3001720/9=800000070↑300000x33000810-1/3300/8=(10/3)01-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3↑00-70/90x3180001-12/5130x2150103/10-1/670x175100-1/101/6570070300220/3000-2-20/3∴X*=(75,15,180,0,0)T∴maxz=70×75+30×15=5700例2:用单纯形法求解maxz=7x1+:加入松弛变量x3,x4,x5,得到等效的标准模型:maxz=7x1+12x2+0x3+0x4+:CBXBb712000θLx1x2x3x4x50x336094100360/4=900x420045010200/5=400x53003(10)001300/10=3000000712↑0000x324078/10010-2/5240/78/10=2400/780x450(5/2)001-1/250/5/2=2012x2303/101001/1030/3/10=10018/512006/517/5↑000-6/50x384001-78/2

《运筹学》复习参考资料知识点及习题 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数29
  • 收藏数0 收藏
  • 顶次数0
  • 上传人zbfc1172
  • 文件大小595 KB
  • 时间2019-12-14