运筹学笔记7单纯形表

改写,改写的目标是约束条件中所有的基变量都用非基变量来表示。

 目标函数,用非基变量来表示。

联立后的方程组的特点是,用非基变量表示了约束条件中的基变量。

 典式的特点以下图中的式子为例:

我们选定了基B是P1,P2,即B=(P1,P2),此时基变量就是x1,x2,那么x3,x4就是非基变量。

下图右下角是上述基B对应的典式。通过观察此典式,可以归纳为出3条特征:

1. 原方程组中的约束条件在典式中的特征是,一个等式只能含有一个基变量,且基变量的系数必须是1;

2. 目标函数等式在典式中不能含有基变量,只能含有非基变量;

3. 所有的变量必须放在等号的左侧;

思考2:

给定基B之后如何得到典式呢?

仍然以上图中例子来说明,不过这次选择B=(P1,P4)来作为基,由此可知基变量为x1,x4,显然非基变量为x2,x3;
如果要写出典式,我们要先写出典式的等价形式,即: 用非基变量表示的约束等式和目标函数;

这三个式子组合在一起,称为当前基B对应的典式的等价形式;

然后移项,把这三个式子中所有的变量放到等号的左侧,然后就得到了标准型关于基B=(P1,P4)的典式;

自己也可练习,找出该问题中的(这个等式中的)其他的基,以及基所对应的典式;

下面可以根据典式来做出一个表格:

表格中当给定基B之后,左上角的xB是固定的,其对应的基变量写在其同一列的下面;b拔是对应的典式中的常量/数,写在其所在列的下方;z则表示目标函数的那些;

单纯形表和典式是一一对应的关系,如果把典式看作是线性方程组的话,那么单纯形表就是其对应系数的增广矩阵的体现;知道其一,可写出另一个;

由单纯形表可看出:当前基所对应的基解,并能看出此基解所对应的目标函数值;并且,可从单纯形表判定当前的基解是不是最优解;

 

单纯形表中,最左侧一列基的顺序,一般是先写序号小的,再写序号大的;但是也没有固定要求,写时注意对应即可。上图例,先写x4,再写x1也行,但要注意对应起来。

如上图示:如果只知道图下部的单纯形表,那么我们应该能知道其基变量示B=(P1,P2),且知道当前基对应的基解是:

因为基解要求非基变量取值必须是零,所以,非基变量的x3,x4取值为零;而x1,x2对应的就是单纯形表最右边一列的值(其对应左边的基变量的取值),18和8;

也即(18,8,0,0)的转置即是当前基B对应的基解;它对应的目标函数值是1(最有一列的1),可把基解带入目标函数验证下;

同理:如果只看上图的单纯性表则可知,上图对应的基是B=(P1,P4),对应的基解是(14,0,0,2)的转置这个列向量;其对应的目标函数值是-40;

原文地址:https://www.cnblogs.com/Li-JT/p/15169325.html