运筹学-总复习_第1页
运筹学-总复习_第2页
运筹学-总复习_第3页
运筹学-总复习_第4页
运筹学-总复习_第5页
已阅读5页，还剩69页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

运筹学复习求解如下线性规划问题例1复习解：加入松弛变量，标准化得建立单纯形表如下：复习复习解毕复习用对偶单纯形法计算例2复习解：为了便于寻找初始正则解，将问题变形为：取{x4,x5}为初始正则解，列单纯形表如下：复习-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4由于初始正则解有负分量，于是取min{-3,-4}=-4x5为换出变量，取x1为换入变量，得新基{x4,x1}，51=-2为主元复习基变换的过程：主元变为1，即用-2去除单纯形表中基变量x5所在的行；主元所在列的其它元变为0，消去非基变量x1所在的列的其余元-1，-2；得新基{x4,x1}的单纯形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-4复习基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110x5-4[-2]1-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1复习-2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-10-5/21/21-1/240-4-10-1可见正则解的有负分量，由于x4=1,所以取x4为换出变量，取x2为换入变量，得新基{x2,x1}，42=-5/2为主元复习-2-3-4XBbx1x2x3x4x5x22/501-1/5-2/51/5x111/5107/5-1/5-2/528/500-3/5-8/5-1/5此时正则解是可行解，也是最优解。X*=(11/5，2/5，0，0，0)；z*=-28/5进行基变换，得新正则解的单纯形表：复习(1)写出下列线性规划的对偶规划(2)试用对偶原理求解线性规划问题已知其对偶规划的最优解为例3复习解：该问题的对偶规划为复习利用松紧关系，代入对偶规划的约束条件得下列约束是松约束，将最优解松约束紧约束其对偶约束是紧约束复习设原问题的最优解为紧约束复习设某种物资有3个产地A1，A2，A3，

生产量分别为9，5，7;有4个销地B1，B2，B3，B4，销售量分别为3，8，4，6

;已知从Ai到Bj

物资的单位运价见下表。求总运费最小的调运方案。B1B2B3B4产量A1291079A213425A384257销量3846例4复习存在基变量为0的解称为退化解。在确定初始基可行解的过程中，如果某一步中出现情况：当产地Ai处的余量与销地Bj处的需求量相等时，在格(i,j)填入运量后，产地Ai处的余量与销地Bj处的销量同时为0,相应地要划去一行和一列。这时就出现了退化。为了使基变量个数恰好有m+n-1个，应在同时划去的一行或一列中的某个格中填入数字0，表示这格中的变量是取值为0的基变量；复习B1B2B3B4ai行差A1291079A213425A384257bj3846列差伏格尔法计算1用伏格尔法寻找初始基：先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。从行差或列差中选出最大者，并选择其所在行或列的最小元素。A1的行差最大，而其中运价c11最小,令x11为优先运输路线。5121123复习B1B2B3B4ai行差A12910795A2134251A3842572bj3846列差11230303/09/6用伏格尔法寻找初始基：销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3填到调运方案表中第1行第1列上。画去运输数据表第一列，A1的产量剩余为9-3=6。得到新的产销平衡与单位运价表.令伏格尔法计算1复习B1B2B3B4ai行差A1291079/65A2134251A3842572bj3/0846列差11230306/15/0用伏格尔法寻找初始基：再算出运价表中的行差与列差。B4的列差最大，而其中运价c24最小,令x24为优先运输路线。产地A2的产量2全供给销地B4，所以x23=x24=0。画去运输数据表中第2行，B4的销量还要6-5=1。得新表。521122112233050令伏格尔法计算1复习B1B2B3B4ai行差A1291079/65A213425/01A3842572bj3/0846/1列差11230304/07/3用伏格尔法寻找初始基：5211221122330505221122211522833204伏格尔法计算1复习B1B2B3B4ai行差A1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格尔法寻找初始基：521122112233050522112221152283320452221122211155228332203伏格尔法计算1复习B1B2B3B4ai行差A1291079/65A213425/01A384257/32bj3/084/06/1列差11230308/57/3/0用伏格尔法寻找初始基：0500452221122211155228332203现在只有一个产地两个销地，故令x12=5

