线性规划与单纯形方法

关于线性规划与单纯形方法12第一节线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例第2页,共129页，2024年2月25日，星期天3一、实例例1生产计划问题(书P8)Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2

。Step2:确定约束条件产品

I

II资源限量设备

1

2

8台时原料A

4

0

16公斤原料B

0

4

12公斤利润

2

3问应如何安排生产使该厂获利最多？第3页,共129页，2024年2月25日，星期天4说明：OBJ表示Objective;

s.t.表示Subjectto

Step3:给出目标函数Step4:整理数学模型第4页,共129页，2024年2月25日，星期天5例2下料问题现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各一根。已知原料长7.4米，问如何下料，使用的原料最少（余料最少或根数最少）？分析：最简单的做法是：每根7.4米长的原材料各截取三种规格的元钢一根，则料头为0.9米，100套则浪费材料90米。关键是要设计套裁方案，不能有遗漏。第5页,共129页，2024年2月25日，星期天6解：设x1,x2,

x3,x4,x5分别代表五种不同的原料用量方案。0.86.6310x50.37.1021x40.27.2220x30.17.3102x207.4301x1余料合计1.5米2.1米2.9米方案余料最少的LP模型：第6页,共129页，2024年2月25日，星期天7根数最少的LP模型：料头最省根数最少＝解1:x1=30,x2=10,x4=50;料头Z=16,根数90。可以做100套钢架，无圆钢剩余。与解1相同≥解2:x1=100,x3=50;料头Z=10,根数150。可以做100套钢架,但余1.5m圆钢300根。与解1相同第7页,共129页，2024年2月25日，星期天8LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。第8页,共129页，2024年2月25日，星期天9

目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。

每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（LP问题）的共同特征第9页,共129页，2024年2月25日，星期天10Max(Min)Z=c1x1+c2x2+…+cnxn(1)

a11x1+a12x2+…+a1nxn

≤(=,≥)b1a21x1+a22x2+…+a2nxn

≤

(=,≥)b2

s.t.

……(2)am1x1+am2x2+…+amnxn

≤

(=,≥)bmxj≥0,j=1,2,…，n(3)(1)—目标函数；(2)约束条件；(3)决策变量非负n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量线性规划模型的一般形式为：第10页,共129页，2024年2月25日，星期天11线性规划模型的紧缩形式n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量第11页,共129页，2024年2月25日，星期天12练习题：是否为线性规划模型？第12页,共129页，2024年2月25日，星期天131.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的图解法第13页,共129页，2024年2月25日，星期天144x1=164x2=12x1+2x2=8x1x248Q1

4Q4

30例3

