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

第一章线性规划问题及单纯形解法第一章线性规划问题及单纯形解法1优选第一章线性规划问题及单纯形解法优选第一章线性规划问题及单纯形解法2三、求解方法采用成熟的单纯形法．目前，用单纯形法解线性规划的计算机程序已大量涌现，在计算机上求解此类问题已十分容易二、模型较为简单，容易建立，容易学习和掌握．3三、求解方法采用成熟的单纯形法．目前，用单纯形法解线性规划的

线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：线性规划解决的问题1、生产的合理安排问题2、投资决策问题3、运输问题4线性规划的一种最大量、最普遍的应用就是研究有限资源的1.1什么是线性规划

（LinearProgramming)的简单例子和模型

（1）数学模型

一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那些量进行科学的分析后得出的反映这些量之间本质联系的数学关系式。51.1什么是线性规划

（LinearProgrammi

单位单位时耗资源

一

二现有工时搅拌机/小时3515成形机/小时215烘箱/小时2211利润（百元/吨）54例1.21饼干生产问题6单位

问题：如何制订生产计划，才能使资源利用充分并使厂方获最大利润。

7问题：如何制订生产计划，才能使资源利用充分并使厂方解：设由x1，x2

分别表示1，2型饼干每天的生产量。maxz=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.max——maximize,s.t.——subjectto8解：设由x1，x2分别表示1，2型饼干每天的生产量。单台运费B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516问题：如何调运才能即满足用户需要，又使总运费最少？ 例1.22运输问题

