大工15秋《运筹学》开卷考试期末复习资料 1 2 3 销量 3 7 2 60 2 5 5 40 7 2 4 20 6 3 5 15 50 60 25 表2 初始调运方案 销地 产地 1 2 3 销量
解：先找出各非基变量的闭回路，即从表2的某一空格（非基变量）为起点，用水平或垂直线，只有碰到数字格（基变量）后才旋转90，继续向前划，直到回到起始空格为止。检验数的计算，就是从空格对应的单位运价开始，对闭回路所对应的单位运价交替地赋予“+”和“-”号，并计算它们的代数和，如表3所示。
表3
空格 （1丙） （1丁） （2乙） （3乙） （3丙） （3丁） 闭回路 （1丙）—（2丙）—（2甲）—（1甲）—（1丙） （1丁）—（2丁）—（2甲）—（1甲）—（1丁） （2乙）—（2甲）—（1甲）—（1乙）—（2乙） （3乙）—（3甲）—（1甲）—（1乙）—（3乙） （3丙）—（3甲）—（2甲）—（2丙）—（3丙） （3丁）—（3甲）—（2甲）—（2丁）—（3丁） 检验数 7-2+7-3=9 6-3+7-3=7 5-7+3-2=-1 5-2+3-2=4 4-2+7-2=7 5-2+7-3=7 选出检验数最小的为（-1），小于0，所以该初始调运方案不是最优调运方案。 3、试用单纯形法解下列线性规划问题。
?甲 10 25 25 60 乙 40 40 丙 20 20 丁 15 15 产量 50 60 25 maxz?x1?2x2
?2x1?2x2?8?s.t.?0x1?2x2?4
?x，x?0?12解：①化标准形，找一个单位矩阵作为基，列出初始单纯形表
大工15秋《运筹学》开卷考试期末复习资料 第13页 共16页
大工15秋《运筹学》开卷考试期末复习资料
maxz?x1?2x2?0x3?0x4
?8?2x1?2x2?x3??x4?4 s.t.?0x1?2x2?x，x，x，x?01234?②建立初始单纯形表
表1
cj 1 2 x2 0 0 biCB 0 0 XB x3 b 8 4 x1 2 0 x3 1 0 x4 0 1 aik ??i 2 2 x4 cj?zj 如表1所示，其中cj为目标函数中决策变量xj的系数（j?1，由系数矩阵A??，2，3，4）
?2210???0201?选择单位矩阵B1=??10?TX?(x，x)作为初始可行基，则对应的基变量为，基变量的系数CB=（0，B34??01?T0），常数向量（资源向量）b?(8,4)，列出约束方程组的增光矩阵bA.（注：XB所对应的列的变量（x3，
x4）为基变量，其余的变量都为非基变量）
③计算初始单纯形表中的检验数
cj?zj=cj?CBB?1Pj=cj?CBPj(1)x2的检验数： ，如非基变量x1，?2?(1)c1?z1=c1?CBP1=1-（0 0）??=1-（0*2+0*2）=1
?0??2?(1)c2?z2=c2?CBP2=2-（0 0）??=2-（0*2+0*2）=2
?2?基变量x3，x4的检验数为0（所有基变量的检验数都必定为0，不用再另行计算），由于非基变量的检验数为1和2，都大于零，所以当前的基础可行解不是最优解，需要进行线性变换。
④确定换入变量和换出变量
由刚才计算得出的检验数最大的为2，则其对应的变量x2为换入变量，接下来运用最小比例原则
大工15秋《运筹学》开卷考试期末复习资料 第14页 共16页
大工15秋《运筹学》开卷考试期末复习资料
?bi?(?=min?aij?o?确定换出变量:
ia???ij??1=b1a11=8/2=4
?2=b2a21=4/2=2
其中2最小，则其对应的变量x4为换出变量，增广矩阵中的换出变量所对应的行与换入变量所对应的列的元素a22=2为主元素，如表2所示。
表2 cj 1 2 x2 0 0 biCB 0 0 XB x3 b 8 4 x1 2 0 1 x3 1 0 0 x4 0 1 0 aik??i 2 【2】 2? 8/2=4 4/2=2? x4 cj?zj ⑤进行迭代运算，得出下一个单纯形表，对增广矩阵进行线性变换，将主元素变为1，将主元素所在列的其他元素变为零。如将主元素所在的行都除以2，则可将主元素变为1，即（4，0，2，0，1）/6=（2，0，1，0，1/2）；再将主元素所在的列的元素2变为0，即（8，2，2，1，0）-（4，0，2，0，1）=（4，2，0，1，-1）。从而得到新的单纯形表，如表3所示。
此时的基本可行解为X??x1,x2,x3,x4?=(0,2,4,0)
TT
表3
cj 1 2 x2 0 0 biCB 0 2 XB x3 b 4 2 x1 【2】 0 1? x3 1 0 0 x4 -1 1/2 -1 aik??i 0 1 0 4/2=2? 2/0 x2 cj?zj ⑥计算新的单纯形表中非基变量的检验数，如表3；根据检验数是否全小于等于零，判断此时的基本可行解是否达到最优，如果没有则重新确定换入变量，换出变量和主元素，如表3；继续进行按上述方法迭代运算，直到求得最优解，如表4所示。
大工15秋《运筹学》开卷考试期末复习资料 第15页 共16页
大工15秋《运筹学》开卷考试期末复习资料
表4
cj 1 2 x2 0 0 biCB 1 2 XB x1 b 2 2 x1 1 0 0 x3 1/2 0 -1/2 x4 -1/2 1/2 -1/2 Taik ??i 0 1 0 x2 cj?zj 此时非基变量的检验数都小于零，所以此时的解X??x1,x2?=(2, 2)
T为最优解，
maxz?x1?2x2?0x3?0x4?6
大工15秋《运筹学》开卷考试期末复习资料 第16页 共16页
相关推荐：
loading