（书P8）：Q2(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q3第14页,共129页，2024年2月25日，星期天15目标函数z=ax1+bx2的值递增的方向与系数a、b有关a>0,b>0a<0,b>0X1X2a<0,b<0a>0,b<0z=ax1+bx2目标函数等值线：ax1+bx2=k移项x2=-a/bx1+k/b目标函数等值线在纵轴上的截距为k/b第15页,共129页，2024年2月25日，星期天16例4Z=36第16页,共129页，2024年2月25日，星期天17例用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当Z值由小变大时，将与Q2Q3重合Q2Q3上任意一点都是最优解有无穷多最优解（多重解）Q3(2,3)第17页,共129页，2024年2月25日，星期天18例用图解法求解线性规划问题可行域无界—无界解（“无有限最优解”或“最优解无界”）约束条件过分宽松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域无解（不闭合）一定就会出现无界解吗？第18页,共129页，2024年2月25日，星期天19例用图解法求解线性规划问题可行域无界—唯一最优解X*=(1,0)，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第19页,共129页，2024年2月25日，星期天20例用图解法求解线性规划问题可行域无界—无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00第20页,共129页，2024年2月25日，星期天21例（书P11）：

无可行解（可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4

无最优解第21页,共129页，2024年2月25日，星期天223.图解法的作用能解决少量问题揭示了线性规划问题的若干规律解的类型可行域类型唯一最优解无穷多最优解最优解无界（无有限最优解）无解（不存在可行域）非空有界无界空集规律1：第22页,共129页，2024年2月25日，星期天23规律2：线性规划问题的可行域为凸集线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到第23页,共129页，2024年2月25日，星期天24小结：图解法的基本步骤：1．在直角坐标系作出可行域S的区域（一般是一个凸多边形）2．令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k3．对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点4．将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动第24页,共129页，2024年2月25日，星期天25四、线性规划问题的标准型1.标准型（1）目标函数：max（2）约束条件：等式（3）变量约束：非负xj0（4）资源限量：非负bi

0标准型的构成要素第25页,共129页，2024年2月25日，星期天262.线性规划标准型的紧缩形式第26页,共129页，2024年2月25日，星期天273.线性规划标准型的向量和矩阵表达式矩阵式:MaxZ=CTXs.t.AX=b

X≥0

n向量式:MaxZ=∑cjxj

j=1

ns.t.∑Pjxj=b

j=1

xj≥0,j=1,2,...,n第27页,共129页，2024年2月25日，星期天284.所有LP问题均可化为标准型（1）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*第28页,共129页，2024年2月25日，星期天29（2）不等式约束条件转换成等式约束条件（3）变量约束转换（4）把bi0转换成bi0第29页,共129页，2024年2月25日，星期天30例5

化标准型可化为1.处理决策变量

2.处理目标函数

3.约束条件不等式

4.处理约束条件右端

常数项

第30页,共129页，2024年2月25日，星期天31例6

化标准型1.处理决策变量

2.处理目标函数

3.约束条件不等式

4.处理约束条件右端

常数项

第31页,共129页，2024年2月25日，星期天32MaxZ’=x1+2x’2+3x4-3x5+0x6+0x7s.t.x1-x’2+x4-x5+x6=7

x1+x’2+x4

-x5-x7=2-3x1-x’2+3x4-3x5=5x’2≥0,xj≥0,j=1,4,5,6,7

MaxZ’=x1+2x’2+3(x4-x5)+0x6+0x7s.t.x1-x’2+(x4-x5)

+x6=7

x1+x’2+(x4

-x5)

-x7=2-3x1-x’2+3(x4-x5)=5x’2≥0,xj≥0,j=1,4,5,6,7

最终结果中间结果第32页,共129页，2024年2月25日，星期天33课堂练习第33页,共129页，2024年2月25日，星期天34五、标准型LP问题解的概念第34页,共129页，2024年2月25日，星期天35（1）（2）（3）约束系数矩阵：x1x2x3x4x5例：第35页,共129页，2024年2月25日，星期天36约束系数矩阵：可能的基矩阵是A中任意三个列的组合，共10个。

第36页,共129页，2024年2月25日，星期天37令B==(P1,P2,…,Pm

)

且|B|0

，则称Pj(j=1,2,…,m)

为基向量。与基向量Pj对应的变量xj称为基变量，记为XB=(x1,x2,…,xm

)T，其余的变量称为非基变量，记为XN

=(xm+1,xm+2,…,xn

)T

。第37页,共129页，2024年2月25日，星期天38第38页,共129页，2024年2月25日，星期天39第39页,共129页，2024年2月25日，星期天40B1=(P1,P2)：基令：XB1=(x1,x2)x1=0，

x2=2X=(0,2,0,0)XB1=(0,2)对应于B1的基解为也是基可行解第40页,共129页，2024年2月25日，星期天41线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解第41页,共129页，2024年2月25日，星期天42例7

MaxZ=2x1+3x2

s.t.x1+2x2≤84x1≤164x2≤12

x1,x2

≥0

六、可行解、基解和基可行解举例非基变量基变量图中的点x4,x5x1=4x2=3x3=-2A基解x3,x5x1=2x2=3x4=8B基可行解x3,x4x1=4x2=2x5=4C基可行解，最优解x2,x4x1=4x3=4x5=12D基可行解x2,x3x1=8x4=-16x5=12E基解x1,x5x2=3x3=2x4=16F基可行解x1,x3x2=4x4=16x5=-4G基解x1,x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型第42页,共129页，2024年2月25日，星期天43例8第43页,共129页，2024年2月25日，星期天44LP标准型问题解的结论

根据LP的图解法及解的基本概念可知：基解对应约束条件的交点；基可行解对应可行域的顶点某个基可行解一定是最优解，即一定在可行域的顶点上得到最优解。第44页,共129页，2024年2月25日，星期天45第二节LP问题的基本理论一、基本概念第45页,共129页，2024年2月25日，星期天46判断以下图形哪些是凸集，哪些不是凸集？判断下列集合是否凸集？第46页,共129页，2024年2月25日，星期天47定理1

LP问题的可行域为一凸集。二、基本定理第47页,共129页，2024年2月25日，星期天48引理线性规划问题的可行解X=(x1,x2,…,xn)T是基可行解的充要条件为X的正分量所对应的系数列向量是线性独立的。第48页,共129页，2024年2月25日，星期天49定理2

线性规划问题的基可行解对应于可行域的顶点。（即：若X是LP问题的可行解，则“X是LP问题的基可行解”等价于“X是LP问题可行域顶点”）因为X是基可行解，则其对应的向量组a1,a2,…,am线性无关(m<n)当j>m时，有xj=xj(1)=xj(2)=0.第49页,共129页，2024年2月25日，星期天50第50页,共129页，2024年2月25日，星期天51第51页,共129页，2024年2月25日，星期天52第52页,共129页，2024年2月25日，星期天53定理3

若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。引理若S是有界凸集，则任何一点X∈S可表示为S的顶点的凸组合。第53页,共129页，2024年2月25日，星期天54

线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。

第54页,共129页，2024年2月25日，星期天55第三节单纯形法一、基本思想检验解的最优性结束Y枢轴运算（旋转运算）确定另一个基本可行解N化LP问题为标准型，确定一个初始基本可行解化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。第55页,共129页，2024年2月25日，星期天56单纯形法举例（P20）化为标准型二、基本原理举例第56页,共129页，2024年2月25日，星期天571.初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基）。第57页,共129页，2024年2月25日，星期天58

令非基变量x1＝0、x2＝0，得到基可行解及相应的目标函数值，X(0)＝(0,0,8,16,12)T，Z(0)＝0。结论：（1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；（2）基变量确定后，目标函数和基变量均可表示成非基变量的代数和形式（如(6)和(5)），从而便于求出基可行解及相应的目标函数值。第58页,共129页，2024年2月25日，星期天592.最优性检验

考察变换后的目标函数(6)式，非基变量x1、x2的系数都为正数，若让x1、x2取正值，则目标函数值会增大。因此，应将非基变量x1、x2变换成基变量。结论：在非基变量的代数和形式表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。第59页,共129页，2024年2月25日，星期天60

当确定x2为换入变量后，x1还是非基变量，故x1＝0。现在要保证x3、x4、x5³0，即(5)当x2＝min（8/2，—，12/4）=3（最小比值规则）可保证x5=0则x5为换出变量。新的基变量为x3、x4、x2

，新的可行基为B1＝(P3,P4,P2)确定换入变量：一般选择正系数最大的非基变量为换入变量。确定换出变量：（a）保证换出的变量取值为0，变成非基量；（b）其它的变量取值为非负。3.确定新的基可行解（基变换）第60页,共129页，2024年2月25日，星期天614.旋转迭代

基变量确定后，旋转迭代就是把目标函数和基变量均表示成非基变量x1、x5的代数和形式。可用高斯消去法实现。

令非基变量x1＝0、x5＝0，得到新的基可行解及相应的目标函数值，X(1)＝(0,3,2,16,0)T，Z(1)＝9。返回至第二步，直至求出最优解。第61页,共129页，2024年2月25日，星期天62这时目标函数的表达式是z=14－1.5x3－0.125x4，当将x1定为换入变量后，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T，这时目标函数的表达式是z=13－2x3+1/4x5，再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q3

将上述方程组求解过程，用列表形式表达，即为线性规划单纯形表。第62页,共129页，2024年2月25日，星期天63以x2为主元素以x1为主元素例

2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)

