线性规划问题及单纯形解法

关于线性规划问题及单纯形解法第1页，讲稿共70页，2023年5月2日，星期三2

线性规划及应用简介

线性规划是运筹学的一个最基本的分支，它已成为帮助各级管理人员进行决策的·一种十分重要的工具．是一种目前最常用而又最为成功的定性分析和定量分析相结合的管理优化技术。其原因有三：一、应用广泛．管理工作中的大量优化问题可以用线性规划的模型来表达第2页，讲稿共70页，2023年5月2日，星期三3三、求解方法采用成熟的单纯形法．目前，用单纯形法解线性规划的计算机程序已大量涌现，在计算机上求解此类问题已十分容易二、模型较为简单，容易建立，容易学习和掌握．第3页，讲稿共70页，2023年5月2日，星期三4

线性规划的一种最大量、最普遍的应用就是研究有限资源的合理利用问题，或说资源的最优配置问题．资源分配问题有多种多样的具体形式．例：

线性规划解决的问题：1、生产的合理安排问题2、投资决策问题3、运输问题第4页，讲稿共70页，2023年5月2日，星期三51.1什么是线性规划

（LinearProgramming)1.1.1Lp的简单例子和模型

（1）数学模型

一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那些量进行科学的分析后得出的反映这些量之间本质联系的数学关系式。第5页，讲稿共70页，2023年5月2日，星期三6

单位单位时耗资源

一

二现有工时搅拌机/小时3515成形机/小时215烘箱/小时2211利润（百元/吨）54例1.2-1饼干生产问题第6页，讲稿共70页，2023年5月2日，星期三7

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

第7页，讲稿共70页，2023年5月2日，星期三8解：设由x1，x2

分别表示1，2型饼干每天的生产量。

max

z=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.max——maximize,s.t.——subjectto第8页，讲稿共70页，2023年5月2日，星期三9单台运费B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516问题：如何调运才能即满足用户需要，又使总运费最少？ 例1.2-2运输问题

第9页，讲稿共70页，2023年5月2日，星期三10第10页，讲稿共70页，2023年5月2日，星期三111.1.2线性规划数学模型的一般表示方式第11页，讲稿共70页，2023年5月2日，星期三121.1.3线性规划数学模型的标准型第12页，讲稿共70页，2023年5月2日，星期三131、标准型的几种不同的表示方式

1）和式

第13页，讲稿共70页，2023年5月2日，星期三142）向量式第14页，讲稿共70页，2023年5月2日，星期三153）矩阵第15页，讲稿共70页，2023年5月2日，星期三16

1）A中没有多余方程；2）b02、对标准型问题作出的假设第16页，讲稿共70页，2023年5月2日，星期三17

最优解使z达到最优的可行解就是最优解（有解（给定的Lp问题有最优解）、否则无解）可行解

满足约束条件和非负条件的解X称为可行解，所有可行解组成的集合称之为可行解集（可行域）3、LP问题解的几个基本概念第17页，讲稿共70页，2023年5月2日，星期三182.第i个约束的bi

为负值，则在bi所在之方程的两边乘以-1。4、一般型变标准型的变换方法：1.目标函数为min型时，价值系数一律反号。即令z(x)=-z(x)=-CX第18页，讲稿共70页，2023年5月2日，星期三193.第i个约束为型，在不等式左边增加一个非负的变量xn+i

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

=0

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

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

=0

第19页，讲稿共70页，2023年5月2日，星期三206.若xj无符号限制，令

xj=xj-xj，xj

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

xj=-xj

，代入非标准型，则有xj

0第20页，讲稿共70页，2023年5月2日，星期三21原非标准型：maxz=5x1+4x2

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

变换举例

例1.

第21页，讲稿共70页，2023年5月2日，星期三22标准型：maxz=5x1+4x2

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

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.第22页，讲稿共70页，2023年5月2日，星期三23例2第23页，讲稿共70页，2023年5月2日，星期三24标准型：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页，讲稿共70页，2023年5月2日，星期三25

1.2求解LP问题的基本定理

1.2.1LP的图解法

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

如：第25页，讲稿共70页，2023年5月2日，星期三26例1.3Maxz=50x1+100x2

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

