运筹学单纯形法.ppt

第32页,共48页，2024年2月25日，星期天确定初始单纯形表后可以得到初始基可行解x0,若有某个非基底变量xk对应的检验数?k=(ck-zk)0,则当前解不是最优解，取使目标增长最大的非基底变量进入基底。根据确定xk为换入变量根据确定xs为换出变量将xk对应的列向量Pk=(a1k,,…,ask,…,ank)T变换为aik=0，isaik=1，i=s重复上述步骤直到所有的检验数满足最优条件，得最优解。第33页,共48页，2024年2月25日，星期天§5单纯形法的进一步讨论人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，?，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。第34页,共48页，2024年2月25日，星期天1、大M法方法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题第35页,共48页，2024年2月25日，星期天111-211000113-4120-1103/21-20[1]000110M16xx4x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3-31100MM-10001M-1M+1zj-cj0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-201