x1+1/2x2+x3=5(1)’0x1+3/2x2-2x3=-9(2)’(2)-(1)×3/2,(1)/2

x1+0x2+5/3x3=80x1+x2-4/3x3=-6(1)’-(2)’/3,(2)’×2/3三、旋转运算结论：旋转运算就是矩阵的初等变换，是高斯消元第63页,共129页，2024年2月25日，星期天64结论：如果LP问题通过单纯形法迭代到某步时，所有检验数≤0,则该LP问题已得到最优解。MaxZ=CXs.t.AX=b

X≥0若cj-CBB-1Pj=σj≤0,则Z≤Z0,Z0即为最优解.(基变量的检验数必为0)令A=(B,N),X=XB

,C=(CB,CN)

XN由AX=b(B,N)XB=b

BXB+NXN=b

B-1BXB+B-1NXN=B-1b

XN

XB=B-1b－B-1NXN(2)将(2)式代入目标函数得Z=CX=(CB,CN)XB=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

XN

=CBB-1b+(CN-CBB-1N)XN=Z0+∑(cj-CBB-1Pj)xj

xj为非基变量四、检验数公式第64页,共129页，2024年2月25日，星期天65对于线性规划问题：MaxZ=CTX

AX=b，X≥0，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。判别定理1

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0，则X为线性规划的最优解。判别定理2

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0，同时有某个非基变量的检验数σk=0(k∈J)，则该线性规划有无穷多最优解；设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj＜0，则该线性规划有唯一最优解。判别定理3设X为线性规划的一个基可行解，若有σk>0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），则该线性规划问题具有无界解（无最优解）。第65页,共129页，2024年2月25日，星期天66一、步骤Step1.化LP问题为标准型,建立初始单纯形表;Step2.若所有检验数≤0,则最优解已达到。否则,计算

