运筹学第五章2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.,单纯形法的表格形式,目标函数：,约束条件：,如：,迭代,次数,0,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,0 0 0 0 0 0,P3,检验数行,1,1.,首先将,LP,问题写为对应于基,B,的典则形式,(,典式,):,典式的特点,:,(1),约束方程组系数矩阵含有一个,m,m,阶的单位矩阵（或以,单位矩阵各列向量组成的矩阵），以这个矩阵作为初始可行基；,（,2,）,目标函数中不含基变量（即基变量系数为零）。,目标函数：,约束条件：,已为典式！,系数矩阵：,选,为基。,2,2.,将典式中的数据填入单纯形表格：,迭代,次数,0,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,0,确定入基变量：,则,为入基变量。,确定出基变量：,列：填入基变量。,列：填入非基变量在原目标函数中的系数。,行：填入典式中目标函数各变量的检验数及常数项的负值。,主元（转轴元）,P1,3,迭代,次数,1,1 1 1 0 0,2 1 0 1 0,0 1 0 0 1,0,1 0 1 0 -1,2 0 0 1 -1,50 0 0 0 -100,-25000,50,150,0 0 -2 1 1,0 1 0 0 1,迭代,次数,2,1 0 1 0 -1,50,50,250,-27500,4,所有的检验数,此基本可行解：,为最优解。,最优目标函数值为：,5,例,1,用单纯形法求解：,解：,引入松弛变量,将问题化为标准形式：,已是典式。,6,迭代,次数,0,4,3 2 0 0 0,-1 2 1 0 0,3 2 0 1 0,1 -1 0 0 1,14,3,0,0,0,3 2 0 0 0,0,7,0 1 1 0 1,0 5 0 1 -3,5,0,0,3,0 5 0 0 -3,-9,1 -1 0 0 1,3,1,7,2,7,0 1 1 0 1,0 5 0 1 -3,5,0,0,3,0 5 0 0 -3,-9,1 -1 0 0 1,3,1,0,2,3,0 1 0 1/5 -3/5,1,0 0 1 -1/5 8/5,1 0 0 1/5 2/5,6,4,0 0 0 -1 0,-14,所有的检验数,最优解为：,最优目标函数值为：,8,3.,用人工变量法求解线性规划问题,第二章例,2,的线性规划模型为,:,目标函数：,约束条件：,引进剩余变量,松弛变量,将上面的问题化为标准型：,目标函数：,约束条件：,在系数矩阵中没有单位,矩阵或由单位矩阵的列向量,构成的矩阵。,9,在约束方程中引进人工变量，使得系数矩阵中含有单位矩阵,或由单位矩阵列向量构成矩阵。,人工变量法：,人工变量法包括：,“,大,M,法,”,和,“,两阶段法,”,。,大,M,法解线性规划问题：,引进人工变量,则约束条件变为：,约束方程组的系数矩阵为：,选初始可行基,基变量为：,初始基可行解为：,10,为了竭尽全力使得人工变量为零，规定人工变量在目标函数,中的系数为,-,M,，,M,为任意大的正数。,如,大,M,法,：,为了构造初始可行基得到初始可行解，把人工变量,“强行”地加入到原来的约束方程中去，又为了尽量把人工变量,从基变量中替换出来，就令人工变量在求最大值的目标函数里,的系数为,-M,，,这个方法，叫大,M,法，,M,叫做,罚因子,。,为了使目标函数达到最大，一般把人工变量从基变量中换,出。,若一直到最后仍不能从基中换出，且人工变量仍不为零，,则该问,题无可行解；,若人工变量虽然在基中，但取值为零，则,新,LP,问题和原,LP,问题有同解。,11,用单纯性表格解该线性规划,475,M,-2+2,M,迭代,次数,0,1 1 -1 0 0 1 0,1 0 0 -1 0 0 1,2 1 0 0 1 0 0,-2 -3 0 0 0 -,M,-,M,-,M,-,M,0,350,125,600,-3+,M,-,M,0,0,0,-,M,350/1,125/1,600/2,12,-,M,-2,0,1 0 0 -1 0 0 1 125,0 1 -1 1 0 1 -1 225,迭代,次数,0,1 1 -1 0 0 1 0,1 0 0 -1 0 0 1,2 1 0 0 1 0 0,475,M,-2 -3 0 0 0 -,M,M,-2+2,M,-3+,M,-,M,-M,0,0,0,-,M,-,M,0,350,125,600,350/1,125/1,600/2,1,1 1 0 2 1 0 -1 325,0,-3+,M,-,M M,-2,0,0,2-2,M,225,M,225/1,-,350/2,225,M,+250,13,2,-,M,-2,0,1 0 0 -1 0 0 1 125,0 1 -1 1 0 1 -1 225,1,1 1 0 2 1 0 -1 350,0,-3+,M,-,M M,-2,0,0,2-2,M,225,M,225/1,-,350/2,3,-,M,-2,0,0 1/2 0 1 1/2 0 -1 175,0 1/2 -1 0 -1/2 1 0 50,1 1/2 0 0 1/2 0 0 300,0 ,M,-2 -,M,0 ,M,+1 0 -,M,50,M,+600,50*2,300*2,175*2,-3,-2,0,0 1 -2 0 -1 2 0 100,1 0 1 0 1 -1 0 250,0 0 1 1 1 -1,-1,125,0 0 -4 0 -1 -,M,+4 -,M,800,注：,由于,M,为任意大数，,x,2,和,s,3,的检验数可以认为是一样大，这时最好选决策变量入基，而不是松弛、剩余和人工变量入基。,14,所有的检验数都小于等于,0,，而且人工变量都已出基，已找到,最优解。,最优解为：,最优目标函数值为：,作业：,P99,5.(2),6,15,