管理运筹学课件

第一章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例§1线性规划及其数学模型1.1问题的提出1.2图解法1.3线性规划问题的标准形式1.4线性规划问题的解的概念§1.1问题的提出在生产管理和经营活动中，经常会碰到一类问题，即如何合理的利用有限的人力、物力、财力等资源以便得到最好的经营效果。例1：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。该工厂每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排计划使该工厂获利最多？产品Ⅰ产品Ⅱ设备128台时原材料A4016kg原材料B0412kg利润（元/件）23可用资源解：设变量x1为计划期内产品Ⅰ的产量；变量x2为计划期内产品Ⅱ的产量。x1+2x2≤8；设备的有效台时数限制4x1≤16；原材料A的限量4x2≤12；原材料B的限量另外，产品数不可能为负，即x1,x2≥0。目标：获得最大利润，利润可以用函数表示为：z=2x1+3x2目标函数maxz=2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1,x2≥0把目标函数和约束条件放在一起，可以建立如下的数学模型：其中：“max”含义为“最大化”；因此，模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。这是一个典型的利润最大化的生产计划问题。线性规划问题的共同特征（模型的三要素）⑴每一个问题都用一组决策变量(x1，x2，…，xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。⑵存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。⑶都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划数学模型的一般形式：max(min)z=c1x1+c2x2+…+cnxnst.a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2………………………….am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥0nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21价值系数动活资源决策变量它们的对应关系可用表格表示：对于模型中只含有两个变量的线性规划问题，可以通过在平面上作图的方法来求解。§1.2图解法图解法的目的•判别线性规划问题的求解结局；•存在最优解的情况下，求出问题的最优解。有关概念可行解：满足约束条件的解。可行域：全部可行解的集合。最优解：可行域中使目标函数值达到最优的可行解。问题无解：不存在可行解的线性规划问题。图解法的步骤：1.在平面上建立直角坐标系；2.图示约束条件，找出可行域；3.图示目标函数和寻找最优解。解法:1.建立平面直角坐标系；2.找出表示每个约束的半平面，所有半平面的交集是可行域（全体可行解的集合）；3.画出目标函数的等值线;4.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。maxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20x1x2044x1=16x1+2x2=84x2=123Q1Q3Q4•Q22x1+3x2=0•Q2(4,2)线性规划问题求解的几种可能结果1.唯一最优解；2.无穷多最优解；3.无界解；4.无可行解。(1)存在唯一最优解maxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20x1x2044x1=16x1+2x2=84x2=123Q1Q3Q4•Q22x1+3x2=0•Q2(4,2)（2）有无穷多最优解若目标函数变为maxz=2x1+4x2则存在无穷多最优解maxz=2x1+4x2s.t.x1+2x284x1164x212x1，x20≥≤≤≤x1x2044x1=164x2=123Q1Q3Q4•Q22x1+4x2=0•Q2(4,2)x1+2x2=8（3）无界解（4）无可行解（可行域为空集）注意：•(3)缺乏必要的约束条件;(4)有矛盾的约束条件•可行域有界时必有最优解，无界时不一定无最优解z由图解法得到的启示1.求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界解，无可行解。2.若线性规划问题的可行域存在，则可行域是一个有界或无界的凸多边形。3.若线性规划问题的最优解存在，则最优解一定在可行域的某个顶点上得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即无穷多最优解。§1.3线性规划问题的标准型形式0aczmax212211222221211121211122111nnnmnmmnnnnnnx,,x,xbxaxaxabxaxaxabxaxaxxcxcx:M约束条件：目标函数：用求和符号表示为:n,,,j,xm,,,i,bxaxczmax:Mjnjijijnjjj'21021111约束条件：目标函数：用向量和矩阵符号表示为：n,,j;bbbb;aaaP;xxxX;c,,c,cCn,,,j,xbxPCXzmax:Mmmjjjjnnjnjjj''212102121212111约束条件：目标函数：用矩阵符号表示为：Tnnmnmn''x,,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000决策变量向量：；资源向量：零向量：系数矩阵：约束条件：目标函数：将一般形式化为标准型式①．将目标函数最小化变为求目标函数最大化minz=CXmaxz’=-CX，其中z’=-z；②．将不等式约束变为等式约束njnjimiimjijijijxbxxabxa110(松弛变量)011imnjnjiimjijijijxbxxabxa（剩余变量）③．将负约束、无符号约束变为非负约束xj0xj=-xj’，xj’0xj为无符号约束变量xj=xj’-xj’’,xj’0,xj’’0x1+2x284x1164x212x1，x20maxz=2x1+3x2+0x3+0x4+0x5标准型：例3．将例1的数学模型化为标准型。maxz=2x1+3x2所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3，c4，c5=0。x1+2x2+x3=84x1+x4=164x2+x5=12x1，x2，x3，x4，x50x1+x2+x37x1–x2+x32–3x1+x2+2x3=5x1，x20，x3为无符号约束例4．将下述线性规划问题化为标准型minz=–x1+2x2–3x3解：令z’=-z，用x4-x5替换x3x1+x2+(x4-x5)+x6=7x1–x2+(x4-x5)-x7=2–3x1+x2+2(x4-x5)=5x1，x2，x4，x5，x6，x70maxz’=x1–2x2+3(x4-x5)+0x6+0x7用标准型求最优解后，再回到原变量。§1.4线性规划问题的解的概念•可行解、可行域•最优解、最优值•基、基向量、基变量、非基变量•基解、基可行解•可行基、最优基1.可行解满足约束条件(1-5)，(1-6)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解，线性规划全部可行解的集合称为可行域。其中使目标函数(1-4)达到最大值的可行解称为最优解，最优解对应的目标函数(1-4)的值称为最优值。)61(,,2,1,0)51(,2,1,)41(max11njxmibxaxczjnjijijnjjj设A为约束方程组的维系数矩阵，其秩为m。B是矩阵A中阶非奇异子矩阵（），则称B是线性规划问题的一个基。2.基，基向量，基变量称Pj(j=1,2,…,m)为基向量。与基向量Pj对应的变量xj(j=1,2,…,m)为基变量。线性规划中除基变量以外的变量称为非基变量。设3.基解，基可行解在约束方程组（1-5）中，令所有非基变量xm+1=xm+2=…=xn=0，又因为有，根据克莱姆法则，由m个约束方程可解出m个基变量的唯一解，将这个解加上非基变量取０的值有称Ｘ为线性规划问题的基解。满足变量非负约束条件(1-6)的基解称为基可行解。显然在基解中变量取非零值的个数不大于方程数m，故基解的总数不超过个。•4可行基、最优基对应于基可行解的基称为可行基。对应于最优解的基称为最优基。注意：线性规划的基解、基可行解和可行基只与线性规划问题标准形式的约束条件有关。图1-6它们之间的关系maxz=2x1+3x2st.x1+2x2≤84x1≤164x2≤12x1,x2≥0例：找出例1所建线性规划问题的全部基解，指出其中的基可行解。解：例1所建的线性规划模型为：化为标准形式为：maxz=2x1+3x2+0x3+0x4+0x5st.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5≥0约束条件的系数矩阵为：A矩阵包含以下10个3×3的子矩阵：B1=[p1，p2，p3]B2=[p1，p2，p4]B3=[p1，p2，p5]B4=[p1，p3，p4]B5=[p1，p3，p5]B6=[p1，p4，p5]B7=[p2，p3，p4]B8=[p2，p3，p5]B9=[p2，p4，p5]B10=[p3，p4，p5]分析：其中B4=0，B８=0，因而B4，B８不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有８个基。下面分别求出各个基所对应的基解。于是对应的基B1不是可行基。X=(x1,x2,x3,x4,x5)T=(4，3，-2，0，0)T对应的基解是：得到x1=4，x2=3，x3=-2解线性方程组：x1+2x2+x3=84x1+0x2+0x3=160x1+4x2+0x3=12首先令非基变量x4=x5=0。以基B1=[p1，p2，p3]为例：类似可得到其它基对应的基解：B1:X=(4,3,-2,0,0)TB2:X=(2,3,0,8,0)TB3:X=(4,2,0,0,4)TB5:X=(4,0,4,0,12)TB6:X=(8,0,0,-16,12)TB7:X=(0,3,2,16,0)TB9:X=(0,4,0,16,-20)TB10:X=(0,0,8,16,12)T其中绿色所示为基可行解，对应的基为可行基。o113x1x22234Q4567845Q3Q2Q1思考1：线性规划问题的基可行解与可行域的顶点之间的关系？思考2：求线性规划问题的最优解的方法？基(最多个）→基可行解(可行域顶点)→最优解?凸集设nEK，若任意两点KX,KX21连线上的所有点，即)(KX)(XX10121aaa则称K为凸集。上图中(a)、(b)是凸集，(c)、(d)不是凸集，任何两个凸集的交集是凸集，如图(e)。从直观上说，凸集没有凹入部分，其内部没有空洞。(a)(b)(c)(d)(e)§2线性规划问题的几何意义2.1基本概念凸组合设，若存在，01，且，使则称X为的凸组合。两点连线上的任何一点都是这两点的凸组合k,,aa1kkXXXaa11)(X)(XX10121aaaianKEX,,X1KX,,X111KiiaX1X2X21顶点（极点）设K是凸集，XK，若X不能用K的其它两点的凸组合表示，即不存在X1K，X2K(X1X2)，能使)(X)(XX10121aaa，则称X为K的一个顶点。(a)(b