,选取σk所对应的变量xk为进基变量;Step3.计算

,选取θl所对应的变量xl为出基变量;Step4.以alk为主元素进行旋转运算,转Step2;第四节单纯形法的步骤第66页,共129页，2024年2月25日，星期天67cj

CBXBb

x1x2

…

xm

xm+1…

xn

σj

基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=01.初始单纯形表c1c2…

cm

cm+1…cnc1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm10…0a1,m+1…

a1n01…0a2,m+1…

a2n∶∶

…

∶

∶

…∶00…1am,m+1…

amn00…0σm+1…

σn-CBTB-1b第67页,共129页，2024年2月25日，星期天68对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。（2）从单纯形表中，可立即得到一个基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=0（3）用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。第68页,共129页，2024年2月25日，星期天692.进基变量的选择cj

c1c2…

cmcm+1…ck…cnθ

CBXBb

x1x2

…

xm

xm+1…xk

…

xn

c1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm

10…0a1,m+1…

a1k

…

a1n01…0a2,m+1…

a2k

…

a2n∶∶

…

∶

∶

…∶…∶00…1am,m+1…amk

…amnσj

-CBTB-1b

00…0σm+1…σk…σn选取

所对应的变量xk为进基变量。第69页,共129页，2024年2月25日，星期天703.出基变量的选择cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

alk

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnθ1∶θl∶θmσj

-CBTB-1b

0…0…0σm+1…σk…σn选取

所对应的变量xl为出基变量。第70页,共129页，2024年2月25日，星期天714.旋转运算cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

[alk]

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnσj

ck

xkbl/alk0…1/alk…0al,m+1/alk…1…aln/alkb1’1…-a1k/alk…0a1,m+1’…

0

…

a1n’bm’0…-amk/alk…1am,m+1’…

0

…

amn’第71页,共129页，2024年2月25日，星期天72二、实例化为标准型第72页,共129页，2024年2月25日，星期天73单纯型表算法

X(0)＝(0,0,8,16,12)T以[1]为主元素进行旋转运算，x1为换入变量，x3为换出变量

0

qi

3

0

0

x5

x2

x3

x40

