运筹学 第1章 线性规划与 (第三版) 单纯形法 《运筹学》教材编写组编 第3节 单纯形法 钱颂迪制作 清华大学出版社
（第三版） 《运筹学》教材编写组 编 清华大学出版社 运筹学 第1章 线性规划与 单纯形法 第3节 单纯形法 钱颂迪 制作
第1章线性规划与单纯形法 第3节单纯形法 3.1举例 3.2初始基可行解的确定 3.3最优性检验与解的判断 34基变换 3.5迭代(旋转运算
第1章 线性规划与单纯形法 第3节 单纯形法 3.1 举例 3.2 初始基可行解的确定 3.3 最优性检验与解的判断 3.4 基变换 3.5 迭代（旋转运算）
单纯形法求解线性规划的思路: 般线性规划问题具有线性方程组的变 量数大于方程个数,这时有不定的解。 但可以从线性方程组中找出一个个的单 纯形,每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还 是变小,决定下一步选择的单纯形。这 就是迭代,直到目标函数实现最大值或 最小值为止。这样问题就得到了最优解, 先举一例来说明
单纯形法求解线性规划的思路： • 一般线性规划问题具有线性方程组的变 量数大于方程个数，这时有不定的解。 但可以从线性方程组中找出一个个的单 纯形，每一个单纯形可以求得一组解， 然后再判断该解使目标函数值是增大还 是变小，决定下一步选择的单纯形。这 就是迭代，直到目标函数实现最大值或 最小值为止。这样问题就得到了最优解， 先举一例来说明
注: 单纯形是指0维中的点,一维中的线段,二维 中的三角形,三维中的四面体,n维空间中的 有n+1个顶点的多面体。例如在三维空间中的 四面体,其顶点分别为(0,0,0),(1,0,0) (0,1,0),(0,0,1)。具有单位截距的单纯 形的方程是∑xi≤1,并且xi≥0,i=1,2,…,m
注： • 单纯形是指0维中的点，一维中的线段，二维 中的三角形，三维中的四面体，n维空间中的 有n+1个顶点的多面体。例如在三维空间中的 四面体，其顶点分别为(0，0，0)，(1，0，0)， (0，1，0)，(0，0，1)。具有单位截距的单纯 形的方程是∑xi≤1，并且xi≥0，i=1,2,…,m
3.1举例 例6试以例1来讨论如何用单纯形法求解。例1的 标准型为: maxz=2x1+3x2+0x3+0x4+0x x,+ 2x tx 4x,1+ =16 (1-12) +xe=12 x≥0j=1,2,…,5
3.1 举例 例6 试以例1来讨论如何用单纯形法求解。例1的 标准型为： max 2 3 0 0 0 (1 11) z = x1 + x2 + x3 + x4 + x5 − 0 1,2, ,5 4 12 4 16 (1 12) 2 8 2 5 1 4 1 2 3 = + = + + = − + + = x j x x x x x x x j