1[1].线性规划与单纯形方法

1第一章线性规划与单纯形法本章重点内容线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划的应用——建模2第一节线性规划问题及数学模型•1939年，（苏）康托洛维奇•1947年，G.B.Dantzig单纯形法•1979年，（苏）哈奇安算法•1984年，Karmarkar算法30,12416482..32max:21212121xxxxxxtsxxZOBJ设I、II两种产品的产量分别为x1,x2。建立该问题的数学模型为:例2现要做100套钢架，每套需2.9米、2.1米和1.5米的元钢各一根。已知原料长7.4米，问如何下料，使余料最少？例1(书P8)III设备128台时原材料A4016公斤原材料B0412公斤设工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应如何安排生产使该厂获利最多？一、实例4解：设I,II,III,IV,V分别代表五种不同的原料用量方案,x1,x2,x3,x4,x5分别代表采用各方案下料的元钢的根数。方案根数2.9米2.1米1.5米合计余料Ix11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.856目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（LP问题）的共同特征7Max(Min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2s.t.……am1x1+am2x2+…+amnxn≤(=,≥)bmxj≥0,j=1,2,…，nn－变量个数；m－约束行数；cj－价值系数；bi－右端项；aij－技术系数线性规划模型的一般形式为：81.线性不等式的几何意义—半平面1)作出LP问题的可行域2)作出目标函数的等值线3)移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的图解法90,12416482..32max:21212121xxxxxxtsxxZOBJ4x1=164x2=12x1+2x2=8x1x248430例3（书P8）：Q(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于点Q(4,2)，表明最优生产计划为：生产I产品4件，生产II产品2件。10例40,78102..46max212212121xxxxxxxtsxxZ1187654322x1876543O109x2ABCEDFGH123Z=363662:21Zxx最优解113.图解法的作用•能解决少量问题LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）规律1：•揭示了线性规划问题的若干规律12规律2：•线性规划问题的可行域为一凸集•线性规划问题凸集的顶点个数是有限的•最优解可在凸集的某顶点处达到的一个顶点。为，则，，）（使得，，若不存在两点为凸集，）顶点：设（）（）（）（）（）（）（）（SXXXXSXXSXS0210210]10[12基本概念为一凸集。，则，，）（若，点维空间一点集，任取两为）凸集：设（）（）（）（）（KKXXKXXnK]10[11212113四、线性规划问题的标准型技术系数右端项价值系数约束行数变量个数:;:;:;:;:,2,1,0,2,1,0..max221122222121112121112211ijijijmnmnmmnnnnnnabcmnmibnjxbxaxaxabxaxaxabxaxaxatsxcxcxcZ1.标准型特点：目标最大化、约束为等式、决策变量非负、右端项非负。142.线性规划标准型的向量和矩阵表达式矩阵式:MaxZ=CTXs.t.AX=bX≥0n向量式:MaxZ=∑cjxjj=1ns.t.∑Pjxj=bj=1xj≥0,j=1,2,...,n其中：C=(c1,c2,...,cn)Tb=(b1,b2,...,bm)TX=(x1,x2,...,xn)Ta11a12...a1nA=a21a22...a2n......am1am2...amn=(P1,P2,...,Pn)153.所有LP问题均可化为标准型)0.(,,,)0,0(;;0)3(3jnjjjjjjjjjjjjjjxabxxabxaxxbxaxxxxxxxxx令若无限制，令若，令若CXZMaxCXMinZZZ，令)1(为剩余变量为松弛变量等式约束条件将不等式约束条件化为0,0,)2(2211ninjijijijninjijijijxbxxabxaxbxxabxa0,0,0)4(ijijijijibxabxab则若16例5化标准型0,12416482..3221212121xxxxxxtsxxMaxZ)5,,1(01241648200032524132154321jxxxxxxxxxxxxxMaxZj可化为17例6化标准型型即可得到该问题的标准改为求，把求令以满足非负约束条件；号两端同乘以在第三个约束条件号的左端减去剩余变量在第二个约束不等式号的左端加入松弛变量在第一个约束不等式；，令其中令;,1;;0;0,0,7622254543ZMaxMinZZZxxxxxxxxxx无约束例：321321321321321,0,053327..32xxxxxxxxxxxxtsxxxMinZMaxZ’=x1+2x’2+3x4-3x5+0x6+0x7s.t.x1-x’2+x4-x5+x6=7x1+x’2+x4-x5-x7=2-3x1-x’2+3x4-3x5=5x’2≥0,xj≥0,j=1,4,5,6,7180;4,2,1,0417431432..42;8424040,2343321321321321434333xjxxxxxxxxxtsxxxZMaxxxxMaxZxxxxxxj即所以，满足；且则有解：令课堂练习62,0,25432032..42321321321321xxxxxxxxxtsxxxMaxZ19五、标准型LP问题解的概念问题的一个基。为），则称非奇异矩阵（的为问题的系数矩阵，为设基问题的最优解；）的可行解，为满足（最优解）的解；）、（满足（可行解其中，LPB0BAB,m)A(rLPALP132)m)A(r,nm(,aaaaaaaaaA,xxxX,cccC)3(0X)2(bAX.t.s)1(XCMaxZmmnmmn2m1mn22221n11211n21n21T20问题的基。均为例：LPBB1001B,1502B,0512B,1301B,0311B,5321B,10530121A4,3,2,1j,0x10xx5x34xx2x.t.sxxMaxZ61654321j4213212121令B==(P1,P2,…,Pm)且|B|0，则称Pj(j=1,2,…,m)为基向量。与基向量Pj对应的变量xj称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xm+n)T。mmm12m1m1211aaaaaa为非基变量。、为一组基变量，、则对应的，如在上例中，41324xxxx0512B基变量：22•基解令非基变量XN=0，求得的一组基变量XB的值称为基解。•基可行解既是基本解，又是可行解。结论：基可行解的个数≤基解的个数≤Cnm23线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解24例1（书P8）：MaxZ=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1,x2≥0六、可行解、基解和基可行解举例非基变量基变量图中的点x4,x5x1=4x2=3x3=-2A基解x3,x5x1=2x2=3x4=8B基可行解x3,x4x1=4x2=2x5=4C基可行解x2,x4x1=4x3=4x5=12D基可行解x2,x3x1=8x4=-16x5=12E基解x1,x5x2=3x3=2x4=16F基可行解x1,x3x2=4x4=16x5=-4G基解x1,x2x3=8x4=16x5=12H基可行解x1+2x2=8x14x1=164x2=12x248430Z=2x1+3x2ABCDEFGH)5,,1(01241648200032524132154321jxxxxxxxxxxxxxMaxZj标准型25例21187654322x1876543O109x2ABCEDFGH123f(x)=36K非基变量基变量图中的点解x1,x2x3=10x4=8x5=7O基础可行解x1,x3x2=10x4=-2x5=-3F基础解x1,x4x2=8x3=2x5=-1E基础解x1,x5x2=7x3=3x4=1A基础可行解x2,x3x1=5x4=3x5=7D基础可行解x2,x4x1=8x3=-6x5=7H基础解x3,x4x1=2x2=6x5=1C基础可行解最优解x3,x5x1=1.5x2=7x4=-0.5G基础解x4,x5x1=1x2=7x3=1B基础可行解x1=2,x2=2,x3=4,x4=4,x5=3K可行解26第二节LP问题的基本理论一、基本概念为一凸集。则称有，对于、维空间一点集为凸集：设SSXXXSXXnS,)1(],10[,,.1)2()1()2()1(的一顶点。为则称成立使，对于若不存在为一凸集凸集顶点：设）（）（SXXXXSXXSXS)0()2()1(0)2()1(0,)1(),10(,,,.2的一个凸组合。为则称使得若存在个点，维空间中的为凸组合：设）（）（）（）（）（）（）（)(211221121)(21,,,)1,10(,,,,,,,,.3kkiiikkkkXXXXXXXXknXXX27显然凸集的交集为凸集，但凸集注1：凸集的交集为凸集，但凸集的并未必是空集。注2：一个有界凸集内的任意一点均可以表示为其若干顶点的凸组合。(a)(b)(c)(d)(e)28定理1LP问题的可行域为一凸集。121122(1)(2)(1)(2)|0,,00[01],(1)[(1)](1)0,,SXAXbXXXSAXbXAXbXXXXAXAXXbbbXXSS（）（）（）（）（）（）证明：记，任取则，；，对于，作则显然则则为一凸集。二、基本定理29引理线性规划问题的可行解X=(x1,x2,…,xn)T是基可行解的充要条件为X的正分量所对应的系数列向量