x4

x3XB

b

sj

0

x1CB

2cj

x1

cj

x2

x3

x4

x5

1

4

0

2

0

4

1

0

0

0

1

0

0

0

1

2

3

0

0

0

b816

12

XB

x3

x4

x5

CB

0

0

0以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量

sj

2

3

0

0

0

qi

8/2

—

12/4[4]

x2

3主元列主元行

0

0

0

1/43

1

4

0

1

016

0

0

1

1

0

-1/22X(1)＝(0,3,2,16,0)T

2

0

0

-3/4

016/4

2/1

—

[1]第73页,共129页，2024年2月25日，星期天74此时达到最优解。X*=(4,2),maxZ=14。

0

qi

3

0

0

x5

x2

x3

x40

x4

x23

XB

b

sj

x1CB

2cj

0

qi

3

0

0

x5

x2

x3

x4x23

x1XB

b

sj

2

x1CB

2cj

0

0

0

1/43

10

-2

0

1/4

0

x1

2

0

1

1

0

-1/22

[2]

0-4

128

08/2

12

—

x50

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0X(3)＝(4,2,0,0,4)TX(2)＝(2,3,0,8,0)T以[2]为主元素进行旋转运算，x5为换入变量，x4为换出变量第74页,共129页，2024年2月25日，星期天754x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解迭代

顶点相邻的顶点迭代

图解法：单纯形表算法：第75页,共129页，2024年2月25日，星期天76对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：判别定理1

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，则X为线性规划的最优解。判别定理2

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，同时有某个非基变量的检验数σk=0(k∈J)，则该线性规划有无穷多最优解；设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj＞0，则该线性规划有唯一最优解。判别定理3

设X为线性规划的一个基可行解，若有σk<0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），则该线性规划问题具有无界解（无最优解）。在进基可行解的转换过程中，进基变量的选取原则是：min{σj

|σj<0}=σk，则可以确定xk为换入变量。出基变量的选取原则不变。第76页,共129页，2024年2月25日，星期天77一、人工变量法第五节LP问题的进一步讨论1.大M法2.两阶段法第77页,共129页，2024年2月25日，星期天781.大M法加入人工变量xn+1,xn+2,…,xn+m问题A问题B第78页,共129页，2024年2月25日，星期天791.大M法加入人工变量xn+1,xn+2,…,xn+m问题C问题D第79页,共129页，2024年2月25日，星期天801.大M法（M为任意大的正数）加入人工变量x6,x7加入松弛变量x4和剩余变量x5第80页,共129页，2024年2月25日，星期天811)人工变量的识别2)目标函数的处理3)计算(单纯形法)第81页,共129页，2024年2月25日，星期天82cj-31100MMθiCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011σj-4M-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001-σj-M-1-11-M00M03M-1注意：本例是求最小值，所以用所有来判别目标函数是否实现了最小化。因而换入变量xk的选取标准为第82页,共129页，2024年2月25日，星期天83结果得:X*=(4,1,9,0,0,0,0)Z*=-2cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001-σj-2-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3σj20001/31/3M-1/3M-2/3（接上表）第83页,共129页，2024年2月25日，星期天841.大M法例用单纯形法（大M法）求解下列线性规划加入松弛变量x3,剩余变量x4，人工变量x5第84页,共129页，2024年2月25日，星期天85用单纯形法计算，其过程如下表所示：Cj3200-MCBXBbx1x2x3x4x50x322[1]100-Mx512340-11σj12M3+3M2+4M0-M02x2221100-Mx54-50-4-11σj-4+4M-1-5M0-2-4M-M0虽然检验数均小于等于0，但基变量中含有非零的人工变量x5=4，所以原问题无可行解第85页,共129页，2024年2月25日，星期天861.大M法

