用单纯形方法解线性规划问题.ppt

《用单纯形方法解线性规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、§12.1线性规划问题的标准型§12.2单纯形解的基本概念§12.3单纯形方法引例§12.4单纯形方法返回第十二章线性规划问题的单纯形法第十二章线性规划问题的单纯形法图解法对于两个变量的线性规划问题，是一个简单易行、形象直观的求解方法，但是当决策变量多于两个时，图解法就失效了．因此有必要研究线性规划问题更一般的解法，这种方法就是单纯形法．本章我们首先介绍线性规划问题的标准型，然后介绍有关单纯形法的重要概念，最后对单纯形法进行讨论．§12.1线性规划问题的标准型一、线性规划模型的标准型线性规划模型的标准型规定如下：s.t.其中其紧缩形式为：其中

2、其矩阵形式为：其中若令则于是线性规划问题的标准型具有如下特点：（1）目标函数为最小：（2）决策变量为非负：（3）约束条件为等式：（4）约束常数为非负：二、线性规划问题的标准化1．目标函数最小化2．决策变量非负化3．约束条件等式化4．约束常数非负化即目标函数统一为最小；决策变量统一为非负；约束条件统一为等式；约束常数统一为非负．如果给出的问题中，目标函数是最大化的类型，则可令S′=-S，这样就将目标函数即最小化．在求出S′的值以后，乘以（-1）就是原问题的最大值．如果某个变量没有非负限制，即xj≤0或xj符号不限．对于xj≤0，可令xj′=-x

3、j，xj′≥0；若符号不限，则可令xj=xj′-xj″,其中xj′≥0,xj″≥0，当约束条件为“≤”式时，可在不等号的左边加上一个非负的变量，一般称为松弛变量，使不等式成为等式．当约束条件为“≥”式时，可在不等号的左边减去一个非负的变量，一般称为剩余变量，使不等式成为等式．若某个约束方程的右端常数为负数时，则可在这个约束等式两端同乘以（-1），从而使得右端常数为非负．例12.1.1将下面的线性规划问题化为标准型解（1）令S=S′，则（2）由于x2没有非负限制，因此可令其中（3）引入剩余变量松弛变量可将第一、二个约束条件化为等式，即（4）以（

4、-1）乘以第三个约束方程两边，使其右端常数非负．于是，可得上述线性规划模型的标准型注1：所求的由于引入的剩余变量在经济问题中表示应付需求的剩余，而松弛变量表示没有被利用的闲置资源，它们都不会产生利润，所以在目标函数中，其系数必为零．注2：§12.2单纯形解的基本概念对于一个线性规划问题其约束矩阵为一、基、基变量和非基变量设约束方程系数矩阵A的前m个列向量线性无关则有=（P1P2…Pm

5、Pm+1…Pn）=（B

6、N）一般总是假r(A)=m

7、，并称构成基阵的列向量为基向量，其余的列向量Pm+1，Pm+2，…，Pn称为非基相对应的称为关于基B的基变量，除此均称为关于基B的非基变量.向量；与基向量二、基本解、基本可行解和最优基本可行解对变量X也做相应的分块，即其中，XB表示关于基B的基变量，XN表示关于基B的非基变量．即因为所以存在B-1，用B-1左乘上式后得可知，每给非基变量XN一组值，就能得到基变量XB的一组相应的值，从而得线性规划问题的一个解．特别当时，得这样，约束方程组AX=b可以改写为称之为线性规划问题的一个基本解．如果在基本解中则称X为线性规划问题的一个基本可行解，相应的

8、基B称为线性规划问题的一个可行基．使目标函数达到最优的基本可行解，称为最优基本可行解，相应的基称为最优基．三、基本可行解的性质（1）线性规划问题如果有可行解，则必有基本可行解．（2）线性规划问题的可行域中，点X是顶点的充要条件是：X为基本可行解．（3）线性规划问题如有最优解，其最优解必可在它的基本可行解中找到．§12.3单纯形方法引例例1某厂用A、B两种原料生产甲、乙两种产品，已知一吨产品分别需要各种原料的数量、可得利润及工厂现存原料的数量如下表所示．甲乙现有原料A1328B4142利润（千元/吨）75试问甲、乙产品各生产多少，可获得最大利润

9、？解设甲、乙产品分别生产吨，则引入松弛变量将模型化为标准型：显然，是一个现成的初始可行基，对应的基变量和非基变量分别为令非基变量可得它是对应基B0的一个基本可行解，此时的目标函数值为零，这表明甲、乙产品都没有安排生产，各种资源都没有动用。解,因而也不是最优基．目标函数值便会减少，所以，从目标函数中可以看出，只要不是最优于是就需要“换基”．怎样换基？即让哪个非基变量“进基”呢？原则上讲，应该先让使目标函数减少得多的那个非基变量进基．的，的系数大由于利润函数中，因此选x1进基．于因为该问题的约束系数矩阵的秩r(A)=2，因此在x1进基的同时，原基

10、变量必须有一个被换出基，那么又让谁“出基”呢？换基后必须保证新基仍然是可行基．因为当x1进基后，x2仍是新基B1的非基变量，所以在新基B1中仍取x2=0．并保持x3