《运筹学 总复习.pptx》由会员分享，可在线阅读，更多相关《运筹学 总复习.pptx（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 求解如下线性规划问题例1复 习第1页/共53页解：加入松弛变量，标准化得建立单纯形表如下：复 习第2页/共53页复 习第3页/共53页解毕复 习第4页/共53页 用对偶单纯形法计算例2复 习第5页/共53页解：为了便于寻找初始正则解，将问题变形为：取x4,x5为初始正则解，列单纯形表如下：复 习第6页/共53页-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-4由于初始正则解有负分量，于是取min-3,-4=-4x5为换出变量，取x1为换入变量，得新基x4,x1，51=-2为主元复 习第7页/共53页基变换的过程：1.主元变为1，即用-2去
2、除单纯形表中基变量x5所在的行；2.主元所在列的其它元变为0，消去非基变量x1所在的列的其余元-1，-2；3.得新基x4,x1的单纯形表-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-4复 习第8页/共53页基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-3-1-2-110 x5-4-21-3010-2-3-421-1/23/20-1/2-10-5/21/21-1/240-4-10-1复 习第9页/共53页-2-3-4XBbx1x2x3x4x5x4x121-1/23/20-1/2-
3、10-5/21/21-1/240-4-10-1可见正则解的有负分量，由于x4=1,所以取x4为换出变量，取x2为换入变量，得新基x2,x1，42=-5/2为主元复 习第10页/共53页-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进行基变换，得新正则解的单纯形表：复 习第11页/共53页试用对偶原理求解线性规划问题已知其对偶规划的最优解为例3复 习第12页/共53页解：解：该问题的对偶规划为该问题的对偶规划
4、为复 习第13页/共53页利用松紧关系，利用松紧关系，代入对偶规划的约束条件得下列约代入对偶规划的约束条件得下列约束是松约束，束是松约束，将最优解松约束紧约束其对偶约束是紧约束复 习第14页/共53页设原问题的最优解为设原问题的最优解为紧约束复 习第15页/共53页 设某种物资有3个产地 A1，A2，A3，生产量分别为9，5，7;有4个销地B1，B2，B3，B4，销售量分别为3，8，4，6;已知从Ai到Bj 物资的单位运价见下表。求总运费最小的调运方案。B1B2B3B4产量产量A1291079A213425A384257销量销量3846例4复 习第16页/共53页存在基变量为0的解称为退化解。
5、在确定初始基可行解的过程中，如果某一步中出现情况：当产地Ai处的余量与销地Bj处的需求量相等时，在格(i,j)填入运量后，产地Ai处的余量与销地Bj处的销量同时为0,相应地要划去一行和一列。这时就出现了退化。为了使基变量个数恰好有m+n-1个，应在同时划去的一行或一列中的某个格中填入数字0，表示这格中的变量是取值为0的基变量；复 习第17页/共53页B1B2B3B4ai行差行差A1291079A213425A384257bj3846列差列差伏伏格格尔尔法法计计算算1 1用伏格尔法寻找初始基：|先算出运价表中各行与各列的最小运费与次小运费的差额，并填入该运价表的最右列和最下行。|从行差或列差中选
6、出最大者，并选择其所在行或列的最小元素。A1的行差最大，而其中运价c11最小,令x11为优先运输路线。5121123复 习第18页/共53页B1B2B3B4ai行差行差A12910795A2134251A3842572bj3846列差列差11230303/09/6用伏格尔法寻找初始基：u销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3 填到调运方案表中第1行第1列上。u画去运输数据表第一列，A1的产量剩余为9-3=6。得到新的产销平衡与单位运价表.u令伏伏格格尔尔法法计计算算1 1复 习第19页/共53页B1B2B3B4ai行差行差A1291079/65A2134251A
7、3842572bj3/0846列差列差11230306/15/0用伏格尔法寻找初始基：u再算出运价表中的行差与列差。uB4的列差最大，而其中运价c24最小,令x24为优先运输路线。u产地A2的产量2全供给销地B4，所以x23=x24=0。u画去运输数据表中第2行，B4的销量还要6-5=1。得新表。521122112233050令伏伏格格尔尔法法计计算算1 1复 习第20页/共53页B1B2B3B4ai行差行差A1291079/65A213425/01A3842572bj3/0846/1列差列差11230304/07/3用伏格尔法寻找初始基：5211221122330505 2 21 12 2
8、211522833204伏伏格格尔尔法法计计算算1 1复 习第21页/共53页B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57/3/0用伏格尔法寻找初始基：5211221122330505 2 21 12 2 21152283320452 2 21122 2 11 1 5 5 2 2 83 3 2 203伏伏格格尔尔法法计计算算1 1复 习第22页/共53页B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差11230308/57
9、/3/0用伏格尔法寻找初始基：0500452 2 21122 2 11 1 5 5 2 2 83 3 2 203现在只有一个产地两个销地，故令x12=5,x14=1为基变量，将其分别填到调运方案表中1行2列与1行4列上。51得到产销平衡运输问题的一个初始方案伏伏格格尔尔法法计计算算1 1复 习第23页/共53页B1B2B3B4aiA1291079A213425A384257bj3846354351此方案的运费是32+59+47+52+34+42=88。伏格尔法给出的初始解往往更接近于最优解。复 习第24页/共53页利用伏格尔法确定的初始解如下表所示：B1B2B3B4aiA1325910179A
10、2134525A38344257bj38461、写出基可行解对应的位势方程组;2、并计算非基变量的检验数。复 习第25页/共53页求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下：在原单位运价表增加一行与一列，在列中填入ui，在行中填入vj；把运价cij记在每一格的右上角，用框标定，在基变量对应的格中标出0，构成表。复 习第26页/共53页由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=-
11、5;最后由u3+v3=2 得v3=7.取u1=0;复 习第27页/共53页检验数表：(计算所有非基变量的检验数)B1B2B3B4uiA102091007A213402A3804025vj0-5-52977(3)(4)(-1)(2)(11)(3)当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。复 习第28页/共53页伏格尔法的初始方案：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3)x22为换入变量,从 x22所在格出发做闭回路L,L中有两个偶点x24,x12，取x12为换出
12、变量，调整量为5.复 习第29页/共53页伏格尔法的调整方案：B1B2B3B4aiA1325910179A21034525A38344257bj3486在闭回路L上，偶点变量减5，奇点变量加5.0 x22为换入变量,取x12为换出变量.065复 习第30页/共53页它所对应的位势与检验数为：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有检验数都非负，迭代停止，运费为：32+67+53+34+42=83复 习第31页/共53页P1：充分利用现有工时，必要时可以加班；P2：A，B，C的最低产量分别为5，5，8台
13、，并依单位工时的利润比例确定权系数；P3：生产线加班时每月不超过20小时；P4：A，B，C的月销售指标分别定为10，12，10台，依单位工时利润比例确定权系数.试建立目标规划模型.A、B、C三种计算机，在一条生产线上装配。装配时间分别为5，8，12小时；利润分别为每台1000元，1440元，2520元。生产线每月正常运转170小时。该厂的经营目标为：例5复 习第32页/共53页复 习第33页/共53页 在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示。地点地点12345所需投资（万元）所需投资（万元）320280240210180占
14、用农田（亩）占用农田（亩）201815118生产能力（万吨）生产能力（万吨）7055422811现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。例6复 习第34页/共53页复 习解：设五个01变量 x1，x2，x3，x4，x5，其中 i=1,2,3,4,5.建立整数规划模型为 Max z=70 x1+55x2+42x3+28x4+11x5s.t.320 x1+280 x2+240 x3+210 x4+180 x5 80020 x1+18x2+15x3+11x4+8x5 60 x1+x2+x3+x4+x5=3x1，x2，x3，x4，x5=0,1第35页/共53
15、页利用割平面算法求解下面的规划问题例7复 习第36页/共53页解：将约束条件的系数化整；去掉“x1,x2是整数”的条件，得到一个线性规划的标准型（LP1）为：利用单纯形法求解这个线性规划问题，得出最终单纯形表：3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4复 习第37页/共53页最优解不是整数解，由最终表得到变量之间的关系：3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4将上面的约束条件
16、当中的变量和系数改写成整数与非负真分数的和把整数部分放在左边，非整数部分放在右边。第38页/共53页下面增加割平面，选真分数最大的一个由于上式左端是整数，因此右端也应是整数，由于变量都是不小于0的整数，所以上式右端必是一个不大于0.5 的整数，即称这个不等式为一个割平面。第39页/共53页引入一个松弛变量，化割平面为：将它作为一个新增加的约束条件加入线性规划LP1中得到一个新的线性规划LP2；或者直接反映到LP1的最终单纯形表中，得LP2单纯形表：割平面的处理：复 习第40页/共53页LP2 的单纯形表：3 2 0 0 0 x1 x2 x3 x4 x5x2x1x55/213/4-1/2 0 1
17、 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 1 0 0 -1/4 -5/4 0 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4LP1：LP2：复 习第41页/共53页 3 2 0 0 0 x1 x2 x3 x4 x5 j 0 0 -1/4 -5/4 0 x2x1x32 7/21 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2 j 0 0 0 -1 -1/2由于不是整数解，找出不满足条件的基变量 x1.用对偶单纯型法求解：复 习第4
18、2页/共53页将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3构造线性规划LP2的割平面复 习第43页/共53页LP3：LP3的单纯形表：3 2 0 0 0 0 x1 x2 x3 x4 x5 x6x2x1x3x6 2 7/2 1-1/2 0 1 0 -1 1 0 1 0 0 1 -1/2 0 0 0 1 1 -2 0 0 0 0 0 -1/2 1 j 0 0 0 -1 0 -1复 习第44页/共53页 3 2 0 0 0 0 x1 x2 x3 x4 x5 x6 j 0 0 0 -1 -1/2 0 x2x1x3x5 1 4 3 1 0 1 0 -1 0 2 1 0 0 1 0
19、-1 0 0 1 1 0 -4 0 0 0 0 1 -2 j 0 0 0 -1 0 -1从上表中我们可以看到，已经找到了整数最优解：x1=4,x2=1。故求解结束。用对偶单纯型法求解：复 习第45页/共53页 有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵 C 表示。应如何分配工作，使他们完成任务的总时间最短？例8第46页/共53页Step 1、先对效率矩阵进行列变换，使其各行各列中都出现 0 元素.效率矩阵变换方法为：从效率矩阵 C 的每行元素中减去该行的最小元素,得矩阵 B；从矩阵 B 中每列元素中减去该列
20、的最小元素得矩阵 C1。min 0 0 5 0第47页/共53页Step 2、确定C1中线性独立的0元素.从第一行开始，若该行只有一个0元素，就对这个0元素加圈，然后划去其所在列的其它0元素;若该行没有其它0元素或有两个以上0元素（已划去的不计），转下一行；直到最后一行为止。然后,从第一列开始,若该列只有一个0元素,就对这个0元素加圈（同样不考虑已划的）,再划去其所在行的其它0元素;若该列没有0元素或有两个以上0元素，则转下列直到最后一列为止。重复上述步骤.第48页/共53页上述步骤可能出现三种情况情况一：矩阵每行都有一个打圈的 0 元素。此时得到问题的最优解.情况二：有多于两行或两列存在两个
21、以上的未处理的 0 元素，即出现 0 元素的闭回路。此时，可从中任选一个 0元素加圈，划掉其同行同列的 0 元素，再重复上述两个步骤。情况三：矩阵中所有 0 元素或被加圈，或被划去，而已加圈的 0 元素m小于矩阵的行数n。即矩阵中至少存在有一行不含加圈的 0 元素。转步骤三。第49页/共53页Step 3 寻找能覆盖C1中所有0元素的最小直线数.(1)按照从上到下、从左到右的顺序对C1没有加圈的0元行打号；(2)对已打号的行中未加圈0元的列打号；(3)对已打号的列中加圈0元的行打号；(4)重复下去，直到找不出打号的行、列为止。(5)对没打号的行划一横线，对打号的列划一纵线，这就是覆盖矩阵C1中所有0元素的最小直线数.第50页/共53页Step 4、改进C1(1)寻找 C1 没有被直线覆盖的所有元素中的最小元素；例中=2.(2)在已打号的行中减去；(3)在已打号的列中加上；得到一个新矩阵 C2。-2603-292301340054300用 C2 代替 C1，返回步骤 2.第51页/共53页即例题的最优分配方案：确定C2中线性独立的0元素.第52页/共53页感谢您的观看！第53页/共53页