大M法的几点结论（1）问题B要实现极大化，必须将人工变量从基变量中换出，否则原问题目标函数不可能实现最优；（2）若在求解问题B的过程中，已将人工变量从基变量中换出，则已得到问题A的一个基可行解，可继续求解，以获得问题A的最优解；（3）若求解问题B已得到最优解，但最优解的基变量中含有不为零的人工变量，则问题A无可行解；这是LP问题无解的判别条件。（4）若求解问题B已得到最优解，且最优解的基变量中不含有人工变量，则问题B的最优解就是问题A的最优解。第86页,共129页，2024年2月25日，星期天87两阶段法(将LP问题分成两个阶段来考虑)

第I阶段:

不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造目标函数，使其为仅含人工变量的和，并要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。

第II阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。第87页,共129页，2024年2月25日，星期天88加入松弛变量x4;剩余变量x5;人工变量x6,x7用单纯形法求解第一阶段的结果得：第88页,共129页，2024年2月25日，星期天891100000-000010-21x30--21-100101x204-52-2100312x4030100-10-100010-21x301-21-100101x61--10010-2310x400010-3-161100010-21x713/201-1021-43x611100011-2111x40x7x6x5x4x3x2x1bXBCB1100000cj此时，达到第一阶段的最优解，W=0第89页,共129页，2024年2月25日，星期天901/31/3000-4/32/31009x31-100101x21-2/31/30014x1-31000-1-0010-21x31--100101x214-2100312x40x5x4x3x2x1bXBCB0011-3cj由于人工变量x6=x7=0,所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段运算：此时达到该LP问题的最优解：X*=(4,1,9,0,0)T;目标函数值Z*=-2。第90页,共129页，2024年2月25日，星期天911.存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为进基变量。2.最小比值相同。在下一次迭代中就有一个或几个基变量等于零。二、单纯形法中存在的问题如果在一个基本可行解的基变量中至少有一个分量为0，则称此基本可行解是退化的基本可行解，这样的线性规划问题称为退化的线性规划问题。第91页,共129页，2024年2月25日，星期天92cj

3/4-201/2-60

00CBXBbx1x2x3x4x5x6x70x501/4-8-191000x601/2-12-1/230100x71001000103/4-201/2-6000第92页,共129页，2024年2月25日，星期天93cj

3/4-201/2-6000CBXBbx1x2x3x4x5x6x73/4x101-32-4364000x60043/2-150100x710010001σj0047/221-300选取x1为换入变量；选取下标最小的x5为换出变量，得下表：此时换出变量为x1，换入变量为x4，迭代后目标函数值不变。这时不同的基表示为同一顶点。第93页,共129页，2024年2月25日，星期天94当线性规划问题出现退化时，用单纯形法计算就会出现所谓的循环，即多次迭代，而基从B1,B2,…,又返回到B1，即出现计算过程的循环，永远达不到最优解。1955年，Beale给出了如下退化与循环的例子，即用单纯形法求解，经过6次转换，又回到初始基可行解上，其基变量的转换次序为:(x5,x6,x7)→(x1,x6,x7)→(x1,x2,x7)→(x3,x2,x7)→(x3,x4,x7)→(x5,x4,x7)→(x5,x6,x7)第94页,共129页，2024年2月25日，星期天95解决退化的方法有：“摄动法”、“辞典序法”、Bland规则等1974年Bland提出Bland算法规则：第95页,共129页，2024年2月25日，星期天963.最小比值原则失效cj2300CBXBbx1x2x3x40x36-20113x24-3101cj-Zj-121100-3经过一次迭代后可得右表当用单纯形法求解LP问题迭代到某步时,存在某σk>0,而σk对应列向量Pk’≤0,则此LP问题有无界解.第96页,共129页，2024年2月25日，星期天974.在最优表中出现某非基变量检验数为0（无穷多最优解）第97页,共129页，2024年2月25日，星期天98CBXBbx1x2x3x4x50x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-360000-10x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj034000结论：若线性规划问题存在某非基变量检验数为0,而其对应列向量Pk≤0,仍可判断线性规划问题有无穷多最优解。第98页,共129页，2024年2月25日，星期天99例1

