第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 是线性独立的，这些向量构成一个基
X3=8-X1-2x2 从(1-12)式可得到： x4=16-4x1 (1-13) x5=12 -4X2 将(1-13)式代入目标函数(1-11) maxz=2x1+3x2+0x3+0x4+0x5 1-11) 得到 z=0+2x1+3x2 (1-14) ·当令非基变量x1=x20,便得到z=0。这时得到一 个基可行解：X0=(0,0,8,16,12)T ·这个基可行解表示：工厂没有安排生产产品I、 Ⅱ；资源都没有被利用，所以工厂的利润指标 Z=0
将(1-13)式代入目标函数(1-11) 54321 )111(00032max 得到 • 当令非基变量x 1=x 2=0，便得到z=0。这时得到一 个基可行解: X(0)=(0,0,8,16,12) T • 这个基可行解表示：工厂没有安排生产产品Ⅰ、 Ⅱ；资源都没有被利用，所以工厂的利润指标 z=0 。 = + + + + xxxxxz − 320 )141( = + + xxz 21 − )131( 412 416 28 5 2 4 1 3 21 − ⎪ ⎩ ⎪ ⎨ ⎧ −= −= −−= x x xx xxx 从(1-12)式可得到:
从分析目标函数的表达式(1-14)可以看到 非基变量x,X,(即没有安排生产产品I, Ⅱ)的系数都是正数，因此将非基变量变 换为基变量，目标函数的值就可能增大。 从经济意义上讲，安排生产产品I或 Ⅱ，就可以使工厂的利润指标增加。所 以只要在目标函数(1-14)的表达式中还存 在有正系数的非基变量，这表示目标函 数值还有增加的可能，就需要将非基变 量与基变量进行对换
从分析目标函数的表达式(1-14)可以看到 • 非基变量 x 1,x 2 (即没有安排生产产品Ⅰ， Ⅱ )的系数都是正数，因此将非基变量变 换为基变量，目标函数的值就可能增大。 从经济意义上讲，安排生产产品Ⅰ或 Ⅱ，就可以使工厂的利润指标增加。所 以只要在目标函数(1-14)的表达式中还存 在有正系数的非基变量，这表示目标函 数值还有增加的可能，就需要将非基变 量与基变量进行对换
如何确定换入、换出变量 ·一般选择正系数最大的那个非基变量x,为 换入变量，将它换入到基变量中去，同 时还要确定基变量中有一个要换出来成 为非基变量，可按以下方法来确定换出 变量。 现分析(1-13)式，当将x,定为换入变量 后，必须从x3,x,X,中确定一个换出变 量，并保证其余的都是非负，即 X3)X4,X5≥0
如何确定换入、换出变量 • 一般选择正系数最大的那个非基变量x 2 为 换入变量，将它换入到基变量中去，同 时还要确定基变量中有一个要换出来成 为非基变量，可按以下方法来确定换出 变量。 • 现分析(1-13)式，当将x 2定为换入变量 后，必须从x 3,x 4,x 5中确定一个换出变 量，并保证其余的都是非负，即 x 3,x 4,x 5≥0
非负限制（可行性） 当x1=0,由(1-13)式得到 X3 8-2x2≥0 X4 =16 ≥0 (1-15) x5=12-4x2≥0 ·只有选择x,=min(8/2,-,12/4)=3时，才能 使(1-15)式成立。 。 因当x,=3时，基变量X=0,这就决定用x2 去替换x°
非负限制（可行性） )151( 0412 16 0 028 5 2 4 3 2 − ⎪ ⎩ ⎪ ⎨ ⎧ ≥−= = ≥ ≥−= xx x x x • 只有选择x 2=min(8/2,-,12/4)=3时，才能 使(1-15)式成立。 • 因当 x 2=3时，基变量 x 5=0，这就决定用 x 2 去替换 x 5 。 当 x 1=0, 由(1-13)式得到
实际意义 。每生产一件产品Ⅱ，需要用掉各种资源 数为(2,0,4)。 ·由这些资源中的薄弱环节，就确定了产 品Ⅱ的产量。 这里就是由原材料B的数量确定了产品Ⅱ 的产量x,12/4=3件
实际意义 • 每生产一件产品Ⅱ，需要用掉各种资源 数为(2，0，4)。 • 由这些资源中的薄弱环节，就确定了产 品Ⅱ的产量。 • 这里就是由原材料B的数量确定了产品Ⅱ 的产量x2=12/4=3件