第1章 线性规划 (2)—03,04,05讲.ppt

1、运筹学,邮箱：luo06_,第1章 线性规划,复习 1、 线性规划问题的数学模型包含三个组成要素： 决策变量 目标函数 约束条件 2、 线性规划数学模型的标准型，以及与非标准型的转化。 3、图解法的一般步骤。,本堂课的主要内容 1、图解法的几何意义； 2、单纯形法的概念； 3、单纯形法的几何语言； 4、单纯形法的代数形式 5、单纯型表格。 重点及难点：单纯形表,1、图解法的几何意义；,凸集（Convex set）概念： 设K是n维欧氏空间的一个点集，若K中的任意两点x(1),x(2)的连线上的一切点x仍在K中，则称K为凸集。 即：若K中的任意两点x(1),x(2) K，存在0=1 使得 x=

2、x(1)+(1- )x(2) K,则称K为凸集,例（凸集）,例（非凸集）,两个基本概念： 凸组合(Convex combination)： 设x(1),x(2) .x(k)是n维欧氏空间中的k个点，若存在数u1,u2,.uk 且0ui 1 (i=1,2,k), ui =1, 使得 x= u1 x(1)+ u2 x(2) +.+ uk x(k) 成立，则称x为x(1),x(2) .x(k)的凸组合。,两个基本概念： 顶点 ：设K是凸集, 若K中的点x 不能成为K中任何线段上的内点，则称x为凸集K的顶点。 即：若K中的任意两点x(1),x(2) ，不存在数 （0 1） 使得 x= x(1)+(1-

3、 )x(2) 成立，则称x为凸集K的一个顶点。,例： 多边形上的点是顶点,圆周上的点都是顶点,1、图解法的几何意义；,以例子1.1为例：,1、图解法的几何意义；,以例子1.1为例：,8个顶点中(0,6)、(2,6)、(4,3)、(4,0)、(0,0)位于可行域的边界上，是可行解。称为顶点可行解；（0,9）、(4,6)、(6,0)称为顶点非可行解。,2、单纯形法的概念,LP（线性规划）解的基本概念,标准型：,2）基：标准型中，A的秩为m， 是矩阵A的满秩子矩阵，则B是线性规划问题的一个基（基矩阵）。 则B中的列向量为基向量，与基向量对应的决策变量称为基变量，其它变量称为非基变量。,1）可行解,满

4、足（1）、（2）的解,2、单纯形法的概念,3） 基解,令非基变量 为0，则由约束方程确定的唯一解,为基本解，简称基解。,4） 基可行解,若基解X0，则称为基可行解。,结论： 1、LP的基可行解对应于可行域的顶点。 2、若可行域有界， LP的目标函数一定可以在其可行域的顶点上达到最优，即一定存在一个基可行解是最优解。,2、单纯形法的概念,求解例1.1的基、基变量、基解、基可行解和可行基。,2、单纯形法的概念,求解例1.1的基、基变量、基解、基可行解和可行基。,2、单纯形法的概念,求解例1.1的基、基变量、基解、基可行解和可行基。,基变量：,2、单纯形法的概念,求解例1.1的基、基变量、基解、基可

5、行解和可行基。,令,解得，,解得，,基解,2、单纯形法的概念,求解例1.1的基、基变量、基解、基可行解和可行基。,基解,基解中所有变量取值为非负，故也是基可行解； 对应的基 是一个可行基,2、单纯形法的概念,2.1 单纯形法的几何意义；,单纯形法：按照一种规则的方式，从一个顶点向相邻的一个顶点转换，直到找到一个最优解为止。,单纯形法的基本方法,基本方法：,确定初始基可行解,检验是否最优？,转到另一更好的 基可行解,停,Y,N,方法前提：模型化为标准型,1. 化为标准型,2. 确定一基可行解,令 B=(P3,P4,P5)，得:,基可行解X(0)=(0,0,360,200,300)T,3. 进基、

6、出基,（1）进基 存在正系数的非基变量 X(0)不是最优，令x2进基,（2）出基 (1)式中，令x1 =0 ，得:,分别令x3,x4,x5 =0 ，得,x2=90,40,30,x5出基,代数形式,故得新基变量XB=(x2, x3,x4)。,将(1)化为:,得新基可行解X(1)=(0, 30,240,50,0)T,将(3)代入目标函数得,Z=3.4 x1 1.2x5+360,Z*=360,4. 重复3,因存在正系数的非基变量，故继续,得,X(2)=(20, 24,84,0,0)T,Z=-1.36 x4 0.52x5+428,故X(2)为最优解， Z*=428,单纯形法的基本方法,基本方法：,确定

7、初始基可行解,检验是否最优？,转到另一更好的 基可行解,停,Y,N,方法前提：模型化为标准型,三、单纯形法的步骤,1. 初始可行基B0的确定,若A中含有I：B0=I 若A中不含I：人工变量法,2. 最优性检验,把目标函数用非基变量表示：,检验数向量，记为。当 0时，当前解为最优解。,方法：,（1）计算每个xj的检验数,（2）若所有j 0 ，则当前解为最优；,否则，至少有k 0 ，转3。,3. 换基迭代（基变换）,得新基，转2。,注：,（2）若对一切非基变量有j 0 ，且存在k =0， 则有无穷多解。,的计算:,四、单纯形法的实现单纯形表,12,0,0,0,单纯形表:,7,90,的计算:,40,

