第一章线性规划问题及单纯形解法课件.ppt

1、第一章线性规划问题及单纯形解法优选第一章线性规划问题及单纯形解法3三、求解方法采用成熟的单纯形法目三、求解方法采用成熟的单纯形法目前，用单纯形法解线性规划的计算机程前，用单纯形法解线性规划的计算机程序已大量涌现，在计算机上求解此类问序已大量涌现，在计算机上求解此类问题已十分容易题已十分容易二、模型较为简单，容易建立，容易二、模型较为简单，容易建立，容易学习和掌握学习和掌握4 线性规划的一种最大量、最普遍的应用线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资就是研究有限资源的合理利用问题，或说资源的最优配置问题资源分配问题有多种多源的最优配置问题资源分配问题有多种多样的具

2、体形式例：样的具体形式例：线性规划解决的问题 1 1、生产的合理安排问题、生产的合理安排问题 2 2、投资决策问题、投资决策问题 3 3、运输问题、运输问题51.1 1.1 什么是线性规划什么是线性规划（Linear Programming)Linear Programming)的简单例子和模型的简单例子和模型 （1 1）数学模型数学模型 一个实际问题的数学模型，是依据一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那客观规律，对该问题中我们所关心的那些量进行科学的分析后得出的反映这些些量进行科学的分析后得出的反映这些量之间本质联系的数学关系式。量之间本质联系的数学关系式。6 单

3、单 位位 单位单位 时耗时耗资源资源 一一 二二现有工现有工时时搅拌机搅拌机/小时小时3515成形机成形机/小时小时215烘箱烘箱/小时小时2211利润（百元利润（百元/吨）吨）54例1.21 饼干生产问题7 问题问题 ：如何制订生产计划，：如何制订生产计划，才能使资源利用充分并使厂方获才能使资源利用充分并使厂方获最大利润。最大利润。8解：设由解：设由x x1 1，x x2 2 分别表示分别表示1 1，2 2型饼干每型饼干每天的生产量。天的生产量。max z=5x max z=5x1 1+4x+4x2 2 s.t.3xs.t.3x1 1+5x+5x2 2 15,15,2x 2x1 1+x+x2

4、 25,5,2x 2x1 1+2x+2x2 211,11,x x1 1,x,x2 20.0.maxmaxmaximize,s.t.maximize,s.t.subject tosubject to9单台运费B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516问题：如何调运才能即满足用户需要，问题：如何调运才能即满足用户需要，又使总运费最少？又使总运费最少？例1.22 运输问题1011x1,x20.设X属于S,若x=0,则一定为极点；基可行解：若基解中所有的XB 都0 时，称为基可行解.4 人工变量的引入及其解法2-2 假设上例中的目标函数变为1试列

