线性规划及单纯形法.ppt

第一章线性规划与单纯形方法复习：线性规划问题的提出线性规划模型的特点线性规划模型的一般形式与标准形式如何将一般形式化为标准形式例1.3将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3无非负限制MaxS=x1-2x2+3x3-3x3s.t.x1+x2+x3-x3+x4=7x1-x2+x3-x3-x5=2-3x1+x2+2x3-2x3=5x1,x2,x3，x3,x4，x501-2线性规划的图解法例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE线性规划问题的有关概念（1）可行解：满足约束条件与非负限制的变量的值，称为可行解。（2）可行域：全部可行解的集合称为可行域。（3）最优解：使目标函数取得最优值的可行解，称为最优解。线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2例1.4例1.5maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20x2504030201010203040x14x1+3x2120x2504030201010203040x12x1+x250x2504030201010203040x12x1+x2504x1+3x2120可行域同时满足：2x1+x2504x1+3x2120x10x20的区域——可行域x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形可行域内的每一点都是可行解。x2504030201010203040x1可行域目标函数等值线x2504030201010203040x1可行域当该直线移到Q2点时，目标函数值达到最大：MaxS=5015+3020=1350此时最优解=（15，20）Q2（15，20）图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线；平移目标函数的等值线，找出最优点，算出最优值。练习：目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x209—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+2x28(0,4)(8,0)目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x204x1164x212图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216可行域图解法9—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1+2x284x1164x216可行域BCDEA图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEA2x1+3x2=6图解法9—8—7—6—5—4—3—2—1—0x2目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20|||||||||123456789x1x1+2x284x1164x216BCDEAx1+2x2=84x1=16最优解(4,2)图解法例某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q线性规划问题求解的几种可能结果(a)唯一最优解x26—5—4—3—2—1—0|||||||||123456789x1目标函数MaxZ=2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1、x2≥0(b)无穷多最优解6—5—4—3—2—1—0x2|||||||||123456789x1线性规划问题求解的几种可能结果目标函数MaxZ=2X1+3X2约束条件2X1+3X2≤84X1≤164X2≤12X1、X2≥0(c)无界解MaxZ=x1+x2-2x1+x24x1-x22x1、x20x2x1线性规划问题求解的几种可能结果该可行域无界，目标函数值可增加到无穷大(d)无可行解MaxZ=2x1+3x2x1+2x284x1164x212-2x1+x24x1、x20可行域为空集线性规划问题求解的几种可能结果该问题可行域为空集，即无可行解，也不存在最优解。重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。线段BC上的所有点都代表了最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。1-3线性规划问题解的概念对于线性规划标准型0maxXbAXCXZ也即：MaxZ=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2………………….am1x1+am2x2+….+amnxn=bmx1,x2….xn0其中：bi0(i=1,2,….m)可行解:满足AX=b,X=0的解X称为线性规划问题的可行解。最优解：使Z=CX达到最大值的可行解称为最优解。基：设r(A)=m,并且B是A的m阶非奇异的子矩阵（|B|0),则称矩阵B为线性规划问题的一个基。基向量：矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。基变量和非基变量：与基向量Pj相对应的变量xj就称为基变量，其余的就称为非基变量。),...,(,...,..............,...,11111mmmmmPPaaaaB不妨设：基础解：对于某一特定的基B，非基变量取0值的解，称为基础解。令非基变量等于零，则可由约束方程组AX＝b求得一个解，这样的解称为基础解。基础可行解：基础解不一定都是可行的。满足非负限制的基础解，称为基础可行解。可行基：与基础可行解对应的基，称为可行基。为了理解基、基变量、基础解和基础可行解的概念，用下列例子说明例1.7：maxS=2x1+3x2s.t.-2x1+3x263x1-2x26x1+x24x1,x20化为标准型：maxS=2X1+3X2+0X3+0X4+0X5s.t.-2X1+3X2+X3=63X1-2X2+X4=6X1+X2+X5=4X1,X2,X3,X4,X50写出约束方程组的系数矩阵：100210102300132A100010001),,(543ppp矩阵A的秩为3，而是一个3×3的满秩矩阵，故是上述线性规划问题的一个基。因而与P3,P4,P5,对应的变量X3，X4，X5是基变量，X1，X2是非基变量。),,(543ppp在约束方程组中，如果令X1=X2=0，即可解得X3=6，X4=6，X5=4，由此TX)4,6,6,0,0(是线性规划问题的一个基础解。因为该基础解中所有变量取值为非负，所以它又是基础可行解。与这个基础可行解对应的基（P3，P4，P5）是一个可行基。解的集合：非可行解可行解解的集合：基础解解的集合：可行解基础解基础可行解解的集合：可行解基础解最优解基础可行解练习：找出下列线性规划问题的基础解、基础可行解和可行基Maxz=1500x1+2500x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0注意，线性规划的基础解、基础可行解和可行基只与线性规划问题标准形式的约束条件有关。32100A=（P1,P2,P3,P4,P5）=2101003001A矩阵包含以下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，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=（p1，p2，p5），令非基变量x3=0，x4=0，即在等式约束中令x3=0，x4=0，解线性方程组：3x1+2x2+0x5=652x1+x2+0x5=400x1+3x2+x5=75得到x1=15，x2=10，x5=45，对应的基础可行解：x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。类似可得到x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T