9单台B1B2B3A1(200)152118A2(150)161010x1,x2≥0.设X属于S,若x=0,则一定为极点；基可行解：若基解中所有的XB都≥0时，称为基可行解.4人工变量的引入及其解法2-2假设上例中的目标函数变为1试列出下面线性规划问题的初始单纯形表(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。第i个约束的bi为负值，则在bi所在之方程的两边乘以-1。4人工变量的引入及其解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。2x1+x2≤5,例的单纯形表及其迭代过程x2+s3=250x1,x2,x3´,x3´´,x4,x5,x6≥0.迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：1、标准型的几种不同的表示方式

1）和式线性规划数学模型的一般表示方式11x1,x2≥0.线性规划数学模型的一般表示方式11线性规划数学模型的标准型12线性规划数学模型的标准型121、标准型的几种不同的表示方式

1）和式

131、标准型的几种不同的表示方式

1）和式

132）向量式142）向量式143）矩阵153）矩阵15

1）A中没有多余方程；2）b02、对标准型问题作出的假设161）A中没有多余方程；2、对标准型问极点就是不能成为E中任何线段的内点的那种点x1,x2,x3´,x3´´,x4,x5,x6≥0.x1,x2,x3´,x3´´,x4,x5,x6≥0.(3)变换非主行、主列元素aij(包括bi)z=3x1+5x22x1+2x2≤11,1.x2+s3=2503x1+5x2≤15,x1x2x3s1s2s3203/2000s.1、标准型有n+m个变量，m个约束行线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：maxz=5x1+4x21.关于LP问题求解的一些基本概念和特点基解:令非基变量XN=0，求得基变量XB的值称为基解.x1,x2,s1,s2,s3≥0023/2-2001、标准型的几种不同的表示方式

1）和式

最优解使z达到最优的可行解就是最优解（有解（给定的Lp问题有最优解）、否则无解）可行解满足约束条件和非负条件的解X称为可行解，所有可行解组成的集合称之为可行解集（可行域）3、LP问题解的几个基本概念17极点就是不能成为E中任何线段的内点的那种点最优解2.第i个约束的bi

为负值，则在bi所在之方程的两边乘以-1。4、一般型变标准型的变换方法1.目标函数为min型时，价值系数一律反号。即令z(x)=-z(x)=-CX182.第i个约束的bi为负值，则在bi所在之方程的两边乘以3.第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量（原有变量为构造变量）；同时令cn+i

=0

4.第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=0

193.第i个约束为型，在不等式左边增加一个非负的变量x6.若xj无符号限制，令

xj=xj-xj，xj

0，xj0，代入非标准型5.若xj0，令

xj=-xj

，代入非标准型，则有xj

0206.若xj无符号限制，令xj=xj-xj，x原非标准型：maxz=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.5、

变换举例

例1.

21原非标准型：maxz=5x1+4x25、变换举例

例标准型：maxz=5x1+4x2

s.t.3x1+5x2+x3=15,2x1+x2+

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.22标准型：maxz=5x1+4x222例223例223标准型：maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x6s.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.24标准型：24X是极点的充分必要条件是：它是基可行解。极点就是不能成为E中任何线段的内点的那种点1、生产的合理安排问题若有bi<0，则单位阵也不能构成一个可行基若有bi<0，则单位阵也不能构成一个可行基3x1+5x2+x3=15,时耗基解:令非基变量XN=0，求得基变量XB的值称为基解.的列向量的全部分量0，则所给问题无A=(P1,P2,…,Pn,Pn+1,,Pn+2,.三、关于最优解的获得方法问题请查看教材P29中单纯形表的组成形式。x2+s3=250x1=50x2=250s.（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x6maxz=5x1+4x21.线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：x1+x2+s1=300x1，x2，x3，x4，x5≥0.

1.2求解LP问题的基本定理

的图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。

如25X是极点的充分必要条件是：它是基可行解。

1.2求解LP问例1.3Maxz=50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1、

x2≥026例1.326采用图解法(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1.3的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=027采用图解法(1)分别取决策变量X1,X2为坐标向量（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040028（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图12所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图1-229（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图1-3z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADEx1+x2=30030（4）目标函数z=50x1+100x2，当z取某一固定值时得得到最优解：

x1=50，x2=250

最优目标值z=2750031得到最优解：31若在上例模型中中引入松弛变量s1s2s3模型化为Maxz=50x1+100x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0可求解得其最优解为x1=50x2=250s1=0s2=50s3=0说明生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有资源1和3，但资源2还剩余50。32若在上例模型中中引入松弛变量s1s2s3模型化为maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5无需化标准形

例1.2-1求解饼干生产问题33maxz=5x1+4x2图中的OABC即为满足约束条件的可行解集S,需在S中找出最优解,若z为一常数z0则z0=5x1+4x2为目标函数等值线（x1=10/7,x2=15/7,z*=110/7)。34图中的OABC即为满足约束条件的可行解集S,需在S中找出最优例1.2-2假设上例中的目标函数变为

z=3x1+5x2

此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）例1.2-3可行解集为一无界集合

见P18图1.3若是求目标函数最小值，则有最优解。若是求目标函数最大值，则无最优解。若可行解集为空集，则无解，P19图1.435例1.2-2假设上例中的目标函数变为此时最优目标函数求解LP问题的重要规律一、解的存在性问题二、解的结构问题三、关于最优解的获得方法问题（在可行解集的某些“顶点”得到）36求解LP问题的重要规律一、解的存在性问题二、解的结构问题三、关于LP问题求解的一些基本概念和特点1、两个基本概念凸集:实向量空间E中任意两点连线上的一切点仍属于E(见P20)

极点就是不能成为E中任何线段的内点的那种点37关于LP问题求解的一些基本概念和特点1、两个基本概念凸集:实

2、Lp问题的几个特点(相关证明请看1.7节)：

最优解只可能在凸集的极点上，而不可能发生在凸集的内部

线性规划问题的可行解集S是凸集

设X属于S,若x=0,则一定为极点；若x0，则为极点的充要条件是：x的正分量所对应的系数列向量线性无关。

只要存在可行解，就一定存在极点

极点的个数是有限的382、Lp问题的几个特点(相关证明请看1.7节)2、“基”的概念在标准型中，技术系数矩阵有n+m列，即

A=(P1,P2,…,Pn,Pn+1,,Pn+2,..Pn+m)因r(A)=m,所以A的极大无关组含有m个线性无关的向量。关于标准型解的若干基本概念1、标准型有n+m个变量，m个约束行392、“基”的概念关于标准型解的若干基本概念1、标准型有

基、基变量、非基变量——技术系数矩阵A（标准线性规划模型）中m个线性无关的列向量所对应的m个变量，构成该LP问题的一个基，这m个变量的系数列向量组成的矩阵称为基阵，记为B。基中的每个变量称为基变量,记为XB。其余的变量即为非基变量,记为XN

。如：Maxz=50x1+100x2s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0基解:令非基变量XN=0，求得基变量XB的值称为基解.基可行解：若基解中所有的XB

都≥0时，称为基可行解.

40基、基变量、非基变量——技术系数矩阵A（标准线性规划模型）

若基可行解的所有基变量均取正值，则称为非退化的基可行解，如果某些基变量取零值，则为退化的基可行解。41若基可行解的所有基变量均取正值，则称为非退化的基可行解，可行解、基解和基可行解举例42可行解、基解和基可行解举例42可行解、基础解和基础可行解举例43可行解、基础解和基础可行解举例43X是极点的充分必要条件是：它是基可行解。由此，有关极点的结果可转到基可行解上：

只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若LP问题有最优解，则最优解一定可以在基可行解中找到。44X是极点的充分必要条件是：它是基可行解。由此，有关极3、LP问题解的几个基本概念若LP问题有最优解，则最优解一定可以在基可行解中找到。三、关于最优解的获得方法问题maxz=5x1+4x2z=10000=50x1+100x2例的单纯形表及其迭代过程s.x1，x2，x3，x4，x5≥0.同时令cn+i=01单纯形表的迭代过程4、一般型变标准型的变换方法2-2假设上例中的目标函数变为迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：关于LP问题求解的一些基本概念和特点可行解、基解和基可行解举例解：设由x1，x2分别表示1，2型饼干每天的生产量。当约束条件为“”型，引入剩余变量和人工变量其余的变量即为非基变量,记为XN。（在可行解集的某些“顶点”得到）在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。

1.3单纯型法的基本思路确定初始基可行解是否为最优确定改善方向求新的基可行解求最优解的目标函数值是否453、LP问题解的几个基本概念1.3单纯型法的基本(1)单纯形表的组成及形式设B是初始可行基向量，则目标函数可写为两部分(1)约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数把XB代入目标函数，整理得到(3)式若所有非基变量的检验数σi0,则达到最优46(1)单纯形表的组成及形式设B是初始可行基向量，则目标单纯形表47单纯形表47例1.1试列出下面线性规划问题的初始单纯形表

48例1.1试列出下面线性规划问题的初始单纯形表

48

找初始基础可行基对于(max,)，松弛变量对应的列构成一个单位阵若有bi<0，则单位阵也不能构成一个可行基

检验当前基础可行解是否为最优解所有检验数σj0，则为最优解，否则标准型的单纯型法基本步骤

49找初始基础可行基检验当前基础可行解是否为最优解标准型的4确定出基变量最小比例原则3确定入基变量从σj>0中找最大者，选中者称为入基变量xj*

第j*列称为主列504确定出基变量3确定入基变量50设第i*行使最小，则第i*行对应的基变量称为出基变量，第i*行称为主行5迭代过程主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行51设第i*行使最小，则第i*行对应的基变量称为出(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤252(2)变换主列6、返回步骤252例1.1单纯形表的迭代过程答：最优解为x1=20,x2=20,x3=0,OBJ=170053例1.1单纯形表的迭代过程答：最优解为x1=20,x2基可行解的判别和改进定理1.6若所有检验数σj0，则为最优解定理1.7若存在某一个检验数>0，而它所对应的列向量的全部分量0，则所给问题无最优解

除上述两种情况外，若每个正检验数所对应的列向量中都有正分量，则为确定最优解需要进行基的变换（换基）54基可行解的判别和改进定理1.6若所有检验数σj0请查看教材P29中单纯形表的组成形式。55请查看教材P29中单纯形表的组成形式。55

当约束条件为“”型，引入剩余变量和人工变量1.4人工变量的引入及其解法56

当约束条件为“”型，引入剩余变量和人工变量

由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量.两种方法：大M法两阶段法57由于所添加的剩余变量的技术系数为1，不能作为初始可行x1=50x2=250x1,x2,x3´,x3´´,x4,x5,x6≥0.此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：2x1+x2+s2=400第i个约束的bi为负值，则在bi所在之方程的两边乘以-1。maxz=5x1+4x21.关于LP问题求解的一些基本概念和特点此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）优选第一章线性规划问题及单纯形解法若xj无符号限制，令xj=xj-xj，xj0，xj0，代入非标准型2、Lp问题的几个特点(相关证明请看1.maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x62x1+x2+s2=4002、对标准型问题作出的假设若xj0，令xj=-xj，代入非标准型，则有xj0多个基础可行解都是最优解，这些解在同一个平面上，且该平面与目标函数等值面平行4、一般型变标准型的变换方法问题：如何调运才能即满足用户需要，又使总运费最少？201010s1=0s2=50s3=0多个基础可行解都是最优解，这些解在同一个平面上，且该平面与目标函数等值面平行最优单纯形表中有非基变量的检验数为01.5单纯形法应用的特例

关于多重解问题58x1=50x2=250多个基础可行解都是最优解，这些5959例的单纯形表及其迭代过程60例的单纯形表及其迭代过程60

在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。关于退化问题

61在单纯形法计算过程中，确定出基变量时有时存在两例用单纯形表求解下列线性规划问题6262迭代次数基变量CBbx1x2x3s1s2s3比值203/20000s1s2s30002431-101002010101110012/14/23/10203/20001x1s2s32002011-10100021-210021-101—0/21/24023/2-200……63迭代次数基x1x2约束条件互相矛盾，无可行域关于无可行解问题64约束条件互相矛盾，无可行域关于无可行解问题64此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）关于LP问题求解的一些基本概念和特点z=10000=50x1+100x2优选第一章线性规划问题及单纯形解法第一章线性规划问题及单纯形解法标准型：maxz=5x1+4x2s.x1+5x2+6x3´-6x3´´+x5=400,同时令cn+i=03、LP问题解的几个基本概念maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x6两种方法：大M法两阶段法1）A中没有多余方程；2x1+x2+s2=400若xj0，令xj=-xj，代入非标准型，则有xj0极点就是不能成为E中任何线段的内点的那种点s.X是极点的充分必要条件是：它是基可行解。2x1+x2≤5,1.65此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（第一章线性规划问题及单纯形解法第一章线性规划问题及单纯形解法66优选第一章线性规划问题及单纯形解法优选第一章线性规划问题及单纯形解法67三、求解方法采用成熟的单纯形法．目前，用单纯形法解线性规划的计算机程序已大量涌现，在计算机上求解此类问题已十分容易二、模型较为简单，容易建立，容易学习和掌握．68三、求解方法采用成熟的单纯形法．目前，用单纯形法解线性规划的

线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：线性规划解决的问题1、生产的合理安排问题2、投资决策问题3、运输问题69线性规划的一种最大量、最普遍的应用就是研究有限资源的1.1什么是线性规划

（LinearProgramming)的简单例子和模型

（1）数学模型

一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那些量进行科学的分析后得出的反映这些量之间本质联系的数学关系式。701.1什么是线性规划

（LinearProgrammi

单位单位时耗资源

一

二现有工时搅拌机/小时3515成形机/小时215烘箱/小时2211利润（百元/吨）54例1.21饼干生产问题71单位

问题：如何制订生产计划，才能使资源利用充分并使厂方获最大利润。

72问题：如何制订生产计划，才能使资源利用充分并使厂方解：设由x1，x2

分别表示1，2型饼干每天的生产量。maxz=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.max——maximize,s.t.——subjectto73解：设由x1，x2分别表示1，2型饼干每天的生产量。单台运费B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516问题：如何调运才能即满足用户需要，又使总运费最少？ 例1.22运输问题

74单台B1B2B3A1(200)152118A2(150)167510x1,x2≥0.设X属于S,若x=0,则一定为极点；基可行解：若基解中所有的XB都≥0时，称为基可行解.4人工变量的引入及其解法2-2假设上例中的目标函数变为1试列出下面线性规划问题的初始单纯形表(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。第i个约束的bi为负值，则在bi所在之方程的两边乘以-1。4人工变量的引入及其解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。2x1+x2≤5,例的单纯形表及其迭代过程x2+s3=250x1,x2,x3´,x3´´,x4,x5,x6≥0.迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：1、标准型的几种不同的表示方式

1）和式线性规划数学模型的一般表示方式76x1,x2≥0.线性规划数学模型的一般表示方式11线性规划数学模型的标准型77线性规划数学模型的标准型121、标准型的几种不同的表示方式

1）和式

781、标准型的几种不同的表示方式

1）和式

132）向量式792）向量式143）矩阵803）矩阵15

1）A中没有多余方程；2）b02、对标准型问题作出的假设811）A中没有多余方程；2、对标准型问极点就是不能成为E中任何线段的内点的那种点x1,x2,x3´,x3´´,x4,x5,x6≥0.x1,x2,x3´,x3´´,x4,x5,x6≥0.(3)变换非主行、主列元素aij(包括bi)z=3x1+5x22x1+2x2≤11,1.x2+s3=2503x1+5x2≤15,x1x2x3s1s2s3203/2000s.1、标准型有n+m个变量，m个约束行线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：maxz=5x1+4x21.关于LP问题求解的一些基本概念和特点基解:令非基变量XN=0，求得基变量XB的值称为基解.x1,x2,s1,s2,s3≥0023/2-2001、标准型的几种不同的表示方式

1）和式

最优解使z达到最优的可行解就是最优解（有解（给定的Lp问题有最优解）、否则无解）可行解满足约束条件和非负条件的解X称为可行解，所有可行解组成的集合称之为可行解集（可行域）3、LP问题解的几个基本概念82极点就是不能成为E中任何线段的内点的那种点最优解2.第i个约束的bi

为负值，则在bi所在之方程的两边乘以-1。4、一般型变标准型的变换方法1.目标函数为min型时，价值系数一律反号。即令z(x)=-z(x)=-CX832.第i个约束的bi为负值，则在bi所在之方程的两边乘以3.第i个约束为型，在不等式左边增加一个非负的变量xn+i

，称为松弛变量（原有变量为构造变量）；同时令cn+i

=0

4.第i个约束为型，在不等式左边减去一个非负的变量xn+i

，称为剩余变量；同时令cn+i

=0

843.第i个约束为型，在不等式左边增加一个非负的变量x6.若xj无符号限制，令

xj=xj-xj，xj

0，xj0，代入非标准型5.若xj0，令

xj=-xj

，代入非标准型，则有xj

0856.若xj无符号限制，令xj=xj-xj，x原非标准型：maxz=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.5、

变换举例

例1.

86原非标准型：maxz=5x1+4x25、变换举例

例标准型：maxz=5x1+4x2

s.t.3x1+5x2+x3=15,2x1+x2+

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.87标准型：maxz=5x1+4x222例288例223标准型：maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x6s.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.89标准型：24X是极点的充分必要条件是：它是基可行解。极点就是不能成为E中任何线段的内点的那种点1、生产的合理安排问题若有bi<0，则单位阵也不能构成一个可行基若有bi<0，则单位阵也不能构成一个可行基3x1+5x2+x3=15,时耗基解:令非基变量XN=0，求得基变量XB的值称为基解.的列向量的全部分量0，则所给问题无A=(P1,P2,…,Pn,Pn+1,,Pn+2,.三、关于最优解的获得方法问题请查看教材P29中单纯形表的组成形式。x2+s3=250x1=50x2=250s.（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。maxf(x)=-3x1+2x2-4x3´+4x3´´+0x4+0x5+0x6maxz=5x1+4x21.线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：x1+x2+s1=300x1，x2，x3，x4，x5≥0.

1.2求解LP问题的基本定理

的图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。

如90X是极点的充分必要条件是：它是基可行解。

1.2求解LP问例1.3Maxz=50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1、

x2≥091例1.326采用图解法(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1.3的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=092采用图解法(1)分别取决策变量X1,X2为坐标向量（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=40030020030040093（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图12所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图1-294（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图1-3z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADEx1+x2=30095（4）目标函数z=50x1+100x2，当z取某一固定值时得得到最优解：

x1=50，x2=250

最优目标值z=2750096得到最优解：31若在上例模型中中引入松弛变量s1s2s3模型化为Maxz=50x1+100x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0可求解得其最优解为x1=50x2=250s1=0s2=50s3=0说明生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有资源1和3，但资源2还剩余50。97若在上例模型中中引入松弛变量s1s2s3模型化为maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5无需化标准形

例1.2-1求解饼干生产问题98maxz=5x1+4x2图中的OABC即为满足约束条件的可行解集S,需在S中找出最优解,若z为一常数z0则z0=5x1+4x2为目标函数等值线（x1=10/7,x2=15/7,z*=110/7)。99图中的OABC即为满足约束条件的可行解集S,需在S中找出最优例1.2-2假设上例中的目标函数变为

z=3x1+5x2

此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）例1.2-3可行解集为一无界集合

见P18图1.3若是求目标函数最小值，则有最优解。若是求目标函数最大值，则无最优解。若可行解集为空集，则无解，P19图1.4100例1.2-2假设上例中的目标函数变为此时最优目标函数求解LP问题的重要规律一、解的存在性问题二、解的结构问题三、关于最优解的获得方法问题（在可行解集的某些“顶点”得到）101求解LP问题的重要规律一、解的存在性问题二、解的结构问题三、关于LP问题求解的一些基本概念和特点1、两个基本概念凸集:实向量空间E中任意两点连线上的一切点仍属于E(见P20)

极点就是不能成为E中任何线段的内点的那种点102关于LP问题求解的一些基本概念和特点1、两个基本概念凸集:实

2、Lp问题的几个特点(相关证明请看1.7节)：

最优解只可能在凸集的极点上，而不可能发生在凸集的内部

线性规划问题的可行解集S是凸集

设X属于S,若x=0,则一定为极点；若x0，则为极点的充要条件是：x的正分量所对应的系数列向量线性无关。

只要存在可行解，就一定存在极点

极点的个数是有限的1032、Lp问题的几个特点(相关证明请看1.7节)2、“基”的概念在标准型中，技术系数矩阵有n+m列，即

A=(P1,P2,…,Pn,Pn+1,,Pn+2,..Pn+m)因r(A)=m,所以A的极大无关组含有m个线性无关的向量。关于标准型解的若干基本概念1、标准型有n+m个变量，m个约束行1042、“基”的概念关于标准型解的若干基本概念1、标准型有

基、基变量、非基变量——技术系数矩阵A（标准线性规划模型）中m个线性无关的列向量所对应的m个变量，构成该LP问题的一个基，这m个变量的系数列向量组成的矩阵称为基阵，记为B。基中的每个变量称为基变量,记为XB。其余的变量即为非基变量,记为XN

。如：Maxz=50x1+100x2s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0基解:令非基变量XN=0，求得基变量XB的值称为基解.基可行解：若基解中所有的XB

都≥0时，称为基可行解.

105基、基变量、非基变量——技术系数矩阵A（标准线性规划模型）

若基可行解的所有基变量均取正值，则称为非退化的基可行解，如果某些基变量取零值，则为退化的基可行解。106若基可行解的所有基变量均取正值，则称为非退化的基可行解，可行解、基解和基可行解举例107可行解、基解和基可行解举例42可行解、基础解和基础可行解举例108可行解、基础解和基础可行解举例43X是极点的充分必要条件是：它是基可行解。由此，有关极点的结果可转到基可行解上：

只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若LP问题有最优解，则最优解一定可以在基可行解中找到。109X是极点的充分必要条件是：它是基可行解。由此，有关极3、LP问题解的几个基本概念若LP问题有最优解，则最优解一定可以在基可行解中找到。三、关于最优解的获得方法问题maxz=5x1+4x2z=10000=50x1+100x2例的单纯形表及其迭代过程s.x1，x2，x3，x4，x5≥0.同时令cn+i=01单纯形表的迭代过程4、一般型变标准型的变换方法2-2假设上例中的目标函数变为迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：关于LP问题求解的一些基本概念和特点可行解、基解和基可行解举例解：设由x1，x2分别表示1，2型饼干每天的生产量。当约束条件为“”型，引入剩余变量和人工变量其余的变量即为非基变量,记为XN。（在可行解集的某些“顶点”得到）在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，即同时有多个基变量可选作出基变量，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。

1.3单纯型法的基本思路确定初始基可行解是否为最优确定改善方向求新的基可行解求最优解的目标函数值是否1103、LP问题解的几个基本概念1.3单纯型法的基本(1)单纯形表的组成及形式设B是初始可行基向量，则目标函数可写为两部分(1)约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数把XB代入目标函数，整理得到(3)式若所有非基变量的检验数σi0,则达到最优111(1)单纯形表的组成及形式设B是初始可行基向量，则目标单纯形表112单纯形表47例1.1试列出下面线性规划问题的初始单纯形表

113例1.1试列出下面线性规划问题的初始单纯形表

48

找初始基础可行基对于(max,)，松弛变量对应的列构成一个单位阵若有bi<0，则单位阵也不能构成一个可行基

检验当前基础可行解是否为最优解所有检验数σj0，则为最优解，否则标准型的单纯型法基本步骤

114找初始基础可行基检验当前基础可行解是否为最优解标准型的4确定出基变量最小比例原则3确定入基变量从σj>0中找最大者，选中者称为入基变量xj*

第j*列称为主列1154确定出基变量3确定入基变量50设第i*行使最小，则第i*行对应的基变量称为出基变量，第i*行称为主行5迭代过程主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行116设第i*行使最小，则第i*行对应的基变量称为出(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2117(2)变换主列6、返回步骤252例1.1单纯形表的迭代过程答：最优解为x1=20,x2=20,x3=0,OBJ=1700118例1.1单纯形表的迭代过程答：最优解为x1=20,x2基可行解的判别和改进定理1.6若所有检验数σj0，则为最优解定理1.7若存在某一个检验数>0，而它所对应的列向量的全部分量0，则所给问题无最优解

除上述两种情况外，若每个正检验数所对应的列向量中都有正分量，则为确定最优解需要进行基的变换（换基）119基可行解的判别和改进定理1.6若所有检验数σj0请查看教材P29中单纯形表的组成形式。120请查看教材P29中单纯形表的组成形式。55

当约束条件为“”型，引入剩余变量和人工变量1.4人工变量的引入及其解法121

当约束条件为“”型，引入剩余变量和人工变量

由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量.两种方法：大M法两阶段法122由于所添加的剩余变量的技术系数为1，不能作为初始可行x1=50x2=250x1,x2,x3´,x3´´,x4,x5,x6≥0.此时最优目标函数等值线与AB边重合，AB上每一点均为最优解（无穷个）线性规划的一种最大量、