,x14=1为基变量，将其分别填到调运方案表中1行2列与1行4列上。51得到产销平衡运输问题的一个初始方案伏格尔法计算1复习B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的运费是3×2+5×9+4×7+5×2+3×4+4×2=88。伏格尔法给出的初始解往往更接近于最优解。复习利用伏格尔法确定的初始解如下表所示：B1B2B3B4aiA1325910179A2134525A38344257bj38461、写出基可行解对应的位势方程组;2、并计算非基变量的检验数。复习求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下：在原单位运价表增加一行与一列，在列中填入ui，在行中填入vj；把运价cij记在每一格的右上角，用框标定，在基变量对应的格中标出0，构成表。复习由u1+v1=2,u1+v2=9,u1+v4=7,得v1=2,v2=9,v4=7;B1B2B3B4uiA102091007A213402A3804025vj0-5-52977位势表：再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;最后由u3+v3=2得v3=7.取u1=0;复习检验数表：(计算所有非基变量的检验数)B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)当存在非基变量的检验数kl

≥0，说明现行方案为最优方案，否则目标成本还可以进一步减小。复习伏格尔法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)x22为换入变量,

从x22所在格出发做闭回路L,L中有两个偶点x24,x12，取x12为换出变量，调整量为5.复习伏格尔法的调整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在闭回路L上，偶点变量减5，奇点变量加5.0x22为换入变量,取x12为换出变量.065复习它所对应的位势与检验数为：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有检验数都非负，迭代停止，运费为：3×2+6×7+5×3+3×4+4×2=83复习P1：充分利用现有工时，必要时可以加班；P2：A，B，C的最低产量分别为5，5，8台，并依单位工时的利润比例确定权系数；P3：生产线加班时每月不超过20小时；P4：A，B，C的月销售指标分别定为10，12，10台，依单位工时利润比例确定权系数.试建立目标规划模型.A、B、C三种计算机，在一条生产线上装配。装配时间分别为5，8，12小时；利润分别为每台1000元，1440元，2520元。生产线每月正常运转170小时。该厂的经营目标为：例5复习复习在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示。地点12345所需投资（万元）320280240210180占用农田（亩）201815118生产能力（万吨）7055422811现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。例6复习复习解：设五个0—1变量x1，x2，x3，x4，x5，其中i=1,2,3,4,5.建立整数规划模型为

Maxz=70x1+55x2+42x3+28x4+11x5s.t.320x1+280x2+240x3+210x4+180x580020x1+18x2+15x3+11x4+8x5

60x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5=0,1利用割平面算法求解下面的规划问题例7复习解：将约束条件的系数化整；去掉“x1,x2是整数”的条件，得到一个线性规划的标准型（LP1）为：利用单纯形法求解这个线性规划问题，得出最终单纯形表：

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4复习最优解不是整数解，由最终表得到变量之间的关系：

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4将上面的约束条件当中的变量和系数改写成整数与非负真分数的和把整数部分放在左边，非整数部分放在右边。下面增加割平面，选真分数最大的一个由于上式左端是整数，因此右端也应是整数，由于变量都是不小于0的整数，所以上式右端必是一个不大于0.5的整数，即称这个不等式为一个割平面。引入一个松弛变量，化割平面为：将它作为一个新增加的约束条件加入线性规划LP1中得到一个新的线性规划LP2

；或者直接反映到LP1的最终单纯形表中，得LP2单纯形表：割平面的处理：复习LP2的单纯形表：

32000x1

x2

x3

x4

x5x2x1x55/213/4-1/2

011/2-1/2010-1/43/4000[-1/2]-1/21

00-1/4-5/40

3200

x1

x2

x3

x4

x2

x1

2.53.25

011/2-1/210-1/43/4

σj

00-1/4-5/4LP1

：LP2

：复习

32000

x1

x2

x3

x4

x5

σj

00-1/4-5/40x2x1x327/21

010-111001-1/20011-2

σj

000-1-1/2由于不是整数解，找出不满足条件的基变量x1.用对偶单纯型法求解：复习将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3∶构造线性规划LP2的割平面复习LP3

