第1章 线性规划与单纯形法-第3节.ppt

(第三版)
《运筹学》教材编写组编
清华大学出版社
运筹学
第1章
线性规划与单纯形法

第3节
单纯形法
钱颂迪制作
第1章线性规划与单纯形法
第3节单纯形法
举例
初始基可行解的确定
最优性检验与解的判断
基变换
迭代(旋转运算)
单纯形法求解线性规划的思路:
一般线性规划问题具有线性方程组的变量数大于方程个数,这时有不定的解。但可以从线性方程组中找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小,决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。这样问题就得到了最优解,先举一例来说明。
注:
单纯形是指0维中的点,一维中的线段,二维中的三角形,三维中的四面体,n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体,其顶点分别为(0,0,0),(1,0,0),(0,1,0),(0,0,1)。具有单位截距的单纯形的方程是∑xi≤1,并且xi≥0,i=1,2,…,m。
举例
例6 试以例1来讨论如何用单纯形法求解。例1的标准型为:
约束方程(1-12)式的系数矩阵
从(1-12)式中可以看到x3,x4,x5的系数列向量
P3 ,P4,P5是线性独立的,这些向量构成一个基 对应于B的变量x3,x4,x5为 基变量.
从(1-12)式中可以得到(1-13)
将(1-13)式代入目标函数(1-11)
得到
当令非基变量x1=x2=0,便得到z=0。这时得到一个基可行解X(0)
X(0)=(0,0,8,16,12)T
这个基可行解表示:工厂没有安排生产产品Ⅰ、Ⅱ;资源都没有被利用,所以工厂的利润指标z=0。
从分析目标函数的表达式(1-14)可以看到
非基变量x1,x2(即没有安排生产产品Ⅰ,Ⅱ)的系数都是正数,因此将非基变量变换为基变量,目标函数的值就可能增大。从经济意义上讲,安排生产产品Ⅰ或Ⅱ,就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量,这表示目标函数值还有增加的可能,就需要将非基变量与基变量进行对换。
如何确定换入,换出变量
一般选择正系数最大的那个非基变量x2为换入变量,将它换入到基变量中去,同时还要确定基变量中有一个要换出来成为非基变量,可按以下方法来确定换出变量。
现分析(1-13)式,当将x2定为换入变量后,必须从x3,x4,x5中确定一个换出变量,并保证其余的都是非负,即x3,x4,x5≥0。