运筹学-总复习

《运筹学-总复习》由会员分享，可在线阅读，更多相关《运筹学-总复习（95页珍藏版）》请在金锄头文库上搜索。

1、运 筹 学,复 习,求解如下线性规划问题,例1,复 习,解：加入松弛变量，标准化得,建立单纯形表如下：,复 习,复 习,解毕,复 习,用对偶单纯形法计算,例2,复 习,练习：求解如下线性规划问题,复 习,由于初始正则解有负分量，于是取min-3,-4=-4 x5为换出变量，取,x1为换入变量，得新基x4,x1 ，51= -2为主元,复 习,基变换的过程：,主元变为1，即用-2去除单纯形表中基变量x5所在的行； 主元所在列的其它元变为0，消去非基变量x1所在的列的其余元-1，-2； 得新基x4,x1的单纯形表,复 习,基变换的过程：,复 习,可见正则解的有负分量，由于x4=1 , 所以取x4为换

2、出变量，取,x2为换入变量，得新基x2,x1 ，42=-5/2为主元,复 习,此时正则解是可行解，也是最优解。X*=(11/5，2/5，0，0，0)；z*=-28/5,进行基变换，得新正则解的单纯形表：,复 习,试用对偶原理求解线性规划问题,已知其对偶规划的最优解为,例3,复 习,解：,该问题的对偶规划为,复 习,利用松紧关系，,代入对偶规划的约束条件得下列约 束是松约束，,将最优解,松约束,紧约束,其对偶约束是紧约束,复 习,设原问题的最优解为,紧约束,复 习,已知其对偶问题的最优解为Y=(4,1)。,练习：试用对偶原理求解线性规划问题,设某种物资有3个产地 A1，A2，A3， 生产量分别为

3、9，5，7;有4个销地B1，B2，B3，B4 ，销售量分别为3，8，4，6 ;已知从Ai到Bj 物资的单位运价见下表。求总运费最小的调运方案。,例4,复 习,存在基变量为0的解称为退化解。,在确定初始基可行解的过程中，如果某一步中出现情况：当产地Ai处的余量与销地Bj处的需求量相等时，在格(i,j)填入运量后，产地Ai处的余量与销地Bj处的销量同时为0,相应地要划去一行和一列。这时就出现了退化。,为了使基变量个数恰好有m+n-1个，应在同时划去的一行或一列中的某个格中填入数字0，表示这格中的变量是取值为0的基变量；,复 习,伏格尔法计算1,用伏格尔法寻找初始基：,先算出运价表中各行与各列的最小

4、运费与次小运费的差额，并填入该运价表的最右列和最下行。 从行差或列差中选出最大者，并选择其所在行或列的最小元素。,A1的行差最大，而其中运价c11最小, 令x11为优先运输路线。,复 习,用伏格尔法寻找初始基：,销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3 填到调运方案表中第1行第1列上。,画去运输数据表第一列，A1的产量剩余为9-3=6。得到新的产销平衡与单位运价表.,令,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,再算出运价表中的行差与列差。,B4的列差最大，而其中运价c24最小, 令x24为优先运输路线。,产地A2的产量2全供给销地B4，所以x23=x24=

5、0。,画去运输数据表中第2行，B4的销量还要6-5=1。得新表。,令,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,伏格尔法计算1,复 习,用伏格尔法寻找初始基：,现在只有一个产地两个销地，故令x12 =5 ,x14 =1为基变量，将其分别填到调运方案表中1行2列与1行4列上。,得到产销平衡运输问题的一个初始方案,伏格尔法计算1,复 习,此方案的运费是 32+59+47+52+34+42=88。 伏格尔法给出的初始解往往更接近于最优解。,复 习,利用伏格尔法确定的初始解如下表所示：,1、写出基可行解对应的位势方程组; 2、并计算非基变量的检验数

6、。,复 习,求解位势及检验数的过程可在一个特殊设计的表上完成，这个表的构造如下： 在原单位运价表增加一行与一列，在列中填入ui，在行中填入vj；把运价cij记在每一格的右上角，用框标定，在基变量对应的格中标出0，构成表。,复 习,由u1+v1=2, u1+v2=9, u1+v4=7,得v1=2, v2=9, v4=7;,0,-5,-5,2,9,7,7,位势表：,再由u2+v4=2，u3+v2=4，得u2=-5，u3=-5;,最后由u3+v3=2 得v3=7.,取u1=0;,复 习,检验数表：,(计算所有非基变量的检验数),0,-5,-5,2,9,7,7,(3),(4),(-1),(2),(11

7、),(3),当存在非基变量的检验数kl 0，说明现行方案为最优方案，否则目标成本还可以进一步减小。,复 习,伏格尔法的初始方案：,(3),(4),(-1),(2),(11),(3),x22为换入变量, 从 x22所在格出发做闭回路L, L中有两个偶点x24, x12，,取x12为换出变量，调整量为5.,复 习,伏格尔法的调整方案：,在闭回路L上，偶点变量减5，奇点变量加5.,0,x22为换入变量,取x12为换出变量.,0,6,5,复 习,它所对应的位势与检验数为：,2,8,6,7,0,-5,-4,(1),(4),(4),(3),(10),(2),所有检验数都非负，迭代停止，运费为： 32 +

8、67 + 53 + 34 + 42 = 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,复 习,复 习,应用实例(习题4.5),某种牌号的酒系是用3种等级