：LP3的单纯形表：

320000

x1

x2

x3

x4

x5

x6x2x1x3x6

27/21-1/2

σj

000-10-1复习

320000

x1

x2

x3x4

x5

x6

σj

000-1-1/20x2x1x3x5

1431

σj

000-10-1从上表中我们可以看到，已经找到了整数最优解：x1=4,x2=1。故求解结束。用对偶单纯型法求解：复习有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵C表示。应如何分配工作，使他们完成任务的总时间最短？Ⅰ

Ⅱ

Ⅲ

Ⅳ例8Step1、先对效率矩阵进行列变换，使其各行各列中都出现0元素.效率矩阵变换方法为：从效率矩阵C

的每行元素中减去该行的最小元素,得矩阵B

；从矩阵B

中每列元素中减去该列的最小元素得矩阵C1

。

min0050Step2、确定C1中线性独立的0元素.从第一行开始，若该行只有一个0元素，就对这个0元素加圈，然后划去其所在列的其它0元素;若该行没有其它0元素或有两个以上0元素（已划去的不计），转下一行；直到最后一行为止。然后,从第一列开始,若该列只有一个0元素,就对这个0元素加圈（同样不考虑已划的）,再划去其所在行的其它0元素;若该列没有0元素或有两个以上0元素，则转下列直到最后一列为止。重复上述步骤.上述步骤可能出现三种情况情况一：矩阵每行都有一个打圈的0元素。此时得到问题的最优解.情况二：有多于两行或两列存在两个以上的未处理的0元素，即出现0元素的闭回路。此时，可从中任选一个0元素加圈，划掉其同行同列的0元素，再重复上述两个步骤。情况三：矩阵中所有0元素或被加圈，或被划去，而已加圈的0元素m小于矩阵的行数n。即矩阵中至少存在有一行不含加圈的0元素。转步骤三。Step3寻找能覆盖C1中所有0元素的最小直线数.(1)按照从上到下、从左到右的顺序对C1没有加圈的0元行打√号；(2)对已打√号的行中未加圈0元的列打√号；(3)对已打√号的列中加圈0元的行打√号；(4)重复下去，直到找不出打√号的行、列为止。√

(5)对没打√号的行划一横线，对打√号的列划一纵线，这就是覆盖矩阵C1中所有0元素的最小直线数.√

√

Step4、改进C1(1)寻找C1

没有被直线覆盖的所有元素中的最小元素θ；例中θ=2.(2)在已打√号的行中减去θ；(3)在已打√号的列中加上θ；得到一个新矩阵C2。√

√

√

-2603-292301340054300用C2代替C1，返回步骤2.即例题的最优分配方案：确定C2中线性独立的0元素.

用dijkstra算法求下图从顶点V1到其余各点的最短路径：例9V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024V1112921865129734136971V1V2V3V4V5V6V7V8V9V1024V1112921865129734136971V1V2V3V4V5V6V7V8V9V1002∞8∞∞∞∞∞∞1240∞∞∞∞∞∞∞∞∞∞V1112921865129734136971V1V2V3V4V5V6V7V8V9V1002∞8∞10∞∞∞∞124V1112921865129734136971V1V2V3V4V5V6V7V8V9V10038∞10∞∞∞∞1224V1112921865129734136971V1V2V3V4V5V6V7V8V9V10081210∞∞6512324V1112921865129734136971V1V2V3V4V5V6V7V8V9V10081210∞146123524V111921865129734136971V1V2V3V4V5V6V7V8V9V10071210∞1412356242V111921865129734136971V1V2V3V4V5V6V7V8V9V100129111921865129734136971V1V2V3V4V5V6V7V8V9V1001210141235679242V111921865129734136971V1V2V3V4V5V6V7V8V9V1001114121056793242V111921865129734136971V1V2V3V4V5V6V7V8V9V1001210567932411132求下图s→t的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●网络最大流例10stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基础上，通过标号寻找增广链。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增广链s→v2→v3→t网络最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)网络最大流(3)擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)网络最大流(4)重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增广链：s→v2→v5→v3→t网络最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论