一个简单的线性规划问题

欢迎大家来到IT世界,在知识的湖畔探索吧!

这里借助网络一个PPT，讲述一个简单的线性规划问题。

可以归纳出线性规划问题的一般形式是：

求一组决策变量 xj (j=1 ,2 , … , n)使得

欢迎大家来到IT世界,在知识的湖畔探索吧!

其中cj , aij , bi (i=1 , 2 , … , n)均为已知实常数．式(2.1)称为目标函数，式(2.2)和(2.3)称为约束条件,特别称式(2.3)为非负约束条件．

问题可以转化为：

这里松弛变量的作用就是把小于等于号转变为等号。因为一共有三个小于等于号，所以引入三个松弛变量。

•为使目标函数值增加得快一些，可选择正系数中最大的那个非基变量为进基（称为“σ 规则”）．

•由于max{2,3} = 3是非基变量 x2 的系数，因此确定 x2 为进基．但基变量的个数是一定的（等于系数矩阵A的秩m），于是还要确定从原基变量 x3 , x4 , x5 中哪一个换出来作为非基变量（称为“岀基”）．为此我们进行如下分析．

•从式（2.38）可知，首先，目标函数中不含基变量 x3 , x4 , x5；其次，非基变量 x1 , x2 的系数都是正数，如果将其中一个变量，例如 x1（或 x2 ）由非基变量换为基变量（称为“进基”），则 x1（或 x2）的取值可以由零变成正值，就会使目标函数的值增大．从而可以断定初始基可行解 x(0) 并不是最优解．

•从经济意义上讲，安排生产产品A（或B），都可以使工厂的利润指标增加．所以，只要不含基变量的目标函数的表达式（2.38）中有非基变量的系数为正，就表示目标函数值还有改进可能．

•从经济意义上讲，由于每生产一件产品B，需要耗掉钢、铁、橡胶三种原料数分别为2吨，0吨，4吨，当确定生产产品B的产量为3/2件时，则需要消耗钢、铁、橡胶三种原料数分别为3吨，0吨，6吨，这说明原料橡胶已全部用完．因此，由这些原料中的薄弱环节橡胶的供应量确定了产品B的产量不超过3/2件．这充分体现了岀基的选择兼顾各种限制条件的思想，又称为最小比值法则．

这里是指对于式2.43中令x3=0，x5=min{2,6}=2时才能满足非负条件，此时最小比值2对应的基变量是x4，x4被换出，变成x5=2-(1/2)x4，然后代入其它两个方程，再令x3，x4都为0 ，就得到上图的解。

这里的基可以换进换出，是因为n维空间中任意n个线性无关的向量都可以作为基变量。

比如，二维平面任意两个不平行的向量都可以作为基向量。‌ 在二维平面中，任意两个不平行（即线性无关）的向量都可以作为基底，用于表示平面内的任何向量‌。

基底的定义是两个不共线的向量。在二维平面中，如果两个向量不平行，那么它们就可以作为基底，用于生成该平面内的所有向量。基底的选择不是唯一的，但必须是线性无关的‌。

上图中一共有四个互不平行的向量，可以任意选择两个作为这个二维平面的基向量。