运筹学-总复习.ppt

解： 该问题的对偶规划为 利用松紧关系， 代入对偶规划的约束条件得下列约 束是松约束， 伏格尔法的调整方案： 7 5 9 ai 6 8 4 3 bj 5 2 7 2 4 10 4 3 9 8 1 2 4 3 A3 5 0 A2 1 5 3 A1 B4 B3 B2 B1 在闭回路L上，偶点变量减5，奇点变量加5. 0 x22为换入变量, 取x12为换出变量. 0 6 5 复 习 它所对应的位势与检验数为： ui vj 5 2 7 2 4 10 4 3 9 8 1 2 4 3 A3 0 5 A2 6 3 A1 B4 B3 B2 B1 2 8 6 7 0 -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个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示。 11 28 42 55 70 生产能力（万吨） 8 11 15 18 20 占用农田（亩） 180 210 240 280 320 所需投资（万元） 5 4 3 2 1 地点 现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。 例6 复 习 复 习 解：设五个0—1变量 x1，x2，x3，x4，x5，其中 i=1,2,3,4,5. 建立整数规划模型为 =0,1 ， x5 ， x4 ， x3 ， x2 x1 =3 +x5 +x4 +x3 +x2 x1 ? 60 +8x5 +11x4 +15x3 +18x2 20x1 ?800 +180x5 +210x4 +240x3 +280x2 320x1 s.t. +11x5 +28x4 +42x3 +55x2 70x1 Max z= 利用割平面算法求解下面的规划问题 例7 复 习 解：将约束条件的系数化整；去掉“x1, x2是整数”的条件，得到一个线性规划的标准型（LP1）为： 利用单纯形法求解这个线性规划问题，得出最终单纯形表： 0 0 -1/4 -5/4 σj 0 1 1/2 -1/2 1 0 -1/4 3/4 2.5 3.25 x2 x1 x1 x2 x3 x4 3 2 0 0 复 习 最优解不是整数解，由最终表得到变量之间的关系： 0 0 -1/4 -5/4 σj 0 1 1/2 -1/2 1 0 -1/4 3/4 2.5 3.25 x2 x1 x1 x2 x3 x4 3 2 0 0 将上面的约束条件当中的变量和系数改写成整数与非负真分数的和 把整数部分放在左边，非整数部分放在右边。 下面增加割平面，选真分数最大的一个 由于上式左端是整数，因此右端也应是整数，由于变量都是不小于0的整数，所以上式右端必是一个不大于0.5 的整数，即 称这个不等式为一个割平面。 引入一个松弛变量，化割平面为： 将它作为一个新增加的约束条件加入线性规划LP1中得到一个新的线性规划LP2 ； 或者直接反映到LP1的最终单纯形表中，得LP2单纯形表： 割平面的处理： 复 习 LP2 的单纯形表： 0 0 -1/4 -5/4 0 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0