x2≥0第26页，讲稿共70页，2023年5月2日，星期三27采用图解法(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1.3的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第27页，讲稿共70页，2023年5月2日，星期三28（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第28页，讲稿共70页，2023年5月2日，星期三29（3）把五个图合并成一个图，取各约束条件的公共部分，如P7图1-2所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图1-2第29页，讲稿共70页，2023年5月2日，星期三30（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=300第30页，讲稿共70页，2023年5月2日，星期三31得到最优解：

x1=50，x2=250

最优目标值z=27500第31页，讲稿共70页，2023年5月2日，星期三32若在上例模型中中引入松弛变量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页，讲稿共70页，2023年5月2日，星期三33maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5无需化标准形

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

z=3x1+5x2

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

见P18图1.3若是求目标函数最小值，则有最优解。若是求目标函数最大值，则无最优解。若可行解集为空集，则无解，P19图1.4第35页，讲稿共70页，2023年5月2日，星期三36求解LP问题的重要规律：一、解的存在性问题二、解的结构问题三、关于最优解的获得方法问题（在可行解集的某些“顶点”得到）第36页，讲稿共70页，2023年5月2日，星期三37关于LP问题求解的一些基本概念和特点：1、两个基本概念凸集:实向量空间E中任意两点连线上的一切点仍属于E(见P20)

极点就是不能成为E中任何线段的内点的那种点第37页，讲稿共70页，2023年5月2日，星期三38

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

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

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

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

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

极点的个数是有限的第38页，讲稿共70页，2023年5月2日，星期三392、“基”的概念在标准型中，技术系数矩阵有n+m列，即

A=(P1,P2,…,Pn,Pn+1,,Pn+2,..Pn+m)因r(A)=m,所以A的极大无关组含有m个线性无关的向量。

关于标准型解的若干基本概念：1、标准型有n+m个变量，m个约束行第39页，讲稿共70页，2023年5月2日，星期三40

基、基变量、非基变量——技术系数矩阵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页，讲稿共70页，2023年5月2日，星期三41

若基可行解的所有基变量均取正值，则称为非退化的基可行解，如果某些基变量取零值，则为退化的基可行解。第41页，讲稿共70页，2023年5月2日，星期三42可行解、基解和基可行解举例第42页，讲稿共70页，2023年5月2日，星期三43可行解、基础解和基础可行解举例第43页，讲稿共70页，2023年5月2日，星期三44X是极点的充分必要条件是：它是基可行解。由此，有关极点的结果可转到基可行解上：

只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若LP问题有最优解，则最优解一定可以在基可行解中找到。第44页，讲稿共70页，2023年5月2日，星期三45

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

第48页，讲稿共70页，2023年5月2日，星期三49

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

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

第49页，讲稿共70页，2023年5月2日，星期三504确定出基变量最小比例原则3确定入基变量从σj>0中找最大者，选中者称为入基变量

xj*

第j*列称为主列第50页，讲稿共70页，2023年5月2日，星期三51设第i*行使最小，则第i*行对应的基变量称为出基变量，第i*行称为主行5迭代过程主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行第51页，讲稿共70页，2023年5月2日，星期三52(2)变换主列除主元保留为1，其余都置0(3)变换非主行、主列元素aij(包括bi)(4)变换CB，XB(5)计算目标函数、机会成本zj和检验数cjzj6、返回步骤2第52页，讲稿共70页，2023年5月2日，星期三53例1.1单纯形表的迭代过程答：最优解为x1=20,x2=20,x3=0,OBJ=1700第53页，讲稿共70页，2023年5月2日，星期三541.3.3基可行解的判别和改进定理1.6

若所有检验数σj0，则为最优解定理1.7

若存在某一个检验数>0，而它所对应的列向量的全部分量0，则所给问题无最优解

除上述两种情况外，若每个正检验数所对应的列向量中都有正分量，则为确定最优解需要进行基的变换（换基）第54页，讲稿共70页，2023年5月2日，星期三55请查看教材P29中单纯形表的组成形式。第55页，讲稿共70页，2023年5月2日，星期三56

当约束条件为“”型，引入剩余变量和人工变量1.4人工变量的引入及其解法第56页，讲稿共70页，2023年5月2日，星期三57

由于所添加的剩余变量的技术系数为1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量.两种方法：大M法两阶段法第57页，讲稿共70页，2023年5月2日，星期三58多个基础可行解都是最优解，这些解在同一个平面上，且该平面与目标函数等值面平行最优单纯形表中有非基变量的检验数为01.5单纯形法应用的特例

1.5.1关于多重解问题第58页，讲稿共70页，2023年5月2日，星期三59第59页，讲稿共70页，2023年5月2日，星期三60例1.5.1的单纯形表及其迭代过程第60页，讲稿共70页，2023年5月2日，星期三61

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

第61页，讲稿共70页，2023年5月2日，星期三62例1.5.2用单纯形表求解下列线性规划问题第62页，讲稿共70页，2023年5月2日，星期三63迭代次数基变量CBbx1x2x3s1s2s3比值203/20000s1s2s30002431-1010020101