第1章线性规划与单纯形法 第3节单纯形法 3.1举例 3.2初始基可行解的确定 3.3最优性检验与解的判断 3.4基变换 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) ·具有单位截距的单纯形的方程是∑x;≤1，并且 x;≥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+0x5(1-11) X1+2x2+X3 三 8 4X1+ +X4 =16 (1-12) 4X2 +x5=12 xj≥0j=1,2,…,5
3.1 举例 例6 试以例1来讨论如何用单纯形法求解。 例1的标准型为： = + + + + xxxxxz 54321 − )111(00032max 5,,2,10 4 12 4 )121(16 2 8 2 5 1 4 321 =≥ " =+ =++ − + + = jx x x x x xxx j
约束方程(1-12)式的系数矩阵 12100 A=(B,D,P,P4,P)= 40010 04001 从(1-12)式中可以看到x3,x4,x的系数列向量 1 0 P3= 0 .Pa .Ps 0 B=(,P4,P)= 0 0 0 1 0 是线性独立的，这些向量构成一个基
约束方程(1-12)式的系数矩阵 从(1-12)式中可以看到x 3,x 4,x 5的系数列向量 ( ) ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = = 1 0 0 0 1 0 040 004 121 ,,,, PPPPPA 54321 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 1 0 0 , 0 1 0 , 0 0 1 3 4 PPP 5 ( ) ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = = 100 010 001 ,, PPPB 543 是线性独立的，这些向量构成一个基