《运筹学复习ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学复习ppt课件.ppt（44页珍藏版）》请在三一文库上搜索。
1、运 筹 学,复 习,运 筹 学,Operational Research,复 习,例1 求解如下线性规划问题,解：加入松弛变量，标准化得,建立单纯形表如下：,解毕,例2 用对偶单纯形法计算,基变换的过程：,最优解 X*=(11/5，2/5，0，0，0)；z*=-28/5,例3,试用对偶原理求解线性规划问题,已知其对偶规划的最优解为,解：,该问题的对偶规划为,利用松紧关系，,代入对偶规划的约束条件得下列约 束是松约束，,将最优解,松约束,紧约束,其对偶约束是紧约束,设原问题的最优解为,紧约束,设某种物资有3个产地 A1，A2，A3， 生产量分别为9，5，7;有4个销地B1，B2，B3，B4 ，销
2、售量分别为3，8，4，6 ;已知从Ai到Bj 物资的单位运价见下表。求总运费最小的调运方案。,例4,伏格尔法计算1,用伏格尔法寻找初始基：,伏格尔法计算1,用伏格尔法寻找初始基：,伏格尔法计算2,用伏格尔法寻找初始基：,伏格尔法计算3,用伏格尔法寻找初始基：,伏格尔法计算4,用伏格尔法寻找初始基：,伏格尔法计算5,用伏格尔法寻找初始基：,得到产销平衡运输问题的一个初始方案.,可以得到基可行解对应的位势方程组是：,利用这些u、v则可以算出,伏格尔法的初始方案及其检验数：,(3),(4),(-1),(2),(11),(3),x22为换入变量, 从 x22所在格出发做闭回路L, L中有两个偶点x24
3、, 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 + 67 + 53 + 34 + 42 = 83,P1：充分利用现有工时，必要时可以加班； P2：A，B，C的最低产量分别为5，5，8台，并依单位工时的利润比例确定权系数； P3：生产线加班时每月不超过20小时； P4：A，B，C的月销售指标分别定为10，12，10台，依单位
4、工时利润比例确定权系数. 试建立目标规划模型.,例5： A、B、C三种计算机，在一条生产线上装配。装配时间分别为5，8，12小时；利润分别为每台1000元，1440元，2520元。生产线每月正常运转170小时。该厂的经营目标为：,例6 厂址选择问题,在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示.,现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大.,解：设五个01变量 x1，x2，x3，x4，x5，其中,i=1,2,3,4,5.,建立整数规划模型为,例7,利用割平面算法求解下面的规划问题,解：将约
5、束条件的系数化整；去掉“x1,x2是整数”的条件，得到一个线性规划的标准型（LP1）为：,利用单纯形法求解这个线性规划问题，得出最终单纯形表：,最优解不是整数解，由最终表得到变量之间的关系：,增加如下割平面，,引入一个松弛变量，化割平面为：,直接反映到LP1的最终单纯形表中，得LP2单纯形表：,LP2 的单纯形表：,由于不是整数解，找出不满足条件的基变量 x1.,用对偶单纯型法求解：,将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3,构造线性规划LP2的割平面,LP3的单纯形表：,从上表中我们可以看到，已经找到了整数最优解：x1=4, x2=1。故求解结束。,用对偶单纯型法求
6、解：,例8：有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵 C 表示。应如何分配工作，使他们完成任务的总时间最短？, ,Step 1、先对效率矩阵进行列变换，使其各行各列中都出现 0 元素.,效率矩阵变换方法为： 从效率矩阵 C 的每行元素中减去该行的最小元素,得矩阵 B ；从矩阵 B 中每列元素中减去该列的最小元素得矩阵 C1 。,min 0 0 5 0,Step 2、确定C1中线性独立的0元素.,从第一行开始，若该行只有一个0元素，就对这个0元素加圈，然后划去其所在列的其它0元素;若该行没有其它0元素或有两
7、个以上0元素（已划去的不计），转下一行；直到最后一行为止。,然后,从第一列开始,若该列只有一个0元素,就对这个0元素加圈（同样不考虑已划的）,再划去其所在行的其它0元素;若该列没有0元素或有两个以上0元素，则转下列直到最后一列为止。,重复上述步骤.,上述步骤可能出现三种情况,情况一：矩阵每行都有一个打圈的 0 元素。此时得到问题的最优解.,情况二：有多于两行或两列存在两个以上的未处理的 0 元素，即出现 0 元素的闭回路。此时，可从中任选一个 0元素加圈，划掉其同行同列的 0 元素，再重复上述两个步骤。,情况三：矩阵中所有 0 元素或被加圈，或被划去，而已加圈的 0 元素m小于矩阵的行数n。即
8、矩阵中至少存在有一行不含加圈的 0 元素。转步骤三。,Step 3 寻找能覆盖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元素.,