2线性规划(20130922)VIP

线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解(另一个顶点)，以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。,一、消去法例1-11：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同(如下表)。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：数学模型maxS=6x1+4x2s.t.2x1+3x21004x1+2x2120 x1,x20,解：引进松弛变量x3,x40数学模型标准形式：maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120 x1,x2,x3,x40,约束条件的增广矩阵为：2310100（Ab)=4201120显然r(A)=r(Ab)=20,1im)=br0/brs(1rm),brs为主元,Xr为出基变量。,对单纯形表T(B)进行初等行变换(主元运算)得到新的单纯形表。经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。,表格单纯形法:例1-12数学模型标准型:maxS=10 x1+3x2+4x3-x4+x5s.t.3x1+6x2+2x3+x4=199x1+3x2+x3+x5=9x1,x2,x3,x4,x50,初始可行基B1=(P4,P5)=I基变量为x4,x5,非基变量x1,x2,x3初始基础可行解:X(0)=(0,0,0,19,9)t,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,10-(-1)3-19=4,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,3-(-1)6-13=6,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,4-(-1)2-11=5,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,(-1)-(-1)1-10=0,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,1-(-1)0-11=0,计算检验数:基变量检验数=0非基变量检验数j=Cj-CBtPj目标函数值:S=CBt*b=-10,(-1)19+19=-10,基变量选择检验数最大的非基变量X2作为进基变量,利用最小比值原则,计算各基变量的比值,利用最小比值原则:计算各基变量的比值,选择X5作为出基变量,进基变量X2与出基变量X5,交叉位置为主元(3).,第二行除以3,第一行加上第二行的(-6)倍,作主元运算,即用初等行变换把主元位置变成为1,该列元素变成0.得到新的基础可行解:X(1)=(0,3,0,1,0)tS=8,判断X(1)=(0,3,0,1,0)tS=8是否是最优解.再计算检验数.,X3的检验数大于零.X3进基变量,X3的检验数大于零.X3进基变量,计算相应的比值.确定X2出基变量,主元为(1/3),第二行乘以3,作主元运算,得到新的基础可行解:X(2)=(0,0,9,1,0)tS=35,判断是否最优解:X(2)=(0,0,9,1,0)tS=35计算检验数,所有检验数全小于零,达到最优解,X*=(0,0,9,1,0)tS=35,最优值为35.,例1-13求解线性规划问题：minS=x1-3x2+2x3+4x4s.t.2x1+4x3+x4=6-x1+x2+3x3=5x1,x2,x3,x40解：化问题为标准型maxS=-x1+3x2-2x3-4x4s.t.2x1+4x3+x4=6-x1+x2+3x3=5x1,x2,x3,x40,第一行除以2，第二行加第一行,因为检验数全小于等于零，得最优解：X=(3,8,0,0),S=21,S=-21,例1-14求解线性规划问题：minS=x1-x2s.t.-x1+x222x1-x22x1,x20解：化标准型：maxS=-x1+x2s.t.-x1+x2+x3=22x1-x2+x4=2x1,x2,x3,x40,B1=（P3，P4）=10=I01,因为检验数全小于等于零，得最优解：X=(0,2,0,4),S=2,S=-2,注意：虽然所有检验数全小于等于零，但非基变量X1对应的检验数=0，且b21=10,x1进基，其最优值不变。,第一行加上第二行,因为检验数全小于等于零，得另一个最优解：X=(4,6,0,0),S=2,S=-2,根据解的性质：最优解X=(0,2)t，X=(4,6)t连线上的点仍是最优解：X=(0,2)t+(1-)(4,6)t(01)本题有无穷多组最优解。,例1-15求解线性规划问题：maxS=2x1+x2s.t.x1-x2-52x1-5x210 x1,x20解：化标准型：maxS=2x1+x2s.t.-x1+x2+x3=52x1-5x2+x4=10 x1,x2,x3,x40,B1=（P3，P4）=10=I01,第二行除以2,第一行加第二行,可行解X=(5,0,10,0)S=10,b02=60,但非基变量X2所对应的系数向量:B2-1P2=(-3/2,-5/2)t0所以原问题无最优解.,单纯形法的几何意义：例1.16生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,数学模型maxS=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1,x20,数学模型的标准形:maxS=50 x1+30 x2s.t.4x1+3x2+x3=1202x1+x2+x4=50 x1,x2,x3,x40,基础可行解X(1)=(0,0,120,50)t,目标函数值S=0,X(1)=(0,0,120,50)t相当于O(0,0),X1进基变量,X4出基变量,主元（2）,第二行除以2,第一行加上第二行的负4倍,新的基础可行解X(2)=(25,0,20,0)t,目标函数值S=1250再计算检验数,X(2)=(25,0,20,0)t相当于Q1(25,0),X2进基变量,X3出基变量,主元(1),第二行加上第一行的负1/2倍,基础可行解X(3)=(15,20,0,0)t,也是最优解,其最优值S=1350,X(3)=(15,20,0,0)t相当于Q2(15,20),X(1)=(0,0,120,50)t相当于O(0,0),X(1)=(0,0,120,50)t相当于O(0,0),X(2)=(25,0,20,0)t相当于Q1(25,0),X(3)=(15,20,0,0)t相当于Q2(15,20),几何概念,代数概念,约束直线,满足一个