运筹学 线性规划 单纯形法.pptx
第五节 单纯形法的进一步讨论本节重点：大M法两阶段法解的存在情况判别第1页/共26页 由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量。由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法：大M法和二阶段法。一、人工变量的引入及其解法1.当约束条件为“”型，引入剩余变量和人工变量第2页/共26页2.大M法的求解过程例1人工变量添加前已为等式，其取值必须为0；-M称为“惩罚因子”第3页/共26页答：最优解为x1=2,x2=2,x3=0,OBJ=36例1的单纯型表迭代过程第4页/共26页3.大M法的一些说明（1）人工变量被迭代出去后一般就不会再成为基变量（2）大M法实质上与原单纯形法一样，M 可看成一个很大的常数（3）当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解（4）大M法手算不会遇到麻烦,但计算机计算很容易产生误差，因此提出了二阶段法。第5页/共26页4.二阶段法的求解过程（1）第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解（2）若第一阶段结束时，人工变量仍在基变量中，则原问题无解（3）第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯形法求解（4）为了简化计算，在第一阶段重新定义价值系数如下：第6页/共26页用二阶段法求解例1的第一阶段第7页/共26页人工变量x6不在基变量中，从最终单纯形表中去除人工变量，更换目标函数为原问题的目标函数，继续用单纯形表计算。第8页/共26页用二阶段法求解例1的第二阶段第9页/共26页1.关于退化问题n当按照最小比值确定换出基变量时，存在多个相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。n退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法，即Bland规则：（1）当按照最大检验数j0确定换入变量时，存在多个相同的最大检验数，始终选取下标值为最小的变量作为换入变量；（2）当按照最小比值确定换出基变量时，存在多个相同的最小比值，始终选取下标值为最小的变量作为换出变量。二、LP解的进一步讨论第10页/共26页第11页/共26页2.关于多重解问题n最优单纯形表中有非基变量的检验数为0第12页/共26页例3 的单纯型表及其迭代过程第13页/共26页4.关于无可行解问题n单纯形表达到最优解检验条件时，人工变量仍在基变量中第14页/共26页例4第一阶段的单纯型表第15页/共26页三、单纯形法小结 如下所示：第16页/共26页1.线性规划模型及其变换根据实际问题给出数学模型，进行标准化，列出初始单纯型表，见表,变量xj 0 xj 0 xj无约束不需要处理令xj=-xj;xj0令xj=xj-xj;xj,xj0约束条件b0b0计 算i=bi/aik令l=mini第l个基变量为换出变量，alk为主元素1xk替换xl2列出新的单纯形表对主元素行（第l行）其它行i（il）否3.对目标函数求极大值标准型线性规划问题，单纯形法计算步骤的框图第19页/共26页例1：某糖果厂用原材料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号的糖果中A、B、C含量，原料成本，各种原料每月限制用量，三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号糖果多少kg，使该厂获利最大。试建立该问题的LP的数学模型。甲乙丙原料售价元/kg每月限量kgA60%30%22000B1.52500C20%5060%11200加工费元/kg0.50.40.3售价元/kg3.42.852.25第20页/共26页第21页/共26页例2：捷运公司拟在下一年度的14月份的4个月需租用仓库堆放物资。已知各月份所需仓库面积数列于下表 月份1234所需仓库面积（100m2）15102012仓库租用费随合同期而定，期限越长，折扣越大。具体数字见下表。合同租借期限1个月2个月3个月4个月合同期内的租金（元/100m2）2800450060007300租借仓库的合同每月初都可办理，每份合同都具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订的租借合同的最优决策，目的是所付租借费用最小。第22页/共26页解：若用变量 表示捷运公司在第 个月初签定的租借期为 个月的仓库面积的合同（单位为100 ）。因5月份起该公司不需要租借仓库，均为零。该公司希望总的租借费用为最小，故有如下的数学模型：目标函数：约束条件第23页/共26页例3 某城市在一昼夜间，市内交通需要车辆数如图，对车辆的需求在昼夜间是变化的，车辆的工作制度是一天连续工作8小时，派车时间在各时间间隔的端点，一旦派出，就连续工作8小时。求保证需要的最小车辆数。车辆数时间04712162024481248121084第24页/共26页 派车时间在各时间间隔的端点，一旦派出，就连续工作8小时。设：各时间间隔所派车辆数为xj j=1，2，6则有：min Z=x1+x2+x3+x4+x5+x6 x1+x64 x1+x28 x2+x3 10 x3+x47 x4+x512 x5+x6 4 x1，x2，x3，x4，x5，x6 0第25页/共26页感谢您的观看！第26页/共26页
