对偶单纯形法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,对偶单纯形法,目标,前提,单纯形法,前提,目标,对偶单纯形法,定理,3.4,若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数,回顾,对偶问题,2,3 0 1,0 0 0,1,x,3,1 0 0,1 -1 0 1,x,5,2 0 0,0 -1 1,2,x,因此，对偶单纯形法换基迭代的前提是保证对偶问题基本解的可行性,原始问题的单纯形表的检验数行非正意味着对偶问题基本解的可行性,例,1,用对偶单纯形法求解线性规划问题,解,将原问题化为如下形式，写出增广矩阵,初始基：,初始单纯形表,初始单纯形表,在,“,b,”,列找出最小的负数，用它所在行的所有负数去除对应的检验数，通过最小比值法则确定轴心项，进行换基迭代,.,第二单纯形表,第二单纯形表,重复上述过程，继续换基迭代,.,第三单纯形表,第三单纯形表,“,b,”,列元素全都非负，第三单纯形表即最优单纯形表,.,得原问题的最优解为,最优值为,对偶单纯形法是在原问题的非基本可行解下进行换基迭代的，其前提是保证对偶问题的可行性，即保证单纯形表中所有检验数非正,总之，在单纯形表中，只要能保证原问题或对偶问题的任一可行性，即可进行换基迭代，直到找出最优解,例,2,用对偶单纯形法求解线性规划问题,解,将原问题化为如下形式，写出增广矩阵,选取初始基：,初始单纯形表,得初始单纯形表,初始单纯形表,第二单纯形表,换基迭代,得,第二单纯形表,继续换基迭代，得,第三单纯形表,第二单纯形表,第三单纯形表,第三单纯形表即最优单纯形表，,得原问题的最优解为,最优值为,第三单纯形表,本节作业,77,页,3.2,用对偶单纯形法求解线性规划问题,（,1,）、（,3,）,