某工厂要用三种原材料D、P、H混合调配出三种不同规格的产品A、B、C。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？产品名称规格要求单价(元/kg）A原材料D不少于50%原材料P不超过25%50B原材料D不少于25%原材料P不超过50%35C不限25原材料名称每天最多供应量(kg)单价(元/kg)D10065P10025H6035第六节应用举例解：设A中D、P、H的含量为x11、x12、x13B中D、P、H的含量为x21、x22、x23

C中D、P、H的含量为x31、x32、x33第99页,共129页，2024年2月25日，星期天100用单纯形法计算得结果：每天生产A产品200kg,分别需要原料:D为100kg;P为50kg;H为50kg.总利润收入Z=500元/天.第100页,共129页，2024年2月25日，星期天101max=-15*x11+25*x12+15*x13-30*x21+10*x22+0*x23-40*x31+0*x32-10*x33;x11+x21+x31<=100;x12+x22+x32<=100;x13+x23+x33<=60;x11/(x11+x12+x13)>=0.50;x12/(x11+x12+x13)<=0.25;x21/(x21+x22+x23)>=0.25;x22/(x21+x22+x23)<=0.50;end第101页,共129页，2024年2月25日，星期天102例2华津机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分别为2500台，4500台，2000台，5000台柴油机。该厂正常生产每月可生产柴油机3000台，利用加班还可以生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低？假设第一月初和第四月末库存为0变量意义(生产成本/台、能力）xi第i月正常生产台数(5000、3000)yi第i月加班生产台数(6500、1500)zi第i月月初库存(200/月.台)需求2500、4500、2000、5000第102页,共129页，2024年2月25日，星期天103设xi为第i月正常生产的柴油机数，yi为第i月加班生产的柴油机数，zi为第i月月初柴油机的库存数。第103页,共129页，2024年2月25日，星期天104min=5000*(x1+x2+x3+x4)+6500*(y1+y2+y3+y4)+200*(z2+z3+z4);x1+y1-z2=2500;x2+y2+z2-z3=4500;x3+y3+z3-z4=2000;x4+y4+z4=5000;x1<=3000;x2<=3000;x3<=3000;x4<=3000;y1<=1500;y2<=1500;y3<=1500;y4<=1500;一月二月三月四月正常生产台数3000300030003000加班生产台数0100001000月初库存数量050001000第104页,共129页，2024年2月25日，星期天105例3

某部门在今后5年内连续给以下项目投资：

项目A，第一年至第四年每年年初投资，次年末回收本利115%；项目B，第三年初投资，第五年末回收本利125%，最大投资额不超过4万元；项目C，第二年初投资，第五年末回收本利140%，最大投资额不超过3万元；项目D，五年内每年初可购买公债，当年末归还，并加利息6%。该部门现有资金10万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D第105页,共129页，2024年2月25日，星期天106第一年第二年第三年第四年第五年第106页,共129页，2024年2月25日，星期天107max=1.15*x4A+1.4*x2C+1.25*x3B+1.06*x5D;x1A+x1D=100000;x2A+x2C+x2D=1.06*x1D;x3A+x3B+x3D=1.06*x2D+1.15*x1A;x4A+x4D=1.06*x3D+1.15*x2A;x5D=1.06*x4D+1.15*x3A;x3B<=40000;x2C<=30000;end第107页,共129页，2024年2月25日，星期天108例4：营养配餐问题序号食品热量蛋白质钙价格1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002

需求量300055800设xj为第j种食品每天购入量Minz=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800xj

0，j=1，…，4第108页,共129页，2024年2月25日，星期天109Min=14*x1+6*x2+3*x3+2*x4;1000*x1+800*x2+900*x3+200*x4>=3000;50*x1+60*x2+20*x3+10*x4>=55;400*x1+200*x2+300*x3+500*x4>=800;Globaloptimalsolutionfound.Objectivevalue:10.00000Totalsolveriterations:0VariableValueReducedCostX10.00000010.66667X20.0000003.333333X33.3333330.000000X40.0000001.333333用Lingo求解第109页,共129页，2024年2月25日，星期天110例5：产品配套问题某厂生产一种产品，由两个B1

零件和三个B2零件配置组装而成。该厂有A1、A2、A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全