清华大学出版社：《运筹学》课程教学资源（PPT课件讲稿，教材第三版）第1章 线性规划与单纯形法 第3节 单纯形法

运筹学 第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

约束方程(1-12)式的系数矩阵 12100 A=(,21)=|40010 从(1-12)式中可以看到x,x,x的系数列向量 P2=0 00

约束方程(1-12)式的系数矩阵 • • 从(1-12)式中可以看到x3 ,x4 ,x5的系数列向量 ( )           = = 1 0 0 0 1 0 0 4 0 4 0 0 1 2 1 , , , , A P1 P2 P3 P4 P5           =           =           = 1 0 0 , 0 1 0 , 0 0 1 P3 P4 P5

P,P,P是线性独立的,这些向量构成一个基 B=(,P1,B)=|010 对应于B的变量x2x4x为 00 基变量 x1+2x2+x 4x1 16(1-12) 从(1-12)式中可以 4. 得到(1-13) x3=8-x1-2x2 4=16-4x (1-13) 5 4x

P3 ,P4 ,P5是线性独立的，这些向量构成一个基 对应于B的变量x3 ,x4 ,x5为 基变量. ( )           = = 0 0 1 0 1 0 1 0 0 , , B P3 P4 P5 4 12 4 16 (1 12) 2 8 2 5 1 4 1 2 3 + = + = − + + = x x x x x x x (1 13) 12 4 16 4 8 2 5 2 4 1 3 1 2 −      = − = − = − − x x x x x x x 从(1-12)式中可以 得到（1-13）

将(1-13)式代入目标函数(1-11) max z=2x1+3x2+0x3+Ox4+Ox5 得到=0+2x1+3x2 (1-14) 当令非基变量x1x2=0,便得到z=0。这时得到 个基可行解X0 X0(0,0,8,16,12) 这个基可行解表示:工厂没有安排生产产品I Ⅱ1;资源都没有被利用,所以工厂的利润指标 0

将(1-13)式代入目标函数(1-11) • 得到 • 当令非基变量x1 =x2 =0，便得到z=0。这时得到 一个基可行解X (0) • X(0)=(0,0,8,16,12)T • 这个基可行解表示：工厂没有安排生产产品Ⅰ、 Ⅱ；资源都没有被利用，所以工厂的利润指标 z=0。 max 2 3 0 0 0 (1 11) z = x1 + x2 + x3 + x4 + x5 − 0 2 3 (1 14) z = + x1 + x2 −

从分析目标函数的表达式(1-14)可以看到 非基变量x1,x2(即没有安排生产产品I, Ⅱ)的系数都是正数,因此将非基变量变 换为基变量,目标函数的值就可能增大 从经济意义上讲,安排生产产品Ⅰ或Ⅱ 就可以使工厂的利润指标增加。所以只 要在目标函数(1-14)的表达式中还存在有 正系数的非基变量,这表示目标函数值 还有增加的可能,就需要将非基变量与 基变量进行对换

从分析目标函数的表达式(1-14)可以看到 • 非基变量x1 ,x2 (即没有安排生产产品Ⅰ， Ⅱ)的系数都是正数，因此将非基变量变 换为基变量，目标函数的值就可能增大。 从经济意义上讲，安排生产产品Ⅰ或Ⅱ， 就可以使工厂的利润指标增加。所以只 要在目标函数(1-14)的表达式中还存在有 正系数的非基变量，这表示目标函数值 还有增加的可能，就需要将非基变量与 基变量进行对换

如何确定换入,换出变量 一般选择正系数最大的那个非基变量x2 为换入变量,将它换入到基变量中去, 同时还要确定基变量中有一个要换出来 成为非基变量,可按以下方法来确定换 出变量。 现分析(1-13)式,当将x2定为换入变量 后,必须从x2,x,x中确定一个换出变量, 并保证其余的都是非负,即x3,Xx5≥0

如何确定换入，换出变量 • 一般选择正系数最大的那个非基变量x2 为换入变量，将它换入到基变量中去， 同时还要确定基变量中有一个要换出来 成为非基变量，可按以下方法来确定换 出变量。 • 现分析(1-13)式，当将x2定为换入变量 后，必须从x3 ,x4 ,x5中确定一个换出变量， 并保证其余的都是非负，即x3 ,x4 ,x5≥0