9、的酒勾兑而成。已知各种等级酒的每天供应量和单位成本如下： 等级1：供应量1500单位/天，成本6元/单位 等级2：供应量2000单位/天，成本4.5元/单位 等级3：供应量1000单位/天，成本3元/单位 这种牌号的酒有3种商标（红、黄、蓝），各种酒的勾兑配比与售价如下：,为保持声誉，确定经营目标为： 1、勾兑配比必须严格按照要求 2、企业获取尽可能多的利润 3、红色商标的酒每天产量不得少于2000单位 试建立问题的规划模型。,解：设i，j=1，2，3分别表示序号 xij: 第i等级的酒在第j种商标酒中的数量 yj: 第j商标的酒产量,产量约束条件（绝对）,原料约束条件（绝对）,配比约束条件（

10、目标）,利润约束条件（目标）,红色商标酒产量约束条件（目标）,目标函数：,例. 已知某实际问题的线性规划模型为,假定重新确定这个问题的目标为：,练习：某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩电的销量是24台，每台获利80元；黑白电视机的销量是30台，每台获利40元。该厂确定的目标依次为：,1：充分利用装配线每周开动40小时；,2：允许装配线加班，但加班时间每周尽量不超过10小时；,3：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权系数为2。 试建立这问题的数学模型(不用求解)。,利用割平面算法求解下面的整数

11、规划问题,例6,复 习,解：将约束条件的系数化整；去掉“x1, x2是整数”的条件，得到一个线性规划的标准型（LP1）为：,利用单纯形法求解这个线性规划问题，得出最终单纯形表：,复 习,最优解不是整数解，由最终表得到变量之间的关系：,将上面的约束条件当中的变量和系数改写成整数与非负真分数的和,把整数部分放在左边，非整数部分放在右边。,下面增加割平面，选真分数最大的一个,由于上式左端是整数，因此右端也应是整数，由于变量都是不小于0的整数，所以上式右端必是一个不大于0.5 的整数，即,称这个不等式为一个割平面。,引入一个松弛变量，化割平面为：,将它作为一个新增加的约束条件加入线性规划LP1中得到一

12、个新的线性规划LP2 ；,或者直接反映到LP1的最终单纯形表中，得LP2单纯形表：,割平面的处理：,复 习,LP2 的单纯形表：,LP1 ：,LP2 ：,复 习,由于不是整数解，找出不满足条件的基变量 x1.,用对偶单纯型法求解：,复 习,将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3,构造线性规划LP2的割平面,复 习,LP3 ：,LP3的单纯形表：,复 习,从上表中我们可以看到，已经找到了整数最优解：x1=4, x2=1。故求解结束。,用对偶单纯型法求解：,复 习,练习：用割平面算法求解下面整数规划问题。,有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这

13、项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵 C 表示。应如何分配工作，使他们完成任务的总时间最短？, ,例7,Step 1、先对效率矩阵进行列变换，使其各行各列中都出现 0 元素.,效率矩阵变换方法为： 从效率矩阵 C 的每行元素中减去该行的最小元素,得矩阵 B ；从矩阵 B 中每列元素中减去该列的最小元素得矩阵 C1 。,min 0 0 5 0,Step 2、确定C1中线性独立的0元素.,从第一行开始，若该行只有一个0元素，就对这个0元素加圈，然后划去其所在列的其它0元素;若该行没有其它0元素或有两个以上0元素（已划去的不计），转下一行；直到最后一行为止。,然后,从第

14、一列开始,若该列只有一个0元素,就对这个0元素加圈（同样不考虑已划的）,再划去其所在行的其它0元素;若该列没有0元素或有两个以上0元素，则转下列直到最后一列为止。,重复上述步骤.,上述步骤可能出现三种情况,情况一：矩阵每行都有一个打圈的 0 元素。此时得到问题的最优解.,情况二：有多于两行或两列存在两个以上的未处理的 0 元素，即出现 0 元素的闭回路。此时，可从中任选一个 0元素加圈，划掉其同行同列的 0 元素，再重复上述两个步骤。,情况三：矩阵中所有 0 元素或被加圈，或被划去，而已加圈的 0 元素m小于矩阵的行数n。即矩阵中至少存在有一行不含加圈的 0 元素。转步骤三。,Step 3 寻

15、找能覆盖C1中所有0元素的最小直线数.,(1)按照从上到下、从左到右的顺序对C1没有加圈的0元行打号； (2)对已打号的行中未加圈0元的列打号； (3)对已打号的列中加圈0元的行打号； (4)重复下去，直到找不出打号的行、列为止。,(5)对没打号的行划一横线，对打号的列划一纵线，这就是覆盖矩阵C1中所有0元素的最小直线数.,Step 4、改进C1,(1)寻找 C1 没有被直线覆盖的所有元素中的最小元素； 例中= 2. (2)在已打号的行中减去； (3)在已打号的列中加上； 得到一个新矩阵 C2。,用 C2 代替 C1，返回步骤 2.,即例题的最优分配方案：,确定C2中线性独立的0元素.,练习：求解下列任务分配问题。,应用动态规划求解,其中 c 是一个给定的正数。,分析：将该规划问题看成是产品生产问题。 即终止状态已知。,例8,设阶段数 k = 1,2,3； 状态变量为 ,其中 , , 决策变量为 ; 的指标函数为 , 则状态转移方程为：,解 用顺序法. 问题直观模型为：,各阶段的允许决策集合为：,令最优值函数 表示从第阶段到第阶段终止状态 所得到的最大值.则基本方程为:,