资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
运筹学考试重点考试题型:1、填空题30分 2、判断题10分 3、原问题转化为对偶问题10分/15分4、M法单纯线性规划计算20分/15分 5、图解法、单纯性法计算30分绪论运筹学的工作步骤P3(1)提出和形成问题;(2)建立模型;(3)求解;(4)解的检验;(5)解的控制;(6)解的实施。运筹学模型的三种基本形式P3(1)形象模型;(2)模拟模型;(3)符号或数学模型,目前用得最多的是符号或数学模型。线性规划的三个特征P9( 必考)(1)每一个问题都用一组决策变量(x1,x2,x3,xn)表示某一方案,这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。(2)存在有关的数据,同决策变量构成互不矛盾的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示。(3)都有一个要求达到的目标,它可用决策变量及其有关的价值系数构成的线性函数(称为目标函数)来表示。按问题的不同,要求目标函数实现最大化或最小化。线性规划的数学模型(一般式形式),以及cj、aij、bi含义、P10max(min)Z=c1x 1c2x n+cnx n 目标函数,cj为价值系数;a11x1a12x 2a1nx n(=,)b1 约束条件a21x1a22x 2a2nx n(=,)b2 约束条件am1x1am2x 2amnx n(=,)bm 约束条件x1 , x 2 x n0 变量的非负约束条件aij技术系数,bi限额系数勃兰特规则:1)选取Cj-Zj0中下标最小的非基变量Xk为换入变量。即 。 2)当按规则计算存在两个和两个以上最小比值时,选择下标最小的基变量为换出变量。线性规划问题的所有可行解构成的集合为 凸集 集合,也可能为 无界域 集合,它有有限个顶点,每个顶点对应于线性规划问题的 基可行解 ,若它有最优解,则必在集合的 某个顶点上 达到。如果把约束方程 x 13x 24 标准化为 x 13x 2x 3 = 4 2x1 5x 25 2x1 5x 2x4x5 =5则:x1为决策变量,x2为决策变量,x3为非负松弛变量,x4为非负剩余变量,x5为人工变量。线性规划问题的基可行解与基解的区别:基解是基可行解的分量0。已知原线性规划数学模型maxZ=CX,AX=b,X0,则其对偶问题数学模型为min=Yb,YAC,Y为无约束。在单纯形法中,初始基可能由决策变量、松弛变量、人工变量 三种类型组成。P78 运输问题的数学模型,它包含mn个变量,(mn)个约束方程,(mn1)个基变量。对产销平衡的运输问题,其数学模型,最多只有(mn1)个独立约束方程,即系数矩阵的秩(mn1)。5个产地,5个销地的平衡运输问题,基变量有9个。设运输问题,求最大值,当所有的检验数0 时,求得最优解。非基变量的系数 CN1CBB-1N1就是第一章中用符合cj-zj表示的检验数。判断题:1、线性规划的基可行解,与可行域D的顶点一一对应()2、若是原问题的可行解,是对偶问题的可行解,则存在Cb ()3、对偶的两个数学模型,其中一个有最优解,那么另一个问题也有最优解。4、凡是基解一定是可行解。5、基解对应的基是可行基。6、线性规划的最优解一定是基最优解。7、互为对偶问题或者同时有最优解或无最优解。8、对偶问题有可行解,原问题也有可行解。9、(mn1)个变量构成基本变量组的充要条件是它们不包闭回路。10、原问题有无界解,对偶问题有不可行解或不可行。P57 弱对偶性 若是原问题的可行解,是对偶问题的可行解,则存在Cb。P58 对偶理论 原问题有最优解,那么对偶问题也有最优解;且目标函数值相等。例:用图解法和单纯形法求解下题。maxZ=2x15x2 x1 4 2x2 12 3x12x218x1,x20图解法步骤:画图;求坐标;找交集;交点的坐标代入原函数。解:图解法建立坐标系,横轴为x1,纵轴为x2,。分别画出x1=4,x2=6,3x12x2=18的图形。其交点为A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)。A2点:由3x12x2=18、x2=6解得x1=2A3点:由3x12x2=18、x1=4解得x2=3 x29 3x12x2=18 A1(0,6) A2(2,6) 2x2=12 A3(4,3) O A4(4,0) 6 x1 x1=4将A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)代入maxZ=2x15x2中,Z1=2056=30;Z2=2256=34;Z3=2453=23;Z4=2450=8。最大值为Z=34为最优解。由图可知,A2 x1=2,x2=6, Z=34。单纯形法:此问题的标准型:maxZ =2x15x20x30x40x5 x1 x3 = 4 2x2 x4 =12 3x12x2 x5 =18x1,x2,x3,x4,x50Cj25000iCBXBbx1x2x3x4x5 0x3410100- 0x412020106 0x518320019j250001=2-(01+00+03)=2;2=5-(00+02+02)=5;3=0-(01+00+00)=0;4=0-(00+01+00)=0;5=0-(00+00+01)=0;或:x3,x4,x5的系数列组成的是单位矩阵,其j均为0。选j最大的数值所对应的列为换入变量,故x2为换入变量。3= b换入变量系数=40=-(无意义);4= 122=6;5= 182=9。选i最小的数值所对应的行为换出变量,故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步,使主元素变成1,本列中的其他系数变成0。Cj25000iCBXBbx1x2x3x4x5 0x34101004 5x260101/20- 0x56300-112j200-5/20Cj25000iCBXBbx1x2x3x4x5 0x320011/3-1/3 5x260101/20 0x12100-1/31/3j000-11/6-2/3当j0时,终止计算。x1=2,x2=6,x3=3,x4=0,x5=0。将其带入目标函数中可得:maxZ =2x15x20x30x40x5=2256030000=34Z=34对偶问题:maxZ =4x18x22x3 x1x2 1 x1x2x3 2 x12x2x3 3 x10,x20,x30解:对偶问题y1 x1x2 1y2 x1x2x3 2y3 x12x2x3 3 x10,x20,x30min W = y12y23y3 y1y2y3 4 y1y22y3 8 0y1y2y3 2 Y10,y20,y30化为标准型: y1y2y3y4=4 y1y22y3 y5=8 0y1y2y3 y6=2 Y1,y2,y3,Y4,y5,y30用图解法和单纯形法解线性规划问题,并指出单纯形法迭代的每一步,相应于图形上的哪一个顶点。maxZ =2x1x2 3x15x215 6x12x224 x1,x20解:化为标准型maxZ =2x1x20x30x4 3x15x2x3 =15 6x12x2 x4=24 x1,x2,x3,x40图解法: x2 6x12x224 12 A3(0,3) A2(15/4,3/4)0 (4,0)A1 5 3x15x215X=(15/4,3/4,0,0)T。将其带入目标函数中可得:maxZ =2x1x20x30x4=215/413/40000=33/4。Z=33/4。单纯形法:Cj2100iCBXBbx1x2x3x4 0x31535105 0x42462014j21001=2-(03+06)=2;2=1-(05+02)=1;3=0-(01+00)=0;4=0-(00+01)=0。3=153=5;4= 246=4。X=(0,0,15,24)T,它对应图解法中的原点。选j最大的数值所对应的列为换入变量,故x1为换入变量。选i最小的数值所对应的行为换出变量,故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步,使主元素变成1,本列中的其他系数变成0。Cj2100iCBXBbx1x2x3x4 0x33041-1/23/4 2X1411/301/612j01/30-1/31=2-(00+21)=0;2=1-(04+21/3)=1/3;3=0-(01+20)=0;4=0-(0-1/2+21/6)=-1/3。3=34=3/4;1= 41/3=12。X=(4,0,3,0)T,它对应图解法中的A
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号