8、30, ,枢纽元素,x3,x4,x2,30,0.3,1,0,0,0.1,50,2.5,0,0,1,-0.5,240,7.8,0,1,0,-0.4,3.4,0,0,0,-1.2,或:,或:,30.8,20,100,x3,x1,x2,24,0,1,0,-0.12,0.16,20,1,0,0,0.4,-0.2,84,0,0,1,-3.12,1.16,0,0,0,-1.36,-0.52,X*=(20,24,84,0,0)T Z*=428,注：单纯形表中的信息 每一列的含义： B-1(bA)=(B-1b, B-1 P1,， B-1 Pn) 每个表中的B和B-1的查找： B从初表中找； B-1从当前表中找

9、，对应于初表中的I的位置。,以第2个表为例：,终表分析最优基B* 和(B*)-1的查找,换入基变量中，得到基可行解,定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况） 证明：某个非基变量,为最优解。故线性规划问题有无穷多最优解。,为一基可行解，有一个变量Xm+k对应,因,为可行解。,定理：若存在检验数大于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况） 证明：,构造一个新的解 ，分量为,定理：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。,定理：若检验数全小于等于零，且某一个非基变量的检验

10、数为0，则线性规划问题有无穷多最优解。,定理：若某一个非基变量的检验数大于0，其系数列向量Pm+k0,则原问题无最优解。（无界解的情况）,线性规划为求最大化的标准型：,线性规划为求最小化的标准型时，相应的结果？,定理（求最小化的最优解判别准则） （1）若= C -CB B-1A 0 ，则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。 （2）若检验数全大于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况） （3）若存在检验数小于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况） 确定换入变量时，找小于0中

11、的最小者。,课堂练习,用单纯形法求解,X*=(6,0,8,0)T Z*= -6,单纯形法的进一步讨论：人工变量法（大M法）,当原问题求最大化时，假定人工变量在目标函数中的系数为（- M）（M为任意大正数），目标函数求最大化，必须把人工变量从基变量换出，否则，不可能实现最大化。,当原问题求最小化时，假定人工变量在目标函数中的系数为M（M为任意大正数），目标函数求最小化，必须把人工变量从基变量换出，否则，不可能实现最小化。,增加人工变量 X人=（xn+1，xn+m）T， X人在目标函数中的系数为 -M（M为充分大正数）。,于是原问题化为() ：,1 问题:,2 方法:,单纯形法求解() ,若,最优

12、基变量中不含X人，则所得解的前n个分量即为X*,否则， ()无解。,3 结论:,例：用单纯形法求解,解：增加人工变量x5、x6，则模型化为：,Max Z = 5x1+3x2+2x3+4x4-Mx5-Mx6,5x1+ x2+ x3+8x4+x5 =10 2x1+4x2+3x3+2x4 +x6=10 x1,x6 0,s.t.,x5,x6,-M,-M,10,10,5/4,5,x4,x6,4,-M,10,2,x4,x2,4,3,5/3,10,x1,x2,5,3,X*=(5/3, 5/3, 0, 0)T, Z*=40/3,单纯形法总结,1、Min型单纯形表与Max型的区别仅在于： 令 k=minj 0的

13、xk进基，当 0时最优。,2、解的几种情况及其在单纯形表上的体现（讨论Max型）,唯一 最优解,j 0, 非基0,无穷多 最优解,j 0 有非基k=0,无界解,有k 0 但B-1Pk 0,无可行解,用大M法求解，最优基中含有X人,退化解,有两个或两个以上的min,线性规划的对偶问题 （Dual Programming，简称DP）,一、对偶问题的提出和模型,1、问题的提出,产品组合问题,今有另公司要购买三种资源，至少出价多少，才能使原公司出让资源？,设三种资源价格分别为y1, y2, y3,Min W=4y1+12y2+18y3,s.t.,y1+3y33,2y2+2y35,y1, y2, y3

14、0,收购总价,收购总价,出让生产某产品的资源 消耗的价值不低于该产品 的利润价值,Min W=4y1+12y2+18y3,s.t.,y1+3y33,2y2+2y35,y1, y2, y3 0,2、模型,原问题（P）：,对偶问题（D）：,Min W = bTY,ATY CT Y 0,s.t.,原问题（P）：,对偶问题（D）：,Min W = bTY,ATY CT Y 0,s.t.,3、如何求LP模型的对偶问题,（1）若LP为Max型，则尽量化成(P)形式。(等式、自由变量不用转换),（2）若LP为Min型，则尽量化成(D)形式。(等式、自由变量不用转换),例：写出下面LP的对偶,解：令,1、对称

15、性,（P）与（D）互为对偶,二、对偶性质与定理,2、弱对偶性,设X、Y 分别为（P）、（D）的任一可行解，则,证：,X、Y 为（P）、（D）的可行解,5、对偶定理,若（P）有最优解，则（D）也有最优解，且二者最优值相等.,3、解的最优性,设 、 分别为（P）与（D）的可行解，且,则,4、无界性,若（P）为无界解，则（D）无可行解,若（D）为无界解，则（P）无可行解,6、松紧定理（互补松弛性）,设 分别为（P）与（D）的可行解,例1.4讲解，掌握对偶问题的基本性质。,其对偶问题的最优解为,试找出原问题的最优解？,线性规划问题最优解为 用对偶问题求原问题的最优解。,解：标准型为：,对偶问题为：,标准型为：,代入原问题标准型有：,三、对偶问题最优解的经济解释影子价格,Y*=(y1* , y2* ,， ym*