单纯形法的计算步骤.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,*,Page,*,单纯形法的计算步骤,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量,x,j,作为换入变量，当有一个以上检验数大于,0,时，一般选择最大的一个检验数，即：，其对应的,x,k,作为换入变量。,确定换出变量。根据下式计算并选择,，,选最小的,对应基变量作为换出变量。,单纯形法的计算步骤,用换入变量,xk,替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。,5,）重复,3,）、,4,）步直到计算结束为止。,单纯形法的计算步骤,换入列,b,i,/a,i2,，,a,i2,0,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,单纯形法的进一步讨论人工变量法,例1.10 用大M法解下列线性规划,解：首先将数学模型化为标准形式,系数矩阵中不存在单位矩阵，无法建立初始单纯形表。,单纯形法的进一步讨论人工变量法,故人为添加两个单位向量，得到人工变量单纯形法数学模型：,其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。,单纯形法的进一步讨论人工变量法,单纯形法的进一步讨论人工变量法,单纯性法小结:,