《运筹学复习ppt课件》由会员分享，可在线阅读，更多相关《运筹学复习ppt课件（44页珍藏版）》请在金锄头文库上搜索。
1、运运 筹筹 学学复复 习习运运 筹筹 学学Operational ResearchOperational Research复复 习习例例1 求解如下线性规划问题求解如下线性规划问题解：加入松弛变量，标准化得解：加入松弛变量，标准化得建立单纯形表如下：建立单纯形表如下：解毕解毕例例2 用对偶单纯形法计算用对偶单纯形法计算解：为了便于寻解：为了便于寻找初始正则解，找初始正则解，将问题变形为：将问题变形为：取取x4,x5为初始正为初始正则解，列单纯形表则解，列单纯形表如下：如下：基变换的过程：基变换的过程：-2-3-4XBbx1x2x3x4x5x4x1-2-3-400XBbx1x2x3x4x5x4-
2、3-1-2-110x5-4-21-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-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例例3 3试用对偶原理求解线性规划问题试用对偶原理求解线性规划问题已知其对偶规划的最优解为已知其对偶规划的最优解为解：该该问题的对
3、偶规划为问题的对偶规划为利用松紧关系，代入对偶规划的约束条件得下列约代入对偶规划的约束条件得下列约束是松约束，束是松约束，将最优解将最优解松约束松约束紧约束紧约束其对偶约束是紧约束其对偶约束是紧约束设设原问题的最优解为原问题的最优解为紧约束紧约束设某种物资有设某种物资有3个产地个产地 A1，A2，A3， 生产量分别生产量分别为为9，5，7;有有4个销地个销地B1，B2，B3，B4 ，销售量分销售量分别为别为3，8，4，6 ;已知从已知从Ai到到Bj 物资的单位运价物资的单位运价见见下表下表。求总运费最小的调运方案。求总运费最小的调运方案。B1B2B3B4产量产量A1291079A213425A
4、384257销量销量3846例例4 B1B2B3B4ai行差行差A1291079A213425A384257bj3846列差列差伏格尔法计算1用伏格尔法寻找初始基：用伏格尔法寻找初始基：5121123B1B2B3B4ai行差行差A12910795A2134251A3842572bj3846列差列差1123伏格尔法计算10303/09/6用伏格尔法寻找初始基：用伏格尔法寻找初始基：B1B2B3B4ai行差行差A1291079/65A2134251A3842572bj3/0846列差列差1123伏格尔法计算20306/15/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：52112211223305
5、0B1B2B3B4ai行差行差A1291079/65A213425/01A3842572bj3/0846/1列差列差1123伏格尔法计算30304/07/3用伏格尔法寻找初始基：用伏格尔法寻找初始基：5211221122330505 2 21 12 2 211522833204B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差1123伏格尔法计算40308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：5211221122330505 2 21 12 2 21152283320452 2 21122 2 11 1
6、 5 5 2 2 83 3 2 203B1B2B3B4ai行差行差A1291079/65A213425/01A384257/32bj3/084/06/1列差列差1123伏格尔法计算50308/57/3/0用伏格尔法寻找初始基：用伏格尔法寻找初始基：0500452 2 21122 2 11 1 5 5 2 2 83 3 2 20351得到产销平衡运输问题的一个初始方案得到产销平衡运输问题的一个初始方案.可以得到基可行解对应的位势方程组是：可以得到基可行解对应的位势方程组是：，从上述方程组中依次得，从上述方程组中依次得先在先在中任中任意取定一个未知量的值。比如取意取定一个未知量的值。比如取出出利用
7、这些利用这些u、v则可以算出则可以算出B1B2B3B4aiA1325910179A2134525A38344257bj3846伏格尔法的初始方案及其检验数：伏格尔法的初始方案及其检验数：B1B2B3B4uiA1325910170A213452-5A3834425-5vj2977(3)(4)(-1)(2)(11)(3) x22为为换入变量换入变量, 从从 x22所在格出发做闭回路所在格出发做闭回路L, L中有两个偶点中有两个偶点x24, x12，取取x12为为换出变量换出变量，调整量为，调整量为5.伏格尔法的调整方案：伏格尔法的调整方案：B1B2B3B4aiA1325910179A2103452
8、5A38344257bj3486在闭回路在闭回路L上，偶点变量减上，偶点变量减5，奇点变量加，奇点变量加5.0 x22为为换入变量换入变量, 取取x12为为换出变量换出变量.065它所对应的位势与检验数为：它所对应的位势与检验数为：B1B2B3B4uiA13291067A2153402A3834425vj28670-5-4(1)(4)(4)(3)(10)(2)所有检验数都非负，迭代停止，运费为：所有检验数都非负，迭代停止，运费为：32 + 67 + 53 + 34 + 42 = 83P1：充分利用现有工时，必要时可以加班；充分利用现有工时，必要时可以加班；P2：A，B，C的最低产量分别为的最低
9、产量分别为5，5，8台，并台，并依单位工时的利润比例确定权系数；依单位工时的利润比例确定权系数；P3：生产线加班时每月不超过生产线加班时每月不超过20小时；小时；P4：A，B，C的月销售指标分别定为的月销售指标分别定为10，12，10台，依单位工时利润比例确定权系数台，依单位工时利润比例确定权系数.试建立目标规划模型试建立目标规划模型.例例5： A、B、C三种计算机，在一条生产线上三种计算机，在一条生产线上装配。装配时间分别为装配。装配时间分别为5，8，12小时；利润分小时；利润分别为每台别为每台1000元，元，1440元，元，2520元。生产线每元。生产线每月正常运转月正常运转170小时。该
10、厂的经营目标为：小时。该厂的经营目标为：例例6 厂址选择问题厂址选择问题 在在5个地点中选个地点中选3处建生产同一产品的工厂，在这处建生产同一产品的工厂，在这5个个地点建厂所需投资，占用农田，建成以后的生产能地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示力等数据如下表所示. 地点地点12345所需投资（万元）所需投资（万元）320280240210180占用农田（亩）占用农田（亩）201815118生产能力（万吨）生产能力（万吨）7055422811现在有总投资现在有总投资800万元，占用农田指标万元，占用农田指标60亩，应如亩，应如何选择厂址，使建成后总生产能力最大何选择厂址
11、，使建成后总生产能力最大. 解：设五个解：设五个01变量变量 x1，x2，x3，x4，x5，其中，其中 i=1,2,3,4,5. 建立整数规划模型为建立整数规划模型为 Max z=70x1+55x2+42x3+28x4+11x5s.t.320x1+280x2+240x3+210x4+180x5 80020x1+18x2+15x3+11x4+8x5 60x1+x2+x3+x4+x5=3x1， x2， x3， x4， x5=0,1例例7利用割平面算法求解下面的规划问题利用割平面算法求解下面的规划问题解：将约束条件的系数化整；去掉解：将约束条件的系数化整；去掉“x1,x2是整数是整数”的条件，得到一
12、个线性规划的标准型（的条件，得到一个线性规划的标准型（LP1）为：为：利用单纯形法求解这个线性规划问题，得出最终单纯利用单纯形法求解这个线性规划问题，得出最终单纯形表：形表： 2 3 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最优解不是整数解，由最终表得到变量之间的关系：最优解不是整数解，由最终表得到变量之间的关系：增加如下割平面，增加如下割平面，引入一个松弛变量，化割平面为：引入一个松弛变量，化割平面为：直接反映到直接反映到LP1的最终单纯形表中，得的最终单纯形表中，得LP2单纯单纯形表：形
13、表：LP2 的单纯形表：的单纯形表： 2 3 0 0 0 x1 x2 x3 x4 x5x2x1x55/213/4-1/2 0 1 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 2 3 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 2 3 0 0 0 x1 x2 x3 x4 x5 j 0 0 -1/4 -5/4 0x2x1x32 7/21 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2 j 0 0 0 -1
14、 -1/2由于不是整数解，找出不满足条件的基变量由于不是整数解，找出不满足条件的基变量 x1.用对偶单纯型法求解：用对偶单纯型法求解：将它作为一个新增加的约束加到线性规划将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划中又得一个线性规划LP3 构造线性规划构造线性规划LP2的割平面的割平面LP3的单纯形表： 2 3 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 2 3 0 0 0 0 x1 x
15、2 x3 x4 x5 x6 j 0 0 0 -1 -1/2 0x2x1x3x5 1 4 3 1 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4 0 0 0 0 1 -2 j 0 0 0 -1 0 -1从上表中我们可以看到，已经找到了整数最优解：从上表中我们可以看到，已经找到了整数最优解：x1=4, x2=1。故求解结束。故求解结束。用对偶单纯型法求解：用对偶单纯型法求解：例例8：有一份资料，要分别译成四种文字，现有：有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字
16、所需要的时间人专长不同，他们翻译成不同文字所需要的时间用效率矩阵用效率矩阵 C 表示。应如何分配工作，使他们完表示。应如何分配工作，使他们完成任务的总时间最短？成任务的总时间最短？Step 1、先对效率矩阵进行列变换，使其各行各、先对效率矩阵进行列变换，使其各行各列中都出现列中都出现 0 元素元素.效率矩阵效率矩阵变换方法变换方法为：为：从效率矩阵从效率矩阵 C 的每行元素的每行元素中减去该行的最小元素中减去该行的最小元素,得矩阵得矩阵 B ；从矩阵从矩阵 B 中中每列元素中减去该列的最每列元素中减去该列的最小元素得矩阵小元素得矩阵 C1 。 min 0 0 5 0Step 2、确定、确定C1
17、中线性独立的中线性独立的0元素元素.从第一行开始，若该行只有一个从第一行开始，若该行只有一个0元素，就对这个元素，就对这个0元素加圈，然后划去其所在列的其它元素加圈，然后划去其所在列的其它0元素元素;若该行若该行没有其它没有其它0元素或有两个以上元素或有两个以上0元素（已划去的不计）元素（已划去的不计），转下一行；直到最后一行为止。，转下一行；直到最后一行为止。然后然后,从第一列开始从第一列开始,若该列只若该列只有一个有一个0元素元素,就对这个就对这个0元素元素加圈（同样不考虑已划的）加圈（同样不考虑已划的）,再划去其所在行的其它再划去其所在行的其它0元素元素;若该列没有若该列没有0元素或有两
18、个以元素或有两个以上上0元素，则转下列直到最后元素，则转下列直到最后一列为止。一列为止。重复上述步骤重复上述步骤.上述步骤可能出现三种情况上述步骤可能出现三种情况情况一情况一：矩阵每行都有一个打圈的：矩阵每行都有一个打圈的 0 元素。此时得到问题的最优解元素。此时得到问题的最优解.情况二情况二：有多于两行或两列存在两个以上的未处理：有多于两行或两列存在两个以上的未处理的的 0 元素，即出现元素，即出现 0 元素的闭回路。此时，可从中元素的闭回路。此时，可从中任选一个任选一个 0元素加圈，划掉其同行同列的元素加圈，划掉其同行同列的 0 元素，元素，再重复上述两个步骤。再重复上述两个步骤。情况三情
19、况三：矩阵中所有：矩阵中所有 0 元素或被加圈，或被划去，元素或被加圈，或被划去，而已加圈的而已加圈的 0 元素元素m小于矩阵的行数小于矩阵的行数n。即矩阵中至即矩阵中至少存在有一行不含加圈的少存在有一行不含加圈的 0 元素。转步骤三。元素。转步骤三。Step 3 寻找能覆盖寻找能覆盖C1中所有中所有0元素的最小直线数元素的最小直线数.(1)按照从上到下、从左到右的顺序对按照从上到下、从左到右的顺序对C1没有加圈没有加圈的的0元行打元行打号；号；(2)对已打对已打号的行中未加圈号的行中未加圈0元的列打元的列打号；号；(3)对已打对已打号的列中加圈号的列中加圈0元的行打元的行打号；号；(4)重复
20、下去，直到找不出打重复下去，直到找不出打号的行、列为止。号的行、列为止。 (5)对没打对没打号的行划一横线，号的行划一横线，对打对打号的列划一纵线，这就号的列划一纵线，这就是覆盖矩阵是覆盖矩阵C1中所有中所有0元素的元素的最小直线数最小直线数. Step 4、改进、改进C1(1)寻找寻找 C1 没有被直线覆盖的没有被直线覆盖的所有元素中的最小元素所有元素中的最小元素；例中例中= 2.(2)在已打在已打号的行中减去号的行中减去；(3)在已打在已打号的列中加上号的列中加上；得到一个新矩阵得到一个新矩阵 C2。 -2603-292301340054300用用 C2 代替代替 C1，返回步骤返回步骤 2.即例题的最优分配方案：即例题的最优分配方案：确定确定C2中线性独立的中线性独立的0元素元素.
