运筹学课程小结.doc

运筹学课程小结《运筹学》课程小结运筹学》问题 1: 问题:如何将一般的线性规划问题化成标准型并根据实际问题的需要列出初始单纯形表。据实际问题的需要列出初始单纯形表。(1 )首先将原问题化成标准型,具体就是: )首先将原问题化成标准型,具体就是: 把目标最小的化成目标为最大的形式; 把目标最小的化成目标为最大的形式; 约束条件右端的常数项均化成≥0 的常数; 的常数; 对于取值可正可负的变量, 对于取值可正可负的变量, 通过令其为两个正变量的相减, 即非负) 形式的相减,将其所有变量均化成≥0( 即非负形式; 即非负形式; 通过加入非负的松弛变量或非负的剩余变量把“通过加入非负的松弛变量或非负的剩余变量把“≥”形式的不等式化成等式; 或“≤”形式的不等式化成等式; (2 )在完成上述步骤后,根据问题的需要,适当加)在完成上述步骤后,根据问题的需要, 入人工变量,利用***列出初始单纯形表法列出初始单纯形表。入人工变量,利用大 M 法列出初始单纯形表。举例如下: 举例如下: Min Z=3 x1+4 x22 x3+5 x44 x1 x2+2 x3 x4=2x+x+3xx≤ 1412342 x1+3 x2 x3+2 x4≥2 x1, x2, x3≥ 0, x4 无约束解:原目标变成新目标: 原目标变成新目标: Max Zχ= 3x1 – 4x2 + 2x3 – 5x4 将第一个约束条件两边同乘以( 1) 变成: 将第一个约束条件两边同乘以(-1) 变成: 变成-4x1 + x2– 2x3 + x4=2令 x4= x4χ- x4δ, 在第二个约束条件中加入非负松弛变量 x5 ,在第三个约束条件中加入非负剩余变量 x6 ,就可将原线性规划问题化成如下标准型: 就可将原线性规划问题化成如下标准型: ′′ MaxZ ′= 3x1 4x2 + 2x3 5x4 + 5x4 ′′′ 4x1 + x2 2x3 + x4 x4′=2x+x+ 3xx′+x ′′+x= 14123445′′ 2x1 + 3x2 x3+ 2x4 2x4 ′ x6=2 x1, x2, x3,x′, x4′, x5, x6≥0′4 在这个标准型中, 在这个标准型中,只有变量 x5 可以作为初始的基变量,为得到一组初始的基变量, 变量,为得到一组初始的基变量,我们必须在第一个可得: 与第三个约束条件中分别加入人工变量 x7、 x8 可得′′ Max Z′= 3x1 4x2 + 2x3 5x4 + 5x4 ′ Mx7 Mx8 ′′ 4x1 + x2 2x3 + x4 x4′+ x7=2x+x+ 3xx′+x ′′+x= 14123445′′ 2x1 + 3x2 x3+ 2x4 2x4 ′ x6+ x8=2 x1, x2, x3,x′,x ′′, x5, x6, x7, x8≥044 由此,我们就可以列出初始单纯形表如下: 由此, 我们就可以列出初始单纯形表如下: cj→ CB XB b* -M 0 -M x7 23 x1 -41 -2-4 x211 32 x3 -23 -1-5 x4χ1 -1 25 x4δ-11 -20 x5010 00 x600 -1 -M-M -M x71000 x8001 0x5 14 x82 检验数σ j3- -4+ 2- -5+ 56M 4M 3M 3M 3M 书 P52 ,第 4 题: ,题 cj→ CB 20 28 -Z XB x6 x2 x4 b*a50 -14 0 x1360b0 x20dec0 x3 -14/3 2f0 28 x400101 x51 5/2 0 -12 x6100g 的值; ( 1 )求 a–g 的值; )( 2 )表中给出的解是否为最优解? )表中给出的解是否为最优解? 解:( 1 )根据单纯形表的计算规则有: )根据单纯形表的计算规则有: 2a+0×5+ 28×0= 14×× 由此得出: 由此得出: a=7; 再由: 再由: 0–(2×3+0×6+ 28× 0)=b×××0–(2×0+0×d+ 28× e) =c×××0–[2× (-14/3) +0×2+ 28×f]=0×××2–(2×1+0×0+ 28× 0) =g××× 可得出: 可得出: b= -6,g=0,f= 1/3 ,,,是基变量,所以有: 而由于 x2 是基变量,所以有: d=1, e=c= 0,,, 故可得出: 故可得出: a-g=7–0=7。(2 )又由于 b= -6 < 0,c=0,g=0 ,即表中的非),, 所以,表中给出的解是最优解, 基变量全都≤0 ,所以,表中给出的解是最优解,但由于有非基变量 x3 的检验数σ3=0 ,所以, 该问题有无,所以, 穷多个最优解。穷多个最优解。书 P53 ,第 5 题: ,题如下表是求某极大化线性规划问题计算