min = = -3x, + x, + x3[x -2x2 +x, ≤11-4xi +x2+2x,≥3-2x +x, =1X,x2,x≥0在第一个约束条件中加入松弛变量x；在第二个约束条件中加入剩余变量x和人工变量x；在第三个约束条件中加入人工变量x。（1）大M法：在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数中的系数为（-M）（M为很大的正数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则自标函数不会实现最大化。对上例求解，加入人工变量后，规划问题变成min z =-3x, +x, + x, + 0x, +0x, + Mx+ Mx,X,-2x2+x+x=11-4xj+X2+2x-Xs+X6=3-2x +X +x =11X1,X2,X3,X4,Xs,X6,X≥0然后，利用单纯形法求解，详见P33。（2）两阶段法第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量后，构造仅含人工变量的目标函数和要求实现最小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数作为第二阶段计算的初始表，利用单纯形法求解。前一个例子的两阶段法求解如下：构造出第一阶段的数学模型如下：min z= X+ XX -2x2 +x +x=11-4x +X2 +2x3-xs+x=3-2x +x +x, =1Xj,x2,Xg,X4,X5,X6,X, ≥0000000.11c
− + = − + + − + = − + + , , 0 2 1 4 2 3 2 11 min 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x 在第一个约束条件中加入松弛变量 4 x ；在第二个约束条件中加入剩余变量 5 x 和人工变量 6 x ；在第三个约束条件中加入人工变量 7 x 。 （1）大 M 法： 在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函 数值不产生影响，可假定人工变量在目标函数中的系数为（-M）（M 为很大的正 数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则 目标函数不会实现最大化。 对上例求解，加入人工变量后，规划问题变成 − + + = − + + − + = − + + = = − + + + + + + , , , , , , 0 2 1 4 2 3 2 11 min 3 0 0 1 2 3 4 5 6 7 1 3 7 1 2 3 5 6 1 2 3 1 2 3 4 5 6 7 x x x x x x x x x x x x x x x x x x x z x x x x x Mx Mx 然后，利用单纯形法求解，详见 P33。 （2）两阶段法 第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量 后，构造仅含人工变量的目标函数和要求实现最小化；然后用单纯形法求解，若 得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停 止计算。 第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数 作为第二阶段计算的初始表，利用单纯形法求解。 前一个例子的两阶段法求解如下： 构造出第一阶段的数学模型如下： − + + = − + + − + = − + + = = + , , , , , , 0 2 1 4 2 3 2 11 min 1 2 3 4 5 6 7 1 3 7 1 2 3 5 6 1 2 3 6 7 x x x x x x x x x x x x x x x x x x x z x x j c 0 0 0 0 0 1 1 i
bCBXBx3Xx4XsX6XX2110111-2 00011x41120103-4-163/2011-20[1]0011760100-1-3cj-zj0000011ci0,6CBXB3sX6Xx4X7X20103-2 0100-1一x4110[1] 00-11-21x61000110一-2X3000100-1c,-2)000001c,10,CBXBbXx34xsX6t230020121-2 -5-x400100111-1-2x2010001-2 1x3000011c,-2j得最优解X=(0,1,1,12,0,0,0)。由于人工变说明变量X==0X=(0,1,1,12,0)是原问题的基可行解，可进行第二阶段运算。利用单纯形法，从下表开始：-311000,cj
CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x 11 1 -2 1 1 0 0 0 11 1 6 x 3 -4 1 2 0 -1 1 0 3/2 1 7 x 1 -2 0 [1] 0 0 0 1 1 j j c − z 6 -1 -3 0 1 0 0 j c 0 0 0 0 0 1 1 i CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x 10 3 -2 0 1 0 0 -1 - 1 6 x 1 0 [1] 0 0 -1 1 -2 1 0 3 x 1 -2 0 1 0 0 0 1 - j j c − z 0 -1 0 0 1 0 0 j c 0 0 0 0 0 1 1 i CB XB b 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x 12 3 0 0 1 -2 2 -5 - 0 2 x 1 0 1 0 0 -1 1 -2 1 0 3 x 1 -2 0 1 0 0 0 1 - j j c − z 0 0 0 0 0 1 1 得最优解 T X = (0,1,1,12,0,0,0) 。由于人工变量 x6 = x7 = 0 ，说明 T X = (0,1,1,12,0) 是原问题的基可行解，可进行第二阶段运算。利用单纯形法，从 下表开始： j c -3 1 1 0 0 i
CBXB6Xix3XsX2x4[3] 101200-2一X41101001-1X21101-200x3一0001-1c,-z,1100cf-30,bCBXBX3XsXiX2X44100-31/3-2/3一X110100-11X219001一x32/3-4/30001/31/3c,-z,二、解的退化所有的检验数均≤01、基变量中有非零的人工变量，无可行解；2、某非基变量的检验数为零，有无穷多解；对于任一检验数>0，若对应的系数向量P，≤0，则有无界解。单纯形法小结x,≥0不需处理x,≤0令x,=-x; x,≥0变量x,无约束令x,=x,-x,,x,x,≥0b≥0不需处理约束条件b<0约束条件两端同乘-1
CB XB b 1 x 2 x 3 x 4 x 5 x 0 4 x 12 [3] 0 0 1 -2 - 1 2 x 1 0 1 0 0 -1 1 1 3 x 1 -2 0 1 0 0 - j j c − z -1 0 0 0 1 j c -3 1 1 0 0 i CB XB b 1 x 2 x 3 x 4 x 5 x -3 1 x 4 1 0 0 1/3 -2/3 - 1 2 x 1 0 1 0 0 -1 1 1 3 x 9 0 0 1 2/3 -4/3 - j j c − z 0 0 0 1/3 1/3 二、解的退化 所有的检验数均 0 1、基变量中有非零的人工变量，无可行解； 2、某非基变量的检验数为零，有无穷多解； 对于任一检验数 0 ，若对应的系数向量 Pj 0 ，则有无界解。 单纯形法小结 变量 x j 0 不需处理 x j 0 令 j j x = −x ' ； x j 0 j x 无约束 令 ' " j j j x = x − x ， , 0 ' " x j x j 约束条件 b 0 不需处理 b 0 约束条件两端同乘-1
加松弛变量xsVI=加人工变量xal减剩余变量x，加人工变量≥Xaimax zmin z目标函数松弛变量xsi0加入变量的系数人工变量xa-M
加松弛变量 si x = 加人工变量 ai x 减剩余变量 si x ，加人工变量 ai x 目标函数 max z min z 加入变量的系 数 松弛变量 si x 0 人工变量 ai x − M
第三章运输问题1、教学计划第2次课2学时第三章授课章节授课方式／理论课口讨论课口实验课口习题课口其他掌握运输问题的模型特点；熟悉表上作业法的基本步骤如初始调运方课堂教学案的确定，非基变量检验数的确定方法，当前解是否最优解的判断，目的及要求闭回路调整方法；非平衡运输问题的求解。重点：初始调运方案的确定，非基变量检验数的确定，判断当前解课堂教学是否最优解，闭回路调整方法，非平衡运输问题的求解方法。重点及难点难点：初始基可行解的确定、判断，非平衡问题的求解思路。教学过程教学方法及手段多媒体讲解3.1运输问题的提出及其模型特征运输问题的提出背景及其模型特征实例讲解3.2运输问题的求解：表上作业法表上作业法的思路和步骤如初始基可行解教学过程的确定（最小元素法和伏格尔法），最优解的判断方法，闭回路调整方法。3.3产销不平衡的运输问题将不平衡问题转化为平衡问题。2、教案3.1运输问题的提出及其模型特征1、背景大规模的物资调运，将物资从生产地点运往消费地点，要求在现有的交通网络下，制定出总费用最小的运输方案。2、模型特征销地21产量n产地1Ci1C12Cina
第三章 运输问题 1、教学计划 第 2 次课 2 学时 授课章节 第三章 授课方式 □√理论课 □讨论课 □实验课 □习题课 □其他 课堂教学 目的及要求 掌握运输问题的模型特点；熟悉表上作业法的基本步骤如初始调运方 案的确定，非基变量检验数的确定方法，当前解是否最优解的判断， 闭回路调整方法；非平衡运输问题的求解。 课堂教学 重点及难点 重点：初始调运方案的确定，非基变量检验数的确定，判断当前解 是否最优解，闭回路调整方法，非平衡运输问题的求解方法。 难点：初始基可行解的确定、判断，非平衡问题的求解思路。 教学过程 教学过程 教学方法及手段 3.1 运输问题的提出及其模型特征 运输问题的提出背景及其模型特征 3.2 运输问题的求解：表上作业法 表上作业法的思路和步骤如初始基可行解 的确定（最小元素法和伏格尔法），最优解的判 断方法，闭回路调整方法。 3.3 产销不平衡的运输问题 将不平衡问题转化为平衡问题。 多媒体讲解 实例讲解 2、教案 3.1 运输问题的提出及其模型特征 1、背景 大规模的物资调运，将物资从生产地点运往消费地点，要求在现有的交通网 络下，制定出总费用最小的运输方案。 2、模型特征 销地 产地 1 2 . n 产量 1 11 c 12 c . n c1 1 a