5、出下面线性规划问题的初始单纯形表(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。第i 个约束的bi 为负值，则在bi所在之方程的两边乘以-1。4 人工变量的引入及其解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。2x1+x25,例的单纯形表及其迭代过程x2 +s3=250 x1,x2,x3,x3,x4,x5,x6 0.迭代的实质是线性变换，即要将主元 ai*j*变为1，主列上其它元素变为0，变换步骤如下：1、标准型的几种不同的表示方式1）和式技术系数右端项价值系数线性规划问题的规模约束行数变量个数为决策变量为约束条件为目标函数或:;:;:

6、;:;:,.z0,),(),(),(.)(max)min(2121221122222121112121112211ijjjnnmnmnmmnnnnnnabcmnmnxxxtsxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxz线性规划数学模型的一般表示方式120,.)(max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxz线性规划数学模型的标准型13njxmibxatsxcxzjinjjijnjjj,2,1 ,0,2,1 ,.)(max111 1、标准型的几种不同的表示方式、标准型

7、的几种不同的表示方式1）和式140000 ),(;),(.)(max210212121010bPXC0XbPCXmmjjjjTnnnjjjbbbaaaxxxcccxtsxz2）向量式）向量式15 ),(),(),(.)(max212121212222111211TmTnnmnmmnnbbbxxxcccaaaaaaaaatsxzbXCA0XbAXCX3）矩阵）矩阵16 1 1）A A中没有多余方程；中没有多余方程；2 2）b b 0 0 2 2、对标准型问题作出的假设、对标准型问题作出的假设17极点就是不能成为E 中任何线段的内点的那种点x1,x2,x3,x3,x4,x5,x6 0.x1,x2,

8、x3,x3,x4,x5,x6 0.(3)变换非主行、主列元素 aij(包括 bi)z=3x1+5x22x1+2x211,1.x2 +s3=2503x1+5x2 15,x1 x2 x3 s1 s2 s32 0 3/2 0 0 0s.1、标准型有 n+m个变量，m 个约束行线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题资源分配问题有多种多样的具体形式例：max z=5x1+4x2 1.关于LP问题求解的一些基本概念和特点基解:令非基变量 XN=0，求得基变量XB的值称为基解.x1,x2,s1,s2,s300 2 3/2 -2 0 01、标准型的几种不同的表

9、示方式1）和式 0,|xbAxRxsn 最优解最优解 使使z达到最优的达到最优的可行解可行解就是就是最优解最优解（有解（有解（给定的Lp 问题有最优解）、否则无解）否则无解）w可行解可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X X 称为可行解，所有可行解组成的集合称之为称为可行解，所有可行解组成的集合称之为可行解集（可行域）可行解集（可行域）3、LP问题解的几个基本概念182.第第i 个约束的个约束的bi 为负值，则在为负值，则在bi所在之方程的两边乘以所在之方程的两边乘以-1。4、一般型变标准型的变换方法1.目标函数为目标函数为min型时，价值系数型时，价值系数一律反号。

10、即令一律反号。即令 z(x)=-z-z(x)=-CX193.3.第第i i 个约束为个约束为 型，在不等型，在不等式左边增加一个非负的变量式左边增加一个非负的变量x xn+in+i ，称为松弛变量（原有变量为构造称为松弛变量（原有变量为构造变量）；同时令变量）；同时令 c cn+in+i =0=04.4.第第i i 个约束为个约束为 型，在不等式型，在不等式左边减去一个非负的变量左边减去一个非负的变量x xn+in+i ，称称为剩余变量；同时令为剩余变量；同时令 c cn+in+i =0=0206.6.若若x xj j 无符号限制，令无符号限制，令 x xj j=x xj j -x xj j，

11、x xj j 0 0，x xj j 0 0，代入非标代入非标准型准型5.5.若若x xj j 0 0，令，令 x xj j=-=-x xj j ，代入非，代入非标准型，则有标准型，则有x xj j 0 021原非标准型：原非标准型：max z=5xmax z=5x1 1+4x+4x2 2 s.t.3xs.t.3x1 1+5x+5x2 2 15,15,2x 2x1 1+x+x2 25,5,2x 2x1 1+2x+2x2 211,11,x x1 1,x,x2 20.0.5、变换举例例1.22标准型：标准型：max z=5x1+4x2 s.t.3x1+5x2+x3=15,2x1+x2 +x4=5,2

12、x1+2x2 +x5=11,x1，x2，x3，x4，x50.230,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型例224标准型：标准型：max f(x)=-3x1+2x2-4x3+4x3+0 x4+0 x5+0 x6 s.t.2x1+3x2+4x3-4x3-x4=300,x1+5x2+6x3-6x3+x5=400,x1+x2+x3-x3+x6=200,x1,x2,x3,x3,x4,x5,x6 0.25X是极点的充分必要条件是：它是基可行解。极点就是不能成为E 中任何线段的内点的那种点1、生产的合理安排问题若有

13、 bi0，则单位阵也不能构成一个可行基若有 bi0，则单位阵也不能构成一个可行基3x1+5x2+x3=15,时耗基解:令非基变量 XN=0，求得基变量XB的值称为基解.的列向量的全部分量 0，则所给问题无A=(P1,P2 ,Pn,Pn+1,Pn+2,.三、关于最优解的获得方法问题请查看教材P29中单纯形表的组成形式。x2 +s3=250 x1=50 x2=250s.（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。max f(x)=-3x1+2x2-4x3+4x3+0 x4+0 x5+0 x6max z=5x1+4x2 1.线性规划的一种最大量、最普遍的

14、应用就是研究有限资源的合理利用问题，或说资源的最优配置问题资源分配问题有多种多样的具体形式例：x1+x2+s1 =300 x1，x2，x3，x4，x50.1.2 求解LP问题的基本定理 的图解法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。如26例例1.3 Maxz=50 x1+100 x2 s.t.x1+x2 300 2 x1+x2 400 x2 250 x1、x2 027采用图采用图 解解 法法(1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1.3的每个约束条件都代表

15、一个半平面。x2x1X20X2=0 x2x1X10X1=028（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=40030020030040029（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图12所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图1-230（4 4）目标函数）目标函数z=50 xz=50 x1 1+10

16、0 x+100 x2 2，当，当z z取某一固定值时得取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函到一条直线，直线上的每一点都具有相同的目标函数值，称之为数值，称之为“等值线等值线”。平行移动等值线，当移。平行移动等值线，当移动到动到B B点时，点时，z z在可行域内实现了最大化。在可行域内实现了最大化。A A，B B，C C，D D，E E是可行域的顶点，对有限个约束条件则其可行是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图1-3z=27500=50 x1+100 x2z=0=50 x1+10

17、0 x2z=10000=50 x1+100 x2CBADEx1+x2=30031得到最优解：x1=50，x2=250 最优目标值z=2750032若在上例模型中中引入松弛变量若在上例模型中中引入松弛变量s1 s2 s3s1 s2 s3模型化模型化为为 Max z=50 x1+100 x2+0s1+0s2+0s3 Max z=50 x1+100 x2+0s1+0s2+0s3 s.t.x1+x2+s1=300 s.t.x1+x2+s1=300 2x1+x2 +s2=400 2x1+x2 +s2=400 x2 +s3=250 x2 +s3=250 x1,x2,s1,s2,s30 x1,x2,s1,s

18、2,s30 可求解得其最优解为可求解得其最优解为 x1=50 x2=250 x1=50 x2=250 s1=0 s2=50 s3=0 s1=0 s2=50 s3=0说明生产说明生产5050单位单位产品和产品和250250单位单位产品将消耗完所产品将消耗完所有资源有资源1 1和和3 3，但资源，但资源2 2还剩余还剩余5050。33 max z=5x1+4x2 1.1 s.t.3x1+5x2 15,1.2 2x1+x25,1.3 2x1+2x211,1.4 x1,x20.1.5无需化标准形 例1.2-1 求解饼干生产问题34图中的OABC即为满足约束条件的可行解集S,需在S中找出最优解,若z 为

19、一常数 z0则z0=5x1+4x2为目标函数等值线（x1=10/7,x2=15/7,z*=110/7)。35例1.2-2 假设上例中的目标函数变为 z=3x1+5x2 此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）例1.2-3 可行解集为一无界集合 见P18图1.3 若是求目标函数最小值，则有最优解。若是求目标函数最大值，则无最优解。若可行解集为空集，则无解，P19图1.436求解求解LPLP问题的重要规律问题的重要规律一、解的存在性问题一、解的存在性问题二、解的结构问题二、解的结构问题三、关于最优解的获得方法问题三、关于最优解的获得方法问题（在可行解集的某些（在可行解集

20、的某些“顶点顶点”得到）得到）37关于LP问题求解的一些基本概念和特点1 1、两个基本概念、两个基本概念凸集凸集:实向量空间实向量空间E 中任意两点连线中任意两点连线上的一切点仍属于上的一切点仍属于E(见见P20)极点就是不能成为极点就是不能成为E 中任何线段的内中任何线段的内点的那种点点的那种点38 2、Lp问题的几个特点问题的几个特点(相关证明请看相关证明请看 1.7节节)：w 最优解只可能在凸集的极点上，而不可能最优解只可能在凸集的极点上，而不可能发生在凸集的内部发生在凸集的内部w 线性规划问题的可行解集线性规划问题的可行解集S是凸集是凸集w 设设X属于属于S,若若x=0,则一定为极点；

21、若则一定为极点；若x 0，则为极点的充要条件是：，则为极点的充要条件是：x的正分的正分量所对应的系数列向量线性无关。量所对应的系数列向量线性无关。w 只要存在可行解，就一定存在极点只要存在可行解，就一定存在极点w 极点的个数是有限的极点的个数是有限的392、“基基”的概念的概念在在标准型标准型中，技术系数矩阵有中，技术系数矩阵有 n+m列，即列，即 A=(P1,P2 ,Pn,Pn+1,Pn+2,.Pn+m)因因r(A)=m,所以所以A的极大无关组含有的极大无关组含有 m个个线性无关的向量。线性无关的向量。关于标准型解的若干基本概念1、标准型有、标准型有 n+m个变量，个变量，m 个约束行个约束

22、行40 基、基变量、非基变量基、基变量、非基变量技术系数矩阵技术系数矩阵A（标准线性规（标准线性规划模型）中划模型）中m个线性无关的列向量所对应的个线性无关的列向量所对应的m个变量，构个变量，构成该成该LP问题的一个基，这问题的一个基，这m个变量的系数列向量组成的个变量的系数列向量组成的矩阵称为基阵，记为矩阵称为基阵，记为B。基中的每个变量称为基变量。基中的每个变量称为基变量,记为记为XB。其余的变量即为非基变量。其余的变量即为非基变量,记为记为XN。如：如：Max z=50 x1+100 x2s.t.x1+x2+s1 =300 2x1+x2 +s2 =400 x2 +s3=250 x1,x2

23、,s1,s2,s30基解:令非基变量令非基变量 X XN N=0=0，求得基变量，求得基变量X XB B的值称为基解的值称为基解.基可行解：若基解中所有的若基解中所有的X XB B 都都0 0 时，称为时，称为基可行基可行解解.41n 若若基可行解基可行解的所有的所有基变量均取正值，基变量均取正值，则称为则称为非退化的基可行解，非退化的基可行解，如果某些如果某些基变量取零值，则为基变量取零值，则为退化的基可行解退化的基可行解。42.36)(max,6,2:0,78102.46)(max21543215242132121xfxxxxxxxxxxxxxxxtsxxxf最优解可行解、基解和基可行解举

24、例43可行解、基础解和基础可行解举例1187654322x1876543O109x2A BCEDFGH123f(x)=36K非基非基变量变量基变量基变量图中的点图中的点解解x1,x2x3=10 x4=8x5=7O 基础可行解基础可行解x1,x3x2=10 x4=-2x5=-3F 基础解基础解x1,x4x2=8x3=2x5=-1E 基础解基础解x1,x5x2=7x3=3x4=1 1A 基础可行解基础可行解x2,x3x1=5x4=3x5=7 7D 基础可行解基础可行解x2,x4x1=8x3=-6x5=7 7H 基础解基础解x3,x4x1=2x2=6x5=1 1C 基础可行解基础可行解最优解最优解x

25、3,x5x1=1.5x2=7 x4=-0.5 G 基础解基础解x4,x5x1=1x2=7x3=1 1B 基础可行解基础可行解x1=2,x2=2,x3=4,x4=4,x5=3 3 K 可行解可行解44 X X是极点的充分必要条件是：它是是极点的充分必要条件是：它是基可行解。由此，有关极点的结果可基可行解。由此，有关极点的结果可转到基可行解上：转到基可行解上：只要存在可行解，就一定存在基可只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若行解；基可行解的个数是有限的；若LPLP问题有最优解，则最优解一定可以在基问题有最优解，则最优解一定可以在基可行解中找到。可行解中找到。453、LP问

26、题解的几个基本概念若LP问题有最优解，则最优解一定可以在基可行解中找到。三、关于最优解的获得方法问题max z=5x1+4x2z=10000=50 x1+100 x2例的单纯形表及其迭代过程s.x1，x2，x3，x4，x50.同时令 cn+i=01 单纯形表的迭代过程4、一般型变标准型的变换方法2-2 假设上例中的目标函数变为迭代的实质是线性变换，即要将主元 ai*j*变为1，主列上其它元素变为0，变换步骤如下：关于LP问题求解的一些基本概念和特点可行解、基解和基可行解举例解：设由x1，x2 分别表示1，2型饼干每天的生产量。当约束条件为“”型，引入剩余变量和人工变量其余的变量即为非基变量,记

27、为XN。（在可行解集的某些“顶点”得到）在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。1.3 单纯型法的基本思路确定初始基可行解是否为最优确定改善方向求新的基可行解求最优解的目标函数值是否46(1)(1)单纯形表的组成及形式单纯形表的组成及形式w设设 B 是初始可行基向量，则目是初始可行基向量，则目标函数可写为两部分标函数可写为两部分(1)w约束条件也写为两部分，经整约束条件也写为两部分，经整理得理得 XB 的表达式的表达式(2)，注意，注意 XB中中含有非基变量作参数含有非

28、基变量作参数w把把 XB 代入目标函数，整理得到代入目标函数，整理得到(3)式式w若所有非基变量的检验数若所有非基变量的检验数i i 0,则达到最优则达到最优(4)3()()()(2)(1)(iN1BNNN1BN1BNN1BNNNN1BNNBBNNBBNNABCCXABCCbBCXAbBCXCXAbBXXAbBXbBXXAXCXC检验数xfxf47单纯形表48例1.1试列出下面线性规划问题的初始单纯形表0,12023310032.244540)(max321321321321xxxxxxxxxtsxxxxf491 找初找初 始基础可行基始基础可行基对于对于(max,)，松弛变量对应的列构成一个

29、单，松弛变量对应的列构成一个单位阵位阵若有若有 bi 0 中找最大者，选中者称为中找最大者，选中者称为入基变量入基变量 xj*n第第j*列称为主列列称为主列51nmjaaajijiji,2,1*n设第设第 i i*行使行使 最小，则第最小，则第 i i*行对行对应的基变量称为应的基变量称为出基变量出基变量，第，第 i i*行称行称为主行为主行5 5 迭代过程迭代过程n主行主行 i i*行与行与主列主列 j j*相交的元素相交的元素a ai i*j j*称称为主元为主元，迭代以主元为中心进行，迭代以主元为中心进行n迭代的实质是线性变换，即要将主元迭代的实质是线性变换，即要将主元 a ai i*j

30、 j*变为变为1 1，主列主列上其它元素变为上其它元素变为0 0，变，变换步骤如下：换步骤如下：(1)(1)变换主行变换主行52(2)变换主列变换主列除主元保留为除主元保留为1，其余都置，其余都置0(3)变换非主行、主列元素变换非主行、主列元素 aij(包括包括 bi)(4)变换变换CB，XB(5)计算目标函数、机会成本计算目标函数、机会成本 zj 和检验数和检验数 cj zj6、返回步骤返回步骤 253例1.1 单纯形表的迭代过程答：最优解为答：最优解为 x1=20,x2=20,x3=0,OBJ=170054基可行解的判别和改进定理定理1.6 若所有检验数若所有检验数 j 0，则为最优解，则

31、为最优解定理定理1.7 若存在某一个检验数若存在某一个检验数0，而它所对应而它所对应的列向量的全部分量的列向量的全部分量 0，则所给问题无，则所给问题无最优解最优解ija 除上述两种情况外，若每个正检验数所除上述两种情况外，若每个正检验数所对应的列向量中都有正分量，则为确定最对应的列向量中都有正分量，则为确定最优解需要进行基的变换（换基）优解需要进行基的变换（换基）55请查看教材P29中单纯形表的组成形式。56 当约束条件为当约束条件为“”型，引入型，引入剩余变量和人工变量剩余变量和人工变量1.4 1.4 人工变量的引入及其解法人工变量的引入及其解法57 由于所添加的剩余变量的技术由于所添加的

32、剩余变量的技术系数为系数为 1 1，不能作为初始可行基变，不能作为初始可行基变量，为此引入一个人为的变量（注量，为此引入一个人为的变量（注意，此时约束条件已为意，此时约束条件已为“=”型），型），以便取得初始基变量，故称为人工以便取得初始基变量，故称为人工变量变量.两种方法：大两种方法：大M M法法 两阶段法两阶段法58x1=50 x2=250 x1,x2,x3,x3,x4,x5,x6 0.此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题资源分配问题有多种多样的具体形式例：2x1+x2

33、+s2=400第i 个约束的bi 为负值，则在bi所在之方程的两边乘以-1。max z=5x1+4x2 1.关于LP问题求解的一些基本概念和特点此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）优选第一章线性规划问题及单纯形解法若xj 无符号限制，令 xj=xj-xj，xj 0，xj 0，代入非标准型2、Lp问题的几个特点(相关证明请看 1.max f(x)=-3x1+2x2-4x3+4x3+0 x4+0 x5+0 x62x1+x2 +s2 =4002、对标准型问题作出的假设若xj 0，令 xj=-xj，代入非标准型，则有xj 0多个基础可行解都是最优解，这些解在同一个平面上

34、，且该平面与目标函数等值面平行4、一般型变标准型的变换方法问题：如何调运才能即满足用户需要，又使总运费最少？2 0 1 0 1 0s1=0 s2=50 s3=0n多个基础可行解都是最优解，这多个基础可行解都是最优解，这些解在同一个平面上，且该平面些解在同一个平面上，且该平面与目标函数等值面平行与目标函数等值面平行n最优单纯形表中最优单纯形表中有非基变量的检有非基变量的检验数为验数为0 01.5 1.5 单纯形法应用的特例单纯形法应用的特例 关于多重解问题关于多重解问题590,12023310032.254540)(max 1.5.1 321321321321xxxxxxxxxtsxxxxf多重

35、最优解例60例的单纯形表及其迭代过程61 在单纯形法计算过程中，确定在单纯形法计算过程中，确定出基变量时有时存在两个以上的相出基变量时有时存在两个以上的相同的最小比值，即同时有多个基变同的最小比值，即同时有多个基变量可选作出基变量，这样在下一次量可选作出基变量，这样在下一次迭代中就有了一个或几个基变量等迭代中就有了一个或几个基变量等于零，这称之为退化。于零，这称之为退化。关于退化问题62例用单纯形表求解下列线性规划问题例用单纯形表求解下列线性规划问题1312131231233max222,24,3,0.zxxxxxxxxxxxx目标函数约束条件63迭迭代代次次数数基基变变量量CBbx1 x2

36、x3 s1 s2 s3比值比值2 0 3/2 0 0 00s1s2s30002431 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12/14/23/102 0 3/2 0 0 01x1s2s32002011 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 10/21/240 2 3/2 -2 0 064n约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域关于无可行解问题65此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）关于LP问题求解的一些基本概念和特点z=10000=50 x1+100 x2优选第一章线性规划问题及单纯形解法第一章线性规划问题及单纯形解法标准型：max z=5x1+4x2s.x1+5x2+6x3-6x3+x5=400,同时令 cn+i=03、LP问题解的几个基本概念max f(x)=-3x1+2x2-4x3+4x3+0 x4+0 x5+0 x6两种方法：大M法 两阶段法1）A中没有多余方程；2x1+x2 +s2=400若xj 0，令 xj=-xj，代入非标准型，则有xj 0极点就是不能成为E 中任何线段的内点的那种点s.X是极点的充分必要条件是：它是基可行解。2x1+x25,1.0,1212.2)(max1.5.3 321321321321321xxxxxxxxxxxxtsxxxxf例